51工具盒子Redis数据结构-ZipList与ListPack {#redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-ziplist%E4%B8%8Elistpack}
在《Reids数据结构》这篇文章中，说到了在Redis6中
List、Sorted Set以及Hash底层都使用了ziplist这一数据结构，并在Redis7后新增了一个数据结构listpack替换了ziplist，这里再简单说下ziplist和listpack。
Redis在什么时候使用ziplist或者listpack {#redis%E5%9C%A8%E4%BB%80%E4%B9%88%E6%97%B6%E5%80%99%E4%BD%BF%E7%94%A8ziplist%E6%88%96%E8%80%85listpack}
这里我们使用Hash这个数据类型来举例，首先在Redis6的配置文件中，我们可以看到两个配置项分别是：
# 当哈希表的条目数量较少且最大条目不超过一个给定的阈值时，
# 哈希表会使用一种内存高效的数据结构进行编码。可以使用以下指令配置这些阈值。
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
hash-max-ziplist-entries：使用ziplist保存时哈希集合中的最大元素个数。hash-max-ziplist-value：使用ziplist保存时哈希集合中单个元素的最大长度。
简单说这两个配置就是表示Hash类型键的字段个数小于hash-max-ziplist-entries并且每个字段名和字段值的长度小于hash-max-ziplist-value时，Redis才会使用OBJ_ENCODING_ZIPLIST来存储，上面的两个条件任意一项不满足都会转变为使用OBJ_ENCODING_HT。
下面我们在Redis6中测试一下：
-
首先可以看到
hash-max-ziplist-entries和hash-max-ziplist-value默认值分别是512和64，这里为了方便测试，我们把这两个配置改小，改成2和4，分别表示这个哈希集合中最大元素是2，单个元素的最大长度是4。127.0.0.1:6379> CONFIG GET hash-max-ziplist-entries 1) "hash-max-ziplist-entries" 2) "512" 127.0.0.1:6379> CONFIG GET hash-max-ziplist-value 1) "hash-max-ziplist-value" 2) "64" 127.0.0.1:6379> CONFIG SET hash-max-ziplist-entries 2 OK 127.0.0.1:6379> CONFIG SET hash-max-ziplist-value 4 OK -
然后来验证
hash-max-ziplist-entries（最大元素个数），这里创建一个key名为user，它有两个字段name和age，查看编码仍然还是ziplist。但是当我们再多加一个字段gender后，编码变成了hashtable。127.0.0.1:6379> HSET user name jack age 18 (integer) 2 127.0.0.1:6379> OBJECT ENCODING user "ziplist" 127.0.0.1:6379> HSET user name jack age 18 gender male (integer) 1 127.0.0.1:6379> OBJECT ENCODING user "hashtable" -
同理来验证
hash-max-ziplist-value（单个元素最大长度），这里创建一个key名为student，它有一个字段name，值为jack长度为4，最后查看编码是ziplist。但是修改值为jackson后，长度变成了7，再次查看编码已经变成了hashtable。127.0.0.1:6379> HSET student name jack (integer) 0 127.0.0.1:6379> OBJECT ENCODING student "ziplist" 127.0.0.1:6379> HSET student name jackson (integer) 0 127.0.0.1:6379> OBJECT ENCODING student "hashtable"
注意：一旦
ziplist转换成了hashtable，Hash类型编码就会一直使用hashtable了，不会再次转换回来。
同理在Redis7中也有类似的配置项，只是换成了listpack：
# 当哈希表的条目数量较少且最大条目不超过给定的阈值时，
# 它们会使用一种内存高效的数据结构进行编码。可以使用以下指令配置这些阈值。
hash-max-listpack-entries 512
hash-max-listpack-value 64
ziplist {#ziplist}
上面说到Redis6 的Hash 类型在底层是用的
ziplist这个数据结构，那这个ziplist是什么呢？
在源码ziplist.c的头部有着这么一段注释：
/* ziplist是一个经过特殊编码的双向链表，旨在提高内存效率。
* 存储字符串和整数值，其中整数被编码为实际整数而不是一系列字符。
* 允许在O(1)时间内在列表的任一侧进行push和pop操作。
* 但是由于每个操作都需要重新分配ziplist使用的内存，因此实际复杂性与ziplist使用的内存量有关。*/
也就是说不同的数据类型在ziplist里由不同的编码方式（可以理解为压缩数据）。但是随着数据量的增加，查询时间复杂度也在增加，因为只有对头尾节点的操作是O(1)复杂度，其他节点都是O(N)。
结构设计 {#%E7%BB%93%E6%9E%84%E8%AE%BE%E8%AE%A1}
通常说到链表，不管是单向或者双向链表，在节点中都是由前/后节点指针的，但是
ziplist中的节点并没由指针，这是为什么呢？
这主要是因为ziplist是Redis 为了节约内存而开发的，它一个是由连续内存块组成的顺序型数据结构，也就是说它是存储在连续的内存上的。ziplist的整体结构如下：
4 bytes 4 bytes 2 bytes 1 byte
# +---------+---------+---------+---------+---------+---------+---------+
# | zlbytes | zltail | zllen | entry | ...... | entry | zlend |
# +---------+---------+---------+---------+---------+---------+---------+
zlbytes：是一个uint_32_t（32位无符号整型），用来记录整个ziplist占用的内存字节数，计算zlend的位置或者对ziplist内存重新分配时会用到。有个好处就是和之前说到的SDS 里面保存一个len来记录字符串长度类似，即获取大小的时候不需要再次遍历计算了，直接获取zlbytes就行了。zltail：是一个uint_32_t（32位无符号整型），用来记录ziplist尾节点距离ziplist起始位置有多少字节，通过这个偏移量，就可以不用遍历整个ziplist也可以找到尾节点的位置。zllen：是一个uint_16_t（16位无符号整型），记录了ziplist中entry的数量，uint_16_t最大是2^16^，但是Redis是这么做的，当entry数量超过最大值后，zllen会被固定成2^16^-1，之后如果要获取entry数量那就需要遍历一遍了。entry：ziplist的每一个节点，真正用来存储数据的结构，长度由保存的内容来决定。zlend：是一个uint_8_t（8位无符号整型），固定为0xFF（十进制表示255），用来标记压缩列表的末端。
entry的结构 {#entry%E7%9A%84%E7%BB%93%E6%9E%84}
在源码ziplist.c第37行中有这么一段注释：
/* ZIPLIST ENTRIES
* ===============
*
* 每个entry节点都包含一些元数据，这些元数据包含两个信息：
* 1. 存储了前一个节点的长度，以便能够从后向前遍历列表。
* 2. 提供了entry节点的编码方式。可以用来表示节点类型（整数或者字符串），如果是字符串，还可以表示字符串的有效长度。
* 所以一个完整的`entry`节点的结构如下：
*
* +-----------+-----------+-----------+
* | prevlen | encoding | entrydata |
* +-----------+-----------+-----------+
*
* 有时候，编码方式encoding代表了entry节点本身（比如对于比较小的整数），在这种情况下，entrydata部分是不存在的：
*
* +-----------+-----------+
* | prevlen | encoding |
* +-----------+-----------+
*
*/
所以entry结构分两种情况：
-
第一种情况：
prevlen：记录前一个节点的长度。encoding：记录当前节点实际数据的类型和长度。entrydata：记录当前节点实际的数据。
-
第二种情况：
-
prevlen：记录前一个节点的长度。 -
encoding：在entry节点中存储的是比较小的int类型时，encoding和entrydata会合并在encoding中表示，此时没有entrydata字段。
-
prelen {#prelen}
prelen的编码分为两种情况：
- 当前一个
entry节点长度小于254的时候，prelen的长度为1个字节，值就是前一个entry节点的长度。 - 当前一个
entry节点长度大于等于254的时候，prelen用5个字节来表示，其中第一个字节固定为254（FE）作为标识，剩余的四个字节则用来表示前一个entry的实际大小。
所以prelen的编码可以是：
/*
* <prevlen from 0 to 253> <encoding> <entry>
*/
或者前一个节点长度大于等于254的时候：
/*
* 0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>
*/
encoding {#encoding}
encoding的编码取决于保存的内容，前两位表示类型，比如前面两位都是1，即11，则表示整数，除此之外的其他都表示字符串。
- 当保存的是字符串的时候，有3种编码方式：
|00pppppp|：此时长度是1字节，后6位用来存储字符串长度。所以长度不能超过63。|01pppppp|qqqqqqqq|：此时长度是2字节，后14位用来存储字符串长度，长度不能超过16383。|10000000|qqqqqqqq|rrrrrrrr|ssssssss|ttttttt|：此时长度是5字节，后面的32位用来存储字符串长度，长度不能超过2^32^ - 1。
- 当保存的是整数的时候，有6种编码方式：
|11000000|：3个字节，后2个字节表示一个int16_t。|11010000|：5个字节，后4个字节表示一个int32_t。|11100000|：9个字节，后8个字节表示一个int64_t。|11110000|：4个字节，后3个字节表示一个24 bit带符号。|11111110|：2个字节，后1个字节表示一个8 bit带符号。|1111xxxx|：1个字节，[0,12]的无符号整数，编码后的值实际上是1到13，因为0000和1111不能用，所以要从编码后的4位值中减去1才能得到正确的值。
|11111111|则表示zlend，用来表示ziplist的结尾。
zlentry源码 {#zlentry%E6%BA%90%E7%A0%81}
在源码ziplist.c第284行可以看到zlentry的结构如下：
/* 我们使用这个函数来接收关于 ziplist 条目的信息。
* 注意这不是数据实际上的编码方式，只是我们得到的填充信息，以便更轻松地操作。*/
typedef struct zlentry {
unsigned int prevrawlensize; /* 编码前一个节点的长度需要的字节 */
unsigned int prevrawlen; /* 前一个节点占用的长度 */
unsigned int lensize; /* 用于编码此节点类型/长度的字节数。 例如，字符串使用 1、2 或 5 个字节的头。整数总是使用单个字节。*/
unsigned int len; /* 表示实际条目所需的字节数。对于字符串，这只是字符串长度，而对于整数，它取决于数字范围，可能是 1、2、3、4、8 或 0（对于 4 位即时整数） */
unsigned int headersize; /* 当前节点的头部大小（prevrawlensize + lensize）即非数据域的大小。 */
unsigned char encoding; /* 根据条目编码设置为 ZIP_STR_* 或 ZIP_INT_*。但是对于 4 位即时整数，它可以假定一个范围的值，并且必须进行范围检查。 */
unsigned char *p; /* 指向条目的起始点，即指向前一个条目长度字段。 */
} zlentry;
连锁更新 {#%E8%BF%9E%E9%94%81%E6%9B%B4%E6%96%B0}
连锁更新是什么呢？首先连锁更新是
ziplist一个比较大的缺点，Redis7.0将ziplist更新位listpack的重要原因就是这个。
上面我们说到了ziplist的每个操作（新增或者修改）都需要重新分配ziplist的内存空间。试想一下每当我们新增一个节点，都可能导致prevlen发生变化，从而引起连锁更新问题，导致每个元素的空间都需要重新分配，这会造成性能下降的问题。
这里假如我们有一个ziplist，现在有A 、B 、C 、D 四个节点，这四个的长度都刚好是253字节，按照前面我们说的prelen的编码情况，它们的prelen肯定都是1字节。然后我们要新增一个长度大于等于254字节的节点E （加到A前面），那么节点A 的prelen则需要变为5个字节，而由于A 的长度已经是253字节了，加上这个变化后的prelen，长度已经超过254，所以后面的节点B也需要跟着变化，依次类推。这便是连锁更新问题，这里举例只用了4个节点，实际应用中如果节点数量很多，那么则会造成很多性能消耗。
# +-----+
# +-----+ | E | 254 bytes
# | A | 253 bytes +-----+
# +-----+ | A | 原本刚好253字节，但是前一个节点的长度超过254，prelen变成5个字节，加上本身的253字节，自己也超过了254字节
# | B | 253 bytes +-----+
# +-----+==============>| B | 同理节点A超过了254字节，B的prelen也变成5字节，自身长度也超过254字节
# | C | 253 bytes +-----+
# +-----+ | C | 同理节点B超过了254字节，C的prelen也变成5字节，自身长度也超过254字节
# | D | 253 bytes +-----+
# +-----+ | D | 同理节点C超过了254字节，D的prelen也变成5字节，自身长度也超过254字节
# +-----+
相关问题 {#%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98}
为什么ziplist特别节省内存 {#%E4%B8%BA%E4%BB%80%E4%B9%88ziplist%E7%89%B9%E5%88%AB%E8%8A%82%E7%9C%81%E5%86%85%E5%AD%98}
首先说ziplist节省内存是对于普通的List数组，数组的每个元素占用内存都是一样的而且是取决于最大的那个元素。所以ziplist增加了encoding字段，用来针对不同的encoding来细化存储大小。最后ziplist使用prelen这个字段记录上一个节点的长度，解决了遍历的问题。
为什么ziplist要这样重新设计 {#%E4%B8%BA%E4%BB%80%E4%B9%88ziplist%E8%A6%81%E8%BF%99%E6%A0%B7%E9%87%8D%E6%96%B0%E8%AE%BE%E8%AE%A1}
-
首先是普通的单向链表或者双向链表的节点都会有一个或两个指针用来指向前后节点，在存储数据特别小的时候，可能数据本身还没有指针占用的空间大。然而从上面我们得知
ziplist并没有维护指针，而是保存了前一个节点的长度和当前节点的长度，虽然牺牲了读取性能但是获得了更多的存储空间，也就是常说的时间换空间。 -
链表在内存中一般不是连续的内存空间，遍历相对来说比较慢。一般数组遍历是根据数组里面存储的数据类型来找到下一个元素的（比如
int类型的数组访问下一个元素每次只需要移动一个sizeof(int)就可以），而ziplist的每个节点的长度是可以不一样的，对于不同长度的节点又不可能直接sizeof(entry)，所以ziplist将一些必要的偏移量信息记录在了每一个节点里面。sizeof()实际上就是获取数据在内存中所占用的空间，单位是字节。 -
ziplist还有zlbytes以及zllen，前面也说到了分别用来记录ziplist的大小以及节点数量，那么有个好处就是（和SDS里面保存一个len来记录字符串长度类似）：获取ziplist大小以及节点数量的时候不需要再次遍历计算了。注意：节点数量超过
uint_16_max（2^16^）个后还是需要重新遍历。
listpack {#listpack}
前面说到
ziplist，但是ziplist有个致命的缺点就是新增和修改元素可能导致连锁更新，这也是Redis7.0新增listpack替换ziplist的原因。那么listpack是什么呢？
Redis作者在github上是这样介绍的：
一个listpack被编码成一个单一线性块的内存。它有一个固定长度的6个字节的头部（与ziplist的10个字节不同，因为我们不再需要一个指向最后一个元素开头的指针）。头部后面直接就是 listpack的元素。理论上，这个数据结构不需要任何终止符，但是出于某些考虑，提供了一个特殊的条目，用于标记listpack的结尾，形式为单个字节，其值为FF（255）。终止符的主要优点是能够在不持有（并在每次迭代时比较）listpack结尾地址的情况下扫描listpack，并且容易识别listpack是否格式正确或缩短。
结构设计 {#%E7%BB%93%E6%9E%84%E8%AE%BE%E8%AE%A1-1}
listpack结构如下：
4 bytes 2 bytes 1 byte
# +--------------+--------------+--------------+--------------+--------------+-----------------+
# | totbytes | num-elements | entry | ...... | entry |listpack-end-byte|
# +--------------+--------------+--------------+--------------+--------------+-----------------+
tot-bytes：是一个uint_32_t（32位无符号整型），表示listpack的总字节数（包括头部本身和终止符），也就是说listpack最多占用4294967295bytes。这基本上是保存listpack所需的总分配大小，当需要时，允许跳到结尾以从最后一个元素向前扫描listpack。num-elements：是一个uint_16_t（16位无符号整型），表示listpack包含的元素总数。 和ziplist的zllen同理，最多记录uint_16_max（2^16^）个元素，超过则固定为2^16^-1，此时要获取数量则需要遍历listpack。
entry的结构 {#entry%E7%9A%84%E7%BB%93%E6%9E%84-1}
Redis作者在github上是这样介绍的：
listpack中的每个元素都具有以下结构：
+----------+----------+----------+
| encoding | element | element |
| type | data | tot-len |
+----------+----------+----------+
| |
+--------------------------------+
(This is an element)
元素的类型（encoding-type）和元素的总长度（element-tot-len）始终存在。
encoding-type：当前元素的编码类型，会对不同长度的整数和字符串进行编码。element-data：实际存储的元素数据。element-tot-len：元素的总长度（encoding-type+element-data的总长度），代表当前节点的回朔起始地址长度的偏移量。
在源码listpack.h第49行是这样定义的：
/* listpack中的每一个节点，不是String就是int. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
uint32_t slen;
/* 当使用integer时，"sval"为 NULL，lval 保存该值。*/
long long lval;
} listpackEntry;
对比ziplist，listpack中的每个节点记录的是当前节点的长度，而不是前一个节点的长度。
ziplist和listpack的区别 {#ziplist%E5%92%8Clistpack%E7%9A%84%E5%8C%BA%E5%88%AB}
listpack相对于ziplist，它的每个节点中不在包含前一个节点的长度，从而避免的连锁更新的问题。listpack相对于ziplist，没有了zltail（尾节点距离ziplist起始位置有多少字节），解决ziplist内存长度限制的问题。但一个listpack最大内存使用不能超过1GB。
