Redis quicklist设计

quicklist 的设计,其实是结合了链表和 ziplist 各自的优势。简单来说,一个 quicklist 就是一个链表,而链表中的每个元素又是一个 ziplist。我们来看下 quicklist 的数据结构,这是在quicklist.h文件中定义的,而 quicklist 的具体实现是在quicklist.c文件中。首先,quicklist 元素的定义,也就是 quicklistNode。因为 quicklist 是一个链表,所以每个 quicklistNode 中,都包含了分别指向它前序和后序节点的指针prev和next。同时,每个 quicklistNode 又是一个 ziplist,所以,在 quicklistNode 的结构体中,还有指向 ziplist 的指针*zl。此外,quicklistNode 结构体中还定义了一些属性,比如 ziplist 的字节大小、包含的元素个数、编码格式、存储方式等。下面的代码显示了 quicklistNode 的结构体定义

quicklist 的设计,其实是结合了链表和 ziplist 各自的优势。简单来说,一个 quicklist 就是一个链表,而链表中的每个元素又是一个 ziplist。

typedef struct quicklistNode {
 struct quicklistNode *prev; //前一个quicklistNode
 struct quicklistNode *next; //后一个quicklistNode
 unsigned char *zl; //quicklistNode指向的ziplist
 unsigned int sz; //ziplist的字节大小
 unsigned int count : 16; //ziplist中的元素个数 
 unsigned int encoding : 2; //编码格式,原生字节数组或压缩存储
 unsigned int container : 2; //存储方式
 unsigned int recompress : 1; //数据是否被压缩
 unsigned int attempted_compress : 1; //数据能否被压缩
 unsigned int extra : 10; //预留的bit位
} quicklistNode;

quicklist 作为一个链表结构,在它的数据结构中,是定义了整个 quicklist 的头、尾指针,这样一来,我们就可以通过 quicklist 的数据结构,来快速定位到 quicklist 的链表头和链表尾。

此外,quicklist 中还定义了 quicklistNode 的个数、所有 ziplist 的总元素个数等属性。

typedef struct quicklist {
 quicklistNode *head; //quicklist的链表头
 quicklistNode *tail; //quicklist的链表尾
 unsigned long count; //所有ziplist中的总元素个数
 unsigned long len; //quicklistNodes的个数
 ...
} quicklist;

也正因为 quicklist 采用了链表结构,所以当插入一个新的元素时,quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素,这是通过 _quicklistNodeAllowInsert 函数来完成判断的。

_quicklistNodeAllowInsert 函数会计算新插入元素后的大小(new_sz),这个大小等于 quicklistNode 的当前大小(node->sz)、插入元素的大小(sz),以及插入元素后 ziplist 的 prevlen 占用大小。

在计算完大小之后,_quicklistNodeAllowInsert 函数会依次判断新插入的数据大小(sz)是否满足要求,即单个 ziplist 是否不超过 8KB,或是单个 ziplist 里的元素个数是否满足要求。

只要这里面的一个条件能满足,quicklist 就可以在当前的 quicklistNode 中插入新元素,否则 quicklist 就会新建一个 quicklistNode,以此来保存新插入的元素。

Redis源码剖析与实战 学习笔记 Day6 06 | 从ziplist到quicklist,再到listpack的启发

https://time.geekbang.org/col...

作者:wkq2786130原文地址:https://segmentfault.com/a/1190000043351460

%s 个评论

要回复文章请先登录注册