深入分析redis之quicklist，不一样的ziplist使用方式？

前言

续接上文：redis压缩列表ziplist，内存优化之路

本文参考源码版本仍为Redis6.2。

quicklist是Redis底层最重要的数据结构之一，它是Redis对外提供的6种基本数据结构中List的底层实现，在Redis 3.2版本中引入。

在引入quicklist之前，Redis采用压缩链表（ziplist）以及双向链表（linked-list）作为List的底层实现。

当元素个数比较少并且元素长度比较小时，Redis采用ziplist作为其底层存储。

当任意一个条件不满足时，Redis采用linked-list作为底层存储结构。

这么做的主要原因是，当元素长度较小时，采用ziplist可以有效节省存储空间，但ziplist的存储空间是连续的，当元素个数比较多时，修改元素时，必须重新分配存储空间，这无疑会影响Redis的执行效率，故而采用一般的双向链表。

quicklist是综合考虑了时间效率与空间效率引入的新型数据结构。

一、quicklist真面目

Redis源码中对quicklist的注释为 A doubly linked list of ziplists；也就是说quicklist是由ziplist组成的双向链表，其中每一个链表节点都是一个独立的ziplist结构，因此，从结构上看，quicklist就是ziplist的升级版。

优化的关键在于，如何控制好每个ziplist的大小

quicklist的节点ziplist越小，越有可能造成更多的内存碎片。极端情况下，一个ziplist只有一个数据entry，也就退化成了linked list

quicklist的节点ziplist越大，分配给ziplist的连续内存空间越困难。极端情况下，一个quicklist只有一个ziplist，也就退化成了ziplist

因此，合理配置参数显得至关重要，不同场景可能需要不同配置；redis提供list-max-ziplist-size参数进行配置，默认-2，表示每个ziplist节点大小不超过8KB

二、原理分析数据存储1. quicklistNode结构：typedef?struct?quicklistNode?{????struct?quicklistNode?*prev;??//前一个quicklistNode????struct?quicklistNode?*next;??//后一个quicklistNode????unsigned?char?*zl;???????????//quicklistNode指向的ziplist????unsigned?int?sz;?????????????//ziplist的字节大小????unsigned?int?count?:?16;?????//ziplist中的元素个数????unsigned?int?encoding?:?2;???//编码格式，原生字节数组或压缩存储????unsigned?int?container?:?2;??//存储方式????unsigned?int?recompress?:?1;?//数据是否被压缩????unsigned?int?attempted_compress?:?1;?//数据能否被压缩????unsigned?int?extra?:?10;?????//预留的bit位}?quicklistNode;

其中

prev、next指向该节点的前后节点；

zl指向该节点对应的ziplist结构；

sz代表整个ziplist结构的大小；

encoding代表采用的编码方式：1代表是原生的，2代表使用LZF进行压缩；

container为quicklistNode节点zl指向的容器类型：1代表none,2代表使用ziplist存储数据

recompress代表这个节点之前是否是压缩节点，若是，则在使用压缩节点前先进行解压缩，使用后需要重新压缩，此外为1，代表是压缩节点；

attempted_compress测试时使用；

extra为预留

2. quicklist结构

quicklist 作为一个链表结构，在它的数据结构中，是定义了整个 quicklist 的头、尾指针，这样一来，可以通过 quicklist 的数据结构，来快速定位到 quicklist 的链表头和链表尾。

typedef?struct?quicklist?{????quicklistNode?*head;???//?quicklist的链表头????quicklistNode?*tail;???//?quicklist的链表尾????unsigned?long?count;???//?所有ziplist中的总元素个数????unsigned?long?len;?????//?quicklistNodes的个数????int?fill?:?QL_FILL_BITS;??//?单独解释????unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩????...}?quicklist;

fill用来指明每个quicklistNode中ziplist长度，当fill为正数时，表明每个ziplist最多含有的数据项数，当fill为负数时，如下：

Length -1: 4k，即ziplist节点最大为4KB

Length -2: 8k，即ziplist节点最大为8KB

Length -3: 16k ...

Length -4: 32k

Length -5: 64k

fill取负数时，必须大于等于-5。可以通过Redis修改参数list-max-ziplist-size配置节点所占内存大小。实际上每个ziplist节点所占的内存会在该值上下浮动。

考虑quicklistNode节点个数较多时，我们经常访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩，通过修改参数list-compress-depth进行配置，即设置compress参数，该项的具体含义是两端各有compress个节点不压缩。

quicklist整体结构：

3. quicklistEntry结构

quicklistNode中ziplist中的一个节点

typedef?struct?quicklistEntry?{????const?quicklist?*quicklist;????quicklistNode?*node;????unsigned?char?*zi;????unsigned?char?*value;????long?long?longval;????unsigned?int?sz;????int?offset;}?quicklistEntry;

其中：

quicklist指向当前元素所在的quicklist;

node指向当前元素所在的quicklistNode结构；

zi指向当前元素所在的ziplist;

value指向该节点的字符串内容；

longval为该节点的整型值；

sz代表该节点的大小，与value配合使用；

offset表明该节点相对于整个ziplist的偏移量，即该节点是ziplist第多少个entry

4. quicklistIter结构

quicklist中用于遍历的迭代器：

typedef?struct?quicklistIter?{????const?quicklist?*quicklist;????quicklistNode?*current;????unsigned?char?*zi;????long?offset;?/*?offset?in?current?ziplist?*/????int?direction;}?quicklistIter;

quicklist指向当前元素所处的quicklist;

current指向元素所在quicklistNode;

zi指向元素所在的ziplist;

offset表明节点在所在的ziplist中的偏移量；

direction表明迭代器的方向。

数据压缩

quicklist每个节点的实际数据存储结构为ziplist，这种结构的主要优势在于节省存储空间。

为了进一步降低ziplist所占用的空间，Redis允许对ziplist进一步压缩，Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段，每个片段有2部分：

一部分是解释字段，另一部分是存放具体的数据字段。

解释字段可以占用1～3个字节，数据字段可能不存在。

解释字段|数据|......|解释字段|数据

LZF压缩的数据格式有3种，即解释字段有3种：

000LLLLL：字面型，解释字段占用1个字节，数据字段长度由解释字段后5位决定；L是数据长度字段，数据长度是长度字段组成的字面值加1。例如：0000 0001代表数据长度为2

LLLooooo oooooooo：简短重复型，解释字段占用2个字节，没有数据字段，数据内容与前面数据内容重复，重复长度小于8；L是长度字段，数据长度为长度字段的字面值加2, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：0010 0000 0000 0100代表与前面5字节处内容重复，重复3字节。

111ooooo LLLLLLLL oooooooo：批量重复型，解释字段占3个字节，没有数据字段，数据内容与前面内容重复；L是长度字段，数据长度为长度字段的字面值加9, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：1110 0000 0000 0010 0001 0000代表与前面17字节处内容重复，重复11个字节。

quicklistLZF结构：

/*?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;

zs 该压缩node的的总长度

compressed压缩后的数据片段(多个)，每个数据片段由解释字段和数据字段组成

当前ziplist未压缩长度存在于quicklistNode->sz字段中

当ziplist被压缩时，node->zl字段将指向quicklistLZF

1. 压缩

LZF数据压缩的基本思想是：数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容。

压缩算法的流程如下：遍历输入字符串，对当前字符及其后面2个字符进行散列运算，如果在Hash表中找到曾经出现的记录，则计算重复字节的长度以及位置，反之直接输出数据。

/*?*?compressed?format?*?*?000LLLLL?<L+1>????;?literal,?L+1=1..33?octets?*?LLLooooo?oooooooo?;?backref?L+1=1..7?octets,?o+1=1..4096?offset?*?111ooooo?LLLLLLLL?oooooooo?;?backref?L+8?octets,?o+1=1..4096?offset?*/unsigned?intlzf_compress?(const?void?*const?in_data,?unsigned?int?in_len,?void?*out_data,?unsigned?int?out_len)

2. 解压缩

根据LZF压缩后的数据格式，可以较为容易地实现LZF的解压缩。需要注意的是，可能存在重复数据与当前位置重叠的情况，例如在当前位置前的15个字节处，重复了20个字节，此时需要按位逐个复制。

unsigned?intlzf_decompress?(const?void?*const?in_data,?unsigned?int?in_len,?void?*out_data,?unsigned?int?out_len)

基本操作1. 插入元素

API定义：

/*?Insert?a?new?entry?before?or?after?existing?entry?'entry'.?*?*?If?after==1,?the?new?value?is?inserted?after?'entry',?otherwise?*?the?new?value?is?inserted?before?'entry'.?*/REDIS_STATIC?void?_quicklistInsert(quicklist?*quicklist,?quicklistEntry?*entry,?void?*value,?const?size_t?sz,?int?after)

其中，参数after用于控制在entry之前或者之后插入。

正因为 quicklist 采用了链表结构，所以当插入一个新的元素时，quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素，这是通过 _quicklistNodeAllowInsert 函数来完成判断的。

REDIS_STATIC?int?_quicklistNodeAllowInsert(const?quicklistNode?*node,???????????????????????????????????????????const?int?fill,?const?size_t?sz)?{????if?(unlikely(!node))????????return?0;????int?ziplist_overhead;????/*?size?of?previous?offset?*/????if?(sz?<?254)????????ziplist_overhead?=?1;????else????????ziplist_overhead?=?5;????/*?size?of?forward?offset?*/????if?(sz?<?64)????????ziplist_overhead?+=?1;????else?if?(likely(sz?<?16384))????????ziplist_overhead?+=?2;????else????????ziplist_overhead?+=?5;????/*?new_sz?overestimates?if?'sz'?encodes?to?an?integer?type?*/????unsigned?int?new_sz?=?node->sz?+?sz?+?ziplist_overhead;????if?(likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz,?fill)))????????return?1;????else?if?(!sizeMeetsSafetyLimit(new_sz))????????return?0;????else?if?((int)node->count?<?fill)????????return?1;????else????????return?0;}

_quicklistNodeAllowInsert 函数会计算新插入元素后的大小（new_sz），这个大小等于 quicklistNode 的当前大小（node->sz）、插入元素的大小（sz），以及插入元素后 ziplist 的 prevlen 占用大小。

在计算完大小之后，_quicklistNodeAllowInsert 函数会依次判断新插入的数据大小（sz）是否满足要求，即单个 ziplist 是否不超过 8KB，或是单个 ziplist 里的元素个数是否满足要求。

只要这里面的一个条件能满足，quicklist 就可以在当前的 quicklistNode 中插入新元素，否则 quicklist 就会新建一个 quicklistNode，以此来保存新插入的元素。

这样一来，quicklist 通过控制每个 quicklistNode 中，ziplist 的大小或是元素个数，就有效减少了在 ziplist 中新增或修改元素后，发生连锁更新的情况，从而提供了更好的访问性能。

2. 删除元素

quicklist对于元素删除提供了删除单一元素以及删除区间元素2种方案。

1）对于删除单一元素，可以使用quicklist对外的接口quicklistDelEntry实现，也可以通过quicklistPop将头部或者尾部元素弹出。

quicklistDelEntry函数调用底层quicklistDelIndex函数，该函数可以删除quicklistNode指向的ziplist中的某个元素，其中p指向ziplist中某个entry的起始位置。

quicklistPop可以弹出头部或者尾部元素，具体实现是通过ziplist的接口获取元素值，再通过上述的quicklistDelIndex将数据删除

2）对于删除区间元素，quicklist提供了quicklistDelRange接口，该函数可以从指定位置删除指定数量的元素

start为需要删除的元素的起始位置，count为需要删除的元素个数。返回0代表没有删除任何元素，返回1并不代表删除了count个元素，因为count可能大于quicklist所有元素个数，故而只能代表操作成功。

总体删除逻辑为：不管什么方式删除，最终都会通过ziplist来执行元素删除操作。先尝试删除该链表节点所指向的ziplist中的元素，如果ziplist中的元素已经为空了，就将该链表节点也删除掉。

3. 更改元素

quicklist更改元素是基于index，主要的处理函数为quicklistReplaceAtIndex。

其基本思路是先删除原有元素，之后插入新的元素。quicklist不适合直接改变原有元素，主要由于其内部是ziplist结构，ziplist在内存中是连续存储的，当改变其中一个元素时，可能会影响后续元素。故而，quicklist采用先删除后插入的方案。

4. 查找元素

quicklist查找元素主要是针对index，即通过元素在链表中的下标查找对应元素。基本思路是，首先找到index对应的数据所在的quicklistNode节点，之后调用ziplist的接口函数ziplistGet得到index对应的数据，源码中的处理函数为quicklistIndex。

您可能感兴趣问答

Collapsible

热门标签

热点问答