quicklist实现

quicklist实现

List属于单值多value，链表用的是双向链表结构，list支持pop、push来操作头部和尾部，既可以用做栈也可以用做队列

在3.2版本之前使用的是ziplist和linkedlist，在3.2版本之后使用的是quicklist

quicklist结构

由于linkedlist的附加空间相对太高，prev和next指针就要占去16个字节，而且每个节点的内存都是单独分配，加剧了内存的碎片化，使用quicklist来代替之前的ziplist+linkedlist

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 : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl; // 对应的是ziplist
    // ziplist的字节总数
    unsigned int sz;             /* ziplist size in bytes */
    // ziplist中的元素数量
    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;

看代码好像底层还是使用的ziplist，而且还有前驱和后继指针，就是一个ziplist+linkedlist混合体，把多个ziplist使用双向指针串联起来了。

默认单个ziplist长度为8字节，使用 list-max-ziplist-size来进行配置

# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.