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

京东链接
豆瓣链接