Redis基础数据结构之 ziplist 压缩列表 源码解读

ziplist 是什么?

压缩列表，内存紧凑的数据结构，占用一块连续的内存空间。一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数， 包括：

• 字符数组
  • 长度小于等于 63 （2^6-1）字节的字符数组
  • 长度小于等于 16383 （12^14-1） 字节的字符数组
  • 长度小于等于 4294967295 （2^32-1）字节的字符数组
• 整数
  • 4 位长，介于 0 至 12 之间的无符号整数
  • 1 字节长，有符号整数
  • 3 字节长，有符号整数
  • int16_t 类型整数
  • int32_t 类型整数
  • int64_t 类型整数
  • Redis 哪些数据结构使用了 ziplist？
  • 哈希键
  • 列表键
  • 有序集合键

ziplist 特点

• 优点
  • 节省内存
• 缺点
  • 不能保存过多的元素，否则访问性能会下降
  • 不能保存过大的元素，否则容易导致内存重新分配，甚至引起连锁更新

ziplist 数据结构

// ziplist 中的元素，是 string 或者 integer
typedef struct {// 如果元素是 string，slen 就表示长度unsigned char *sval;unsigned int slen;// 如果是 integer，sval 是 NULL，lval 就是 integer 的值long long lval;
} ziplistEntry;

为了方便地取出 ziplist 的各个域以及一些指针地址， ziplist 模块定义了以下宏：

// 取出 zlbytes 的值
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))// 取出 zltail 的值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))// 取出 zllen 的值
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))// 返回 ziplist header 部分的长度，总是固定的 10 字节
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))// 返回 ziplist end 部分的长度，总是固定的 1 字节
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))// 返回到达 ziplist 第一个节点（表头）的地址
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)// 返回到达 ziplist 最后一个节点（表尾）的地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))// 返回 ziplist 的末端，也即是 zlend 之前的地址
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

ziplist 节点

typedef struct zlentry {// 前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点unsigned int prevrawlen;unsigned int prevrawlensize;// entry 的编码方式// 1. entry 是 string，可能是 1 2 5 个字节的 header// 2. entry 是 integer，固定为 1 字节unsigned int lensize;// 实际 entry 的字节数// 1. entry 是 string，则表示 string 的长度// 2. entry 是 integer，则根据数值范围，可能是 1, 2, 3, 4, 8unsigned int len;// prevrawlensize + lensizeunsigned int headersize;// ZIP_STR_* 或者 ZIP_INT_*unsigned char encoding;unsigned char *p;            /* Pointer to the very start of the entry, thatis, this points to prev-entry-len field. */
} zlentry;

pre_entry_length

记录前一个节点的长度。通过这个值，可以进行指针计算，从而跳转到上一个节点。

area        |<---- previous entry --->|<--------------- current entry ---------------->|size          5 bytes                   1 byte             ?          ?        ?+-------------------------+-----------------------------+--------+---------+
component   | ...                     | pre_entry_length | encoding | length | content ||                         |                  |          |        |         |
value       |                         | 0000 0101        |    ?     |   ?    |    ?    |+-------------------------+-----------------------------+--------+---------+^                         ^
address     |                         |p = e - 5                 e

以上图为例，从当前节点的指针 e，减去 pre_entry_length 的值（0000 0101 的十进制值，5），就可以得到指向前一个节点的地址 p。

encoding 和 length

encoding 和 length 两部分一起决定了 content 部分所保存的数据的类型（以及长度）。

其中， encoding 域的长度为两个 bit ， 它的值可以是 00 、 01 、 10 和 11 ：

• 00 、 01 和 10 表示 content 部分保存着字符数组。
• 11 表示 content 部分保存着整数。

以 00 、 01 和 10 开头的字符数组的编码方式如下：

表格中的下划线 _ 表示留空，而变量 b 、 x 等则代表实际的二进制数据。为了方便阅读，多个字节之间用空格隔开。

11 开头的整数编码如下：

content

content 部分保存着节点的内容，类型和长度由 encoding 和 length 决定。

以下是一个保存着字符数组 hello world 的节点的例子：

area      |<---------------------- entry ----------------------->|size        ?                  2 bit      6 bit    11 byte+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       ||                  |          |        |               |
value     | ?                |    00    | 001011 | hello world   |+------------------+----------+--------+---------------+

encoding 域的值 00 表示节点保存着一个长度小于等于 63 字节的字符数组， length 域给出了这个字符数组的准确长度 —— 11 字节（的二进制 001011）， content 则保存着字符数组值 hello world 本身（为了方便表示， content 部分使用字符而不是二进制表示）。

以下是另一个节点，它保存着整数 10086 ：

area      |<---------------------- entry ----------------------->|size        ?                  2 bit      6 bit    2 bytes+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       ||                  |          |        |               |
value     | ?                |    11    | 000000 | 10086         |+------------------+----------+--------+---------------+

ziplist 基本操作

插入（Insertion）

在Ziplist中插入新元素时，Redis需要找到合适的位置并将新元素添加进去。由于Ziplist是连续存储的，插入操作通常会导致整个列表或部分列表的重新分配和复制，这是因为新元素的插入会改变后续元素的位置。

删除（Deletion）

删除Ziplist中的元素同样涉及到内存的重新分配和复制，因为删除后的元素位置需要被前面或后面的元素覆盖。

查找（Search）

查找特定元素时，Redis需要从Ziplist的开头开始逐个元素地遍历，直到找到目标元素为止。由于Ziplist中的每个元素都有长度信息，查找时可以快速定位到下一个元素的起始位置，但依然需要逐个元素地检查。

更新（Update）

更新Ziplist中的元素涉及到内存的重新分配。如果更新后的元素大小发生了变化，那么更新操作可能会导致该元素后面的所有元素需要重新分配和复制。

示例

假设我们有一个Ziplist，其中包含以下元素：“key1:value1”, “key2:value2”, “key3:value3”。每个元素的长度信息和实际内容是紧密相连的。

• 插入新元素
  如果我们想要在"key2:value2"之前插入一个新的元素"key1.5:value1.5"，Redis需要找到"key2:value2"的位置，并在其前面插入新元素。这意味着Redis需要重新分配内存，将"key2:value2"及其后面的元素向后移动。

• 删除元素
  如果我们要删除"key2:value2"，Redis需要找到该元素的位置，并将其后面的元素向前移动以填补空缺。

• 更新元素
  如果我们将"key2:value2"更新为"key2:updated_value2"，并且更新后的字符串长度与原字符串长度不同，Redis需要重新分配内存，并将更新后的元素替换原有元素的位置。

Ziplist在存储小数据集时非常高效，但由于其紧凑存储的特性，在进行插入、删除和更新操作时可能会涉及到内存的重新分配和复制。因此，Ziplist最适合用于内存敏感的应用场景，特别是当数据集较小且操作以读取为主时。对于大型数据集或频繁的写操作，Redis可能会选择其他更适合的数据结构。