Redis 源码阅读 --- quicklist

Redis 快速链表相关源码阅读笔记，源码文件 quicklist.h & quicklist.c。

1. 小结

quicklist 是由 ziplist 组成的双向链表，兼顾节省内存空间和提高查询效率的需求。

每个 quicklistNode 中包含一个 ziplist，此 ziplist 的长度受到 list-max-ziplist-size 的限制
考虑到链表的读写操作通常集中于两端，故 quicklist 中间部分的 quicklistNode 中的 ziplist 可能会使用 LZF 算法进行压缩以进一步节省内存空间，压缩程度由 list-compress-depth 控制

2. quicklist 相关数据结构

quicklist 结构定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist. */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    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[];  /* 'bookmakrs are an optional feature that
                                     * is used by realloc this struct, so that
                                     * they don't consume memory when not used. */
} quicklist;

quicklistNode: 快速链表节点，包含一 ziplist，其结构介绍将在下文详述
count: 该快速链表中所有 ziplist 的 zlentry 总数
len: 该快速链表中 quicklistNode 个数

fill: 其用于限制该快速链表中每个 quicklistNode 中 ziplist 的长度

从 ziplist 那一章节中我们知道 ziplist 每次更改操作耗时和其长度成正比，因此 ziplist 不应过长，但是如果其过短的话就无法达到节省内存空间的效果，特别地，当 fill = 1 时，quicklist 退化成普通的双向链表

可在 redis.conf 中通过设置 list-max-ziplist-size 进行配置

其值为正数时，表示的是每个 ziplist 中 zlentry 个数(zllen)上限

其值为负数时，表示的是每个 ziplist 所用字节总数(zlbytes)上限

1
2
3
4
5


-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

compress: 链表的读写通常情况下集中在两端，因此在 quicklist 中，可能会对中间的 quicklistNode 节点使用无损数据压缩算法 LZF 对其包含的 ziplist 进行压缩以进一步节省内存使用。
- compress 的大小含义如下：
  - $0$: 表示不进行压缩
  - $\mathbb{Z}^+$: 表示首尾 compress 个 quicklistNode 不会被压缩
- 可以看出，head 和 tail 节点永远不会被压缩

quicklistBookmark

quicklist 中最后一个 field 为一个柔性数组成员 bookmarks，bookmark_count 保存该数组的长度。当 quicklist 长度特别长，需要迭代遍历时，会使用到该数组作为缓存。该数组的长度应保持在较小值，以供高效查找更新，其结构定义如下：

1
2
3
4


typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

quicklistNode

quicklistNode 包装了单个 ziplist，其结构定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist. */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;           /* ziplist */
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* true if node is temporarry decompressed for usage. */
    unsigned int attempted_compress : 1; /* node can't compress; too small
                                          * used for verifying during testing */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

sz: ziplist 所占用的字节总数(zlbytes)
count: 16-bits(0 to 65535)，表示在 ziplist 中 zlentry 个数(zllen)。
- 我们知道 ziplist 的长度受到 quicklist 中 fill 参数的限制，在 32 位机器上 QL_FILL_BITS = 14，在 64 位机器上 QL_FILL_BITS = 16
  - 当 fill > 0 时，表示 zllen，其最大值为 32767，小于 65535
  - 当 fill < 0 时，表示 zlbytes，其最大值为 64kb，从 ziplist 中我们知道，当所有 zlentry 存储的是 0 到 12 的整数时，每个 zlentry 的大小为 $sizeof(prevlen) + sizeof(encoding) = 1 + 1 = 2$ 字节，$64 \times 1024 \div 2 = 32768 < 65535$
- 综上可知，16-bit 的 count 足够使用
encoding: 表示所包含的 ziplist 是否被压缩，值为 1 表示未被压缩，值为 2 表示已使用 LZF 压缩算法压缩
container: 表示 quicklistNode 所包装的数据类型，目前值固定为 2，表示包装的数据类型为 ziplist
recompress: 当我们访问 ziplist 时，需要解压数据，该参数表示 ziplist 是否被临时解压
attempted_compress: 测试用

quicklistLZF

当 quicklistNode 中的 ziplist 被压缩后，quicklistNode->zl 指向 quicklistLZF 结构，其定义如下：

1
2
3
4
5


/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'. */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

值得注意的是，此处 sz 指的是压缩后得到的 compressed 字节数组的长度，而 quicklistNode->sz 指的是 ziplist 压缩前的长度。

quicklistIter

quicklist 的迭代器，其结构如下：

1
2
3
4
5
6
7


typedef struct quicklistIter {
    const quicklist *quicklist;
    quicklistNode *current;
    unsigned char *zi;
    long offset; /* offset in current ziplist */
    int direction;
} quicklistIter;

quicklist: 当前迭代的快速链表
current: 当前迭代的 quicklistNode
zi: 当前迭代的 zlentry
offset: 当前访问的 zlentry 在 current->zl 中的偏移量
direction: 迭代方向

quicklistEntry

用于描述 quicklist 中的每个 zlentry 的状态。

1
2
3
4
5
6
7
8
9


typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;

quicklist: 指向该 zlentry 所在的快速链表
node: 指向该 zlentry 所在的 quicklistNode
zi: 指向该 zlentry
offset: 该 zlentry 在 node->zl 中的偏移量
当 zlentry 的数据类型为字符串时，value 和 sz 保存了 zlentry 的值
当 zlentry 的数据类型为整型时，longval 保存了 zlentry 的值

Table of Contents

1. 小结

2. quicklist 相关数据结构