在早期的 Redis 版本中，数据量较小时使用 ziplist 作为列表的数据结构，数据量较大时则使用 linkedlist。但考虑到 ziplist 需要频繁的重新分配内存，而 linkedlist 的指针需要额外占用一定的内存（pre 和 next 占据 16 字节），并且由于内存不连续的缘故，更容易产生内存碎片。因此3.2版本之后统一使用 quicklist 作为 列表的数据结构。

结构

quicklist 是 ziplist 和 linkedlist 的一种结合体，中和了两种数据结构的缺点。

快速列表 quicklist

1
2
3
4
5
6
7
8
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 : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;
  • head、tail：分别指向头尾 quicklistNode 节点
  • count：所有 ziplist 中 entry 的总和
  • len：quicklistNode 节点数量
  • fill：ziplist 的大小设置
  • compress：压缩深度，0表示不压缩

快速列表节点 quicklistNode

1
2
3
4
5
6
7
8
9
10
11
12
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;
  • prev 、next：双向链表指针
  • zl：如果未被压缩，则指向一个 ziplist，如果被压缩的话则指向一个 quicklistLZF 结构
  • sz：ziplist占用多少字节
  • count：当前 ziplist 存储多少元素
  • encoding：编码格式：RAW、LZF
  • container：存储结构，目前只有 ziplist，未来可能会使用其它数据结构

压缩

quicklist 结构体当中有一个 compress 属性：

  • 当 compress 取值为0的时候表示不压缩
  • 当 compress 取值为n的时候表示两端的 n 个节点不被压缩

由此可见不论 compress 取值为多少，quicklist 的头尾节点都不会被压缩

当一个 quicklistNode 节点需要被压缩时，就会将其 zl（ziplist） 属性使用 LZF 算法进行压缩，并形成下面的这个结构体

1
2
3
4
5
6
7
typedef struct quicklistLZF {
    //表示被LZF算法压缩后的ziplist的大小
    unsigned int sz; /* LZF size in bytes*/
     
    //保存压缩后的ziplist的数组，柔性数组
    char compressed[];
} quicklistLZF;

当表list存储大量数据的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（访问起来性能也很低）。如果应用场景符合这个特点，那么list还提供了一个选项，能够把中间的数据节点进行压缩，从而进一步节省内存空间。Redis的配置参数list-compress-depth就是用来完成这个设置的。