关于redis:Redis核心原理与实践列表实现原理之quicklist结构

在上一篇文章《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）公布书中局部章节内容，作为书的预览内容，欢送大家查阅，谢谢。

京东链接
豆瓣链接