深入学习Redis-底层数据结构详解

1. 动态字符串SDS

Redis中保存的key是字符串,value往往是字符串或者是字符串的集合,可见字符串是Redis中最常用的一种数据结构。Redis构建了一种新的字符串结构称为简单动态字符串(Simple Dynamic String)简称为SDS

它的本质是一个结构体

struct __attribute__()sdshdr8{
    uint8_t len;//buf已保存的字符串总数,不包含结束的标识
    uint8_t alloc;//buf申请的总的字节数,不包含结束标识
    unsigned char flags;//不同的SDS头类型,用来控制SDS的头大小
    char[] buf
}

SDS之所以叫做动态字符串,是因为它具有动态扩容的机制,它在扩容的时候遵循下面的机制:

• 如果新字符串的大小是小于1M的,那么新空间扩展后的字符串长度就是新字符串的长度*2+1,其中+1是包括结尾的\0
• 如果新字符串的大小是大于1M的,那么新空间扩展后的字符串长度就是len+1M+1

为什么需要内存预分配

这是内存的分配本质上是一个系统调用,会导致操作系统从用户态陷入内核态,其上下文的切换以及开销是非常严重的,因此为了尽可能地减少内存分配,所以的话尽量一次性分配尽可能多的内存空间,但是又不要浪费。

说说SDS的特点?以及为什么这样设计

首先要说明的问题是:为什么不使用c语言原生的字符串,而是使用自己设计的SDS?

第一个问题,C语言本身并没有字符串这个概念,在C++STL中才有完善的string可以被使用,在C语言中字符串实际上是一个char类型的数组,那么管理数组就有两个常见的问题

• 如何获取数组的长度?

在char[]中,并没有附加的属性,因此每一次获取c语言自带的char[]的话,都需要遍历,是O(n)的复杂度

• 如何数组如何定界?

在char[]中,规定了最后一位是\0,这个就是定界符,以这个\0标识结束,最终就可以定位到字符串的结束了

问题在于:①获取长度需要O(n)的复杂度,开销大,使用起来不方便②二进制不安全,假设在char[]存储了\0而后面有数据,那么在这样的情况下,就会导致字符串的读取提前结束,整个就完蛋了

还有一个问题就是在于c语言的字符串是不可变的,如果要做字符串的拼接等操作,就意味着需要申请新的空间,就涉及到了内存分配,如果频繁地进行内存分配,那么就会导致性能的严重下降

针对这三个问题,Redis开发了SDS

SDS从设计的头部解决了这些问题,在头部中存放了两个变量,他们分别是用来记录当前字符串长度的长度,实现了O(1)获取长度的目标

第二个变量是记录了当前字符串已经分配了多少内存是可用的,从而能够根据扩容的情况,选择是否进行系统调用,解决了频繁系统调用导致性能下降的问题

第三个问题就是二进制不安全的问题,所谓二进制不安全的问题就是说,当有一些例如视频,音乐,图片等信息以二进制的形式输入进来,经过编码和解码存到字符串的时候,会产生一些特殊字符,而如果特殊字符恰好是一些边界字符的时候,就会导致信息不安全,解析/编码的时候被破坏了,SDS解决这个问题的时候,将其相关的API的解析改造为基于二进制的形式进行操作的,从而保证了原本数据的安全

关于字符串的常见操作如下:

set myKey 123456#OK
get myKey #123456
# 判断某个key是否存在
EXISTS myKey# 1,当key存在的时候,返回1,否则返回一个nil
# 得到某个key所对应的value的长度
STRLEN myKey # 返回6,当key不存在的时候返回一个nil
# 删除key
DEL myKey # 返回1,代表删除成功,不存在的时候返回一个nil
# 批量设置
MSET key1 v1 key2 v2 key3 v3
# 批量获取
MGET key1 key2 key3 key4
1) "v1"
2) "v2"
3) "v3"
4) "null"

计数器的操作

set number 0
INCR number #自增1,当键不存在的时候会自动创建
INCRBY num 10 #INCRBY 自增10
DECR number #同理
(integer) 10
# 将key中存储的数字值键 10
DECRBY number 10
(integer) 0

过期时间的设置

# 设置这个key的过期时间是 60
SET key  value EX 60
SETEX key 60 value

2. 整数集合INTSET

INTSET是Redis中set集合的一种实现方式,它是基于整数数组实现的,长度可变,有序。

typedef struct intset {
    uint32_t encoding;//编码方式,支持存放16位,32位,64位的整数
    uint32_t length;// 元素的个数
    int8_t contents[];//整数数组,保存集合的数据
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))/*short*/
#define INTSET_ENC_INT32 (sizeof(int32_t))/*int*/
#define INTSET_ENC_INT64 (sizeof(int64_t))/*long*/

支持三种不同的编码,表示存储的整数大小不同

现在来总结一下INTSET整数集合这种数据结构的特点以及运行机制:

首先要明确的一点是,整数集合并不是数据结构意义上的set, 而是一个有序数组,它底层的数组元素大小是有序的,因此可以利用O(logn)的时间复杂度对数据进行查询,而其数据总数被限制在了512个以下,那么也就意味着,当查询一个元素的时候,最多只需要执行9次的指针运算就可以完成查找,其效率还是很快的

然后要讲述的是整数集合的定义数据结构,它和SDS一样,分为header和data的部分,其中header部分包含有encoding部分和length部分,encoding部分的作用是为了快速实现动态扩容,length是为了快速查询数组元素的个数

而其数据的存储方式,是8个字节为一个单位的数组,但是实际上,它在按下标取值的并不是按照下标直接去使用这个数组的,而是根据当前的encoding部分和下标值来确定的。

比如说,原本数组都是存储到的short类型的数据,于是每个元素都只占16个字节,然后寻址的话就是通过公式:数组起始地址+下标*encoding,最终再按照数值的类型将二进位取出来,就可以取到值了

然后这时候来了个50000,超过了short,那么这时候就触发了动态扩容机制,这个机制非常精髓:

第一步,将编码升级为32位的编码,判断要插入的数值是正数还是负数,如果是正数,那么他肯定就是最大的,如果是负数,那么它肯定就是最小的,于是判断出来一个插入的位置,是队头还是队尾,注意,这时候还没有插入

第二步,开始搬动元素,从原数组的元素倒序,从后往前一个个地搬动到目标位置上

为什么要从后往前?

因为从前往后的话,在扩容的时候如果复用数组的空间,那么就会导致下一个的数值被扩容后的字节数据给覆盖掉

第三步,根据之前计算出来的数组位置,插入到对应的位置上去,这个过程是O(1)的复杂度

最终修改encoding的值即可

总结:关于INTSET,其插入和删除的时间复杂度到达了O(n)的时间复杂度,查找的时间复杂度到达了O(logn),扩容过程的时间复杂度是O(n),空间复杂度是O(n+2) = O(n)不需要借助多余的元素,因此是比较节省空间的一种数据结构,在大数据量下不适合,因此在超过512之后改用了哈希表,做了一个权衡,可以节省空间

3. 字典DICT

DICT由三部分组成,分别是哈希表DictHashTable,哈希节点DictEntry,字典Dict

首先来看看字典DICT到底是什么,说白了它就是一个哈希表,那么它put()一个元素的流程和jdk中的hashMap是一致的,主要流程如下:

首先就是它拿到一个key值,然后执行哈希函数,然后计算出来一个h值,将该h值与哈希掩码进行and运算,最终就可以得到这个entry在数组对应的下标了,如果没有哈希冲突的话就可以直接存进去了,如果有哈希冲突,则会形成一条链表,这个新节点会插入到链表的头部

有一个问题,为什么是and运算?

这个的话首先要明白,取余运算在编译器允许的情况下,是可以转换为位运算的,但是有些是无法转换为位运算的,只能够通过除法的运算来得到%运算的值,但是除法的效率是非常慢的,因此在这样的情况下,能否有一种规则,使得取余运算始终以位运算的形式开展呢?

那么做法就是使得数组的长度始终为2^n-1,为什么这样设计?首先2^n肯定是n+1位为1,然后其他位都为0,如果减一,那么除了0~n位就都为1了,最终根据and运算的特性来看,与1进行运算,最终只会得到自己本身,也就等效于取余运算了。

这个entry在一般情况下都是存储一个指针,这个指针指向的是SDS的对象地址

4. 字典DICT是如何进行扩容的?

DICT中的HashTable就是数组结合单向链表的表现,当集合中元素过多的时候,肯定就会造成哈希冲突,而链表形式就会造成O(1)的复杂度退化为O(n)的复杂度。

渐进式rehash

DICT在每次新增键值对的时候都会检查负载因子(LoadFactor = userd/size),满足以下两种情况将会触发扩容:1. 哈希表的LoadFactory>=1,并且服务器没有执行BGSAVE或者BGWRITEAOF等后台程序

2. 哈希表的LoadFactory>5

当DICT在删除元素的时候,也会对当前的负载因子进行检查,如果负载因子<0.1的话,那么就会产生一次收缩,回收一部分被浪费的空间,但是收缩的大小不会小于4

在redis所设计的HashMap中,不管是扩容还是收缩,都必定会创建新的哈希表,导致哈希表的size和sizeMask产生变化,而key的查询是与sizemask有关的,因此必须对哈希表中的每一个key重新计算索引,插入新的哈希表,这个过程称为rehash

• 计算新hash表的realSize,值取决于当前要做的是扩容还是收缩
  • 如果是扩容,那么新size就是第一个大于等于dict.ht[0].userd+1的2^n
  • 如果是收缩,那么新size就是第一个大于等于dict.ht[0].userd的2^n
• 按照新的realSize申请内存空间,创建dictht,并且赋值给dict.ht[1]
• 设置dict.ht[0]中的每一个dictEntry都rehash到新的dict.ht[0]

这一步执行rehash,每次执行CRUD的时候,都会检查是否处于rehash的状态,如果是的话,那么就会将dict.ht[0].table[rehashId]的entry拷贝到dict.ht[1].table[rehashId++]中,直到所有entry都拷贝到另外一张表上,将标志位设置为-1

• 将dict.ht[1]赋值给dict.ht[0],然后给dict.ht[1]初始化为新的空表,然后释放掉原本dict.ht[0]的内存

当DICT中的数量太多的时候,rehash极有可能会导致主线程的阻塞,基于这个问题,提出一个折中的方案

也就是渐进式哈希,分多次执行,将大任务分成若干个时间片进行执行

有个问题,这个就相当于是两个副本的执行,那么如何来保证这两个副本的一致性呢?

分为两种情况,第一种情况是新增,如果新增的数据插入到旧表中,而旧表中的这一项的rehashId已经走过了,那么肯定就会造成主从副本的不一致,因此对从副本操作是没有意义的,要插入到新节点上去

第二种是删除和修改,删除和修改,都是基于目前已经有的数据来操作的,有两种情况

• 如果这个数据在两个表中都有,那么就同时修改两边的数据
• 如果这个数据仅在从表中有,那么就仅修改从表中的数据,等待拷贝即可

关于查询,查询的话是会在两个表中同时搜索,搜到有为止

5. 压缩列表ZipList

ZipList是一种特殊的双端链表,由一系列特殊编码的连续内存块组成,可以在任意一端进行压入/弹出的操作,并且该操作的时间复杂度为O(1)

其最终的特性是它的内存空间分配是连续的,不需要通过指针寻址,由它的结构来确定

首先先来通过其组成看它的特点

它的第一个4字节的字段是zlbytes,这个字段用来记录的是整个压缩列表所占用的内存字节数,包括了最后的那个用来标识结束的zlend的字段

然后是zltail,它是4个字节的,这个字段用来标记最后一个entry距离列表起始的偏移量

zllen,表示了压缩列表中的数量,2个字节存储,当超出了65535的时候,每一次对这个ZL的长度查询算法的复杂度就变成了O(n),这也就是为什么要避免big key

entry:列表节点,存储的主要负载,压缩列表包括的各个节点,节点的长度是由节点保存的内容来决定的

zlend:恒定为0xff,用来标记压缩列表的末端

然后来说一下每一个entry是如何组织的,按照我的理解,作者在设计ZL的时候,将内存的压缩使用到了极致,基本上就是能省的地方他全部都给省掉了

• previous_entry_length:这个代表的是上一个entry的长度,它的作用就是用来寻址的,如果我想要通过当前节点的指针地址指向,找到上一个元素的元素的话,那么我就可以用当前节点的指针-这个previous_entry_length,就可以找到上一个元素的位置了。以此,就实现了列表的基本功能

如果前一个节点的长度小于254个字节,那么prelen属性就需要使用1个字节的空间来保存这个长度值

如果前一个节点的长度是大于等于254个字节的,那么prelen属性就需要使用5个字节的空间来保存这个长度值。(思考:如果有字符串在中途被修改了,那么对于列表中后续的元素会发生什么?)

总结:prelen的长度要么是1字节,要么是5字节

那么,系统是怎么知道这个prelen到底是要占5个字节还是1个字节呢?

通过标志位,如果读取第一个字节是0xfe的话,那么就说明后面四个字节才是实际的长度

如果读取的第一个字节不是0xfe,那么就说明后面四个字节不是实际的长度,prelen就是第一个字节读出来的值

• encoding:这个属性的空间大小与实际的value到底是字符串还是整形有关系。

通过以上这两幅图,可以看出关于这个encoding的规定还是比较复杂的,但是可以主要概括为:

• 如果当前节点的数据是整数的话,那么encoding就会使用1个字节的空间进行编码,通过encoding进行编码的原则是:通过前两个bit来确定数据的类型,比如说以11开头的就是整形,然后后面的6位,就代表着具体是哪一种类型,比如说11 0000是int16等
• 如果当前节点的数据是字符串的话,那么encoding就会使用1/2/5字节的空间进行编码,encoding编码的前两个bit表示数据的类型,后续的其他bit标识字符串数据的实际长度。

总结一下:首先,ZIPList是基于链表方式寻址+数组方式存储的这样一种结合的方式设计出来的数据结构,它的设计思想是这样的:结合了数组是在内存空间连续存储的特性,放弃了链表方式需要使用固定8个字节指针寻址方式,利用数组通过字节寻址的方式,完成对内存空间的节省,使得原本固定的16字节的指针存储开销,变为了最大只需要10字节的控制字段开销,同时由于ZL在内存中是连续存放的,有利于提高CPUCache的命中率。

其设计的高明之处在于,可以通过控制字段的zllen来快速找到ZL的尾部,于是,在头尾进行插入,均是O(1)的时间复杂度,而通过prelen和encoding字段的解析,就可以知道下一个节点的地址或者上一个节点的地址到底偏移当前节点多远,从而可以通过指针的快速运算,得到临近节点的地址,以此实现了遍历。

然后是关于元素搜素的复杂度,元素搜索的时候,由于只能够一个个搜索,因此搜索的复杂度为O(n)

而对于数组的长度,由于数组的长度字段只留了2个byte,因此能够得到的最大长度就是65535,当超过了这个数值,就需要遍历了,因此在65535之前是O(1)的复杂度,在之后是O(n)的复杂度

再来说说新增和删除的时间复杂度,由于其本质上还是数组,因此其新增和删除的时间复杂度还是O(n)的

而且在这两个过程中,可能产生连锁更新的问题,后果是比较严重的。

6. ZipList的连锁更新问题

首先来概述一下什么叫连锁更新:压缩列表在新增或者修改某个元素的时候,如果空间不够,压缩列表占用的内存空间就需要重新分配了,而当插入的元素较大的时候,就可能会导致后续元素的prelen都发生变化,从而引起了连锁更新。下面来复现一下这个场景:

如图所示,这里面所有的entry的长度(包含了头部)在250个字节里面,因此prelen都是一个字节,但是首先头部插入了一个255个字节的节点,那么就导致e1的prelen就变成了5个字节,那么同理,后面所有的节点都变成了5个字节,最终导致每个节点都需要修改

然而,最麻烦的是节点向后搬的这个操作, 如果内存足够,那么只是在运算而已,如果内存不够,那么就会不断地触发内存回收与分配,就相当于在JVM中不断地触发FULLGC,不断在内核态和用户态之间切换,导致的性能下降是非常严重的。

从上面可以看出,ZipList虽然能够节省空间,但是在大数据量的情况下,它的表现是非常差的,这也就是为什么我们不提倡搞bigKey,作者也当然想到了这个问题,于是在后续引入了quickList和listpack

7. QuickList

虽然说ZipList会比较节省内存,但是这就类似于JVM中关于大对象的分配问题一样,如果在老年代中空间不够的话,那么就会触发FullGC,会产生大量的引用重定位,这是一种比较重量级的操作,因此它是一把双刃剑

如果想要存储大量数据,但是超过了ZipList的最佳上限,那么这时候该怎么办?

分片的思想:可以创建多个ZipList来分片存储数据,从而保证每一个ZipList都符合它的最佳上限

问题在于,这多个分片如何建立起联系?

建立一个维护和管理这些分片的链表,将这些分片记录起来

为了避免QuickList中的每个ZipList中的entry过多,Redis中提供了一个配置项list-max-ziplist-size来进行配置:

如果值为正,那么就代表ZipList的允许的entry个数的最大值

如果值为负,那么就代表着ZipList的最大内存大小。

config set list-max-ziplist-size xxx

什么是QuickList

总结:QuickList是为了解决ZipList难以连续分配巨大空间而设计出来的一种具有分片思想的双端链表,其底层是以链表的形式来存储每一个ZipList的起始地址,每当需要遍历节点的时候,就可以通过zl指针去获取到对应的起始地址从而完成遍历,同时,它还能够完成内部节点的进一步压缩,可以将中间节点的大小以某种压缩形式压缩下来,节省空间。总而言之,它在保持节省内存的前提下,解决了连续分配巨大内存的问题。

同时因为列表的元素被控制得相对较小,因此连锁更新的副作用被降低了,提供了更好的访问性能

8. SkipList(跳表)

什么是跳表?

首先Redis设计出来的几种列表型的数据结构,如ZipList和QuickList,它们在查询的时候,时间复杂度都是O(n)的,因此查询的速度较慢。

它首先是一条链表,但与传统链表相比有不同的地方:

链表在查询的时候,它的复杂度为O(n),这是因为它的指针的跨度是1,那么假设说我想要访问n个节点,那么就必须执行n次的指针运算,而跳表解决了这个问题,跳表建立了多层级结构,这个所谓的多层级结构就是说,一个节点建立了多个不同跨度的节点,比如说第0层指针可以跨越1个节点,第1层节点可以跨越2个节点….根据这种特性,就可以实现跳表对元素的快速定位,而且根据链表中的元素是有序的特点,可以实现一个类二分查找的算法,从而到达O(logn)的算法复杂度,优化O(n)的算法复杂度。

跳表的多层级结构是如何实现的?

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

这个问题需要从跳表中的元素节点开始说起,之前说到这个跳表中的元素它是有序的,那么它是如何实现有序的呢?

节点内部存的是一个sds类型的实际值,然后根据此实际值计算出来一个得分,这个得分就是节点在链表中存储位置的依据,也因此,链表中的元素才形成一个有序的序列。

然后节点内部还存储了一个后向指针,这个后向指针是单步指针,通过它可以访问到上一个节点。

最终的就是节点的level数组,这个level数组中记录了前向指针这个指针的跨度,这个指针的跨度是不确定的,在Redis中使用了一种算法来确定这个跨度到底要设计为多少。

这个level数组记录了每一个层级中的指针的指向情况,比如说level1的前向指针就是跨度为1的,通过它能够找到下一个节点,level2的前向指针就是跨度为2的,通过它能够找到下一个节点,通过数组元素的切换,最终就可以实现多层级了。

跳表节点是如何查询的?

查询一个跳表节点的过程中,它会先从跳表的多层级结构中,找到最高层的节点,逐一遍历每一层,在遍历每一层的跳表节点的时候,会使用跳表节点中的SDS类型的元素和元素的权重进行判断,一共有两个条件

• 如果当前节点的权重score小于要查找的权重的时候,跳表就会访问该层上的下一个节点

这个意思就是说,直接让当前的遍历指针指向forward

• 如果当前节点的权重socre等于要查找的权重的时候,注意,可以存在有多个score相同的对象,因此在score相同的时候,不能够直接断言找到了元素,而是要遍历这些元素,找到最合适的那个。

如果当前的SDS的类型数据要小于要查找的数据的时候,跳表就会访问该层上的下一个节点

如果当前的SDS的类型数据要大于要查找的数据的时候,指针就会使用目前遍历到的节点的level数组里的下一个指针,然后沿着下一层继续查找,这就相当于跳到了下一层去继续查找。

根据例子来具体理解一下这个过程:

假设我们要寻找元素[abcd,4]这个元素:

1. 先从最高层次的元素开始查找,此时找到的是[abc,3]然后开始比较,发现权重比要查找的要小,因此就要沿着当前层级向前继续查找
2. 然而发现下一步的指针为NULL,于是宣告这一层节点的查询结束了,使用下一层层级的指针,level--,发现下一步不为NULL,于是走到了[abcde,4]
3. 此时权重相等,而abcde > abcd,这说明当前要查找的元素,在当前锁定的区间里面,于是level--,进入到下一个层级,也就是level[0],然后检查下一个元素,是[abcd,4],查找结束

为什么要使用跳表而不使用平衡树?

我认为这与具体的上层的数据结构有关,比如说zset等需要经常做一个范围查询的时候,这时候跳表的操作要比平衡树要简单,在平衡树上,我们找到指定范围的小值之后,还需以中序遍历的顺序继续寻找其他不超过大值的节点,这就是说,当存在多个socre相同的时候,还要对这个范围进行遍历,在实现这个过程的时候,使用跳表要远比平衡树简单,比如说,当我们锁定了右边的区域,只需要在当前的层级上进行指针迭代即可,但是对于平衡树而言,它还要对平衡树进行改造。

从算法的实现复杂度来看,跳表的实现更加容易,平衡树所涉及到的旋转等操作,比较复杂。

9. RedisObject

Redis中任意的数据类型的键和值都会被封装为RedisObject,也被叫做Redis对象。

10. 新数据结构listpack

为什么需要有listpack

这是因为zipList中的entry的头部的字段prelen有可能会引起连锁更新问题,这是因为prelen是变长的,因此为了彻底解决这个问题,作者将ZipList中的entry进行了优化,设计了listpack

listpack和ZipList中的entry有什么区别?

先来讲讲结构有什么不同吧

ZipList中的entry的包含有三个字段,分别是prelen(用来记录上一个节点的字节数),第二个是encoding,第三个字段就是data,其中prelen是变长的,encoding在存储字符串的时候也是变长的

list中的entry的存储从左到右的字段分别是encoding、data、len,其中len是用来记录当前这个节点的长度的,这样做有什么好处?这样做的话就可以同时实现向前向后遍历

这个就好像Mysql中的那个行格式,从那个next指针向右读,读到的那个记录的起点,向左读就是变长列表的头部字段,向右读就是实际的数据

那么listpack如果要实现向前遍历,那么就可以向左读取字节,就可以读取到上一个entry的长度了,然后就能够到上一个节点去

encoding是变长的,彻底解决了问题了吗?

注意,元素搬动的问题依然存在,而且是数组这种结构的弊端,但是连锁更新是伴生物,是完全可以解决的,因此这个设计只是解决了连锁更新的问题。

​