Redis中内部数据结构quicklist的作用是什么

共计 9051 个字符，预计需要花费 23 分钟才能阅读完成。

Redis 中内部数据结构 quicklist 的作用是什么，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

quicklist 概述

Redis 对外暴露的上层 list 数据类型，经常被用作队列使用。比如它支持的如下一些操作：

lpush: 在左侧（即列表头部）插入数据。

rpop: 在右侧（即列表尾部）删除数据。

rpush: 在右侧（即列表尾部）插入数据。

lpop: 在左侧（即列表头部）删除数据。

这些操作都是 O(1) 时间复杂度的。

当然，list 也支持在任意中间位置的存取操作，比如 lindex 和 linsert，但它们都需要对 list 进行遍历，所以时间复杂度较高，为 O(N)。

概况起来，list 具有这样的一些特点：它是一个能维持数据项先后顺序的列表（各个数据项的先后顺序由插入位置决定），便于在表的两端追加和删除数据，而对于中间位置的存取具有 O(N) 的时间复杂度。这不正是一个双向链表所具有的特点吗？

list 的内部实现 quicklist 正是一个双向链表。在 quicklist.c 的文件头部注释中，是这样描述 quicklist 的：

A doubly linked list of ziplists

它确实是一个双向链表，而且是一个 ziplist 的双向链表。

这是什么意思呢？

我们知道，双向链表是由多个节点（Node）组成的。这个描述的意思是：quicklist 的每个节点都是一个 ziplist。ziplist 我们已经在
上一篇介绍过。

ziplist 本身也是一个能维持数据项先后顺序的列表（按插入位置），而且是一个内存紧缩的列表（各个数据项在内存上前后相邻）。比如，一个包含 3 个节点的 quicklist，如果每个节点的 ziplist 又包含 4 个数据项，那么对外表现上，这个 list 就总共包含 12 个数据项。

quicklist 的结构为什么这样设计呢？总结起来，大概又是一个空间和时间的折中：

双向链表便于在表的两端进行 push 和 pop 操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。

ziplist 由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的 realloc。特别是当 ziplist 长度很长的时候，一次 realloc 可能会导致大批量的数据拷贝，进一步降低性能。

于是，结合了双向链表和 ziplist 的优点，quicklist 就应运而生了。

不过，这也带来了一个新问题：到底一个 quicklist 节点包含多长的 ziplist 合适呢？比如，同样是存储 12 个数据项，既可以是一个 quicklist 包含 3 个节点，而每个节点的 ziplist 又包含 4 个数据项，也可以是一个 quicklist 包含 6 个节点，而每个节点的 ziplist 又包含 2 个数据项。

这又是一个需要找平衡点的难题。我们只从存储效率上分析一下：

每个 quicklist 节点上的 ziplist 越短，则内存碎片越多。内存碎片多了，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个 quicklist 节点上的 ziplist 只包含一个数据项，这就蜕化成一个普通的双向链表了。

每个 quicklist 节点上的 ziplist 越长，则为 ziplist 分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间（它们加起来很多），但却找不到一块足够大的空闲空间分配给 ziplist 的情况。这同样会降低存储效率。这种情况的极端是整个 quicklist 只有一个节点，所有的数据项都分配在这仅有的一个节点的 ziplist 里面。这其实蜕化成一个 ziplist 了。

可见，一个 quicklist 节点上的 ziplist 要保持一个合理的长度。那到底多长合理呢？这可能取决于具体应用场景。实际上，Redis 提供了一个配置参数 list-max-ziplist-size，就是为了让使用者可以来根据自己的情况进行调整。

list-max-ziplist-size -2

我们来详细解释一下这个参数的含义。它可以取正值，也可以取负值。

当取正值的时候，表示按照数据项个数来限定每个 quicklist 节点上的 ziplist 长度。比如，当这个参数配置成 5 的时候，表示每个 quicklist 节点的 ziplist 最多包含 5 个数据项。

当取负值的时候，表示按照占用字节数来限定每个 quicklist 节点上的 ziplist 长度。这时，它只能取 - 1 到 - 5 这五个值，每个值含义如下：

-5: 每个 quicklist 节点上的 ziplist 大小不能超过 64 Kb。（注：1kb = 1024 bytes）

-4: 每个 quicklist 节点上的 ziplist 大小不能超过 32 Kb。

-3: 每个 quicklist 节点上的 ziplist 大小不能超过 16 Kb。

-2: 每个 quicklist 节点上的 ziplist 大小不能超过 8 Kb。（- 2 是 Redis 给出的默认值）

-1: 每个 quicklist 节点上的 ziplist 大小不能超过 4 Kb。

另外，list 的设计目标是能够用来存储很长的数据列表的。比如，Redis 官网给出的这个教程：
Writing a simple Twitter clone with PHP and Redis，就是使用 list 来存储类似 Twitter 的 timeline 数据。

当列表很长的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（访问起来性能也很低）。如果应用场景符合这个特点，那么 list 还提供了一个选项，能够把中间的数据节点进行压缩，从而进一步节省内存空间。Redis 的配置参数 list-compress-depth 就是用来完成这个设置的。

list-compress-depth 0

这个参数表示一个 quicklist 两端不被压缩的节点个数。注：这里的节点个数是指 quicklist 双向链表的节点个数，而不是指 ziplist 里面的数据项个数。实际上，一个 quicklist 节点上的 ziplist，如果被压缩，就是整体被压缩的。

参数 list-compress-depth 的取值含义如下：

0: 是个特殊值，表示都不压缩。这是 Redis 的默认值。

1: 表示 quicklist 两端各有 1 个节点不压缩，中间的节点压缩。

2: 表示 quicklist 两端各有 2 个节点不压缩，中间的节点压缩。

3: 表示 quicklist 两端各有 3 个节点不压缩，中间的节点压缩。

依此类推…

由于 0 是个特殊值，很容易看出 quicklist 的头节点和尾节点总是不被压缩的，以便于在表的两端进行快速存取。

Redis 对于 quicklist 内部节点的压缩算法，采用的
LZF——一种无损压缩算法。

quicklist 的数据结构定义

quicklist 相关的数据结构定义可以在 quicklist.h 中找到：

typedef struct quicklistNode {
 struct quicklistNode *prev;
 struct quicklistNode *next;
 unsigned char *zl;
 unsigned int sz; /* ziplist size in bytes */
 unsigned int count : 16; /* count of items in ziplist */
 unsigned int encoding : 2; /* RAW==1 or LZF==2 */
 unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
 unsigned int recompress : 1; /* was this node previous compressed? */
 unsigned int attempted_compress : 1; /* node can t compress; too small */
 unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
typedef struct quicklistLZF {
 unsigned int sz; /* LZF size in bytes*/
 char compressed[];} quicklistLZF;
typedef struct quicklist {
 quicklistNode *head;
 quicklistNode *tail;
 unsigned long count; /* total count of all entries in all ziplists */
 unsigned int len; /* number of quicklistNodes */
 int fill : 16; /* fill factor for individual nodes */
 unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode 结构代表 quicklist 的一个节点，其中各个字段的含义如下：

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 的实现里也没用上。

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

sz: 表示压缩后的 ziplist 大小。

compressed: 是个柔性数组（
flexible array member），存放压缩后的 ziplist 字节数组。

真正表示 quicklist 的数据结构是同名的 quicklist 这个 struct：

head: 指向头节点（左侧第一个节点）的指针。

tail: 指向尾节点（右侧第一个节点）的指针。

count: 所有 ziplist 数据项的个数总和。

len: quicklist 节点的个数。

fill: 16bit，ziplist 大小设置，存放 list-max-ziplist-size 参数的值。

compress: 16bit，节点压缩深度设置，存放 list-compress-depth 参数的值。

上图是一个 quicklist 的结构图举例。图中例子对应的 ziplist 大小配置和节点压缩深度配置，如下：

list-max-ziplist-size 3
list-compress-depth 2

这个例子中我们需要注意的几点是：

两端各有 2 个橙黄色的节点，是没有被压缩的。它们的数据指针 zl 指向真正的 ziplist。中间的其它节点是被压缩过的，它们的数据指针 zl 指向被压缩后的 ziplist 结构，即一个 quicklistLZF 结构。

左侧头节点上的 ziplist 里有 2 项数据，右侧尾节点上的 ziplist 里有 1 项数据，中间其它节点上的 ziplist 里都有 3 项数据（包括压缩的节点内部）。这表示在表的两端执行过多次 push 和 pop 操作后的一个状态。

现在我们来大概计算一下 quicklistNode 结构中的 count 字段这 16bit 是否够用。

我们已经知道，ziplist 大小受到 list-max-ziplist-size 参数的限制。按照正值和负值有两种情况：

当这个参数取正值的时候，就是恰好表示一个 quicklistNode 结构中 zl 所指向的 ziplist 所包含的数据项的最大值。list-max-ziplist-size 参数是由 quicklist 结构的 fill 字段来存储的，而 fill 字段是 16bit，所以它所能表达的值能够用 16bit 来表示。

当这个参数取负值的时候，能够表示的 ziplist 最大长度是 64 Kb。而 ziplist 中每一个数据项，最少需要 2 个字节来表示：1 个字节的 prevrawlen，1 个字节的 data（len 字段和 data 合二为一；详见
上一篇）。所以，ziplist 中数据项的个数不会超过 32 K，用 16bit 来表达足够了。

实际上，在目前的 quicklist 的实现中，ziplist 的大小还会受到另外的限制，根本不会达到这里所分析的最大值。

下面进入代码分析阶段。

quicklist 的创建

当我们使用 lpush 或 rpush 命令第一次向一个不存在的 list 里面插入数据的时候，Redis 会首先调用 quicklistCreate 接口创建一个空的 quicklist。

quicklist *quicklistCreate(void) {
 struct quicklist *quicklist;
 quicklist = zmalloc(sizeof(*quicklist));
 quicklist- head = quicklist- tail = NULL;
 quicklist- len = 0;
 quicklist- count = 0;
 quicklist- compress = 0;
 quicklist- fill = -2;
 return quicklist;
}

在很多介绍数据结构的书上，实现双向链表的时候经常会多增加一个空余的头节点，主要是为了插入和删除操作的方便。从上面 quicklistCreate 的代码可以看出，quicklist 是一个不包含空余头节点的双向链表（head 和 tail 都初始化为 NULL）。

quicklist 的 push 操作

quicklist 的 push 操作是调用 quicklistPush 来实现的。

void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
 int where) { if (where == QUICKLIST_HEAD) { quicklistPushHead(quicklist, value, sz);
 } else if (where == QUICKLIST_TAIL) { quicklistPushTail(quicklist, value, sz);
 }
/* Add new entry to head node of quicklist.
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
 quicklistNode *orig_head = quicklist- head;
 if (likely( _quicklistNodeAllowInsert(quicklist- head, quicklist- fill, sz))) {
 quicklist- head- zl =
 ziplistPush(quicklist- head- zl, value, sz, ZIPLIST_HEAD);
 quicklistNodeUpdateSz(quicklist- head);
 } else { quicklistNode *node = quicklistCreateNode();
 node- zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
 quicklistNodeUpdateSz(node);
 _quicklistInsertNodeBefore(quicklist, quicklist- head, node);
 }
 quicklist- count++;
 quicklist- head- count++;
 return (orig_head != quicklist- head);
/* Add new entry to tail node of quicklist.
 *
 * Returns 0 if used existing tail.
 * Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
 quicklistNode *orig_tail = quicklist- tail;
 if (likely( _quicklistNodeAllowInsert(quicklist- tail, quicklist- fill, sz))) {
 quicklist- tail- zl =
 ziplistPush(quicklist- tail- zl, value, sz, ZIPLIST_TAIL);
 quicklistNodeUpdateSz(quicklist- tail);
 } else { quicklistNode *node = quicklistCreateNode();
 node- zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
 quicklistNodeUpdateSz(node);
 _quicklistInsertNodeAfter(quicklist, quicklist- tail, node);
 }
 quicklist- count++;
 quicklist- tail- count++;
 return (orig_tail != quicklist- tail);
}

不管是在头部还是尾部插入数据，都包含两种情况：

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

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

在_quicklistInsertNodeAfter 的实现中，还会根据 list-compress-depth 的配置将里面的节点进行压缩。它的实现比较繁琐，我们这里就不展开讨论了。

quicklist 的其它操作

quicklist 的操作较多，且实现细节都比较繁杂，这里就不一一分析源码了，我们简单介绍一些比较重要的操作。

quicklist 的 pop 操作是调用 quicklistPopCustom 来实现的。quicklistPopCustom 的实现过程基本上跟 quicklistPush 相反，先从头部或尾部节点的 ziplist 中把对应的数据项删除，如果在删除后 ziplist 为空了，那么对应的头部或尾部节点也要删除。删除后还可能涉及到里面节点的解压缩问题。

quicklist 不仅实现了从头部或尾部插入，也实现了从任意指定的位置插入。quicklistInsertAfter 和 quicklistInsertBefore 就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作，情况比较复杂，有众多的逻辑分支。

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

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

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

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

quicklistSetOptions 用于设置 ziplist 大小配置参数（list-max-ziplist-size）和节点压缩深度配置参数（list-compress-depth）。代码比较简单，就是将相应的值分别设置给 quicklist 结构的 fill 字段和 compress 字段。

看完上述内容，你们掌握 Redis 中内部数据结构 quicklist 的作用是什么的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注丸趣 TV 行业资讯频道，感谢各位的阅读！