1.quicklist 简介
quicklist 并不像前面章节介绍的sds、链表、zskiplist、ziplist 没有很明确的对外暴露，而它直接对外暴露的我们平常使用的List 。
quicklist.c - A doubly linked list of ziplists
上面解释从quicklist.c 文件拿来的 ，官方对quicklist的解释是一个ziplist的双向链表，可以理解为一个双向链表其中内部的Node 都是ziplist结构。
ziplist 我们的知道本身就是能维持数据项先后顺序的列表 并且在内存上是连续，上一章Redis 存储效率的追求-ziplist 有很详细的讲解。
在前面章节的基础上和看到quicklist的官方解释大体就能猜到quicklist 是怎么样的结构，作为一个list 必然需要考虑俩个比较大的问题：查找和更新（包含插入）。在我们工作学习中都会用很多的列表、链表等并且都会在这俩个问题中进行选择。
下面我们了解下quicklist这样设计到底为了什么
1、ziplist 内存是连续，存储的效率非常高，但是它并不适合大量的更新，每次的数据更新都导致内存的重新分配甚至导致连锁反应。在数据量比较大的情况，可能是灾难性的。
2、双向链表 优点本身就很明显，数据的更新本身就它具备的优势。
双向链表的节点都是单独的内存空间并且不连续，链表大来必然会导致大量的内存碎片，作为以性能为优势的redis 肯定是不能容忍的。如果我们将node 全部以ziplist进行存储，可想而知性能肯定是比较大的提升，这样就产生了我们的quicklist。总结起来， quicklist是对时间和空间的一种折中方案。
既然我们大体了解quicklist的结构，我们可能会有这样一些个疑问
- quicklist 的ziplist 难道就没有大小限制吗？
- 都是追求性能难道我们不应该考虑下是不是可以把数据进行压缩？
针对上面的问题我们先看下redis.conf 俩个配置项
# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# 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.
list-max-ziplist-size -2
# Lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression. The head and tail of the list
# are always uncompressed for fast push/pop operations. Settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
# going from either the head or tail"
# So: [head]->node->node->...->node->[tail]
# [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
# 2 here means: don't compress head or head->next or tail->prev or tail,
# but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0
我们先看下list-max-ziplist-size 字面上很容理解列表最大的ziplist长度，但是为什么会是负数，在redis.conf里面已经有比较详细的解释，下面我们来看下。
list-max-ziplist-size 负数情况只有5个选值为-1到-5，它表示并不是size等于多少个，而是大小。
- -1:quicklist 的节点ziplist大小最大不能超过4KB
- -2:quicklist 的节点ziplist大小最大不超过8KB
- -3:quicklist 的节点ziplist大小最大不超过16KB
- -4:quicklist 的节点ziplist大小最大不超过32KB
- -5:quicklist 的节点ziplist大小最大不超过64KB
list-max-ziplist-size 为正数的时候表示quicklist节点ziplist的长度，当这个参数配置为3，表示quicklist节点ziplist的数据项最多3个。
我们在看下list-compress-depth 字面理解是quicklist的压缩深度，官方注释意思是这个配置项表示quicklist 压缩节点ziplist的数量并且两端不被压缩，还解释到为了快速的 push/pop操作 head和tail不进行压缩。
- 0:表示quicklist所有的节点ziplist 都不进行压缩。
- 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
- 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
- 3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。
依此类推…
看到这里其实我们可能会有疑问为什么会有这样奇怪的配置，设置中间端压缩，这样的设置很方便我们在表的两端进行快速存取。
看到俩个配置项就已经解释了上面的俩个问题。
2、quicklist 结构定义
/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
* We use bit fields keep the quicklistNode at 32 bytes.
* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
* encoding: 2 bits, RAW=1, LZF=2.
* container: 2 bits, NONE=1, ZIPLIST=2.
* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
* attempted_compress: 1 bit, boolean, used for verifying during testing.
* extra: 12 bits, free for future use; pads out the remainder of 32 bits */
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;
/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
* 'sz' is byte length of 'compressed' field.
* 'compressed' is LZF data with total (compressed) length 'sz'
* NOTE: uncompressed length is stored in quicklistNode->sz.
* When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
unsigned int sz; /* LZF size in bytes*/
char compressed[];
} quicklistLZF;
/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
* 'count' is the number of total entries.
* 'len' is the number of quicklist nodes.
* 'compress' is: -1 if compression disabled, otherwise it's the number
* of quicklistNodes to leave uncompressed at ends of quicklist.
* 'fill' is the user-requested (or default) fill factor. */
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;
quicklistNode结构代表quicklist的一个节点，其中各个字段的含义如下：
- prev: 指向链表前一个节点的指针。
- next: 指向链表后一个节点的指针。
- zl: 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
- sz: 表示zl指向的ziplist的总大小（包括
zlbytes,zltail,zllen,zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。 - count: 表示ziplist里面包含的数据项个数 大小16bit
- encoding: 表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
- container: 是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
- recompress: 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
- attempted_compress: 这个值只对Redis的自动化测试程序有用。我们不用管它。
- extra: 其它扩展字段。目前Redis的实现里也没用上。
quicklistLZF结构表示一个被压缩过的ziplist。其中：
- sz: 表示压缩后的ziplist大小。
- compressed: 存放压缩后的ziplist字节数组。
quicklist的数据结构：
- head: 指向头节点（左侧第一个节点）的指针。
- tail: 指向尾节点（右侧第一个节点）的指针。
- count: 所有ziplist数据项的个数总和。
- len: quicklist节点的个数。
- fill: 16bit，ziplist大小设置，存放
list-max-ziplist-size参数的值。 - compress: 16bit，节点压缩深度设置，存放
list-compress-depth参数的值。
上面的quicklistNode.count 表示ziplist里面包含的数据项个数，我们考虑下这个16bit大小的字段是否真的够用？
- 当list-max-ziplist-size 为-5 表示ziplist最大存储为64KB，假设ziplist的数据项只需要2个字节，1个字节prevlen，1个字节为entry-data 那么最多存储为32KB的数据项，16bit 存储最大为65536，32*1024=32768个字节，完全足够了。
- 当list-max-ziplist-size 正数的情况 list-max-ziplist-size参数是由quicklist结构的fill字段来存储的，而fill字段是16bit，所以它所能表达的值能够用16bit来表示。
3、总结
- quicklist是 Redis从性能折中考虑构建的一种数据结构。
- 对链表和ziplist 理解的前提下 很容易理解quicklist。
网友评论