redis主要的数据类型有:String,List,Hash,Set,SortedSet,也称为对象,而这些数据类型,底层是基于特定的数据结构来实现的。
我们之前也在IT宅(itzhai.com)以及Java架构杂谈中聊过了一些常见的数据结构:
而Redis中,基于存储效率和访问效率的考虑,使用到了一些其他的数据结构。我们首先来看看Redis中常见的这些数据结构,然后在看看这些数据类型是由什么数据结构组成的。
1、SDS
我们知道,String类内部定义了常量数组进行存储字符串,是不可以修改的,每次对字符串操作都会另外分配一个新的常量数组空间。
而Redis中的字符串是动态的。字符串是Redis中最为常见的存储类型,底层采用简单动态字符串实现(SDS[1], simple dynamic string),是可以修改的字符串,类似于Java中的ArrayList,采用预分配冗余空间的方式来减少内存的频繁分配。
Redis中的键值对中的键、值里面的字符串、缓冲区、AOF缓冲区、等都是用的SDS。
下面是SDS数据结构的一个图示:
亮点:
- 获取字符串长度时间复杂度为O(1),而C语言则需要遍历整个数组才能得到长度;
- 采用空间预分配避免反复对字节数组进程扩容,如上图的SDS,还有2个字节的空闲空间,如果只是追加一个字符,就不用扩容了。避免了类似C语言要手动重新分配内存的情况下,忘记了进行分配而导致的缓冲区溢出或者内存泄露问题;
- 惰性空间释放:当要缩短字符串长度的时候,程序不会立刻释放内存,而是通过free属性将这些需要释放的字节数量记录下来,等待将来重复使用;
- 二进制安全:所有的SDS API都会以处理二进制的方式来处理SDS的buf数组数据,这样就避免了C字符串读取到空字符就返回,导致读取不完整字符串的问题。二进制安全的SDS,是的Redis可以保存任意格式的二进制数据,而不仅仅是文本数据。
- 如果是C语言,字符串存入了一种使用空字符(\0,不是指空格)来分隔单词的特殊数据格式,存储如下内容:
- 使用C字符串函数读取到的结果会丢失空字符后面的内容,得到:itzhai,丢失了com。
- SDS使用len属性的值来判断字符串是否结束,而不是空字符。
- 兼容部分C字符串函数:为了兼容部分C字符串函数库,SDS字符串遵循C字符串以空字符结尾的惯例。
空间预分配规则
- 字符串大小小于1M的时候,每次扩容加倍;
- 超过1M,扩容只会多扩容1M的空间,上限是512M。
更多关于Redis字符串的命令:Redis - Strings[2]
2、链表 linkedlist
Redis中List[3]使用的是双向链表存储的。
如下图:
List特点:
- 双向链表;
- 无环;
- 带head和tail指针;
- 带链表长度;
- 多态,链表节点可存储不同类型的值;
List提供了以下常用操作参考:命令列表:redis.io/commands#list[3:1]
通过LPUSH,LPOP,RPUSH,RPOP操作,可以把List当成队列或者栈来使用:
3、Hash字典
Redis的字典使用哈希表作为底层实现。该数据结构有点复杂,我直接画一个完整的结构图,如下:
如上图,字典结构重点属性:
-
type和privdata主要是为创建多态字典而设置的;
-
ht[1]: 包含两个哈希表,正常情况下,只使用ht[0],当需要进行rehash的时候,会使用到ht[1];
-
rehashidx: 记录rehash目前的进度,如果没有在rehash,则值为-1;
而哈希表又有如下属性:
- 哈希表数组,里面的元素作为哈希表的哈希桶,该数组每个元素都会指向一个dictEntry结构指针,dictEntry结构保存具体的键值对;
- 数组大小,记录了哈希表数组的大小;
- 哈希掩码,主要用于计算哈希索引值,这个属性和哈希值决定一个键在哈希表数组中的位置;
- 已有节点个数,记录哈希表目前已有节点的数量。
dictEntry结构如图中代码所示:
- key保存键值对的键的指针;
- v保存着键值对的值,值可以是一个指针,或者是unit64_t整数,或者是int64_t整数。
3.1、hash和hash冲突
作为哈希表,最重要的就是哈希函数,计算新的数据应该存入哪个哈希桶中。
具有良好统一的哈希函数的时候,才能真正的实现花费恒定时间操作哈希表。由于哈希算法计算的数据是无限的,而计算结果是有限的,因此最终会出现哈希冲突。常用的两种解决哈希冲突的方式是链地址法和开放定址法。而Redis中使用的是链地址法。
3.2、字典是如何进行rehash的?
随着哈希冲突的不断加剧,hash查找的效率也就变慢了,为了避免这种情况的出现,我们要让哈希表的负载因子维持在一个合理地范围之内。
当哈希冲突增加的时候,就需要执行rehash操作了。
rehash操作,也就是指增加哈希表中的哈希桶数量,让超负载哈希桶中的entry元素重新分散到更多的桶里面,从而减少单个桶中的元素数量,减少哈希冲突,从而提高查找效率。
rehash的流程
Redis的rehash是一个渐进的rehash的过程。为什么要这样做呢?
如果需要rehash的字典非常大,有几百上千万个键值对,那么执行rehash就要很长的时间了,这个期间有客户端需要写入新的元素,就会被卡住了,因为Redis执行命令是单线程的,最终将导致Redis服务器在这段时间不能正常提供服务,后果还是比较严重的。
这种这种情况,我们可以采用分而治之的思想,把rehash的过程分小步一步一步来处理,每一步迁移少量键值对,并在对字典的操作流程中做一些兼容处理,确保rehash流程对客户端无感知,这就是我们所说的渐进式rehash。
大致流程如下:
这样,从第0个哈希桶开始,每次执行命令的时候,都rehash下一个哈希桶中的entry,并且新增的元素直接往ht[1]添加。于是ht[0]的元素逐渐减少,最终全部转移到了ht[1]中,实现了哈希表的平滑rehash,最小程度的降低对Redis服务的影响。
4、跳跃表 skiplist
Redis中的跳跃表是一种有序数据结构,通过在每个节点维持指向其他节点的指针,从而实现快速访问节点的目的。
Redis中的有序集合就是使用跳跃表来实现的。
为了简化跳跃表模型,我们先来看看,假设所有跳跃表节点的层级都是1的情况,如下图:
这个时候,跳跃表相当于一个双向链表,查找元素的复杂度为最差的O(N),即需要遍历所有的节点。
为了提高遍历效率,让跳跃表真正的跳起来,现在我们尝试在各个节点添加更多的Level,让程序可以沿着这些Level在各个节点之间来回跳跃,如下图,我们现在要查找score=9的节点,查找流程如下图红线所示:
这种查找类似于二分查找,首先从最高层L3进行查找,发现L3的下一个节点score=10,比目标节点大,于是下降到L2继续比较,发现L2的下一个节点为5,比目标节点小,于是继续找下一个节点,为10,比目标节点大,于是在score为5的节点中继续下降到L1,查找下一个节点,刚好为9,至此,我们就找到了目标节点,查找的时间复杂度为O(log N)。
如果每一层节点数是下面一层节点个数的一半,那就是最理想的类,跟二分查找一样。但是这样每次插入新元素,都会打乱上下两层链表节点个数2:1的比例关系,如果要维持这种关系,就必须对插入节点的后面所有节点进行重新调整。为了避免这种问题,跳跃表不做这个严格的上下级比例约束,而是每个节点随机出一个Level层数。
跳跃表节点如何生成level数组?
每次创建新的跳跃表节点的时候,都会根据幂次定律,随机生成一个介于1~32之间的数组大小,这个大小就是level数组元素个数。
插入节点操作只需要修改插入节点前后的指针就可以了,降低了插入的复杂度。
5、整数集合 intset
在Redis中,当一个集合只包含整数值,并且集合元素不多的时候,会使用整数集合保存整数集,集合中的数据不会出现重复,集合元素从小到大有序排列,可以保存int16_t,int32_t,int64_t的整数值。
下面是整数集合的数据结构:
在内存中,整数集合是在一块连续的内存空间中的,如下图所示:
- contents数组按从小到大的顺序保存集合的元素;
- encoding编码,可选编码:
- INTSET_ENC_INT16(From −32,768 to 32,767)
- INTSET_ENC_INT32(From −2,147,483,648 to 2,147,483,647)
- INTSET_ENC_INT64(From −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807)
整数集合是如何升级的?
当往整数集合添加的元素比当前所有元素类型都要长的时候,需要先对集合进行升级,确保集合可以容纳这个新的元素。
升级方向:INTSET_ENC_INT16 --> INTSET_ENC_INT32 --> INTSET_ENC_INT64
注意,一旦升级之后,就不可以降回去了。
下面是一个升级的过程说明:
原本整数数组存的都是INTSET_ENC_INT16编码的元素,接下来往里面插入一个元素 32768,刚好超出了原来编码的范围,于是需要对整数集合进行升级。于是对intset进行内存扩容,扩容后也是通过一块连续空间存储的,这有可能带来一次数据拷贝。
如果要插入的元素在中间,说明不用进行升级,这个时候会使用二分查找算法找到插入的位置,然后扩容插入元素,重新调整元素位置。
intset特点
- 由于intset是从小到到排列的,所以可以进行二分查找,查找性能比ziplist的遍历查找性能高;
- intset只能存储整数,并且由于是内存紧凑的存储模式,没有携带len信息,所以每个元素必须统一编码;
- intset存储可能变成字典存储,条件:
- 添加了一个超过64bit的有符号数字之后;
- 添加的集合元素个数超过了
set-max-intset-entries
配置的值;
6、压缩列表 ziplist
压缩列表是为了节省Redis内存,提高存储效率而开发的数据结构,是列表键和哈希键的底层实现之一,当hash中的数据项不多,并且hash中的value长度不大的时候,就会采用压缩列表存储hash。
为什么要这样设计呢?是因为ziplist不擅长存储大量数据:
- 数据量大了,每次插入或者修改引发的realloc操作可能会造成内存拷贝,加大系统开销;
- ziplist数据量大了,由于是遍历查找,查找性能会变得很低。
以下是压缩列表的数据结构:
尾节点地址 = 压缩列表起始指针地址 + zltail(偏移量)
我们再来看看压缩列表节点的结构:
xxxx部分表示存储的长度内容,或者是0~12整数。
压缩列表的content可以保存一个字节数组或者一个整数值。
如上图,ziplist通过特殊的编码约定,通过使用尽可能少的空间,很巧妙的存储了编码和长度信息,并且通过entry中的属性,可以在ziplist中进行双向遍历,效果相当于双向链表,但是占用更少的内存。
整数编码 1111xxxx为什么能存储2^4-1个整数?
由于11110000,11111110分别跟24位有符号整数和8位有符号整数冲突了,所以只能存储 00011101范围,代表113数值,但是数值应该从0开始计数,所以分别代表 0~12。
什么是ziplist连锁更新问题?
假设我们有一个ziplist,所有节点都刚好是253字节大小,突然往中间插入了一个254字节以上大小的节点,会发生什么事情呢?
如下图,由于新的节点插入之后,新节点的下一个节点的previous_entry_length为了记录新节点的大小,就必须扩大4个字节了。然后又会触发后续节点的previous_entry_length扩大4个字节,一直这样传递下去。所以这个过程也成为连锁更新。
最坏情况进行N次空间重新分配,每次重新分配最坏复杂度O(N)。触发连锁更新的最坏复杂度为O(N^2)。
但是实际情况,出现连续多个节点长度结语250~253之间的情况还是比较少的,所以实际被连续更新的节点数量不会很多,平均时间复杂度为O(N)。
由于ziplist的数据是存储在一块连续的空间中,并不擅长做修改操作,数据发生改动则会触发realloc并且触发连锁更新,可能导致内存拷贝,从而降低操作性能。
7、quicklist
linkedlist由于需要存储prev和next指针,消耗内存空间比较多,另外每个节点的内存是单独分配的,会加剧内存的碎片化,影响内存管理的效率。
于是,在Redis 3.2之后的版本,重新引入了一个新的数据结构:quicklist,用来代替ziplist和linkedlist。
为何需要quicklist?
我们得先来说说ziplist和linkedlist的优缺点:
- linkedlist优点:插入复杂度很低;
- linkedlist缺点:有prev和next指针,内存开销比较大;
- ziplist优点:数据存储在一段连续的内存空间中,存储效率高;
- ziplist缺点:修改复杂度高,可能会触发连锁更新。
为了整合linkedlist和ziplist的优点,于是引入了quicklist。quicklist底层是基于ziplist和linkedlist来实现的。为了进一步节省空间,Redis还会对quicklist中的ziplist使用LZF算法进行压缩
quicklist结构
如上图所示,quicklist结构重点属性:
- head:指向链表表头;
- tail:指向链表表尾;
- count:所有quicklistNode中的ziplist的所有entry节点数;
- len:链表的长度,即quicklistNode的个数。
quicklistNode重点属性:
- *prev:指向链表前一个节点的指针;
- *next:指向链表后一个节点的指针;
- *zl:数据指针,如果当前节点数据没有被压缩,那么指向一个ziplist结构;否则,指向一个quicklistLZF结构;
- sz:不管有没有被压缩,sz都表示zl指向的ziplist占用的空间大小;
- count:ziplist里面包含的entry个数;
- encoding:ziplist是否被压缩,1没有被压缩,2被压缩了;
- container:预留字段,固定为2,表示使用ziplist作为数据容器;
- recompress:之前是否已经压缩过此节点?当我们使用类似index这样的命令查看已经压缩的节点数据的时候,需要暂时解压数据,通过这个属性标记后边需要把数据重新压缩。
quicklist配置项
list-max-ziplist-size:指定quicklist中每个ziplist最大的entry元素个数,负数表示:
- -5:指定快速列表的每个ziplist不能超过64 KB;
- -4:指定快速列表的每个ziplist不能超过32 KB;
- -3:指定快速列表的每个ziplist不能超过16 KB;
- -2:指定快速列表的每个ziplist不能超过8 KB。这是默认值;
- -1:指定快速列表的每个ziplist不能超过4 KB。
list-compress-depth:指定列表中两端未压缩的条目数。有效值:0到65535。
- 0:不压缩列表中的节点。这是默认值;
- 1到65535:不压缩列表两端的指定节点数,但是压缩所有中间节点。
可以看出,表头和表尾总是不会被压缩,以便在两端进行快速存取。
而实际上,Redis顶层是以对象(数据类型)的形式提供数据的操作API的,而对象的底层实现,则是用到了以上的数据结构。
接下来我们继续看看Redis中的对象。