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: 该快速链表中所有 ziplistzlentry 总数

  • len: 该快速链表中 quicklistNode 个数

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

    • ziplist 那一章节中我们知道 ziplist 每次更改操作耗时和其长度成正比,因此 ziplist 不应过长,但是如果其过短的话就无法达到节省内存空间的效果,特别地,当 fill = 1 时,quicklist 退化成普通的双向链表
    • 可在 redis.conf 中通过设置 list-max-ziplist-size 进行配置
      • 其值为正数时,表示的是每个 ziplistzlentry 个数(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}^+$: 表示首尾 compressquicklistNode 不会被压缩
    • 可以看出,headtail 节点永远不会被压缩

quicklistBookmark

quicklist 中最后一个 field 为一个柔性数组成员 bookmarksbookmark_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),表示在 ziplistzlentry 个数(zllen)。

    • 我们知道 ziplist 的长度受到 quicklistfill 参数的限制,在 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: 当前访问的 zlentrycurrent->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: 该 zlentrynode->zl 中的偏移量
  • zlentry 的数据类型为字符串时,valuesz 保存了 zlentry 的值
  • zlentry 的数据类型为整型时,longval 保存了 zlentry 的值