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

前景提要

在介绍快速列表之前,建议你要先了解下 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 —— 一种无损压缩算法,有兴趣的可以看下 zh.wikipedia.org/wiki/LZFSE

结构字段详解

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

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

    typedef struct quicklistLZF {
        unsigned int sz; /* LZF size in bytes*/
        char compressed[];
    } quicklistLZF;
复制代码
属性 大小 含义
prev 8字节 指向链表前一个节点的指针。
next 8字节 指向链表后一个节点的指针。
zl 8字节 数据指针。如果当前节点的数据没有压缩,那么它指向一个 ziplist 结构;否则,它指向一个 quicklistLZF 结构。
sz 4字节 ziplist 占用的字节总数。如果指向的 ziplist 被压缩,仍然表示压缩前的字节总数。
count 16位 ziplist 包含的元素个数。
encoding 2位 表示ziplist是否压缩了。目前只有两种取值:2表示被压缩了(而且用的是LZF压缩算法),1表示没有压缩。
container 2位 数据容器。为1时表示 NONE,即一个 quicklist 节点下面直接存数据,为2时表示ZIPLIST,即使用ziplist存数据。
recompress 1位 bool值,当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时,需要把数据暂时解压,这时就设置 recompress = 1 做一个标记,等有机会再把数据重新压缩。
attempted_compress 1位 bool值,在单元测试的时候用到。
extra 10位 扩展字段,以备后用。

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

属性 大小 含义
head 8字节 指向头节点的指针。
tail 8字节 指向尾节点的指针。
count 8字节 所有 ziplists 的元素总个数。
len 8字节 quicklist 节点的个数。
fill 16位 ziplist大小设置,存放 list-max-ziplist-size 参数的值。
compress 16位 节点压缩深度,存放 list-compress-depth 参数的值。

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

属性 大小 含义
sz 4字节 压缩后的ziplist大小
compressed 待定 LZF 压缩后的数据

为什么 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 来表达足够了。