乐趣区

关于redis: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…

退出移动版