快速列表

quicklist.h - A generic doubly linked quicklist implementation

quicklist正是一个双向压缩链表,是空间和时间的折中:

  • 双向链表便于在表的两端进行push和pop操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。
  • ziplist由于是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能。
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    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;

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;


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;

list-max-ziplist-size

每个quicklist节点上的ziplist越短,则内存碎片越多。 每个quicklist节点上的ziplist越长,则不利于修改。

list-max-ziplist-size -2

  • 当取正值的时候,表示按照数据项个数来限定每个quicklist节点上的ziplist长度
  • 当取负值的时候,表示按照占用字节数来限定每个quicklist节点上的ziplist长度

  • -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。(注:1kb => 1024 bytes)
  • -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
  • -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
  • -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。(-2是Redis给出的默认值)
  • -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

list-compress-depth

当列表很长的时候,最容易被访问的很可能是两端的数据,中间的数据被访问的频率比较低(访问起来性能也很低)。如果应用场景符合这个特点,那么list还提供了一个选项,能够把中间的数据节点进行压缩,从而进一步节省内存空间。

  • 0: 是个特殊值,表示都不压缩。这是Redis的默认值。
  • n: 表示quicklist两端各有n个节点不压缩,中间的节点压缩。

Redis对于quicklist内部节点的压缩算法,采用的LZF——一种无损压缩算法。