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结构分两种情况：

第一种情况：
1. prevlen：记录前一个节点的长度。
2. encoding：记录当前节点实际数据的类型和长度。
3. entrydata：记录当前节点实际的数据。
第二种情况：
1. prevlen：记录前一个节点的长度。
2. 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字节
#                       +-----+

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。