Redis底层数据结构-Quicklist源码分析

简介

quicklist是Redis 3.2中引入的数据结构,其本质是一个双向链表,链表的节点类型是ziplist,当ziplist节点过多,quicklist会退化成双向链表,以提高效率。

数据结构

quicklistNode

该结构为节点类型。 - prev:指向前驱节点 - next:指向后继节点 - zl:指向对应的压缩列表 - sz:压缩列表的大小 - encoding:采用的编码方式,1为原生,2代表使用LZF进行压缩 - container:为节点指向的容器类型,1代表none,2代表ziplist存储数据 - recompress:代表这个节点是否是压缩节点,如果是,则使用压缩节点前先进行解压缩,使用后重新压缩 - attempted_compress:测试时使用

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
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; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklistLZF

如果使用LZF算法进行压缩,节点指向的结构为quicklistLZF,其中sz表示compressed数组所占用字节大小。

1
2
3
4
typedef struct quicklistLZF {
unsigned int sz; /* LZF size in bytes*/
char compressed[];
} quicklistLZF;
## quicklist - head:指向头节点 - tail:指向尾节点 - count:quicklist中压缩列表的entry总数 - len:节点个数 - fill:每个节点的ziplist长度,可以通过参数list-max-ziplist-size配置节点所占内存大小 - compress:该值表示两端各有compress个节点不压缩
1
2
3
4
5
6
7
8
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 : 16; /* fill factor for individual nodes */
unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistEntry

  • quicklist:指向当前元素所在的quicklist
  • node:指向当前元素所在的节点
  • zi:当前元素所在的ziplist
  • value:当前节点的字符串内容
  • longval:当前节点的整型值
  • sz:节点的大小
  • offset:该节点相对于整个ziplist的偏移量,即相当于第几个entry
    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;

quicklistIter

用于quicklist遍历的迭代器。 - quicklist:指向对应的quicklist - current:指向元素所在的节点 - zi:指向元素所在的ziplist - offset:表示节点在ziplist中的偏移量 - direction:表示迭代器的方向

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;

接口

quicklistPushHead

该接口在头部插入元素。传入参数分别是待插入的quicklist,插入的数据value,大小sz。返回指为0代表没有新建head节点,1代表新建了head节点 基本逻辑如下: - 查看quicklist的head节点是否允许插入,可以就利用ziplist的接口进行插入。 - 否则新建head节点进行插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
//检查头节点是否允许插入
if (likely(
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
//使用头节点中的ziplist接口进行插入
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
quicklistNodeUpdateSz(quicklist->head);
} else {
//创建新节点进行插入
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
//更新对应数据
quicklist->count++;
quicklist->head->count++;
return (orig_head != quicklist->head);
}

quicklistReplaceAtIndex

更改元素需要传入index,基本逻辑是: - 删除原有元素 - 插入新元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
int sz) {
quicklistEntry entry;
//检查index位置的元素是否存在
if (likely(quicklistIndex(quicklist, index, &entry))) {
//删除
entry.node->zl = ziplistDelete(entry.node->zl, &entry.zi);
//添加
entry.node->zl = ziplistInsert(entry.node->zl, entry.zi, data, sz);
//更新sz字段
quicklistNodeUpdateSz(entry.node);
quicklistCompress(quicklist, entry.node);
return 1;
} else {
return 0;
}
}

quicklistIndex

该方法主要通过元素的下标查找对应元素,找到index对应数据所在的节点,再调用ziplist的ziplistGet得到Index对应的数据。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//idx为需要查找的下标, 结果写入entry,返回0代表没找到,1代表找到
int quicklistIndex(const quicklist *quicklist, const long long idx,
quicklistEntry *entry) {
quicklistNode *n;
unsigned long long accum = 0;
unsigned long long index;
//idx为负值,表示从尾部向头部的偏移量
int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */
//初始化entry
initEntry(entry);
entry->quicklist = quicklist;

if (!forward) {
//idx小于0,将idx设置为(-idx) - 1,从尾部查找
index = (-idx) - 1;
n = quicklist->tail;
} else {
index = idx;
n = quicklist->head;
}

if (index >= quicklist->count)
return 0;
//遍历Node节点,找到对应的index元素
while (likely(n)) {
if ((accum + n->count) > index) {
break;
} else {
D("Skipping over (%p) %u at accum %lld", (void *)n, n->count,
accum);
accum += n->count;
n = forward ? n->next : n->prev;
}
}

if (!n)
return 0;

D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n,
accum, index, index - accum, (-index) - 1 + accum);
//计算index所在的ziplist的偏移量
entry->node = n;
if (forward) {
/* forward = normal head-to-tail offset. */
entry->offset = index - accum;
} else {
/* reverse = need negative offset for tail-to-head, so undo
* the result of the original if (index < 0) above. */
entry->offset = (-index) - 1 + accum;
}

quicklistDecompressNodeForUse(entry->node);
entry->zi = ziplistIndex(entry->node->zl, entry->offset);
//利用ziplistGet获取元素
ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval);
/* The caller will use our result, so we don't re-compress here.
* The caller can recompress or delete the node as needed. */
return 1;
}

总结

本文主要介绍了Quicklist的基本数据结构,并对该结构的基本增删改查接口做了简要分析。