关于Redis

redis是一个开源的使用C语言编写的一个kv存储系统,是一个速度非常快的非关系远程内存数据库。它支持包括String、List、Set、Zset、hash五种数据结构。除此之外,通过复制、持久化和客户端分片等特性,用户可以很方便地将redis扩展成一个能够包含数百GB数据和每秒处理上百万次的请求的系统。目前支持多种语言的api,方便用户使用。

redis同时也内置了事务、LUA脚本、复制等功能,提供两种持久化选项,一种是每隔一段时间将数据导入到磁盘(快照模式),另一种是追加命令到日志中(AOF模式)。如果只是作为高效的内存数据库使用也可以关闭持久化功能。通过哨兵(sentinel)和自动分区(Cuuster)的方式可以提高redis服务器的高可用性。

与关系型数据库相比,redis的命令请求不需要经过查询分析器或查询优化器进行处理,也避免了更新数据时引起的随机读\写,这些慢操作。它直接读写内存中的数据,并且数据是按照一定的数据结构存储的。所以它的速度非常快。

五种数据结构

字符串(String)

与其它编程语言或其它键值存储提供的字符串非常相似,键(key)———值(value) (字符串格式),字符串拥有一些操作命令,如:get set del 还有一些比如自增或自减操作等等。redis是使用C语言开发,但C中并没有字符串类型,只能使用指针或符数组的形式表示一个字符串,所以redis设计了一种简单动态字符串(SDS[Simple Dynamic String])作为底实现:

定义SDS对象,此对象中包含三个属性:

  • len buf中已经占有的长度(表示此字符串的实际长度)
  • free buf中未使用的缓冲区长度
  • buf[] 实际保存字符串数据的地方

所以取字符串的长度的时间复杂度为O(1),另,buf[]中依然采用了C语言的以\0结尾可以直接使用C语言的部分标准C字符串库函数。

空间分配原则:当len小于IMB(1024*1024)时增加字符串分配空间大小为原来的2倍,当len大于等于1M时每次分配 额外多分配1M的空间。

由此可以得出以下特性:

  • redis为字符分配空间的次数是小于等于字符串的长度N,而原C语言中的分配原则必为N。降低了分配次数提高了追加速度,代价就是多占用一些内存空间,且这些空间不会自动释放。
  • 二进制安全的
  • 高效的计算字符串长度(时间复杂度为O(1))
  • 高效的追加字符串操作。

列表(List)

redis对键表的结构支持使得它在键值存储的世界中独树一帜,一个列表结构可以有序地存储多个字符串,拥有例如:lpush lpop rpush rpop等等操作命令。在3.2版本之前,列表是使用ziplist和linkedlist实现的,在这些老版本中,当列表对象同时满足以下两个条件时,列表对象使用ziplist编码:

  • 列表对象保存的所有字符串元素的长度都小于64字节
  • 列表对象保存的元素数量小于512个

当有任一条件 不满足时将会进行一次转码,使用linkedlist。

而在3.2版本之后,重新引入了一个quicklist的数据结构,列表的底层都是由quicklist实现的,它结合了ziplist和linkedlist的优点。按照原文的解释这种数据结构是【A doubly linked list of ziplists】意思就是一个由ziplist组成的双向链表。那么这两种数据结构怎么样结合的呢?

ziplist的结构

由表头和N个entry节点和压缩列表尾部标识符zlend组成的一个连续的内存块。然后通过一系列的编码规则,提高内存的利用率,主要用于存储整数和比较短的字符串。可以看出在插入和删除元素的时候,都需要对内存进行一次扩展或缩减,还要进行部分数据的移动操作,这样会造成更新效率低下的情况。

这篇文章对ziplist的结构讲的还是比较详细的:

https://blog.csdn.net/yellowriver007/article/details/79021049

linkedlist的结构

意思为一个双向链表,和普通的链表定义相同,每个entry包含向前向后的指针,当插入或删除元素的时候,只需要对此元素前后指针操作即可。所以插入和删除效率很高。但查询的效率却是O(n)[n为元素的个数]。

了解了上面的这两种数据结构,我们再来看看上面说的“ziplist组成的双向链表”是什么意思?实际上,它整体宏观上就是一个链表结构,只不过每个节点都是以压缩列表ziplist的结构保存着数据,而每个ziplist又可以包含多个entry。也可以说一个quicklist节点保存的是一片数据,而不是一个数据。总结:

  • 整体上quicklist就是一个双向链表结构,和普通的链表操作一样,插入删除效率很高,但查询的效率却是O(n)。不过,这样的链表访问两端的元素的时间复杂度却是O(1)。所以,对list的操作多数都是poll和push。
  • 每个quicklist节点就是一个ziplist,具备压缩列表的特性。

在redis.conf配置文件中,有两个参数可以优化列表:

  1. list-max-ziplist-size 表示每个quicklistNode的字节大小。默认为-2 表示8KB
  2. list-compress-depth 表示quicklistNode节点是否要压缩。默认是0 表示不压缩

Redis的数据结构 - 图1

哈希(hash)

redis的散列可以存储多个键 值 对之间的映射,散列存储的值既可以是字符串又可以是数字值,并且用户同样可以对散列存储的数字值执行自增操作或者自减操作。散列可以看作是一个文档或关系数据库里的一行。hash底层的数据结构实现有两种:

  • 一种是ziplist,上面已经提到过。当存储的数据超过配置的阀值时就是转用hashtable的结构。这种转换比较消耗性能,所以应该尽量避免这种转换操作。同时满足以下两个条件时才会使用这种结构:
    • 当键的个数小于hash-max-ziplist-entries(默认512)
    • 当所有值都小于hash-max-ziplist-value(默认64)
  • 另一种就是hashtable。这种结构的时间复杂度为O(1),但是会消耗比较多的内存空间。

集合(Set)

redis的集合和列表都可以存储多个字符串,它们之间的不同在于,列表可以存储多个相同的字符串,而集合则通过使用散列表(hashtable)来保证自已存储的每个字符串都是各不相同的(这些散列表只有键,但没有与键相关联的值),redis中的集合是无序的。还可能存在另一种集合,那就是intset,它是用于存储整数的有序集合,里面存放同一类型的整数。共有三种整数:int16_t、int32_t、int64_t。查找的时间复杂度为O(logN),但是插入的时候,有可能会涉及到升级(比如:原来是int16_t的集合,当插入int32_t的整数的时候就会为每个元素升级为int32_t)这时候会对内存重新分配,所以此时的时间复杂度就是O(N)级别的了。注意:intset只支持升级不支持降级操作。

intset在redis.conf中也有一个配置参数set-max-intset-entries默认值为512。表示如果entry的个数小于此值,则可以编码成REDIS_ENCODING_INTSET类型存储,节约内存。否则采用dict的形式存储。

有序集合(zset)

有序集合和散列一样,都用于存储键值对:有序集合的键被称为成员(member),每个成员都是各不相同的。有序集合的值则被称为分值(score),分值必须为浮点数。有序集合是redis里面唯一一个既可以根据成员访问元素(这一点和散列一样),又可以根据分值以及分值的排列顺序访问元素的结构。它的存储方式也有两种:

  • 是ziplist结构。

与上面的hash中的ziplist类似,member和score顺序存放并按score的顺序排列

  • 另一种是skiplist与dict的结合。

skiplist是一种跳跃表结构,用于有序集合中快速查找,大多数情况下它的效率与平衡树差不多,但比平衡树实现简单。redis的作者对普通的跳跃表进行了修改,包括添加span\tail\backward指针、score的值可重复这些设计,从而实现排序功能和反向遍历的功能。

一般跳跃表的实现,主要包含以下几个部分:

  • 表头(head):指向头节点
  • 表尾(tail):指向尾节点
  • 节点(node):实际保存的元素节点,每个节点可以有多层,层数是在创建此节点的时候随机生成的一个数值,而且每一层都是一个指向后面某个节点的指针。
  • 层(level):目前表内节点的最大层数
  • 长度(length):节点的数量。

跳跃表的遍历总是从高层开始,然后随着元素值范围的缩小,慢慢降低到低层。

Redis的数据结构 - 图2

跳跃表的实现原理可以参考:https://blog.csdn.net/Acceptedxukai/article/details/17333673

前面也说了,有序列表是使用skiplist和dict结合实现的,skiplist用来保障有序性和访问查找性能,dict就用来存储元素信息,并且dict的访问时间复杂度为O(1)。

应用场景

redis一般应用场景

  1. 缓存会话(单点登录)
  2. 分布式锁,比如:使用setnx
  3. 各种排行榜或计数器
  4. 商品列表或用户基础数据列表等
  5. 使用list作为消息对列
  6. 秒杀,库存扣减等

五种类型的应用场景

  1. String,redis对于KV的操作效率很高,可以直接用作计数器。例如,统计在线人数等等,另外string类型是二进制存储安全的,所以也可以使用它来存储图片,甚至是视频等。
  2. hash,存放键值对,一般可以用来存某个对象的基本属性信息,例如,用户信息,商品信息等,另外,由于hash的大小在小于配置的大小的时候使用的是ziplist结构,比较节约内存,所以针对大量的数据存储可以考虑使用hash来分段存储来达到压缩数据量,节约内存的目的,例如,对于大批量的商品对应的图片地址名称。比如:商品编码固定是10位,可以选取前7位做为hash的key,后三位作为field,图片地址作为value。这样每个hash表都不超过999个,只要把redis.conf中的hash-max-ziplist-entries改为1024,即可。
  3. list,列表类型,可以用于实现消息队列,也可以使用它提供的range命令,做分页查询功能。
  4. set,集合,整数的有序列表可以直接使用set。可以用作某些去重功能,例如用户名不能重复等,另外,还可以对集合进行交集,并集操作,来查找某些元素的共同点
  5. zset,有序集合,可以使用范围查找,排行榜功能或者topN功能。