Redis 数据结构——ziplist

大家好，我是讯享网，很高兴认识大家。

一、ziplist 简介

二、ziplist 结构

整个 ziplist 在内存中的存储格式如下：
在这里插入图片描述
讯享网
ziplist 主要有这么几个部分：
zlbytes：32 位无符号整型，表示整个 ziplist 所占的空间大小，包含了 zlbytes 所占的 4 个字节。这个字段可以在重置整个 ziplist 大小时不需要遍历整个 list 来确定大小，空间换时间。在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用。

zltail：32 位无符号整型，表示整个 list 中最后一项所在的偏移量，用来倒序遍历压缩列表。

zllen：16 位，表示 ziplist 中所存储的 entry 数量，但是注意，这里最多表示 2^16 − 2 个 entry，如果是2^16 − 1，则有特殊含义，2^16 − 1 表示存储数量超过了 2^16 − 2 个，但具体是多少个得遍历一次才能知道。

entry：不定长，可能有多个，list 中具体的数据项，下面会详细介绍。

zlend：8 位，ziplist 的末尾表示，值固定是 255。

entry

这里最核心的就是 entry 的数据格式，entry 有些复杂，从上图中可以看出它主要有三个部分。
prevlen：前一个 entry 的存储大小，主要是为了方便从后往前遍历。

encoding：数据的编码形式（比如：表示的是字符串还是数字，以及对应的长度）

entry-data：实际存储的数据

比较复杂的是 Redis 为了节省内存空间，对上面三个字段设计了一套比较复杂的编码方式，本质上就是一套变长的编码协议，具体规则如下：

prevlen

encoding

encoding 的具体值取决于 entry 中具体的内容，当 entry 是个 string 时，encoding 的第一个字节的前 2 位将保存用于存储字符串长度的编码类型，然后是字符串的实际长度。当 entry 是一个整数的时候，前 2 位都设置为 1，在后面的 2 位用于指定在这个报头之后将存储哪种类型的整数。对不同类型和编码的概述如下。第一个字节总是足以确定条目的类型。

不同的 encoding 类型示例如下：

|00pppppp| - 1 字节
长度小于或者等于 63 字节的 String 类型，‘pppppp’ 无符号 6 位数标识 string 长度。

|01pppppp|| - 2 字节
长度小于或者等于 16383 字节的 String 类型 (14位)，注意：14 位 ‘pppppp’ 采用大端的方式存储。

|||rrrrrrrr|ssssssss|tttttttt| - 5 字节
长度大于等于 16384 字节的 String 类型，第二字节开始的 rrsstt 都是用来存储字符串长度的二进制位，可表示的字符串长度最大 2^32 - 1，第一字节的低 6 位没有用，所以都是 0。注意：32 位数采用大端的方式存储。

|| - 3 字节
存储 int16_t (2 字节)。

|| - 5 字节
存储 int32_t (4 字节)。

|| - 9 字节
存储 int64_t (8 字节)。

|| - 4 字节
24 位有符号类型整数 (3 字节)。

|| - 2 字节
8 位有符号类型整数 (1 字节)。

|1111xxxx| - (xxxx 在 0001 和 1101 之间) 4 位无符号整数
0 到 12 的无符号整数，编码值实际上是从 1 到 13，因为 0000、1110 和 1111 不能使用，要留出一位表示 0，所以应该从编码值中减去 1 才是准确值。

||
表示 ziplist 的结束，也就是 zlend 的值 0xFF。

在某些比较小的数值下，具体值可以直接存储到 encoding 字段里。

举个例子：

上图是一个包含了字符串 “2” 和 “5” 的压缩列表。

最前面的 4 个字节的代表着数字 0x0f = 15（zlbytes = 15），表示这个 ziplist 总共占用了 15 个字节。紧跟着的 4 个字节代表数字 0x0c = 12（zltail = 12），说明最后一个元素的偏移量是 12，也就是 “5” 这个元素到 ziplist 开头的长度。接着是 zllen = 2，代表总共有 2 个元素。之后就是实际储存 “2” 和 “5” 的 entry。解读下 “2” 为什么是 00 f3，00 表示前一个元素长度为 0，因为它是第一个元素，f3 是 0x，也就是我们的 1111xxxx encoding 类型，3 - 1 = 2 正好是我们的 “2”，“5” 也同理。最后是 ff 结尾表示结束。

如果把上面的字符串“5”换成“Hello World”，那么原先的 “5” 这个 entry 会变成：

zlentry

ziplist 其实只是一种双向队列的序列化方式，是在内存中的存储格式，实际上并不能直接拿过来用，用户看到的 ziplist 只是一个 char * 指针，其中每个 entry 在实际使用中还需要反序列化成 zlentry 方便调用。

zlentry 结构：

三、总结

ziplist 是个压缩列表，因此在内存中是高度紧凑的连续存储，这意味着它其实对修改并不友好，如果要对 ziplist 做修改类的操作，那就需重新分配新的内存来存储新的 ziplist，代价很大。

举个例子：

如上图，有 entryX-1 512字节，entryX 128字节，entryX+1 253字节，entryX+2 253 字节。

由于 entryX 元素长度为 128 字节，那么 entryX + 1 元素的 prevlen 的元素的长度就只要 1 个字节就可以了。

这个时候，在 entryX 和 entryX+1 之间加了一个 entryNew 元素，这个元素长度是 1024 字节，那么，这个时候 entryX+1 中的 prevlen 就需要变成 5 个字节了。注意：后面的元素可能也要进行更新。

当删除 entryX 的时候，entryX+1 的 prevlen 就变成了 5 字节，那么 entryX+1 的长度就变成了 257 字节；又导致后面进行更新，这种叫做连锁更新。