【redis】ziplist详细解析 redis

本文根据5.0.2版本的redis源码详细解析ziplist数据结构。

1 创建一个ziplist

文章图片

ziplist的内存结构如上图。

一个uint32_t的totalsize，保存当前ziplist所占用内存总量
接着一个uint32_t的offset，指向最后一个元素的位置，ziplist中的元素称作zlentry，起始时，offset指向ZIP_END
之后是uint16_t的len，这个存储的是当前 ziplist中元素的个数
最后是一个字节的ZIP_END，ZIP_END的值是 0xFF(255)，用来标记ziplist的结束
ziplist的头部，共占用10个字节，尾部1个字节的标识符，额外占用了11个字节

2 ziplist中的元素

文章图片

ziplist中的元素称作zlentry，内存结构如上。
首先是前一个元素的长度 prevlen ，接着是当前元素长度 curlen的编码encoding ，之后是当前元素实际数据 value。
zlentry中包含了以下信息：

prevrawlensize：前一个元素的内存大小的编码空间
prevrawlen：前一个元素的内存大小
lensize：当前元素value部分占用内存大小的编码空间
len：当前元素value部分占用内存大小
_encoding：编码类型，标志value的类型和占用的字节数

以上信息，在经过一定的编码后进行存储。prevrawlensize和prevrawlen信息存储在prevlen部分；lensize、len、_encoding信息存储在encoding部分；当value是数值类型，同时小于一定阈值的时候，会同时将value存储在encoding中。value也是按照大端存储。
详细的存储编码过程如下：
前一个元素长度 prevlen，保存的是前一个zlentry所占内存的总大小，prevlen可以占用 1个字节或者 5个字节 :

prevrawlen长度 < 254，此时prevlen使用一个字节，直接存储 prevrawlen长度
prevrawlen长度 >= 254, 此时prevlen使用五个字节，第一个字节存储254作为标记，后面四个字节存储 prevrawlen长度，用大端的方式存储
在ziplist插入元素的过程中，会产生 prevrawlen长度 < 254 但是占用5个字节的情况。这个在后面会有说到。
解码时，判断第一个字节的大小，确定使用的字节数，然后获得对应的长度
255已经被用作了ZIP_END，所以，这里用了254作为标志
疑问：这里改为varint方式编码是否更好？
答：个人认为，varint可以进一步压缩数据。不过，因为varint会使得prevlen编码长度取值范围更大（1到5），会使插入过程造成连锁反应的概率更大。所以，varint会进一步降低ziplist的写效率。在短数据的情况下，现在的编码方式能有效压缩数据；同时，只有两种编码长度的情况下，连锁反应发生的概率也比较低，这算是在数据压缩和写入效率之间得到的一个平衡点吧。

当前元素长度curlen 经过编码之后存储，区分字符串和数值类型，可以占用 1个字节、2个字节或者5个字节。编码过程如下：

value是数值的情况下，根据value值的大小进行编码，此时encoding使用一个字节：
value >= 0 && value <= 12 ：encoding的高四位是 1111（0xF），低四位存储value + 1，此时value长度是0，此时encoding的取值范围是 1111 0001-1111 1101
疑问：这里低四位为什么存储 value + 1，不是直接存储 value？
答：如果直接存储value，那么value=https://www.it610.com/article/0的时候，encoding的值是0xF0（1111 0000）；而后面存储3个字节长度的value时，encoding的编码也是 0xF0（1111 0000），这时候产生了冲突。
那是否可以改变高四位的值，从而避免冲突？
高两位11不可变，这是用来区分数值和字符串的。接着的两位，后续的数值编码分别使用了 11、00、01、10，这样，不管高四位改变成什么值，都可能和后续的某个编码冲突，所以这种方法不行。
疑问：这里value阈值为什么是12？
答：如果value=https://www.it610.com/article/13 (0000 1101) ，那么此时 encoding的值是 0xFE(1111 1110)；和之后存储一个字节长度的value时，encoding冲突。所以value最大是12。
疑问：是否可以修改后续encoding的编码值，从而使得此时的encoding低四位可以直接存储value，并且value阈值不限于12？
答：我感觉可以的说，因为在使用encoding确定数值长度的时候，也是根据encoding的值是否相等进行判断的。
value >= INT8_MIN && value <= INT8_MAX：encoding存储0xFE（1111 1110），表明value长度curlen 是1
value >= INT16_MIN && value <= INT16_MAX：encoding存储0xC0（1100 0000），表明value长度curlen 是2
value >= INT24_MIN && value <= INT24_MAX：encoding存储0xF0（1111 0000），表明value长度curlen 是3
value >= INT32_MIN && value <= INT32_MAX：encoding存储0xD0（1101 0000），表明value长度curlen 是4
value是其他值：encoding存储0xE0（1110 0000），表明value长度curlen 是8
可以看出，value是数值情况下，encoding的高两位都是11，也就是说encoding的值肯定大于0xC0(1100 0000)，这也是和字符串区分的方式。
value是字符串的情况下，根据value长度 curlen 判断，encoding可以占用 1个字节、2个字节或者5个字节
curlen <= 0x3F (63) 的时候， encoding使用一个字节，高两位是 00,低六位存储curlen
curlen<=0x3FFF(16383)的时候，encoding使用两个字节；第一个字节高两位是01，低六位存储curlen的高字节，第二个字节存储curlen的低字节
curlen>0x3FFF的时候， encoding使用五个字节；第一个字节值是(1000 0000)，高两位是10；后面四个字节存储curlen，按照大端方式存储，即先存储curlen的高字节，最后存curlen的低字节
解码时，判断encoding首字节的值和 0xC0(1100 0000)的大小，encoding > 0xC0(1100 0000) 说明value是数值类型，之后按照数值类型的编码方式进行解码；否则是字符串。
数值类型的解码，直接按照encoding的值进行判断
encoding == 0xFE，则curlen =1
encoding == 0xC0，则curlen =2
encoding == 0xF0，则curlen =3
encoding == 0xD0，则curlen =4
encoding == 0xE0，则curlen =8
encoding是其他值，则curlen=0，此时，value的值等于 encoding的低四位 - 1
字符串类型的解码，根据encoding首字节的高两位进行判断
encoding首字节的高两位 == 00，则 encoding占一个字节，curlen= encoding首字节的低六位
encoding首字节的高两位 == 01，则encoding占两个字节， curlen= encoding首字节的低六位 + 第二个字节
encoding首字节的高两位 == 10，则encoding占五个字节， curlen= encoding首字节之后的四个字节大端存储的数据

由上可知，每个原始数据经过ziplist的编码之后，最多额外增加10个字节（5个prevlen + 5个encoding）。

ziplist也叫作压缩列表，看看它的压缩效率如何，可以把下个元素的prevlen看做是当前元素的，以此来分析：
对于数值类型数据：

INT8范围以内的数据会占用2个或3个字节（1个prevlen，1个encoding，0或1个字节的value）
INT16范围以内的数据会占用4个字节（1个prevlen，1个encoding，2个字节的value）
INT24范围以内的数据会占用5个字节（1个prevlen，1个encoding，3个字节的value）
INT32范围以内的数据会占用6个字节（1个prevlen，1个encoding，4个字节的value）
INT64范围以内的数据会占用10个字节（1个prevlen，1个encoding，8个字节的value）

在可以存储64位数值的情况下，只有超出32位大小的数值，才会占用超过8字节。我们的数值大部分都是在24位大小以内的，越小的数值出现的概率越大。所以，这种编码对数值有比较好的压缩。
同时，字符串形式的数字，会被转为数值存储，进一步压缩了空间。
对于字符串类型数据：

curlen <= 0x3F (63) 的时候，占用curlen + 2个字节（1个prevlen，1个encoding，curlen 个字节的value）
0x3F (63) < curlen < 254 - 3的时候，占用curlen + 3个字节（1个prevlen，2个encoding，curlen 个字节的value）
254 - 3 <= curlen <=0x3FFF(16383) - 7的时候，占用curlen + 7个字节（5个prevlen，2个encoding，curlen 个字节的value）
curlen > 0x3FFF(16383)的时候，占用curlen + 10个字节（5个prevlen，5个encoding，curlen 个字节的value）

对于短字符串，ziplist对长度有一定的压缩，但是当字符串较长的时候，会占用较多的额外空间，此时不适合再使用ziplist。

这里有个疑问：是否可以把每个元素zlentry的结构变成这样：

文章图片

其中，encoding和value和之前一样，curvlen表示encoding和value占用的字节数，可以用reverse varint实现。
计算下一个元素的时候，根据encoding和value占用的字节数算出curvlen占用的字节数，然后得到下一个元素地址；
寻找前一个元素的时候，从当前元素地址往前，从高字节到低字节按varint方式进行解码，得到前一个元素占用的字节数，从而得到前一个元素的地址。
这样做的好处是，插入和删除都不会有连锁反应了。

3 插入一个元素
ziplist是使用一块连续内存存储的数据结构。
每当插入一个数据的时候，就会改变当前ziplist内存大小，此时就需要realloc，所以，每次zl的指针在插入时会被改变。同时，插入可能会导致下一个元素中保存的prevlen所占内存大小改变，可能要依次调整之后的所有元素，这样可能造成连锁反应。
插入过程如下：

获取前一个元素的长度，也就是prevlen。对于插入到ziplist末尾的情况，根据offset获取最后一个元素的长度。对于插入到非末尾的情况，从下一个元素的prevlen获取。
确定当前元素的encoding和value的长度curlen，这样就可以得到当前元素所需的空间reqlen 了。reqlen = prevlen的编码长度+ encoding的编码长度 + curlen
确定到下一个元素的prevlen编码长度是否需要调整。因为插入之后，下一个元素的prevlen保存的是当前元素的大小，和原来的prevlen编码长度可能会有不同。这个也是造成连锁反应的原因。这部分的源码如下：
int forcelarge = 0; nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; if (nextdiff == -4 && reqlen < 4) { nextdiff = 0; forcelarge = 1; }
- nextdiff 是当前元素所需空间reqlen的编码长度和下一个元素保存的prevlen编码长度之差。
- 由于prevlen的取值范围只有1，或者5，所以nextdiff 的取值只能是0、-4、4
- nextdiff == 0：说明插入后下个元素的prevlen编码长度不变
- nextdiff == -4：说明下个元素的prevlen编码长度为5，插入后需要缩减4个字节
- nextdiff == 4：说明下个元素的prevlen编码长度为1，插入后需要扩充4个字节
- 疑问：nextdiff == -4 && reqlen < 4 这个判断是做什么呢？
- 答：上面已经分析了nextdiff == -4 。 reqlen < 4 这个条件说明什么呢？因为reqlen = prevlen的编码长度+ encoding的编码长度 + curlen，那么可以推出 prevlen的编码长度 < 4。而当前元素的prevlen是从下个元素的prevlen得到的，从而下个元素的prevlen的编码长度 < 4。但是nextdiff == -4 推导出下个元素的prevlen的编码长度==5，这明显是矛盾的，两种情况不会同时出现才对。那么这个条件是什么用处呢？
- 答：可以先把这个问题放放。先看看这种情况下会起到什么作用。
- 在符合nextdiff == -4 && reqlen < 4 的情况下，将nextdiff = 0 ，这表明下个元素的prevlen不需要缩减了。而后面的操作证实了这一点，forcelarge 标志会导致下一个元素的prevlen强制占用5个字节，即使 prevlen < 254。这有什么好处呢？既然下个元素的prevlen不需要缩减了，那么也就不会导致后续的连锁反应了。所以，这种情况是一种防止连锁反应的特殊操作。
- 疑问：为什么要求 reqlen < 4 ，这个阈值是怎么确定的呢？暂时还不知道，先接着往下看。
为新元素申请空间。因为ziplist使用连续内存，所以此时需要realloc，重新申请的空间大小 size = totalsize + reqlen + nextdiff 。totalsize是当前ziplist的空间
插入点是p，确定插入点到ziplist头的偏移量 offset = p - zl
将下一个元素及之后的数据后移，空出 reqlen个字节，留给当前元素。后移过程如下：
- 从p - nextdiff 处开始，拷贝到 p + reqlen 处，拷贝的数据长度是totalsize - 1 - offset + nextdiff 。
- 更新下个元素的prevlen编码。如果有forcelarge 标志，强制占用5个字节。这里对prevlen的强制操作，会使得占用5个字节的prevlen，实际却是prevlen<254，这就有可能符合之前 nextdiff == -4 && reqlen < 4的条件了。但是，这里的强制操作是由该条件导致的，那么第一个符合该条件的情况是怎么产生的呢？接着往下看。
- 更新 ziplist的 offset值， ziplist的offset总是指向最后一个元素的起始位置。对于这部分源码，也有一些疑问。源码如下：
  /* Update offset for tail */ ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); /* When the tail contains more than one entry, we need to take * "nextdiff" in account as well. Otherwise, a change in the * size of prevlen doesn't have an effect on the *tail* offset. */ zipEntry(p+reqlen, &tail); if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); }
- 疑问：这里为什么不能直接在offset上加入 nextdiff ，还要再判断一下呢？
- 答：下个元素实际后移了reqlen，如果下个元素就是最后一个元素，那么此时offset不需要再加上nextdiff了。
- 后移的具体过程会在之后详细说明，同时也会解答之前的“nextdiff == -4 && reqlen < 4” 这个疑问。
如果下个元素的prevlen编码长度有变化，即(nextdiff != 0)，那么下个元素占用的空间也会变化，从而导致下下个prevlen编码长度变化，这样可能引起了连锁反应。此时需要处理这样的连锁反应，具体处理过程之后单独说。
此时，ziplist的内存已经扩充好，需要后移的数据已经操作完成。在插入点p，到p + reqlen之间的内存之间，按zlentry的编码写入当前元素即可。

4 元素后移的过程说明
元素后移需要考虑三种情况。以下图示没有考虑下个元素是最后一个元素的情况，对于这种情况，会影响ziplist的offset改动，前面已经提到。
1）nextdiff = 4:

此时，p处下一个元素需要扩充 nextdiff 个字节。
做法是，拷贝的时候，多拷贝四个字节的数据，也就是从 p - nextdiff (p - 4)处开始拷贝。
文章图片
如上图所示：这时，多向后移动了4个字节，多出的部分用于扩充下个元素的prevlen编码。

2）nextdiff = -4:

此时， p处下一个元素需要缩容4个字节。
做法是，拷贝的时候，少拷贝四个字节的数据，也就是从 p - nextdiff (p + 4)处开始拷贝。
文章图片
如上图所示：这时，少向后移动了4个字节，下个元素的prevlen编码进行了缩减。
上图是 reqlen > 4 的情况。考虑下reqlen < 4的情形，这时候， p + reqlen 比 p - nextdiff 小，那么，插入一个数据不再是后移，而是前移！！这样来看，之前的 nextdiff = -4 && reqlen < 4条件操作，防止了前移！！！这应该是增加此条件判断的原因。