Redis 核心原理与实践 -- 列表实现原理之 quicklist 结构

关注

发布于: 1 小时前

在上一篇文章《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 所示。

配置说明

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）发布书中部分章节内容，作为书的预览内容，欢迎大家查阅，谢谢。

京东链接

豆瓣链接

发布于: 1 小时前阅读数: 4

原文链接:【http://xie.infoq.cn/article/1723194c9edbc36af771acbd1】。文章转载请联系作者。