ziplist实现

Redis ziplist（压缩列表）实现详解（基于 6.0.10 版本）

ziplist（压缩列表）是 Redis 为节省内存设计的紧凑数据结构，通过连续内存块存储数据，避免了传统链表的指针开销。它并非通过 “压缩算法” 压缩数据，而是通过紧凑布局减少内存浪费，广泛用于 Hash、List、ZSet 等数据类型的底层实现（当数据量较小时）。

ziplist 核心设计目标

• 节省内存：通过连续内存存储，消除链表节点的指针（prev/next）开销（传统双向链表每个节点需 16 字节指针）。
• 支持双向遍历：通过特殊结构设计，既支持正向遍历，也能高效反向遍历。
• 适配小数据：针对小尺寸元素（如短字符串、整数）优化，不适合存储大型数据或大量元素。

ziplist 整体结构

ziplist 由一系列连续的内存块组成，整体结构如下（单位：字节）：

+--------+--------+--------+----------------+----------------+--------+
| zlbytes| zltail | zllen  | entry 1        | entry 2        | zlend  |
| (4B)   | (4B)   | (2B)   | ...            | ...            | (1B)   |
+--------+--------+--------+----------------+----------------+--------+

各字段含义：

字段名	长度（字节）	作用
zlbytes	4	记录 ziplist 总字节数（包括自身），用于快速计算内存大小和重分配。
zltail	4	记录表尾节点距离 ziplist 起始地址的偏移量（字节），支持快速定位尾节点（无需遍历）。
zllen	2	记录节点数量（entry 个数），最大值为 65535（2^16-1）。若超过此值，需遍历整个列表获取真实数量。
entry	可变	存储实际数据的节点（每个 entry 结构不同，见下文）。
zlend	1	标记列表结尾，固定值为 0xFF（255）。

entry 节点结构

每个 entry 是 ziplist 的数据单元，结构如下：

+----------+----------+------------+
| prevlen  | encoding | entry-data |
| (1B/5B)  | (1B/2B/5B)| 可变       |
+----------+----------+------------+

1. prevlen：前节点长度

• 作用：记录前一个 entry 的总字节数，用于反向遍历（当前节点地址 - prevlen = 前节点地址）。
• 长度：
  • 若前节点长度 ≤ 254 字节，用 1 字节存储（值 = 前节点长度）。
  • 若前节点长度 ＞ 254 字节，用 5 字节存储（第 1 字节固定为 0xFE，后 4 字节存储实际长度）。
• 示例：
  前节点长度为 100 → prevlen = 0x64（1 字节）。
  前节点长度为 300 → prevlen = 0xFE 0x00 0x00 0x01 0x2C（5 字节，0x0000012C = 300）。

2. encoding：编码与数据长度

• 作用：标识 entry-data 的类型（字符串 / 整数）和长度，避免额外的类型字段开销。
• 编码规则：
  • 字符串类型：
    • 1 字节编码：最高 2 位为 00（长度 ≤ 63 字节），后 6 位存储长度（00xxxxxx）。
    • 2 字节编码：最高 2 位为 01（长度 ≤ 16383 字节），后 14 位存储长度（01xxxxxx xxxxxxxx）。
    • 5 字节编码：最高 2 位为 10（长度 ≥ 16384 字节），后 32 位存储长度（10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx，前 2 位固定为 10，后 30 位无效，实际长度存在第 2-5 字节）。
  • 整数类型：最高 2 位为 11，后 6 位标识整数类型（如 11000000 表示 32 位整数，11000011 表示 8 位整数等），entry-data 直接存储整数二进制值（无需额外长度字段）。

3. entry-data：实际数据

• 若为字符串：存储字符串的字节数组（长度由 encoding 指定）。
• 若为整数：存储整数的二进制值（如 8 位整数占 1 字节，32 位整数占 4 字节）。

ziplist 的双向遍历机制

ziplist 支持高效的双向遍历，核心依赖 zltail 和 prevlen：

• 正向遍历：从头部开始，通过当前 entry 的总长度（prevlen + encoding 长度 + data 长度）计算下一个 entry 的地址。
• 反向遍历：
  1. 用 zltail 定位尾节点（起始地址 + zltail）。
  2. 通过尾节点的 prevlen 计算前一个节点地址（当前地址 - prevlen）。
  3. 重复步骤 2，直至遍历到头部。

使用 ziplist 的数据类型及配置

Redis 中 Hash、List、ZSet 会根据数据规模自动选择 ziplist 或其他结构（如哈希表、双向链表、跳表），触发条件由配置参数控制。

1. Hash 类型

• 底层结构转换：当 Hash 元素较少且元素尺寸较小时，用 ziplist 存储（key 和 value 作为相邻 entry）；否则转为哈希表。

• 配置参数：

  hash-max-ziplist-entries 512  # 最大元素个数，超过则转哈希表
  hash-max-ziplist-value 64     # 单个 key/value 最大字节数，超过则转哈希表

2. List 类型

• 底层结构转换：当 List 长度较短时，用 ziplist 存储；否则转为双向链表（quicklist，Redis 3.2+ 引入，由多个 ziplist 组成）。

• 配置参数：

  # 允许的最大内存占用（字节），-2 表示 8KB
  list-max-ziplist-size -2  

3. ZSet 类型

• 底层结构转换：当 ZSet 元素较少且元素尺寸较小时，用 ziplist 存储（value 和 score 作为相邻 entry）；否则转为跳表。

• 配置参数：

  zset-max-ziplist-entries 128  # 最大元素个数，超过则转跳表
  zset-max-ziplist-value 64     # 单个 value 最大字节数，超过则转跳表

ziplist 的优缺点

优点

• 内存高效：连续存储消除指针开销，小数据压缩率高（如存储 100 个短字符串，比链表节省 50%+ 内存）。
• 遍历高效：双向遍历无需指针跳转，适合小规模数据的迭代操作。

缺点

• 插入 / 删除效率低：由于内存连续，插入 / 删除元素可能需要重新分配内存并移动大量数据（时间复杂度 O (n)）。
• 连锁更新风险：若修改一个 entry 的长度，可能导致后续 entry 的 prevlen 字段长度变化（如从 1 字节变为 5 字节），引发一系列更新（“连锁更新”），最坏情况时间复杂度 O (n^2)。
• 不适合大数据：元素过多或过大时，内存重分配和拷贝成本剧增，性能下降明显