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