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

2022-01-11  本文已影响0人  小波同学

一、前言

在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 指针就要占去 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;

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;

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。其中：

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 整个内存布局大致如下：


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)，而不管是在头部还是尾部插入数据，都包含两种情况：

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

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 其他

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

总结

从代码和结构可以看出，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

上一篇 下一篇

猜你喜欢

热点阅读