redis 6源码解析之 ziplist

ziplist

ziplist结构

ziplist的布局如下,所有的字符默认使用小端序保存:

+--------+--------+--------+--------+-------+-------+-------+
|zlbytes | zltail |  zllen | entry  |  ...  | entry | zlend |
+--------+--------+--------+--------+-------+-------+-------+
  • uint32_t zlbytes:为一个无符号整数。保存了ziplist占用的字节数,包含zlbytes字段本身占用的4个字节。主要用于调整数据结构的大小。

  • uint32_t zltail:最后一个entry的字节偏移量(非zlend)。用于从list的另一端执行pop操作(即倒序遍历)

  • uint16_t zllen:entry的数目。当保存的entry大于216-2个entry时,则将该值设置为216-1,此时需要遍历整个entry list来计算list中的entry数目

  • uint8_t zlend:表示ziplist中的最后一个entry。字节编码等同于255(即FF)。表示ziplist的结束符

ziplist中的每个entry都使用一个元数据作为前缀,该元数据包含两部分的信息:首先保存了前一个entry的长度,用于倒序查找;再者保存了entry的编码类型,表示entry的类型,如整数或字符串,当编码类型为字符串时,该字段也表示了字符串的长度。字符串的entry-data的长度就等同于该字符串的长度,而整数的entry-data的长度需要根据编码类型进行判断,并不一定等同于其entry-data字符串的长度(见下文encoding)。一个完整的entry为:

+--------+--------+----------+
|prevlen |encoding|entry-data| 
+--------+--------+----------+

有时编码类型即表示entry本身(例如小的整数),这种情况下会忽略entry-data字段,此时entry变为:

+--------+--------+
|prevlen |encoding|
+--------+--------+

prevlen

prevlen表示前一个entry的长度,使用如下方式进行编码:当前一个entry的长度小于254(255是个特殊字符,被zlend使用)字节时,该字段会使用一个字节(即8 bit)表示长度;当长度大于或等于254时,将会使用5个字节,此时第一个字节会被设置为254(FE)来表示一个较大的数值,后续4个字节表示前面一个entry的长度。

因此,prevlen的编码为:

  • 如果前一个entry的长度小于254,编码为:

    +-------+--------+-----+
    |prevlen|encoding|entry| 
    +-------+--------+-----+
  • 如果前一个entry的长度大于254,编码如下:

    +----+---------------+--------+-----+
    |0xFE|4 bytes prevlen|encoding|entry| 
    +----+---------------+--------+-----+

encoding

entryencoding字段取决于entry的内容。当entry为字符串时,encoding的第一个字节的前2bit保存了编码类型,剩余的bit位表示字符串的长度。当entry为整数时,encoding仅占用1个字节,encoding的前2bit都设置为1,后续的2bit用于指定整数的类型,如int16_t,int32_t。encoding中的第一个字节总是用于判定entry的类型。举例如下:

* |00pppppp| - 1 byte
 *       字符串的长度小于或等于63字节(6 bits).
 *      "pppppp" 表示6bit长度的无符号整数.
 * |01pppppp|qqqqqqqq| - 2 bytes
 *       字符串的长度小于或等于16383字节(14 bits).
 *       IMPORTANT: 14 bit的数字使用大端序保存.
 * |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
 *      字符串的长度大于或等于16384字节,只使用第1个字节之后的4个字节表示长度,最大为32^2-1,第一个
 *      字节的低6位没有使用,设置为0。因此entry的最大长度为32
 *      IMPORTANT: 32 bit的数字使用大端序保存.
 * |11000000| - 3 bytes
 *      整数编码为int16_t (2 bytes).
 * |11010000| - 5 bytes
 *      整数编码为int32_t (4 bytes).
 * |11100000| - 9 bytes
 *      I整数编码为int64_t (8 bytes).
 * |11110000| - 4 bytes
 *      编码为24 bit的有符号整数 (3 bytes).
 * |11111110| - 2 bytes
 *      编码为8 bit的有符号整数 (1 byte).
 * |1111xxxx| - (xxxx  取值为 0000 到 1101) 表示4bit的整数
 *      无符号整数的取值为0到12,由于无法使用0000(被|11110000|编码占用)和1111(被zlend占用),因此取值
 *      为1到13,因此需要从低4位的整数减去1获得entry的值.
 * |11111111| - 表示ziplist的终止entry,即zlend

举例

整数编码

如下ziplist包含2个元素,表示字符串"2"和"5",长度为15字节,可以看到由于数值小于13,其编码和数值放在了一个字节中。

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
       |             |          |       |       |     |
    zlbytes        zltail    entries   "2"     "5"   end

前4个字节(zlbytes)表示15,即整个ziplist包含的字节数;第2个4字节(zltail)最后一个entry的字节偏移,即字符串为"5"的entry的位置,偏移量为12字节;接下来的16bit(entries)表示ziplist中的entry的数目,为2;"00 f3"表示list中的第一个entry "2",它包含了前一个entry的长度(prevlen),为0,"f3"对应的编码为"|1111xxxx|","xxxx"的取值为0001到1101,去除前4个bit "1111",并减去1,得到entry的值为2。下一个entry的prevlen为2,表示前一个entry占用了2字节."f6"的编码与前一个相同,去除前4个bit,并减去1,得到entry的值为5;最后的"ff"表示ziplist的结束(zlend)。

字符串编码

在上述ziplist中追加一个"Hello World"的entry的编码。第一个字节表示前面entry的长度,第二个字节表示encoding,二进制为"|00pppppp|",因此"0b"表示一个11字节的字符串。从第3个字节(48)到最后一个字节(64)表示ASCII编码的字符串"Hello World"。

[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

源码解析参见:ziplist.c

相关推荐