Redis 快速链表相关源码阅读笔记,源码文件 quicklist.h
& quicklist.c
。
小结
quicklist
是由 ziplist
组成的双向链表,兼顾节省内存空间和提高查询效率的需求。
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
进行配置
-
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
的值
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);
|