Redis 核心数据结构（一）

Redis 官方在 ziplist.c 文件的注释中对 ziplist 进行了定义：

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

就是说，ziplist 是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist 可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以 O(1) 的时间复杂度在表的两端提供 push 和 pop 操作。

1. <zlbytes>: 32bit，表示ziplist占用的字节总数（也包括<zlbytes>本身占用的4个字节）。

2. <zltail>: 32bit，表示ziplist表中最后一项（entry）在ziplist中的偏移字节数。

   <zltail> 的存在，使得我们可以很方便地找到最后一项（不用遍历整个ziplist），从而可以在ziplist尾端快速地执行push或pop操作。

3. <zllen>: 16bit， 表示ziplist中数据项（entry）的个数。zllen字段因为只有16bit，所以可以表达的最大值为216-1。<zllen> 等于16bit全为1的情况，那么 <zllen> 就不表示数据项个数了，这时要想知道 ziplist 中数据项总数，那么必须对ziplist从头到尾遍历各个数据项，才能计数出来。

4. <entry>: 表示真正存放数据的数据项，长度不定。一个数据项（entry）也有它自己的内部结构，这个稍后再解释。

5. <zlend>: ziplist 最后 1 个字节，是一个结束标记，值固定等于 255。

ziplist 将表中每一项存放在前后连续的地址空间内，一个ziplist整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list）。

ziplist 为了在细节上节省内存，对于值的存储采用了变长的编码方式。

每一个数据项<entry>的构成：

1. <prevlen>: 表示前一个数据项占用的总字节数。

   1. 如果前一个数据项占用字节数小于254，那么 <prevlen> 就只用一个字节来表示，这个字节的值就是前一个数据项的占用字节数： <prevlen from 0 to 253> <encoding> <entry>

   2. 如果前一个数据项占用字节数大于等于254，那么 <prevlen> 就用5个字节来表示，其中第1个字节的值是254（作为这种情况的一个标记），而后面4个字节组成一个整型值，来真正存储前一个数据项的占用字节数

      0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>  // (2) (3)

2. <encoding>: 表示当前数据项的类型，整型或者字符串。

3. <entry-data>: 数据

关于 <encoding> <entry-data> 的编码，直接引用官方文档：

引用在网上找的例子，来做个说明：

1. 这个ziplist一共包含 33 个字节。字节编号从 byte[0] 到 byte[32]。图中每个字节的值使用 16 进制表示。

2. 头 4 个字节（0x21000000）是按小端（little endian）模式存储的 <zlbytes> 字段。什么是小端呢？就是指数据的低字节保存在内存的低地址中（参见维基百科词条 Endianness）。因此，这里 <zlbytes> 的值应该解析成 0x00000021，用十进制表示正好就是33。

3. 接下来 4 个字节（byte[4..7]）是 <zltail>，用小端存储模式来解释，它的值是 0x0000001D（值为29），表示最后一个数据项在 byte[29] 的位置（那个数据项为 0x05FE14）。

4. 再接下来 2 个字节（byte[8..9]），值为 0x0004，表示这个 ziplist 里一共存有4项数据。

5. 接下来 6 个字节（byte[10..15]）是第 1 个数据项。其中，prevlen=0，因为它前面没有数据项；len=4，相当于前面定义的9种情况中的第1种，表示后面4个字节按字符串存储数据，数据的值为：name。

6. 接下来 8 个字节（byte[16..23]）是第 2 个数据项，与前面数据项存储格式类似，存储 1 个字符串：tielei。

7. 接下来 5 个字节（byte[24..28]）是第 3 个数据项，与前面数据项存储格式类似，存储 1 个字符串： age。

8. 接下来3个字节（byte[29..31]）是最后一个数据项，它的格式与前面的数据项存储格式不太一样。其中，第 1 个字节 prevlen=5，表示前一个数据项占用 5 个字节；第 2 个字节 = FE，相当于前面定义的9种情况中的第8种，所以后面还有1个字节用来表示真正的数据，并且以整数表示。它的值是20（0x14）。

9. 最后1个字节（byte[32]）表示 <zlend>，是固定的值255（0xFF）。

有两个问题需要注意：

1. 如何反向遍历 ziplist ？

   <prevlen>: 表示前一个数据项占用的总字节数。那么就能找到前一个元素的起始位置，就能实现反向遍历。

2. 如何从 ziplist 中添加/删除数据？删除数据后，对应位置的 Bits 位怎么处理？

   在某个/某些节点的前面添加新节点之后， 程序必须沿着路径挨个检查后续的节点，是否满足新长度的编码要求， 直到遇到一个能满足要求的节点（如果有一个能满足，则这个节点之后的其他节点也满足）， 或者到达 ziplist 的末端 zlend 为止， 这种检查操作的复杂度为 O(N2) 。

   因为只有在新添加节点的后面有连续多个长度接近 254 的节点时， 这种连锁更新才会发生， 所以可以普遍地认为， 这种连锁更新发生的概率非常小， 在一般情况下， 将添加操作看成是 O(N) 复杂度也是可以的。

   删除元素就进行内存移位，覆盖 target 原本的数据，然后通过内存重分配，收缩多余空间。

Redis 在下面这个几个地方使用了 ziplist：

1. 列表包含少量的列表项，并且列表项只是整数或者短小的字符串时。（在下面 quicklist 小节中，在最新版 Redis 中测试，显示的是 quicklist，而 quicklist 内部使用的是 ziplist 来存储数据，只是外面被 quicklist 包裹着。）

2. 在哈希键值包含少量键值对，并且每个键值对只包含整数或短小字符串时。

   $ redis-cli --raw
   
   127.0.0.1:6379> HMSET site domain "https://www.diguage.com" owner "D瓜哥"
   OK
   
   127.0.0.1:6379> HGET site domain
   https://www.diguage.com
   
   127.0.0.1:6379> HGET site owner
   D瓜哥
   
   127.0.0.1:6379> TYPE site
   hash
   
   127.0.0.1:6379> OBJECT encoding site
   ziplist