Redis设计与实现-底层数据结构

发表于 | 分类于
本文简单介绍redis五种不同类型的对象，剖析底层数据结构，总结优点和缺点，帮助大家理解和记忆。本书主要为这本书的读书笔记，有问题的地方欢迎指正

正文

本文简单介绍五种不同类型的对象，剖析底层数据结构，总结优点和缺点，帮助大家理解和记忆

SDS简单动态字符串

定义如下：

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    
    //记录buf数组中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
}

C 语言使用长度未N+1的字符数组来表示长度为N的字符串，并且字符数组的最后一个元素总是’\0’。

这样的设计有几个坏处：

  1. 每次获取字符串长度的操作复杂度为O(n)，通过遍历字符数组获得。
  2. 对于一些二进制数据，包含一些特殊字符，乃至于’\0’字符，无法保存
  3. 缓冲区溢出。s1为”redis”, s2为”cluster”， 二者内存相连，一旦s1发生变更为更长的字符串如’redis_test’，则会影响s2的值
  4. 每次扩展和截断字符串，都需要进行耗时严重的内存重分配操作

SDS的结构则完美避开了这些风险：

  1. 通过len记录了字符串长度，每次获取长度操作为O(1)
  2. 由于不需要根据末尾的空字符判定字符串结束，所以支持复杂的二进制数据
  3. 杜绝缓冲区溢出，在修改字符串之前会首先根据len判断空间是否足够，不够的话，进行空间大小的修改
  4. 扩展字符串采用空间预分配策略，截断字符串采用惰性空间释放策略。

空间预分配

  1. 如果对SDS进行修改时，len的值小于1MB，那么预分配和len同样大小的未使用空间，即free == len

  2. 如果len的值大于1MB，那么程序会固定分配1MB的free

    ​

惰性空间释放

  1. 当需要进行截断操作时，程序并不立即使用内存重分配收回多余内存，而是使用free来记录多出来的字节，并等待将来的使用
  2. SDS存在api可以真正删除未使用的空间

链表

redis实现的c语言本身没有内置链表，因此redis自己实现了一套。

定义如下（注意，是双向链表）：

1
2
3
4
5
6
7
8
9
10
typedef struct listNode {
    //前置节点
    struct listNode *prev;
    
    //后置节点
    struct listNode *next;
    
    //节点的值
    void *value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct list {
    //表头节点
    listNode *head;
    
    //表尾节点
    listNode *tail;
    
    //链表节点数量
    unsigned long length;
    
    //表头值复制函数
    void *(*dup)(void *ptr);
    
    //表头值释放函数
    void *(*free)(void *ptr);
    
    //节点值对比函数
    void *(*match)(void *ptr, void *key);
    
}

redis链表的特点：

  1. 双向
  2. 无环
  3. 带表头指针和表尾指针，获取复杂度为O(1)
  4. 带链表长度计数器，获取复杂度为O(1)

字典

redis实现的c语言本身没有内置字典（键值对），因此redis自己实现了一套。

字典使用哈希表实现。

哈希表整体实现使用拉链法实现。

每个字典包含了一个长度为2的哈希表数组ht，这个数组一般只使用ht[0]的哈希表，ht[1]只会在对ht[0]rehash时使用。

如果两个键hash之后发生冲突，则在相同的索引下，构成一个链表，新节点位于头部（因为没有指向链表尾部的指针）。

当哈希表需要扩展和收缩时，策略是：

  1. 为ht[1]分配空间，如果是扩展操作，则大小为第一个大于等于ht[0]已经使用的节点数的2倍数的2的n 次幂（有点绕，比如已经使用了5，那么应该扩展为5 * 2 = 10 < 16 即16的空间）
  2. 如果是收缩操作，则大小为第一个大于等于ht[0]已经使用的节点数的2的n 次幂（比如已经使用了5，那么应该扩展为5 < 8 即8的空间）
  3. 将ht[0]上的键值对重新rehash计算索引，转移到ht[1]上
  4. 释放ht[0], 将ht[1]设置为hr[0]，并为ht[1]新创建一个空白哈希表，为下一次rehash做准备

正常情况下，扩容复杂因子为1，收缩复杂因子为5。（还有非正常情况）

在将ht[0]上的值rehash到ht[1]上时，采用渐进式rehash，策略是：

  1. 字典中维护rehashindx，默认－1
  2. 每次对字典的增删改查操作之后，都会执行一次rehash,把rehashindx对应索引的键值对，重新hash到ht[1]上，直到全部结束
  3. 好处是，避免了集中式的rehash而带来的巨大计算量，而是分多次，渐进式的完成操作。

需要注意的是，在此期间：

  1. 查找操作，会ht[0], ht[1]都查，优先查ht[0]，如果找不到，才会查ht[1]
  2. 添加操作，只会添加到ht[1]
  3. 删除和修改操作则是两个哈希表都会执行

这样做保证了ht[0]只会越来越少，直至变成空表。

跳跃表

跳跃表是一种有序数据结构，平均O(logN),最坏O(N)复杂度的节点查找。

跳跃表节点结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct zskiplistNode {
    //后退指针
    struct zskiplistNode *backward;
    
    //分值
    double *score;
    
    //成员对象
    robj *obj;
    
    //层
    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode; *forward
        
        //跨度
        unsigned int span;
    } level[];
    
} zskiplistNode
  1. 层。每次新创建一个新跳跃表节点的时候，会随机声称一个介于1到32之间的值作为level数组的大小
  2. 前进指针。用于从表头向表尾方向访问节点
  3. 跨度。用于记录两个跳跃表节点之前的跨度值（是否能一步到位）
  4. 后退指针。从表尾向表头方向访问
  5. 分值。跳跃表中所有节点都按照分值从小到大排序
  6. 成员对象。一个sds字符串对象

跳跃表结构如下：

1
2
3
4
5
6
7
8
9
10
11
typedef struct zskiplist {
    //表头节点和表尾节点
    structz skiplistNode *header, *tail;
    
    //表中节点的数量
    unsigned long length;
    
    //表中节点层数最大的节点的层数
    int level;
    
} zkiplist;

整数集合

如果当一个集合只包含整数值元素，并且整个集合数量不多时，redis会使用整数集合来作为集合键的底层实现

1
2
3
4
5
6
7
8
9
10
11
typedef struct intset {
    //编码方式
    uint32_t encoding;
    
    //集合包含的元素数量
    uint32_t length;
    
    //保存元素的数组，从小到大有序存储
    int8_t contents[];
    
} intset;

contents虽然声明了是int8_t,但实际真正的取值取决于encoding

当新增一个新元素时，如果该元素类型比整数集合现有所有元素类型都长，则需先进行升级操作，然后再添加

  1. 根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
  2. 将底层数组所有的元素转化成与新元素相同的类型，并将类型转化后的元素放置到正确的位上，而且再放置元素的过程中，需要继续维持底层数组的有序性质不变
  3. 将新元素添加到底层数组里

由于以上原因，向整数集合添加新元素的时间复杂度为O(N)

注意，一旦升级，编码就会一直保持升级后的状态，整数集合不支持降级。

压缩列表

压缩列表是列表键和哈希键的底层实现之一。

当一个列表键或者哈希键，值包含少量列表项，且要么为小整数，要么为长度较短的字符串，则redis会采用压缩列表作为其底层实现方式。

为什么压缩节点能够节省内存呢？