SDS

SDS又称Simple Dynamic String，是用于储存字符串的数据结构。

我们都知道，C里面有char[]字符数组这种基本数据类型，但是为什么Redis还需要用SDS去储存字符串呢？

C语言字符数组的缺点

1. 以'\0' 结尾，可能无法储存二进制数据。
2. 没有边界检查，容易造成缓冲区溢出。
3. 在获取字符串长度时需要遍历字符串，时间复杂度为O(n)。

解决方法

为了解决以上问题，Redis设计者便设计了SDS这种数据结构，SDS是一个结构体，参数如下：

1. len：字符串长度。
2. alloc：已分配的字符数组大小。
3. flags：sds类型，有sdshdr5（后序版本废除）/sdshdr8/sdshdr16/sdshdr32/sdshdr64。
4. char[]数组：用于保存字符串数据。

为了节省内存空间，结构体还指定了__attribute((packed))__，表示结构体中的元素内存对齐按一字节对齐。同时flags类型指定了结构体中length和alloc的类型（如sdshdr8表示length和alloc按八位大小储存），这样可以优化储存长度较小的字符串时带来的开销。

list

在Redis中，list是采用双向链表的形式储存的。

我们来看看链表中的节点：

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

• 既然是双向链表，那么一定有指向前驱节点后继节点的指针，指针指向的也是一个链表节点。
• 节点中还有储存value的指针，这个指针指向的是该节点的值。

我们来看看链表这个数据结构：

typedef struct list {
    //链表表头
    struct listNode *head;
    //链表表尾
    struct listNode *tail;
    //节点复制函数
    void (*dump)(void *ptr);
    //节点释放内存函数
    void (*free)(void *ptr);
    //节点值的比较函数
    int (*match)(void *ptr, void *key);
    //链表中的节点数量
    unsigned long len;
} list;

我们可以看到，list结构体储存了指向链表头和链表尾的指针，访问他们的时间复杂度是O(1)；与此同时，结构体提供了自定义的三个函数，为不同的数据提供相对应的函数实现，因此链表节点可以保存各种不同类型的值；同时，结构体中还储存了链表节点数量。

链表的优点：

1. 采用了双向链表设计，可以很方便的遍历前一个节点及后一个节点，范围查询方便，也方便插入和删除节点。
2. 节点中的值可以自定义，同时也提供了对应的free、dup、match函数指针实现对应功能。
3. 可以很方便的查找链表头节点、链表尾节点以及链表长度。

链表的缺点：

1. 内存不连续，无法充分利用CPU缓存。
2. 当链表较长的情况下，对链表查询效率可能会很慢。
3. 保存一个链表的值需要创建一个结点，内存开销大。

压缩列表

我们现在知道，链表使用的是不连续的储存空间，这样会影响CPU缓存，从而影响性能。为了解决这一问题，Redis早期使用了压缩列表ziplist，结构体如下：

1. zlbytes：储存整个压缩列表占用的字节数。
2. zltail：储存最后一个元素的偏移量。
3. zllen：压缩列表元素个数。
4. entry：压缩列表的每一个元素。
5. zlend：一个标记位，其值为255，标记压缩列表结束。

每一个entry的结构如下：

1. prevlen：保存上一个元素的长度。
2. encoding：当前元素的编码长度。
3. data：数据内容。

为了压缩内存占用空间，prevlen和encoding都采用了不定长的方式进行储存。

• prevlen：小于254字节时，使用8位（1字节）储存（2^8 = 256）；大于等于254字节时，采用40位（5字节储存）。

  • Q：为什么要小于254呢？1字节可以表示最大数据为255，那254和255干什么去了？
  • A：上面提到了255是ziplist的结束标记位，如果遇到该标记位就表示ziplist结束。另外，254也是一个标记位，他标记prevlen的数据长度是否由原来的1字节需要扩展成五字节（1字节标记位 + 4字节数据位）。

• encoding：当数据类型是整数时，encoding会以1字节长度进行编码；当数据类型是字符串时，会以1/2/5字节长度进行编码。

通过这种不定长的方式进行储存，一定程度上可以节省内存空间。

压缩列表的连锁更新问题

刚才聊到了，压缩列表中entry里的prevlen是不定长设计。

假如出现这样一种极端情况：每一个entry的prevlen的值都在250-253之间，当有新的数据（数据长度大于253）插入，或者把一个entry节点中的数据增加至超过253字节，就会导致后面的prevlen全部都要拓展至5字节，这种更新一个数据导致后面每一个数据都要进行更新的情况就叫连锁更新。如下图所示：

连锁更新会导致性能的损失，针对这一问题，Redis的设计者先后设计了quicklist和listpack。

quicklist

quicklist的设计思路是：将压缩列表ziplist拆分成每一小块，每一块ziplist采用链表的形式串联起来。

quicklist结构体和list类似，相比于list多了一些参数：

typedef struct quicklist {
    //链表表头
    struct quicklistNode *head;
    //链表表尾
    struct quicklistNode *tail;
    //所有ziplist中的元素总数量
    unsigned long count;
    //listnode的数量
    unsigned long len;
    ...
} quicklist;

quicklistNode结构体如下：

typedef struct quicklistNode {
    //前一个quicklistNode
    struct quicklistNode *prev;
    //后一个quicklistNode
    struct quicklistNode *next;
    //quicklistNode指向的压缩列表
    unsigned char *zl;
    //压缩列表的的字节大小
    unsigned int sz;
    //压缩列表ziplist中的元素个数
    unsigned int count : 16;
    ....
} quicklistNode;

优点与不足

1. 一定程度降低了连锁更新带来的性能影响，但没有完全解决。
2. 采用链表意味着数据不是连续存储的，无法充分利用CPU缓存。

listpack

上面说到，为了规避连锁更新带来的问题，quicklist采用了list+ziplist的方式，但仍然无法完全解决连锁更新问题。此外，因为引入了链表，会使得数据在内存储存不连续，从而导致CPU缓存问题。

listpack的设计则完美解决了这些问题。

1. 延续了ziplist的内存连续型设计。
2. entry中摒弃了prevlen，转而在entry尾部加入len记录entry长度。

如图所示：

entry-encoding：encoding也是可变长度设计，包含编码类型 + 数据长度。在获取encoding长度时，首先先读取编码类型，计算出数据长度储存的位数，然后再度数据长度。

entry-len：len也是可变长度设计，他是按字节储存数据，采用大端储存，每个字节的首位是标记位，用来记录是否可扩展，低七位保存数据。

标记位内容如下：

• 最高位为 1，表示 entry-len 还没有结束，当前字节的左边字节仍然表示 entry-len 的内容；
• 最高位为 0，表示当前字节已经是 entry-len 最后一个字节了。

如图所示，下面表示了entry-len为512时的编码方式：

正是因为listpack摒弃了prevlen，使得每一个entry节点都不会对上一个节点产生关联，这样就避免ziplist带来的连锁更新了。

参考资料

1. 极客时间 —— Redis源码剖析与实战
2. 小林Coding —— 图解Redis：数据结构 40 图（完整版）