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
entry的encoding字段取决于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