在上一篇文章《Redis 列表实现原理之 ziplist 构造》，咱们剖析了 ziplist 构造如何应用一块残缺的内存存储列表数据。
同时也提出了一个问题：如果链表很长，ziplist 中每次插入或删除节点时都须要进行大量的内存拷贝，这个性能是无奈承受的。
本文剖析 quicklist 构造如何解决这个问题，并实现 Redis 的列表类型。
quicklist 的设计思维很简略，将一个长 ziplist 拆分为多个短 ziplist，防止插入或删除元素时导致大量的内存拷贝。
ziplist 存储数据的模式更相似于数组，而 quicklist 是真正意义上的链表构造，它由 quicklistNode 节点链接而成，在 quicklistNode 中应用 ziplist 存储数据。
提醒：本文以下代码如无非凡阐明，均位于 quicklist.h/quicklist.c 中。
本文以下说的“节点”，如无非凡阐明，都指 quicklistNode 节点，而不是 ziplist 中的节点。
定义
quicklistNode 的定义如下：
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
unsigned int sz;
unsigned int count : 16;
unsigned int encoding : 2;
unsigned int container : 2;
unsigned int recompress : 1;
unsigned int attempted_compress : 1;
unsigned int extra : 10;
} quicklistNode;- prev、next：指向前驱节点，后驱节点。
- zl：ziplist，负责存储数据。
- sz：ziplist 占用的字节数。
- count：ziplist 的元素数量。
- encoding：2 代表节点已压缩，1 代表没有压缩。
- container：目前固定为 2，代表应用 ziplist 存储数据。
- recompress：1 代表临时解压（用于读取数据等），后续须要时再将其压缩。
- extra：预留属性，暂未应用。
当链表很长时，两头节点数据拜访频率较低。这时 Redis 会将两头节点数据进行压缩，进一步节俭内存空间。Redis 采纳是无损压缩算法—LZF 算法。
压缩后的节点定义如下：
typedef struct quicklistLZF {
unsigned int sz;
char compressed[];} quicklistLZF;- sz：压缩后的 ziplist 大小。
- compressed：寄存压缩后的 ziplist 字节数组。
quicklist 的定义如下：
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : QL_FILL_BITS;
unsigned int compress : QL_COMP_BITS;
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];} quicklist;- head、tail：指向头节点、尾节点。
- count：所有节点的 ziplist 的元素数量总和。
- len：节点数量。
- fill：16bit，用于判断节点 ziplist 是否已满。
- compress：16bit，寄存节点压缩配置。
quicklist 的构造如图 2 - 5 所示。
操作剖析
插入元素到 quicklist 头部：
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
// [1]
if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {// [2]
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
// [3]
quicklistNodeUpdateSz(quicklist->head);
} else {// [4]
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);
}参数阐明：
- value、sz：插入元素的内容与大小。
【1】判断 head 节点 ziplist 是否已满，_quicklistNodeAllowInsert 函数中依据 quicklist.fill 属性判断节点是否已满。
【2】head 节点未满，间接调用 ziplistPush 函数，插入元素到 ziplist 中。
【3】更新 quicklistNode.sz 属性。
【4】head 节点已满，创立一个新节点，将元素插入新节点的 ziplist 中，再将该节拍板插入 quicklist 中。
也能够在 quicklist 的指定地位插入元素：
REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
void *value, const size_t sz, int after) {
int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
int fill = quicklist->fill;
quicklistNode *node = entry->node;
quicklistNode *new_node = NULL;
...
// [1]
if (!_quicklistNodeAllowInsert(node, fill, sz)) {full = 1;}
if (after && (entry->offset == node->count)) {
at_tail = 1;
if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {full_next = 1;}
}
if (!after && (entry->offset == 0)) {
at_head = 1;
if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {full_prev = 1;}
}
// [2]
...
}参数阐明：
- entry：quicklistEntry 构造，quicklistEntry.node 指定元素插入的 quicklistNode 节点，quicklistEntry.offset 指定插入 ziplist 的索引地位。
- after：是否在 quicklistEntry.offset 之后插入。
【1】依据参数设置以下标记。
- full：待插入节点 ziplist 是否已满。
- at_tail：是否 ziplist 尾插。
- at_head：是否 ziplist 头插。
- full_next：后驱节点是否已满。
-
full_prev：前驱节点是否已满。
提醒：头插指插入链表头部，尾插指插入链表尾部。
【2】依据下面的标记进行解决，代码较繁缛，这里不再列出。
这里的执行逻辑如表 2 - 2 所示。
咱们只看最初一种场景的实现：
// [1]
quicklistDecompressNodeForUse(node);
// [2]
new_node = _quicklistSplitNode(node, entry->offset, after);
new_node->zl = ziplistPush(new_node->zl, value, sz,
after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
// [3]
__quicklistInsertNode(quicklist, node, new_node, after);
// [4]
_quicklistMergeNodes(quicklist, node);【1】如果节点已压缩，则解压节点。
【2】从插入节点中拆分出一个新节点，并将元素插入新节点中。
【3】将新节点插入 quicklist 中。
【4】尝试合并节点。_quicklistMergeNodes 尝试执行以下操作：
- 将 node->prev->prev 合并到 node->prev。
- 将 node->next 合并到 node->next->next。
- 将 node->prev 合并到 node。
- 将 node 合并到 node->next。
合并条件：如果合并后节点大小仍满足 quicklist.fill 参数要求，则合并节点。
这个场景解决与 B + 树的节点决裂合并有点类似。
quicklist 罕用的函数如表 2 - 3 所示。
| 函数 | 作用 |
|---|---|
| quicklistCreate、quicklistNew | 创立一个空的 quicklist |
| quicklistPushHead，quicklistPushTail | 在 quicklist 头部、尾部插入元素 |
| quicklistIndex | 查找给定索引的 quicklistEntry 节点 |
| quicklistDelEntry | 删除给定的元素 |
配置阐明
- list-max-ziplist-size：配置 server.list_max_ziplist_size 属性，该值会赋值给 quicklist.fill。取正值，示意 quicklist 节点的 ziplist 最多能够寄存多少个元素。例如，配置为 5，示意每个 quicklist 节点的 ziplist 最多蕴含 5 个元素。取负值，示意 quicklist 节点的 ziplist 最多占用字节数。这时，它只能取 - 1 到 - 5 这五个值（默认值为 -2），每个值的含意如下：
-5：每个 quicklist 节点上的 ziplist 大小不能超过 64 KB。
-4：每个 quicklist 节点上的 ziplist 大小不能超过 32 KB。
-3：每个 quicklist 节点上的 ziplist 大小不能超过 16 KB。
-2：每个 quicklist 节点上的 ziplist 大小不能超过 8 KB。
-1：每个 quicklist 节点上的 ziplist 大小不能超过 4 KB。 - list-compress-depth：配置 server.list_compress_depth 属性，该值会赋值给 quicklist.compress。
0：示意节点都不压缩，Redis 的默认配置。
1：示意 quicklist 两端各有 1 个节点不压缩，两头的节点压缩。
2：示意 quicklist 两端各有 2 个节点不压缩，两头的节点压缩。
3：示意 quicklist 两端各有 3 个节点不压缩，两头的节点压缩。
以此类推。
编码
ziplist 因为结构紧凑，能高效应用内存，所以在 Redis 中被宽泛应用，可用于保留用户列表、散列、有序汇合等数据。
列表类型只有一种编码格局 OBJ_ENCODING_QUICKLIST，应用 quicklist 存储数据（redisObject.ptr 指向 quicklist 构造）。列表类型的实现代码在 t_list.c 中，读者能够查看源码理解实现更多细节。
总结
- ziplist 是一种结构紧凑的数据结构，应用一块残缺内存存储链表的所有数据。
- ziplist 内的元素反对不同的编码格局，以最大限度地节俭内存。
- quicklist 通过切分 ziplist 来进步插入、删除元素等操作的性能。
- 链表的编码格局只有 OBJ_ENCODING_QUICKLIST。
本文内容摘自作者新书 《Redis 外围原理与实际》，这本书深刻地剖析了 Redis 罕用个性的外部机制与实现形式，大部分内容源自对 Redis 源码的剖析，并从中总结出设计思路、实现原理。通过浏览本书，读者能够疾速、轻松地理解 Redis 的外部运行机制。
通过该书编辑批准，我会持续在集体技术公众号（binecy）公布书中局部章节内容，作为书的预览内容，欢送大家查阅，谢谢。
京东链接
豆瓣链接