Redis数据结构之快速列表-quicklist

链表

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

// 链表节点
struct listNode<T> {
    listNode *prev;
    listNode *next;
    T value;
} listNode;
​
// 链表
struct list {
    listNode *head; // 表头指针
    listNode *tail; // 表尾指针
    long len;       // 链表长度
} list;

对于链表,有以下特性:

  • 双端:节点带有prevnext指针以获取前置、后置节点

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

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

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

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

快速列表

使用链表的附加空间相对太高,因为64bit系统中指针是8个字节,所以prevnext指针需要占据16个字节,且链表节点在内存中单独分配,会加剧内存的碎片化,影响内存管理效率。

考虑到链表的以上缺点,Redis后续版本对列表数据结构进行改造,使用quicklist代替了ziplistlinkedlist

// 快速列表节点
struct quicklistNode {
    quicklistNode *prev;
    quicklistNode *next;
    ziplist *zl;         // 指向压缩列表
    int32 size;          // ziplist字节总数
    int16 count;         // ziplist中元素数量
    int2 encoding;       // 存储形式,表示原生字节数组还是LZF压缩存储
    ...
} quicklistNode;
​
// 快速列表
struct quicklist {
    quicklistNode *head;
    quicklistNode *next;
    long count;           // 元素总数
    int nodes;            // ziplist节点个数
    int compressDepth;    // LZF算法压缩深度
}
quicklist;

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

Redis数据结构之快速列表-quicklistRedis数据结构之快速列表-quicklist

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

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

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

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

上一篇:redis源码解析(十五)快速链表API功能函数解析


下一篇:Redis之quicklist源码分析