Redis中内部数据结构quicklist的作用是什么

63次阅读
没有评论

共计 9051 个字符,预计需要花费 23 分钟才能阅读完成。

Redis 中内部数据结构 quicklist 的作用是什么,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

quicklist 概述

Redis 对外暴露的上层 list 数据类型,经常被用作队列使用。比如它支持的如下一些操作:

lpush: 在左侧(即列表头部)插入数据。

rpop: 在右侧(即列表尾部)删除数据。

rpush: 在右侧(即列表尾部)插入数据。

lpop: 在左侧(即列表头部)删除数据。

这些操作都是 O(1) 时间复杂度的。

当然,list 也支持在任意中间位置的存取操作,比如 lindex 和 linsert,但它们都需要对 list 进行遍历,所以时间复杂度较高,为 O(N)。

概况起来,list 具有这样的一些特点:它是一个能维持数据项先后顺序的列表(各个数据项的先后顺序由插入位置决定),便于在表的两端追加和删除数据,而对于中间位置的存取具有 O(N) 的时间复杂度。这不正是一个双向链表所具有的特点吗?

list 的内部实现 quicklist 正是一个双向链表。在 quicklist.c 的文件头部注释中,是这样描述 quicklist 的:

A doubly linked list of ziplists

它确实是一个双向链表,而且是一个 ziplist 的双向链表。

这是什么意思呢?

我们知道,双向链表是由多个节点(Node)组成的。这个描述的意思是:quicklist 的每个节点都是一个 ziplist。ziplist 我们已经在
上一篇介绍过。

ziplist 本身也是一个能维持数据项先后顺序的列表(按插入位置),而且是一个内存紧缩的列表(各个数据项在内存上前后相邻)。比如,一个包含 3 个节点的 quicklist,如果每个节点的 ziplist 又包含 4 个数据项,那么对外表现上,这个 list 就总共包含 12 个数据项。

quicklist 的结构为什么这样设计呢?总结起来,大概又是一个空间和时间的折中:

双向链表便于在表的两端进行 push 和 pop 操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。

ziplist 由于是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的 realloc。特别是当 ziplist 长度很长的时候,一次 realloc 可能会导致大批量的数据拷贝,进一步降低性能。

于是,结合了双向链表和 ziplist 的优点,quicklist 就应运而生了。

不过,这也带来了一个新问题:到底一个 quicklist 节点包含多长的 ziplist 合适呢?比如,同样是存储 12 个数据项,既可以是一个 quicklist 包含 3 个节点,而每个节点的 ziplist 又包含 4 个数据项,也可以是一个 quicklist 包含 6 个节点,而每个节点的 ziplist 又包含 2 个数据项。

这又是一个需要找平衡点的难题。我们只从存储效率上分析一下:

每个 quicklist 节点上的 ziplist 越短,则内存碎片越多。内存碎片多了,有可能在内存中产生很多无法被利用的小碎片,从而降低存储效率。这种情况的极端是每个 quicklist 节点上的 ziplist 只包含一个数据项,这就蜕化成一个普通的双向链表了。

每个 quicklist 节点上的 ziplist 越长,则为 ziplist 分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间(它们加起来很多),但却找不到一块足够大的空闲空间分配给 ziplist 的情况。这同样会降低存储效率。这种情况的极端是整个 quicklist 只有一个节点,所有的数据项都分配在这仅有的一个节点的 ziplist 里面。这其实蜕化成一个 ziplist 了。

可见,一个 quicklist 节点上的 ziplist 要保持一个合理的长度。那到底多长合理呢?这可能取决于具体应用场景。实际上,Redis 提供了一个配置参数 list-max-ziplist-size,就是为了让使用者可以来根据自己的情况进行调整。

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 的设计目标是能够用来存储很长的数据列表的。比如,Redis 官网给出的这个教程:
Writing a simple Twitter clone with PHP and Redis,就是使用 list 来存储类似 Twitter 的 timeline 数据。

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

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 的数据结构定义

quicklist 相关的数据结构定义可以在 quicklist.h 中找到:

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 的实现里也没用上。

quicklistLZF 结构表示一个被压缩过的 ziplist。其中:

sz: 表示压缩后的 ziplist 大小。

compressed: 是个柔性数组(
flexible array member),存放压缩后的 ziplist 字节数组。

真正表示 quicklist 的数据结构是同名的 quicklist 这个 struct:

head: 指向头节点(左侧第一个节点)的指针。

tail: 指向尾节点(右侧第一个节点)的指针。

count: 所有 ziplist 数据项的个数总和。

len: quicklist 节点的个数。

fill: 16bit,ziplist 大小设置,存放 list-max-ziplist-size 参数的值。

compress: 16bit,节点压缩深度设置,存放 list-compress-depth 参数的值。

上图是一个 quicklist 的结构图举例。图中例子对应的 ziplist 大小配置和节点压缩深度配置,如下:

list-max-ziplist-size 3
list-compress-depth 2

这个例子中我们需要注意的几点是:

两端各有 2 个橙黄色的节点,是没有被压缩的。它们的数据指针 zl 指向真正的 ziplist。中间的其它节点是被压缩过的,它们的数据指针 zl 指向被压缩后的 ziplist 结构,即一个 quicklistLZF 结构。

左侧头节点上的 ziplist 里有 2 项数据,右侧尾节点上的 ziplist 里有 1 项数据,中间其它节点上的 ziplist 里都有 3 项数据(包括压缩的节点内部)。这表示在表的两端执行过多次 push 和 pop 操作后的一个状态。

现在我们来大概计算一下 quicklistNode 结构中的 count 字段这 16bit 是否够用。

我们已经知道,ziplist 大小受到 list-max-ziplist-size 参数的限制。按照正值和负值有两种情况:

当这个参数取正值的时候,就是恰好表示一个 quicklistNode 结构中 zl 所指向的 ziplist 所包含的数据项的最大值。list-max-ziplist-size 参数是由 quicklist 结构的 fill 字段来存储的,而 fill 字段是 16bit,所以它所能表达的值能够用 16bit 来表示。

当这个参数取负值的时候,能够表示的 ziplist 最大长度是 64 Kb。而 ziplist 中每一个数据项,最少需要 2 个字节来表示:1 个字节的 prevrawlen,1 个字节的 data(len 字段和 data 合二为一;详见
上一篇)。所以,ziplist 中数据项的个数不会超过 32 K,用 16bit 来表达足够了。

实际上,在目前的 quicklist 的实现中,ziplist 的大小还会受到另外的限制,根本不会达到这里所分析的最大值。

下面进入代码分析阶段。

quicklist 的创建

当我们使用 lpush 或 rpush 命令第一次向一个不存在的 list 里面插入数据的时候,Redis 会首先调用 quicklistCreate 接口创建一个空的 quicklist。

quicklist *quicklistCreate(void) {
 struct quicklist *quicklist;
 quicklist = zmalloc(sizeof(*quicklist));
 quicklist- head = quicklist- tail = NULL;
 quicklist- len = 0;
 quicklist- count = 0;
 quicklist- compress = 0;
 quicklist- fill = -2;
 return quicklist;
}

在很多介绍数据结构的书上,实现双向链表的时候经常会多增加一个空余的头节点,主要是为了插入和删除操作的方便。从上面 quicklistCreate 的代码可以看出,quicklist 是一个不包含空余头节点的双向链表(head 和 tail 都初始化为 NULL)。

quicklist 的 push 操作

quicklist 的 push 操作是调用 quicklistPush 来实现的。

void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
 int where) { if (where == QUICKLIST_HEAD) { quicklistPushHead(quicklist, value, sz);
 } else if (where == QUICKLIST_TAIL) { quicklistPushTail(quicklist, value, sz);
 }
/* Add new entry to head node of quicklist.
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
 quicklistNode *orig_head = quicklist- head;
 if (likely( _quicklistNodeAllowInsert(quicklist- head, quicklist- fill, sz))) {
 quicklist- head- zl =
 ziplistPush(quicklist- head- zl, value, sz, ZIPLIST_HEAD);
 quicklistNodeUpdateSz(quicklist- head);
 } else { quicklistNode *node = quicklistCreateNode();
 node- zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
 quicklistNodeUpdateSz(node);
 _quicklistInsertNodeBefore(quicklist, quicklist- head, node);
 }
 quicklist- count++;
 quicklist- head- count++;
 return (orig_head != quicklist- head);
/* Add new entry to tail node of quicklist.
 *
 * Returns 0 if used existing tail.
 * Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
 quicklistNode *orig_tail = quicklist- tail;
 if (likely( _quicklistNodeAllowInsert(quicklist- tail, quicklist- fill, sz))) {
 quicklist- tail- zl =
 ziplistPush(quicklist- tail- zl, value, sz, ZIPLIST_TAIL);
 quicklistNodeUpdateSz(quicklist- tail);
 } else { quicklistNode *node = quicklistCreateNode();
 node- zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
 quicklistNodeUpdateSz(node);
 _quicklistInsertNodeAfter(quicklist, quicklist- tail, node);
 }
 quicklist- count++;
 quicklist- tail- count++;
 return (orig_tail != quicklist- tail);
}

不管是在头部还是尾部插入数据,都包含两种情况:

如果头节点(或尾节点)上 ziplist 大小没有超过限制(即_quicklistNodeAllowInsert 返回 1),那么新数据被直接插入到 ziplist 中(调用 ziplistPush)。

如果头节点(或尾节点)上 ziplist 太大了,那么新创建一个 quicklistNode 节点(对应地也会新创建一个 ziplist),然后把这个新创建的节点插入到 quicklist 双向链表中(调用_quicklistInsertNodeAfter)。

在_quicklistInsertNodeAfter 的实现中,还会根据 list-compress-depth 的配置将里面的节点进行压缩。它的实现比较繁琐,我们这里就不展开讨论了。

quicklist 的其它操作

quicklist 的操作较多,且实现细节都比较繁杂,这里就不一一分析源码了,我们简单介绍一些比较重要的操作。

quicklist 的 pop 操作是调用 quicklistPopCustom 来实现的。quicklistPopCustom 的实现过程基本上跟 quicklistPush 相反,先从头部或尾部节点的 ziplist 中把对应的数据项删除,如果在删除后 ziplist 为空了,那么对应的头部或尾部节点也要删除。删除后还可能涉及到里面节点的解压缩问题。

quicklist 不仅实现了从头部或尾部插入,也实现了从任意指定的位置插入。quicklistInsertAfter 和 quicklistInsertBefore 就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作,情况比较复杂,有众多的逻辑分支。

当插入位置所在的 ziplist 大小没有超过限制时,直接插入到 ziplist 中就好了;

当插入位置所在的 ziplist 大小超过了限制,但插入的位置位于 ziplist 两端,并且相邻的 quicklist 链表节点的 ziplist 大小没有超过限制,那么就转而插入到相邻的那个 quicklist 链表节点的 ziplist 中;

当插入位置所在的 ziplist 大小超过了限制,但插入的位置位于 ziplist 两端,并且相邻的 quicklist 链表节点的 ziplist 大小也超过限制,这时需要新创建一个 quicklist 链表节点插入。

对于插入位置所在的 ziplist 大小超过了限制的其它情况(主要对应于在 ziplist 中间插入数据的情况),则需要把当前 ziplist 分裂为两个节点,然后再其中一个节点上插入数据。

quicklistSetOptions 用于设置 ziplist 大小配置参数(list-max-ziplist-size)和节点压缩深度配置参数(list-compress-depth)。代码比较简单,就是将相应的值分别设置给 quicklist 结构的 fill 字段和 compress 字段。

看完上述内容,你们掌握 Redis 中内部数据结构 quicklist 的作用是什么的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注丸趣 TV 行业资讯频道,感谢各位的阅读!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-08-03发表,共计9051字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)