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


quicklist 相关数据结构

quicklist 是由 ziplist 组成的双向链表,兼顾节省内存空间和提高查询效率的需求,其结构定义如下:

 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 的值

quicklist APIs

Get/Set Interfaces

1
2
3
4
5
6
7
/* Set fill & compress field in quicklist */
void quicklistSetCompressDepth(quicklist *quicklist, int depth);
void quicklistSetFill(quicklist *quicklist, int fill);
void quicklistSetOptions(quicklist *quicklist, int fill, int depth);

/* Return cached quicklist count */
unsigned long quicklistCount(const quicklist *ql);

构造函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/* Create a new quicklist. Free with quicklistRelease(). */
quicklist *quicklistCreate(void);

/* Create a new quicklist with some default parameters. */
quicklist *quicklistNew(int fill, int compress);

/* Create new (potentially multi-node) quicklist from a single existing ziplist.
 *
 * Returns new quicklist.  Frees passed-in ziplist 'zl'. */
quicklist *quicklistCreateFromZiplist(int fill, int compress, unsigned char *zl);

/* Duplicate the quicklist.
 * On success a copy of the original quicklist is returned.
 *
 * The original quicklist both on success or error is never modified.
 *
 * Returns newly allocated quicklist. */
quicklist *quicklistDup(quicklist *orig);

析构函数

1
2
/* Free entire quicklist. */
void quicklistRelease(quicklist *quicklist);

Push

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/* Add new entry to head node of quicklist.
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);

/* 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, const size_t sz);

/* Wrapper to allow argument-based switching between HEAD/TAIL push */
void quicklistPush(quicklist *quicklist, void *value, const size_t sz, int where);

Pop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/* pop from quicklist and return result in 'data' ptr.  Value of 'data'
 * is the return value of 'saver' function pointer if the data is NOT a number.
 *
 * If the quicklist element is a long long, then the return value is
 * returned in 'sval'.
 *
 * Return value of 0 means no elements available.
 * Return value of 1 means check 'data' and 'sval' for values.
 * If 'data' is set, use 'data' and 'sz'.  Otherwise, use 'sval'. */
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
                       unsigned int *sz, long long *sval,
                       void *(*saver)(unsigned char *data, unsigned int sz));

/* Default pop function
 *
 * Returns malloc'd value from quicklist */
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
                 unsigned int *sz, long long *slong);

Append

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/* Create new node consisting of a pre-formed ziplist.
 * Used for loading RDBs where entire ziplists have been stored
 * to be retrieved later. */
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);

/* Append all values of ziplist 'zl' individually into 'quicklist'.
 *
 * This allows us to restore old RDB ziplists into new quicklists
 * with smaller ziplist sizes than the saved RDB ziplist.
 *
 * Returns 'quicklist' argument. Frees passed-in ziplist 'zl' */
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
                                            unsigned char *zl);

Delete

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/* Delete one element represented by 'entry'
 *
 * 'entry' stores enough metadata to delete the proper position in
 * the correct ziplist in the correct quicklist node. */
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);

/* Delete a range of elements from the quicklist.
 *
 * elements may span across multiple quicklistNodes, so we
 * have to be careful about tracking where we start and end.
 *
 * Returns 1 if entries were deleted, 0 if nothing was deleted. */
int quicklistDelRange(quicklist *quicklist, const long start, const long stop);

Insert

1
2
3
4
5
6
7
/* Insert a new entry after existing entry 'entry'. */
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
                          void *value, const size_t sz);

/* Insert a new entry before existing entry 'entry'. */
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
                           void *value, const size_t sz);

quicklistGetLzf

1
2
3
4
/* Extract the raw LZF data from this quicklistNode.
 * Pointer to LZF data is assigned to '*data'.
 * Return value is the length of compressed LZF data. */
size_t quicklistGetLzf(const quicklistNode *node, void **data);

quicklistReplaceAtIndex

1
2
3
4
5
/* Replace quicklist entry at offset 'index' by 'data' with length 'sz'.
 *
 * Returns 1 if replace happened.
 * Returns 0 if replace failed and no changes happened. */
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, int sz);

quicklistRotate

1
2
/* Rotate quicklist by moving the tail element to the head. */
void quicklistRotate(quicklist *quicklist);

quicklistCompare

1
2
3
4
/* Passthrough to ziplistCompare() */
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len) {
    return ziplistCompare(p1, p2, p2_len);
}

quicklistIndex

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/* Populate 'entry' with the element at the specified zero-based index
 * where 0 is the head, 1 is the element next to head
 * and so on. Negative integers are used in order to count
 * from the tail, -1 is the last element, -2 the penultimate
 * and so on. If the index is out of range 0 is returned.
 *
 * Returns 1 if element found
 * Returns 0 if element not found */
int quicklistIndex(const quicklist *quicklist, const long long index,
                   quicklistEntry *entry);

迭代相关

 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
27
28
29
30
31
32
33
34
35
36
37
38
/* Returns a quicklist iterator 'iter'. After the initialization every
 * call to quicklistNext() will return the next element of the quicklist. */
quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction);

/* Initialize an iterator at a specific offset 'idx' and make the iterator
 * return nodes in 'direction' direction. */
quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
                                         int direction, const long long idx);

/* Get next element in iterator.
 *
 * Note: You must NOT insert into the list while iterating over it.
 * You *may* delete from the list while iterating using the
 * quicklistDelEntry() function.
 * If you insert into the quicklist while iterating, you should
 * re-create the iterator after your addition.
 *
 * iter = quicklistGetIterator(quicklist,<direction>);
 * quicklistEntry entry;
 * while (quicklistNext(iter, &entry)) {
 *     if (entry.value)
 *          [[ use entry.value with entry.sz ]]
 *     else
 *          [[ use entry.longval ]]
 * }
 *
 * Populates 'entry' with values for this iteration.
 * Returns 0 when iteration is complete or if iteration not possible.
 * If return value is 0, the contents of 'entry' are not valid */
int quicklistNext(quicklistIter *iter, quicklistEntry *node);

/* Release iterator.
 * If we still have a valid current node, then re-encode current node. */
void quicklistReleaseIterator(quicklistIter *iter);

/* Not yet implemented */
void quicklistRewind(quicklist *quicklist, quicklistIter *li);
void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);

bookmark 相关

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/* Create or update a bookmark in the list which will be updated to the next node
 * automatically when the one referenced gets deleted.
 * Returns 1 on success (creation of new bookmark or override of an existing one).
 * Returns 0 on failure (reached the maximum supported number of bookmarks).
 * NOTE: use short simple names, so that string compare on find is quick.
 * NOTE: bookmakrk creation may re-allocate the quicklist, so the input pointer
         may change and it's the caller responsibilty to update the reference. */
int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node);

/* Delete a named bookmark.
 * returns 0 if bookmark was not found, and 1 if deleted.
 * Note that the bookmark memory is not freed yet, and is kept for future use. */
int quicklistBookmarkDelete(quicklist *ql, const char *name);

/* Find the quicklist node referenced by a named bookmark.
 * When the bookmarked node is deleted the bookmark is updated to the next node,
 * and if that's the last node, the bookmark is deleted (so find returns NULL). */
quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name);

/* Free the bookmarks array in quicklist. */
void quicklistBookmarksClear(quicklist *ql);