Redis 时间和空间的折中-quicklist

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。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

Redis 时间和空间的折中-quicklist