前言

之前我们已经讨论过 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

数据结构

首先要看的肯定是结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 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 的结构上来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
2
3
4
5
6
7
8
/* 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;

单个元素的结构是：

1
2
3
4
<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)

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

参考链接