Redis存储结构之QuickList

QuickList（快速列表）

原理

快速列表（quicklist）是以压缩列表（ziplist）为节点的链表（linkedlist），将链表按段切分，每一段使用压缩列表进行内存的连续存储，多个压缩列表通过prev和next指针组成的双向链表。它结合了压缩列表和链表的优势，进一步压缩了内存的使用量，进一步提高了效率。

特性

通过ziplist的学习了解到它又两个缺点：

1. 不能保存过多的元素，否则性能就会下降
2. 不能保存过大的元素，否则容易导致内存重新分配，甚至引起连锁更新

那么quicklist的设计就是结合了链表和ziplist的各自优势，所以一个quicklist就是一个链表，元素会分配在链表的每个节点中，每个节点又是一个ziplist，最终元素会全部存储在ziplist中

添加元素分析：

1. 先检查quicklistNode节点的ziplist是否满了
2. 如果没有满则直接添加
3. 如果满了，则添加新的quicklistNode节点并保存

源码

typedef struct quicklist {
    quicklistNode *head;   /* 表头 */
    quicklistNode *tail;   /* 表尾 */
    unsigned long count;        /* 链表中的元素总数 */
    unsigned long len;          /* 链表中的 quicklistNode 总数*/
    int fill : QL_FILL_BITS;              /* 压缩列表的最大大小，存放list-max-ziplist-size参数的值。当超出了这个配置，就会新建一个压缩列表 */
    unsigned int compress : QL_COMP_BITS; /* 结点压缩深度，存放list-compress-depth参数的值 */
    unsigned int bookmark_count: QL_BM_BITS; /* bookmarks数组的大小 */
    quicklistBookmark bookmarks[];          /* 用来快速列表重新分配内存空间时使用的数组，不使用时不占用空间 */
} quicklist;
1
2
3
4
5
6
7
8
9
10

typedef struct quicklistNode {
    struct quicklistNode *prev;  /* 指向前一个节点的指针 */
    struct quicklistNode *next;  /* 指向后一个节点的指针 */
    unsigned char *zl;           /* 指向压缩列表 */
    unsigned int sz;             /* 压缩列表字节的大小 */
    unsigned int count : 16;     /* 压缩列表的元素个数 */
    unsigned int encoding : 2;   /* 存储形式，原生字节数组还是LZF压缩存储 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 当查看了某一项被压缩的数据时，需要把数据暂时解压，这时就设置 recompress = 1 做一个标记，等有机会再把数据重新压缩 */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
1
2
3
4
5
6
7
8
9
10
11
12

typedef struct quicklistLZF {
    unsigned int sz;   /* 压缩后的ziplist大小*/
    char compressed[]; /* 柔性数组，存放压缩后的ziplist字节数据*/
} quicklistLZF;
1
2
3
4