Redis笔记-结构篇-快速列表

注意：本系列文章分析的 Redis 源码版本：https://github.com/Sidfate/redis，是文章发布时间的最新版。

前景提要

在介绍快速列表之前，建议你要先了解下 ziplist 和 adlist，特别是 ziplist （参考我的文章《【最完整系列】Redis-结构篇-压缩列表》），关于 adlist 下面我会简单解释一下。

adlist

adlist 其实就是一个常规的双向链表实现，show you source code：

    typedef struct listNode {
        struct listNode *prev;
        struct listNode *next;
        void *value;
    } listNode;
    
    typedef struct list {
        listNode *head;
        listNode *tail;
        void *(*dup)(void *ptr);
        void (*free)(void *ptr);
        int (*match)(void *ptr, void *key);
        unsigned long len;
    } list;

如果你对上面的结构还很陌生不熟悉，可以在网上或者随便一本数据结构的书都可以找到，这里我也不再详细介绍了。

quicklist

ok，在我们切入正题前，先讲下在早期的 redis 版本中，列表键的实现分 2 种，元素数量少时用 ziplist，多时用 adlist，但在 3.2（网上资料查到的，不一定准确）之后的版本里，都用 quicklist 取代：

    > lpush test_list 1
    (integer) 1
    > object encoding test_list
    "quicklist"

为什么要专门设计一个 quicklist 来重新定义呢？接下来从源码的角度来解读。首先还是看注释（redis 源码的注释真香）：

quicklist.c - A doubly linked list of ziplists

然后再看下源码结构实现：

    typedef struct quicklistNode {
        struct quicklistNode *prev;
        struct quicklistNode *next;
        unsigned char *zl;         
        unsigned int sz;             /* ziplist 占用的字节总数 */
        unsigned int count : 16;     /* ziplist 的元素个数 */
        unsigned int encoding : 2;   /* 是否被压缩，2表示被压缩，1表示原生 */
        unsigned int container : 2;  
        unsigned int recompress : 1; 
        unsigned int attempted_compress : 1; 
        unsigned int extra : 10; 
    } quicklistNode;
    
    typedef struct quicklist {
        quicklistNode *head;
        quicklistNode *tail;
        unsigned long count;        /* 所有 ziplists 的元素总和 */
        unsigned long len;          /* quicklistNodes 的个数 */
        int fill : 16;              
        unsigned int compress : 16; 
    } quicklist;

字段的详细解释请参照本文末尾的字段详解部分。

所大家明白了吗，为什么我在一开始让大家先去了解下 ziplist 和 adlist，因为 quicklist 其实就是一个以 ziplist 为节点（quicklistNode 中存放指向 ziplist 的指针）的 adlist，没图说个JB：

知道结构后再回到我们最初的问题，quicklist 的结构为什么这样设计呢？quicklist 平衡了 ziplist 和 adlist 的优缺点：

• 双向链表便于在表的两端进行 push 和 pop 操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片，不利于内存管理。
• ziplist 由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的 realloc。特别是当 ziplist 长度很长的时候，一次 realloc 可能会导致大批量的数据拷贝，进一步降低性能。

但是问题还是类了，quicklist 中 quicklistNode 包含多长的 ziplist 多少合适呢？长度如果小了，跟普通的双向链表也就差不多了，还是有内存碎片的问题；长度大了，每个 quicklist 节点上的 ziplist 需要大片的连续内存，操作内存的效率还是下降了。所以这个长度肯定是一个平衡值，它是 redis 提供的一个选项配置，默认是 -2，来看下官方说明：

# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

这里我就不翻译了，原生英文解释的很清楚了，唯一一点要说明下的是，当 list-max-ziplist-size 设置为正数时，表示每个 list 节点中储存元素个数。

压缩机制

大家仔细看 quicklist 的源码结构时，可能还注意到出现了很多 compress 的字样，这是因为 redis 为 quicklist 提供了一套压缩机制。

当 quicklist 很长的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（访问起来性能也很低）。如果应用场景符合这个特点，redis 还提供了一个选项，能够把中间的数据节点进行压缩，从而进一步节省内存空间。Redis的配置参数 list-compress-depth 就是用来完成这个设置的。

# 列表也可以被压缩。
# 压缩深度指的是列表两侧开始不需要 ziplist 节点的深度（下面会解释）。
#	为了执行快速的 push/pop 操作，列表的头和尾通常不压缩。
# 设置如下:
# 0: 禁用压缩机制
# 1: 压缩深度 1 表示压缩除了头和尾之外的所有内部节点。例如结构：
#    [head]->node->node->...->node->[tail]
#    因为[head], [tail]永远不会被压缩，它们直接的 node 都后被压缩。
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
#    2 表示不压缩 head，head->next，tail->prev 和 tail, 它们之前的 node 都压缩。
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# 以此类推...
list-compress-depth 0

这个参数默认是 0 也就是不压缩，Redis对于 quicklist 内部节点的压缩算法，采用的 LZF —— 一种无损压缩算法，有兴趣的可以看下 https://zh.wikipedia.org/wiki/LZFSE。

结构字段详解

之前的内容已经对源码结构中大多数的字段做了说明，但是还遗留一些字段我在这里统一解释下。

首先补充一个结构 quicklistLZF，后面的说明中会出现：

    typedef struct quicklistLZF {
        unsigned int sz; /* LZF size in bytes*/
        char compressed[];
    } quicklistLZF;

需要注意的是，我发现网上的很多文章都没有提到的一点，官方给出的解释中说明了 quicklistNode 是一个 32 字节的结构，这应该是针对 64 位系统而言的，因为 prev，next 和 zl 都是指针，在 64 位系统中占 8 字节，以下的结构同理。

另外需要注意一点的是 quicklist 结构在 64 位系统中是占 40 个字节，但是如上计算我得出的长度是 36 字节，这里面涉及到了结构体字节对齐约定，目的的话还是为了提升数据的读取效率。

为什么 quicklistNode 中的 count 用 16 位就可以表示？

我们已经知道，ziplist 大小受到 list-max-ziplist-size 参数的限制。按照正值和负值有两种情况：

• 当这个参数取正值的时候，就是恰好表示一个 quicklistNode 结构中 zl 所指向的 ziplist 所包含的数据项的最大值。list-max-ziplist-size 参数是由quicklist结构的 fill 字段来存储的，而 fill 字段是 16bit，所以它所能表达的值能够用 16bit 来表示。
• 当这个参数取负值的时候，能够表示的 ziplist 最大长度是 64 Kb。而 ziplist 中每一个数据项，最少需要 2 个字节来表示（详见《【最完整系列】Redis-结构篇-压缩列表》）。所以，ziplist中数据项的个数不会超过 32 Kb，用 16bit 来表达足够了。