我要评论一、概述
ziplist（压缩列表）是 redis 中一种极致紧凑的序列化数据结构，用于在内存中存储少量元素的列表。它是 redis 为节省内存而设计的核心编码之一。
1.1 为什么需要 ziplist？
问题：redis 的 list、hash、zset 等数据结构如果用标准链表或哈希表实现，内存开销很大。
解决方案：ziplist 将多个元素紧凑地编码到连续内存中，大幅减少内存占用。
1.2 使用场景
| 数据类型 | 使用条件 | 说明 |
|---|---|---|
| list | 元素少且短 | <list-max-ziplist-entries 且 <list-max-ziplist-value |
| hash | 字段少且短 | <hash-max-ziplist-entries 且 <hash-max-ziplist-value |
| zset | 元素少且短 | <zset-max-ziplist-entries 且 <zset-max-ziplist-value |
注意：redis 7.0+ 中，ziplist 已逐渐被 listpack 替代，但理解 ziplist 对理解 redis 的设计思想至关重要。
二、整体布局
2.1 内存结构
+-----------+-----------+-----------+--------+--------+-----+--------+
| zlbytes | zltail | zllen | entry1 | entry2 | ... | zlend |
| (4 bytes) | (4 bytes) | (2 bytes) | | | | 1 byte |
+-----------+-----------+-----------+--------+--------+-----+--------+
^
所有字段都是小端序（little endian）| 字段 | 类型 | 大小 | 说明 |
|---|---|---|---|
| zlbytes | uint32_t | 4 bytes | 整个 ziplist 占用的字节数 |
| zltail | uint32_t | 4 bytes | 到最后一个 entry 的偏移量 |
| zllen | uint16_t | 2 bytes | entry 数量（最大 65535，超过需遍历统计） |
| entry | 变长 | 不定 | 实际数据条目 |
| zlend | uint8_t | 1 byte | 结束标记，固定为 0xff（255） |
2.2 空 ziplist
[11 00 00 00] [0b 00 00 00] [00 00] [ff]
| | | |
zlbytes=11 zltail=11 zllen=0 zlend
空 ziplist 大小：11 bytes（header 10 bytes + end 1 byte）
三、entry 编码详解
每个 entry 的格式：
<prevlen> <encoding> <entry-data>
3.1 prevlen（前一条目长度）
用于反向遍历，记录前一条目的总字节数。
| 长度范围 | 编码方式 | 大小 |
|---|---|---|
| < 254 | 直接存储 | 1 byte |
| >= 254 | 0xfe + 4 bytes | 5 bytes |
// 编码前一条目长度
if (len < 254) {
p[0] = len; // 1 byte
} else {
p[0] = 0xfe; // 标记
memcpy(p+1, &len, 4); // 4 bytes
}3.2 encoding（编码方式）
encoding 字节决定了数据的类型和长度。
字符串编码
| 编码模式 | 格式 | 最大长度 | 示例 | |||
|---|---|---|---|---|---|---|
| ` | 00pppppp | ` | 1 byte | 63 bytes | 0x0b = 长度 11 的字符串 | |
| ` | 01pppppp | qqqqqqqq | ` | 2 bytes | 16383 bytes | 0x40 0x01 = 长度 64 的字符串 |
| ` | 10000000 | ...` | 5 bytes | 2^32-1 bytes | 0x80 00 00 10 00 = 长度 4096 |
整数编码
| 编码模式 | 编码字节 | 数据大小 | 范围 | ||
|---|---|---|---|---|---|
| ` | 11000000 | ` | 0xc0 | 2 bytes | int16_t |
| ` | 11010000 | ` | 0xd0 | 4 bytes | int32_t |
| ` | 11100000 | ` | 0xe0 | 8 bytes | int64_t |
| ` | 11110000 | ` | 0xf0 | 3 bytes | 24-bit signed |
| ` | 11111110 | ` | 0xfe | 1 byte | int8_t |
| ` | 1111xxxx | ` | 0xf1-0xfd | 0 byte | 4-bit immediate (0-12) |
3.3 编码示例
示例 1：存储整数 2 和 5
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
| | | | | |
zlbytes=15 zltail=12 zllen=2 "2" "5" end解析：
- 第一个 entry：00 f3
- 00：prevlen = 0（第一个 entry）
- f3：1111 0011，immediate integer = 3 - 1 = 2
- 第二个 entry：02 f6
- 02：prevlen = 2（第一个 entry 的长度）
- f6：1111 0110，immediate integer = 6 - 1 = 5
示例 2：存储字符串 "hello world"
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64] | | | prevlen=2 len=11 "hello world" (11 bytes)
解析：
- 02：前一条目长度为 2 bytes
- 0b：0000 1011，string 编码，长度 = 11
- 48 65 ... 64："hello world" 的 ascii
四、核心 api
4.1 创建与销毁
// 创建空 ziplist unsigned char *ziplistnew(void); // 释放 ziplist void zfree(unsigned char *zl); // 直接用 zfree
4.2 插入操作
// 在头部或尾部插入
unsigned char *ziplistpush(unsigned char *zl, unsigned char *s,
unsigned int slen, int where);
// where: ziplist_head=0, ziplist_tail=1
// 在指定位置插入
unsigned char *ziplistinsert(unsigned char *zl, unsigned char *p,
unsigned char *s, unsigned int slen);
4.3 删除操作
// 删除指定位置的 entry
unsigned char *ziplistdelete(unsigned char *zl, unsigned char **p);
// 删除范围内的 entry
unsigned char *ziplistdeleterange(unsigned char *zl, int index, unsigned int num);
// 替换指定位置的 entry
unsigned char *ziplistreplace(unsigned char *zl, unsigned char *p,
unsigned char *s, unsigned int slen);
4.4 查询操作
// 按索引获取 entry（支持负数索引）
unsigned char *ziplistindex(unsigned char *zl, int index);
// 获取下一个 entry
unsigned char *ziplistnext(unsigned char *zl, unsigned char *p);
// 获取上一个 entry
unsigned char *ziplistprev(unsigned char *zl, unsigned char *p);
// 获取 entry 的值
unsigned int ziplistget(unsigned char *p, unsigned char **sval,
unsigned int *slen, long long *lval);
// 获取 ziplist 长度
unsigned int ziplistlen(unsigned char *zl);
// 获取总字节数
size_t ziplistbloblen(unsigned char *zl);
4.5 查找操作
// 查找匹配的 entry
unsigned char *ziplistfind(unsigned char *zl, unsigned char *p,
unsigned char *vstr, unsigned int vlen,
unsigned int skip);
// 比较 entry 和字符串
unsigned int ziplistcompare(unsigned char *p, unsigned char *s,
unsigned int slen);
五、级联更新（cascade update）
5.1 问题描述
当插入或删除一个 entry 时，可能导致后续 entry 的 prevlen 字段长度发生变化：
before:
[entry a: 2 bytes] [entry b: 253 bytes] [entry c: ...]
| |
prevlen=1 prevlen=1
after: insert a new entry before b with 300 bytes
[entry a: 2 bytes] [new entry: 300 bytes] [entry b: 253 bytes] [entry c: ...]
| |
prevlen=1 prevlen=5 (!!!)
问题：entry b 的 prevlen 从 1 byte 变成了 5 bytes，导致 b 自身变大了！
5.2 级联效应
b 变大了 -> c 的 prevlen 可能也要变 -> c 也变大 -> ...
这种连锁反应就是级联更新。
5.3 解决方案
unsigned char *__ziplistcascadeupdate(unsigned char *zl, unsigned char *p) {
// 1. 计算当前 entry 的长度
// 2. 检查下一个 entry 的 prevlen 是否需要更新
// 3. 如果需要，更新并继续检查下一个
// 4. 直到不需要更新为止
}
优化：
- 只增不减（避免"抖动"）
- 实际发生级联的概率很低（需要连续多个 entry 刚好在边界）
- 最坏情况下是 o(n)，但平均情况是 o(1)
六、编码自动转换
6.1 整数编码
ziplist 会自动尝试将字符串转换为整数编码：
// 尝试将字符串编码为整数
int ziptryencoding(unsigned char *entry, unsigned int entrylen,
long long *v, unsigned char *encoding) {
if (string2ll((char*)entry, entrylen, &value)) {
// 可以编码为整数
if (value >= 0 && value <= 12) {
*encoding = zip_int_imm_min + value; // 4-bit immediate
} else if (value >= int8_min && value <= int8_max) {
*encoding = zip_int_8b;
} else if (value >= int16_min && value <= int16_max) {
*encoding = zip_int_16b;
} // ... 以此类推
return 1;
}
return 0; // 无法编码为整数，保持字符串
}
6.2 编码选择策略
| 数据类型 | 编码方式 | 大小 | ||
|---|---|---|---|---|
| 字符串 | ` | 00pppppp | ` | 1 + len |
| 整数 0-12 | ` | 1111xxxx | ` | 1 byte（无数据） |
| 整数 -128~127 | ` | 11111110 | ` | 1 + 1 = 2 bytes |
| 整数 -32768~32767 | ` | 11000000 | ` | 1 + 2 = 3 bytes |
| 大整数 | ` | 11100000 | ` | 1 + 8 = 9 bytes |
七、性能分析
7.1 时间复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 头部插入 | o(n) | 需要 memmove + 级联更新 |
| 尾部插入 | o(1) | 直接追加（无级联时） |
| 按索引查找 | o(n) | 线性遍历 |
| 按值查找 | o(n) | 线性遍历 |
| 删除 | o(n) | memmove + 级联更新 |
| 获取长度 | o(1) | 直接读取 zllen |
| 获取总字节数 | o(1) | 直接读取 zlbytes |
7.2 空间复杂度
| 场景 | 内存占用 | 说明 |
|---|---|---|
| 空 ziplist | 11 bytes | header + end |
| 存储小整数 | 1-3 bytes/个 | 极致紧凑 |
| 存储短字符串 | 1-64 bytes/个 | 取决于字符串长度 |
| 存储长字符串 | 较大 | 不适合用 ziplist |
八、与 listpack 的对比
| 特性 | ziplist | listpack |
|---|---|---|
| 设计目标 | 紧凑编码 | 紧凑编码 + 改进 |
| prevlen | 存储前一条长度 | 存储当前条长度 |
| 级联更新 | 可能发生 | 避免 |
| 遍历方向 | 双向 | 单向（从头遍历） |
| 安全性 | 较低（级联 bug） | 更高 |
| 状态 | 逐步淘汰 | redis 7.0+ 默认 |
九、设计亮点总结
9.1 紧凑编码
思想："每一个 bit 都要有价值"
- 整数自动编码（最小 1 byte）
- 字符串长度按需编码（1/2/5 bytes）
- prevlen 按需编码（1/5 bytes）
9.2 双向遍历
思想："用空间换时间，但空间要花在刀刃上"
- 通过 prevlen 实现反向遍历
- o(1) 获取尾部（通过 zltail）
9.3 自动类型转换
思想："对用户透明，自动选择最优编码"
- 字符串自动转整数
- 小整数用 immediate encoding
附录：完整编码表
|00pppppp| - 1 byte
string value with length <= 63 bytes
|01pppppp|qqqqqqqq| - 2 bytes
string value with length <= 16383 bytes
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
string value with length >= 16384 bytes
|11000000| - 3 bytes total
integer encoded as int16_t (2 bytes)
|11010000| - 5 bytes total
integer encoded as int32_t (4 bytes)
|11100000| - 9 bytes total
integer encoded as int64_t (8 bytes)
|11110000| - 4 bytes total
integer encoded as 24 bit signed (3 bytes)
|11111110| - 2 bytes total
integer encoded as int8_t (1 byte)
|1111xxxx| - 1 byte (xxxx between 0001 and 1101)
immediate 4 bit integer (0-12)
|11111111| - end of ziplist
参考源码：redis 8.8.2 (src/ziplist.h, src/ziplist.c)
到此这篇关于redis ziplist压缩列表的实现的文章就介绍到这了,更多相关redis ziplist压缩列表内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论