乐趣区

关于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 所示。

函数 作用
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)公布书中局部章节内容,作为书的预览内容,欢送大家查阅,谢谢。

京东链接
豆瓣链接

退出移动版