Redis 3.2版本后list的实现-quickList

Redis quickList

quickList简述

• Redis中的列表对象在版本3.2之前，列表底层的编码是ziplist和linkedlist实现的，但是在版本3.2之后，重新引入了一个 quicklist 的数据结构，列表的底层都由quicklist实现。

• 在早期的设计中， 当列表对象中元素的长度比较小或者数量比较少的时候，采用ziplist来存储，当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表linkedlist来存储。

这两种存储方式的优缺点

• 双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
• ziplist存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝。

基本结构

基本结构

参数配置

• list-max-ziplist-size -2
  

  当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。

  当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，每个值含义如下：

• -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 0
  

  这个参数表示一个quicklist两端不被压缩的节点个数。注：这里的节点个数是指quicklist双向链表的节点个数，而不是指ziplist里面的数据项个数。实际上，一个quicklist节点上的ziplist，如果被压缩，就是整体被压缩的。

  参数list-compress-depth的取值含义如下：

• 0: 是个特殊值，表示都不压缩。这是Redis的默认值。

• 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。

• 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。

• 3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。

• 依此类推…

  由于0是个特殊值，很容易看出quicklist的头节点和尾节点总是不被压缩的，以便于在表的两端进行快速存取。

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

quicklist的数据结构定义

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 int 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;

quicklistNode结构代表quicklist的一个节点，其中各个字段的含义如下：

• prev: 指向链表前一个节点的指针。
• next: 指向链表后一个节点的指针。
• zl: 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
• sz: 表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
• count: 表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。
• encoding: 表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
• container: 是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
• recompress: 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
• attempted_compress: 这个值只对Redis的自动化测试程序有用。我们不用管它。
• extra: 其它扩展字段。目前Redis的实现里也没用上。