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

一、什么是quicklist

quicklist 是 Redis 3.2 版本以后针对链表和压缩列表进行改造的一种数据结构，是 zipList 和 linkedList 的混合体，相对于链表它压缩了内存。进一步的提高了效率。

quicklist 其实就是简单的双链表，但每个双链表节点中保存一个 ziplist，然后每个 ziplist 中存一批 list 中的数据 (具体 ziplist 大小可配置)，这样既可以避免大量链表指针带来的内存消耗，也可以避免 ziplist 更新导致的大量性能损耗，将大的 ziplist 化整为零。

二、quicklist 的结构

2.1 quicklist 结构体

quicklist 结构体定义如下：

typedef struct quicklist {
    quicklistNode *head; /* 头结点 */
    quicklistNode *tail; /* 尾结点 */
    unsigned long count; /* 在所有的ziplist中的entry总数 */
    unsigned long len; /* quicklist节点总数 */
    int fill : QL_FILL_BITS; /* 16位，每个节点的最大容量 */
    unsigned int compress : QL_COMP_BITS; /* 16位，quicklist的压缩深度，0表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩 */
    unsigned int bookmark_count: QL_BM_BITS; /*4位，bookmarks数组的大小，bookmarks是一个可选字段，用来quicklist重新分配内存空间时使用，不使用时不占用空间*/
    quicklistBookmark bookmarks [];
} quicklist;

其中，fill 和 compress 是两个重要的字段，它们决定了 quicklist 的内存和性能特性。

• fill 表示每个 quicklistNode 节点的最大容量，不同的数值有不同的含义，默认是 -2，当然也可以配置为其他数值，具体数值含义如下：

• compress 表示 quicklist 的压缩深度，0 表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩。例如，compress 为 1 表示从两端开始，有 1 个节点不做 LZF 压缩。LZF 是种无损压缩算法。Redis 为了节省内存空间，会将 quicklist 的节点用 LZF 压缩后存储，但这里不是全部压缩，可以配置 compress 的值。

2.2 quicklistNode 结构体

quicklistNode 结构体定义如下：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl; /* quicklist节点对应的ziplist */
    unsigned int sz; /* ziplist的字节数 */
    unsigned int count : 16; /* ziplist的item数*/
    unsigned int encoding : 2; /* 数据类型，RAW==1 or LZF==2 */
    unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 这个节点以前压缩过吗？ */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* 未使用到的10位 */
} quicklistNode;

其中，zl 指向了一个 ziplist 结构，encoding 表示该 ziplist 是否被 LZF 压缩过，recompress 表示该节点是否需要重新压缩。

2.3 quicklist 的示意图

下面是一个 quicklist 的示意图，其中绿色的节点是未压缩的 ziplist 节点，红色的节点是压缩后的 ziplist 节点。假设 compress 为 1，那么从两端开始，有一个节点不压缩，其余的节点都压缩。

三、quicklist 的常用操作

3.1 创建

创建一个 quicklist 的函数如下：

quicklist *quicklistCreate(void); // 创建quicklist
quicklist *quicklistNew(int fill, int compress); // 用一些指定参数创建一个新的quicklist
void quicklistSetCompressDepth(quicklist *quicklist, int depth); // 设置压缩深度

3.2 头插和尾插

对于 list 而已，头部或者尾部插入是最常见的操作了，但其实头插和尾插还算是比较简单。

void quicklistPushHead(quicklist *quicklist, void *value, size_t sz); // 头插
void quicklistPushTail(quicklist *quicklist, void *value, size_t sz); // 尾插

3.3 头删和尾删

对于 list 而已，头部或者尾部删除也是很常见的操作了，但其实头删和尾删也还算是比较简单。

int quicklistPop(quicklist *quicklist, int where, unsigned char **data, size_t *sz, long long *slong); // 头删或尾删

3.4 查找

查找操作需要遍历整个 quicklist，对每个 ziplist 进行查找。如果找到了匹配的元素，就返回一个 quicklistEntry 结构体，表示该元素在哪个 ziplist 中，以及在 ziplist 中的位置。

int quicklistIndex(const quicklist *quicklist, const long long idx, quicklistEntry *entry); // 根据索引查找元素
void quicklistRewind(const quicklist *quicklist, quicklistIter **iter); // 创建一个从头开始的迭代器
void quicklistRewindTail(const quicklist *quicklist, quicklistIter **iter); // 创建一个从尾开始的迭代器
int quicklistNext(quicklistIter *iter, quicklistEntry *node); // 迭代器获取下一个元素
void quicklistReleaseIterator(quicklistIter *iter); // 释放迭代器

3.5 删除

删除操作需要先找到要删除的元素在哪个 ziplist 中，然后调用 ziplist 的删除函数删除该元素。如果删除后导致 ziplist 空了，就把整个 ziplist 节点从链表中删除。

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); // 删除迭代器指向的元素
int quicklistDelRange(quicklist *quicklist, const long start, const long stop); // 删除指定范围内的元素

删除操作的示意图如下：

假设我们要删除第 5 个元素，也就是 ziplist2 中的第一个元素，那么我们先找到 ziplist2，然后调用 ziplistDelete 函数删除该元素。如果 ziplist2 还有其他元素，那么就结束了。如果 ziplist2 空了，那么我们就把 ziplist2 节点从链表中删除，并释放内存。同时，更新 quicklist 的 count 和 len 字段。

3.6 其它

除了上面介绍的操作，quicklist 还有一些其它的操作，例如：

• quicklistRotate(quicklist *quicklist); // 将尾部的元素移动到头部
• quicklistDup(quicklist *orig); // 复制一个 quicklist
• quicklistRelease(quicklist *quicklist); // 释放一个 quicklist
• quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); // 比较两个元素是否相等

四、quicklist 的应用场景

quicklist 的应用场景主要是在需要使用 list 类型的数据结构时，例如：

• 存储有序的数据，如时间线、消息队列、日志等。
• 实现栈或队列的功能，如 LIFO 或 FIFO 的数据结构。
• 实现发布订阅模式，如使用 BLPOP 或 BRPOP 命令阻塞地弹出元素。
• 实现阻塞队列，如使用 LPUSH 和 RPOP 命令实现生产者消费者模式。

quicklist 相比于普通的链表，有以下优点：

• 节省内存空间，因为每个节点是一个压缩列表，可以存储多个元素，并且可以根据配置进行 LZF 压缩。
• 降低更新复杂度，因为每次插入或删除元素时，只需要更新对应的压缩列表，而不需要重新分配整个链表的内存空间。
• 提高查询效率，因为每个节点有一个计数器，可以快速定位到目标元素所在的压缩列表，而不需要遍历整个链表。

五  请问如何在Redis中使用快速列表？

在 Redis 中使用 quicklist 的方法很简单，只需要使用 list 类型的命令，

如 lpush, rpush, lpop, rpop 等，就可以自动创建和操作 quicklist。

Redis 会根据配置文件中的参数，如 list-max-ziplist-size, list-compress-depth 等，来决定 quicklist 的结构和压缩策略。

你不需要关心 quicklist 的内部实现细节，只需要按照 list 的语义来使用即可。

关于 quicklist 的性能测试报告，我没有找到专门针对 quicklist 的，但是我找到了一些关于 Redis list 的性能测试报告，你可以参考一下：

• Redis List Performance Benchmark 这是一个 PPT，介绍了 Redis list 的性能测试方法和结果，比较了不同的配置参数和命令对性能的影响。
• Redis List Performance Benchmark Report 这是一个 PDF，是上面 PPT 的详细报告，包含了更多的数据和分析。
• Redis List Performance Benchmarking 这是一个视频，是上面 PPT 的演讲录像，可以听听作者的讲解和观点。

五、总结

quicklist 是 Redis 为了优化 list 的内存和性能而设计的一种数据结构，它结合了 ziplist 和 linkedlist 的优点，既节省了内存空间，又降低了更新复杂度。quicklist 的操作也比较简单，主要是对 ziplist 的封装和管理。quicklist 是 Redis 中的一种重要的数据结构，值得我们深入学习和理解。

参考资料：

: Redis数据结构——快速列表(quicklist) - 随心所于 - 博客园 

: Redis源码剖析之快速列表(quicklist) - 知乎