关于redis:Redis-List-设计与实现

前言

之前咱们曾经探讨过 Sorted Set 在 Redis 的实现，学习到了 Redis 在不同数据量的时候应用了不同的构造来优化存储和性能，并且应用两种不同的数据结构的组合来进一步优化。而明天要探讨的 List 也一模一样。

List

List 就是咱们常见的列表，在很多语言中都有实现，无论是数组还是链表，它最终的表现形式都差不多，都是一个“长长的数据”，而对于不同的底层实现，所对应的操作带来的性能也不同。比方在 java 中就有 LinkedList 和 ArrayList。而 Redis 是如何做的呢？

如果你对 Redis 的 List 应用并不是很相熟，倡议下查看一下它所有反对的命令 https://redis.io/commands/?group=list

老版本

在 Redis 的老版本中 list 的实现和 Sorted Set 策略相似，对于不同数据量的状况下实现是不一样的。在数据量小的时候，应用的也是 ziplist 也就是压缩列表（能够看做数组），而当数据质变大触发条件时，就变成了 linkedlist 也就是双向链表。

ziplist 就是通过数据的长度来定位前一个和后一个数据，从而缩小了双向链表中的前后指针。

而新版本中 Redis 应用了 quicklist 来实现，所以咱们次要探讨的是 quicklist 是如何实现的。

quicklist

数据结构

首先要看的必定是构造定义

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: 0 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmarks are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all listpacks */
    unsigned long len;          /* number of quicklistNodes */
    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];} quicklist;

咱们抓重点：

• 头节点
• 尾节点
• 长度

不错，曾经“很链表”了，那么咱们问题的要害就放到了 quicklistNode 的构造上来了。

/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items).
 * recompress: 1 bit, bool, true if node is temporary decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             /* entry size in bytes */
    unsigned int count : 16;     /* count of items in listpack */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
    unsigned int extra : 9; /* more bits to steal for future usage */
} quicklistNode;

看到 prev 和 next 就很“双向链表”了，我看到这里的时候都要开始奇怪了，如果就这样也没必要改了吧。既然从构造上看不出来，咱们就来看看办法外面是如何实现的来判断它具体节点的连贯关系。

quicklistPushTail

/* Add new entry to tail node of quicklist.
 *
 * Returns 0 if used existing tail.
 * Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_tail = quicklist->tail;
    if (unlikely(isLargeElement(sz))) {__quicklistInsertPlainNode(quicklist, quicklist->tail, value, sz, 1);
        return 1;
    }

    if (likely(_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {quicklist->tail->entry = lpAppend(quicklist->tail->entry, value, sz);
        quicklistNodeUpdateSz(quicklist->tail);
    } else {quicklistNode *node = quicklistCreateNode();
        node->entry = lpAppend(lpNew(0), value, sz);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    quicklist->count++;
    quicklist->tail->count++;
    return (orig_tail != quicklist->tail);
}

从这里咱们就能够看出端倪了，先不论判断条件，咱们看到有两个分支：

• 一个分支间接将元素 append 到了 tail 的 entry 外面
• 另一个分支却创立了一个新的 node，而后将元素 append 到新的 node 外面，再放到 quicklist 外面

OK，先不论 lpAppend 办法，大抵就有感觉了，并不是一个一般的双链表，对于双链表中的每个节点来说都是一个新的构造，满足肯定条件才会创立新的 node。所以，quicklist 解决问题的形式是压缩存储，本来的一般的双链会很长，将一些元素合并起来组成一个个 node，将这些 node 再连起来。嗯（我过后真感叹一下，是个不择手段的设计）

那么就留下了两个问题：

1. 什么时候才会创立新的 node，或者说能够预感的是必定和大小无关，那么一个 node 能存多少数据？
2. node 外面的数据是怎么寄存的呢？不会就是单纯的数组把？lpAppend 外面到底干了什么事件？

什么时候才会创立新的 node

咱们想到的必定是和大小有关系，如果数据太多必定就存不下了，看到分支的判断办法 _quicklistNodeAllowInsert

REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
                                           const int fill, const size_t sz) {if (unlikely(!node))
        return 0;

    if (unlikely(QL_NODE_IS_PLAIN(node) || isLargeElement(sz)))
        return 0;

    /* Estimate how many bytes will be added to the listpack by this one entry.
     * We prefer an overestimation, which would at worse lead to a few bytes
     * below the lowest limit of 4k (see optimization_level).
     * Note: No need to check for overflow below since both `node->sz` and
     * `sz` are to be less than 1GB after the plain/large element check above. */
    size_t new_sz = node->sz + sz + SIZE_ESTIMATE_OVERHEAD;
    if (unlikely(quicklistNodeExceedsLimit(fill, new_sz, node->count + 1)))
        return 0;
    return 1;
}

ok，非常简单和清晰的正文，isLargeElement 联合正文，太大的元素，比方 1GB，那必定独自创立 node 切实了，没话说。the lowest limit of 4k 好了，破案了。

最初，留神一个细节 listpack？是什么？没错，它就是咱们下一个问题的答案

node 外面数据是如何寄存的

在老版本外面，都会通知你，quicklist 就是双链套 ziplist，没错在老版本的确是这样实现的，而我只会通知你看最新的源码，学的才是最多的。redis 曾经缓缓在用 listpack 替换掉 ziplist 了。听我上面缓缓道来。

ziplist 的问题

ziplist 其实最大的一个问题就是连锁更新，因为 ziplist 利用数据长度来定位前后元素，通过计算长度来失去下一个元素的地位。那么势必问题就是当数据更新时，长度也更新，前一个数据的更新会导致前面数据一起动，一起移动地位。 尽管咱们晓得在列表中间接更新某个数据并非常见，但的确当真正呈现这样场景的时候就会变的十分艰难。而本来的双链表因为保留的时指针，更新数据非常容易。指针都不必动。

那想要防止这个问题，就须要对 list 的编码方式从新设计。

listpack

这个数据结构的设计理念能够参考：https://github.com/antirez/listpack/blob/master/listpack.md

/* Each entry in the listpack is either a string or an integer. */
typedef struct {/* When string is used, it is provided with the length (slen). */
    unsigned char *sval;
    uint32_t slen;
    /* When integer is used, 'sval' is NULL, and lval holds the value. */
    long long lval;
} listpackEntry;

单个元素的构造是：

    <encoding-type><element-data><element-tot-len>
    |                                            |
    +--------------------------------------------+
                (This is an element)

1. encoding-type 编码方式
2. element-data 原数据
3. element-tot-len 长度 = len(encoding-type + element-data)

就这样？对就这样。设计的关键点次要就是编码方式，它通过 11110001 这样的模式来通知你前面的数据是什么类型的数据，保留数据的位数是多少。
举例来说：11110001 示意一个 16 位整数，数据记录在后续 2 个字节的 data 中。

ziplist 因为通过长度来找到后一个元素的地位，当数据变动是长度跟着一起变了。而 listpack 要留神了，它保留的是编码方式，而对于雷同类型的数据，比方 16 位整数，前面存储的地位是固定的就是 2 个字节，即便数据变了，那也还是那个地位。绝对应的，从后向前查找时与 ziplist 是统一的通过 element-tot-len 能找到前一个元素的地位，不会影响。

总结

在看 Redis List 实现之前，我常常会感觉，不就是个 list 的嘛，弄个数组一下不就搞定了？但对于谋求极致性能和微小内存压力的缓存来说，能优化一点就要尽力去优化一点。对于 List 咱们能学到：

1. 通过不同的数据结构的组合 (双链 +listpack) 来补救对应的有余
2. 通过编码数据来优化存储构造和空间(listpack)

这两点是咱们能从中学到的，尽管咱们不肯定会遇到如此要求下的极致优化，但这样的思路又让咱们有了更厉害的武器。

参考链接

• https://github.com/antirez/listpack/blob/master/listpack.md
• https://juejin.cn/post/7245854874196459579
• https://github.com/zpoint/Redis-Internals/blob/5.0/Object/listpack/listpack.md
• https://zhuanlan.zhihu.com/p/566543361