Redis数据结构——快速列表(quicklist)

一、前言

在Redis的早期版本中，存储list列表结构时，如果元素少则使用压缩列表ziplist，否则使用双向链表linkedlist。

但是考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。因此Redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

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


// 链表
typedef struct list{
    //表头节点
    listNode *head;
    
    //表尾节点
    listNode *tail;
    
    //链表所包含的节点数量
    unsigned long len;
    
    //节点值复制函数
    void *(*dup)(void *ptr);
    
    //节点值释放函数
    void *(*free)(void *ptr);
    
    //节点值对比函数
    int (*match)(void *ptr,void *key);
}list;

对于链表，有以下特性：

• 双端：节点带有prev和next指针以获取前置、后置节点

• 无环：表头的prev和表尾的tail指向NULL

• 带表头表尾指针：获取表头表尾节点复杂度为O(1)

• 带链表长度计数器：获取节点数复杂度为O(1)

• 多态：使用void*来保存节点值，可保存不同类型值

二、快速列表

但是考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。因此Redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

quicklist 实际上是 zipList 和 linkedList 的混合体，它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。

三、quicklist的结构实现

quicklist有关的数据结构定义在quicklist.h中。

3.1 quicklist表头结构

typedef struct quicklist {
    //指向头部(最左边)quicklist节点的指针
    quicklistNode *head;

    //指向尾部(最右边)quicklist节点的指针
    quicklistNode *tail;

    //ziplist中的entry节点计数器
    unsigned long count;        /* total count of all entries in all ziplists */

    //quicklist的quicklistNode节点计数器
    unsigned int len;           /* number of quicklistNodes */

    //保存ziplist的大小，配置文件设定，占16bits
    int fill : 16;              /* fill factor for individual nodes */

    //保存压缩程度值，配置文件设定，占16bits，0表示不压缩
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

• head：指向头节点（左侧第一个节点）的指针。
• tail：指向尾节点（右侧第一个节点）的指针。
• count：所有ziplist数据项的个数总和。
• len：quicklist节点的个数。
• fill：16bit，ziplist大小设置，存放list-max-ziplist-size参数的值。
• compress：16bit，节点压缩深度设置，存放list-compress-depth参数的值。

3.2 quicklist节点结构

typedef struct quicklistNode {
    struct quicklistNode *prev;     //前驱节点指针
    struct quicklistNode *next;     //后继节点指针

    //不设置压缩数据参数recompress时指向一个ziplist结构
    //设置压缩数据参数recompress指向quicklistLZF结构
    unsigned char *zl;

    //压缩列表ziplist的总长度
    unsigned int sz;                  /* ziplist size in bytes */

    //ziplist中包的节点数，占16 bits长度
    unsigned int count : 16;          /* count of items in ziplist */

    //表示是否采用了LZF压缩算法压缩quicklist节点，1表示压缩过，2表示没压缩，占2 bits长度
    unsigned int encoding : 2;        /* RAW==1 or LZF==2 */

    //表示一个quicklistNode节点是否采用ziplist结构保存数据，2表示压缩了，1表示没压缩，默认是2，占2bits长度
    unsigned int container : 2;       /* NONE==1 or ZIPLIST==2 */

    //标记quicklist节点的ziplist之前是否被解压缩过，占1bit长度
    //如果recompress为1，则等待被再次压缩
    unsigned int recompress : 1; /* was this node previous compressed? */

    //测试时使用
    unsigned int attempted_compress : 1; /* node can't compress; too small */

    //额外扩展位，占10bits长度
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

• prev：指向链表前一个节点的指针。

• next：指向链表后一个节点的指针。

• zl：数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。

• sz：表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。

• count：表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。

• encoding：表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。

• container：是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。

• recompress：当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。

• attempted_compress：这个值只对Redis的自动化测试程序有用。我们不用管它。

• extra：其它扩展字段。目前Redis的实现里也没用上。

3.3 压缩过的ziplist结构——quicklistLZF

当指定使用lzf压缩算法压缩ziplist的entry节点时，quicklistNode结构的zl成员指向quicklistLZF结构

typedef struct quicklistLZF {
    //表示被LZF算法压缩后的ziplist的大小
    unsigned int sz; /* LZF size in bytes*/

    //保存压缩后的ziplist的数组，柔性数组
    char compressed[];
} quicklistLZF;

quicklistLZF结构表示一个被压缩过的ziplist。其中：

• sz：表示压缩后的ziplist大小。
• compressed：是个柔性数组（flexible array member），存放压缩后的ziplist字节数组。

3.4 管理ziplist信息的结构quicklistEntry

和压缩列表一样，entry结构在储存时是一连串的内存块，需要将其每个entry节点的信息读取到管理该信息的结构体中，以便操作。在quicklist中定义了自己的结构。

//管理quicklist中quicklistNode节点中ziplist信息的结构

typedef struct quicklistEntry {
    const quicklist *quicklist;   //指向所属的quicklist的指针
    quicklistNode *node;          //指向所属的quicklistNode节点的指针
    unsigned char *zi;            //指向当前ziplist结构的指针
    unsigned char *value;         //指向当前ziplist结构的字符串vlaue成员
    long long longval;            //指向当前ziplist结构的整数value成员
    unsigned int sz;              //保存当前ziplist结构的字节数大小
    int offset;                   //保存相对ziplist的偏移量
} quicklistEntry;

quicklistEntry 占 48 个字节，前 5 个字段都是 8 个字节，后面两个字段各 4 个字节。

• quicklist：指向当前的快速列表
• node：指向当前的 quicklistNode 节点
• zi：指向元素所在的 ziplist
• value：指向该节点的字符串成员
• longval：为该节点的整型值 【因为节点既可存字符串又可存整型，所以就分别用 value 和 longval】
• sz：表示当前 ziplist 结构的大小【占多少字节】
• offset：表示相对 ziplist 的偏移量

quicklist 整个内存布局大致如下：

3.5 迭代器结构实现

在redis的quicklist结构中，实现了自己的迭代器，用于遍历节点。

//quicklist的迭代器结构
typedef struct quicklistIter {
    const quicklist *quicklist;   //指向所属的quicklist的指针
    quicklistNode *current;       //指向当前迭代的quicklist节点的指针
    unsigned char *zi;            //指向当前quicklist节点中迭代的ziplist
    long offset;                  //当前ziplist结构中的偏移量      /* offset in current ziplist */
    int direction;                //迭代方向
} quicklistIter;

3.6 优劣

为什么要定义一个 quicklist, 列表结构还不够多吗？??

纯粹的使用 Linkedlist, 也就是普通链表来存储数据有两个弊端：

每个节点都有自己的前后指针，指针所占用的内存有点多，太浪费了。
每个节点单独的进行内存分配，当节点过多，造成的内存碎片太多了。影响内存管理的效率。
因此，定义了 quicklist, 将 linkedlist 和 ziplist 结合起来，形成一个，将多个 ziplist 通过前后指针互相连接起来的结构，可以在一定程度上缓解上面说到的两个问题。

为了进一步节约内存，Reids 还可以对 ziplist 进行压缩存储，应用 LZF 算法压缩。

3.7 ziplist 切割大小

既然 quicklist 本质上是将 ziplist 连接起来，那么每个 ziplist 存放多少的元素，就成为了一个问题。

太小的话起不到应有的作用，极致小的话（为 1 个元素）, 快速列表就退化成了普通的链表。

太大的话性能太差，极致大的话（整个快速列表只用一个 ziplist), 快速列表就退化成了 ziplist.

quickli 内部默认定义的单个 ziplist 的大小为 8k 字节. 超过这个大小，就会重新分配一个 ziplist 了。这个长度可以由参数list-max-ziplist-size来控制。

3.8 压缩深度

前面提到了，quicklist 可以对 ziplist 来进行压缩，而且可以指定压缩深度。（由list-compress-depth参数决定）.

默认的压缩深度为 0, 也就是所有的节点都不压缩。

为了支持快速的 push/pop 操作，quicklist 两端的第一个 ziplist 不进行压缩，这时压缩深度为 1.

如果压缩深度为 2, 则是两端各自两个 ziplist 不压缩。

因为如果将一个 ziplist 压缩，那么要从它里面读取值，必然要先解压，会造成性能变差，因此可以将两端即将被操作的节点不压缩，其他的选择压缩。

四、常用操作

4.1 插入

quicklist可以选择在头部或者尾部进行插入(quicklistPushHead和quicklistPushTail)，而不管是在头部还是尾部插入数据，都包含两种情况：

• 1、如果头节点（或尾节点）上ziplist大小没有超过限制（即_quicklistNodeAllowInsert返回1），那么新数据被直接插入到ziplist中（调用ziplistPush）。

• 2、如果头节点（或尾节点）上ziplist太大了，那么新创建一个quicklistNode节点（对应地也会新创建一个ziplist），然后把这个新创建的节点插入到quicklist双向链表中。

也可以从任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作，要比在头部和尾部的进行插入要复杂一些：

• 当插入位置所在的ziplist大小没有超过限制时，直接插入到ziplist中就好了；

• 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小没有超过限制，那么就转而插入到相邻的那个quicklist链表节点的ziplist中；

• 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小也超过限制，这时需要新创建一个quicklist链表节点插入。

• 对于插入位置所在的ziplist大小超过了限制的其它情况（主要对应于在ziplist中间插入数据的情况），则需要把当前ziplist分裂为两个节点，然后再其中一个节点上插入数据。

4.2 查找

list的查找操作主要是对index的我们的quicklist的节点是由一个一个的ziplist构成的每个ziplist都有大小。所以我们就只需要先根据我们每个node的个数，从而找到对应的ziplist，调用ziplist的index就能成功找到。

4.3 删除

区间元素删除的函数是 quicklistDelRange

quicklist 在区间删除时，会先找到 start 所在的 quicklistNode，计算删除的元素是否小于要删除的 count，如果不满足删除的个数，则会移动至下一个 quicklistNode 继续删除，依次循环直到删除完成为止。

quicklistDelRange 函数的返回值为 int 类型，当返回 1 时表示成功的删除了指定区间的元素，返回 0 时表示没有删除任何元素。

4.4 其他

除了上面介绍的基本操作之外还有一些其它操作：

• quicklistCreate：创建 quicklist
• quicklistInsertAfter：在某个元素的后面添加数据
• quicklistInsertBefore：在某个元素的前面添加数据
• quicklistReplaceAtIndex：替换某个元素
• quicklistDelEntry：删除单个元素
• quicklistDelRange：删除区间元素
• quicklistPushHead：头部插入元素
• quicklistPushTail：尾部插入元素

总结

从代码和结构可以看出，quicklist实际上是ziplist和linkedlist的混合体，它将linkedlist按段进行切分，每一段使用ziplist进行紧凑存储，多个ziplist之间使用双向指针进行串接。

quicklist内部默认单个ziplist长度为8k字节，超出这个字节数就会新起一个ziplist进行存储。

在quicklist内部，为进一步节约空间，还会使用LZF算法对ziplist进行压缩存储。

默认情况下，quicklist压缩深度为0即不压缩，实际压缩深度由配置中的list-compress-depth决定。

为支持快速pop/push，quicklist首尾两个ziplist不进行压缩，此时压缩深度为1，深度为2就表示首尾第一个和第二个ziplist都不进行压缩。

参考：
https://www.cnblogs.com/hunternet/p/12624691.html

https://www.cnblogs.com/jeemzz/p/11444143.html

https://zhuanlan.zhihu.com/p/103367294

https://blog.csdn.net/qq_24848931/article/details/104472805