面试题：Redis 的 ListPack 数据结构是什么？

Redis 的 ListPack 是 Redis 7.0 引入的一种新型紧凑数据结构，用于替代早期版本中使用的 Ziplist（压缩列表）。其设计目标是优化内存利用率、减少连锁更新问题，并提升数据操作的性能。

ListPack 是 Redis 中 List、Hash、ZSet 等数据类型的底层实现之一。

一、ListPack 的核心设计

ListPack 的核心思想是通过 连续内存块 存储元素，并采用 变长编码 和 扁平化结构 来节省内存空间，同时避免 Ziplist 的连锁更新问题。

1. 结构组成

ListPack 的结构分为三部分：

Header（头部）：
- tot-bytes：4 字节，记录整个 ListPack 的总字节数（包括头部和所有元素）。
- num-elements：2 字节，记录元素数量（最大支持 65535 个元素；超过后需遍历统计）。
Entry（元素区域）：
- 每个元素由 编码类型、数据和 长度字段 组成。
- 元素之间无指针，直接通过偏移量访问。
End Byte（结束标志）：
- 1 字节，固定为 0xFF，表示 ListPack 的结束。

2. 元素结构

每个元素的结构如下：

Encoding Type（编码类型）：
- 1 字节，定义元素的编码方式（如整数、短字符串、长字符串等）。
- 支持多种编码类型，例如：
  - 0b0xxxxxxx：7 位无符号整数。
  - 0b10xxxxxx：6 位长度的短字符串（最大 63 字节）。
  - 0b11110000：5 字节长度的长字符串。
  - 0b11110001：3 字节有符号整数。
  - 0b11110010：4 字节有符号整数。
  - 0b11110011：5 字节有符号整数。
  - 0b11111111：结束标志（仅用于 ListPack 结尾）。
Data（数据）：
- 实际存储的数据（字符串或整数）。
Length（长度字段）：
- 1-5 字节，记录 Encoding Type + Data 的总长度。
- 采用 大端模式 编码，并支持 多字节扩展（例如，第一个字节为 0xFF 表示后续还有字节）。

3. 示例

假设存储字符串 "hello" 和整数 1024，ListPack 的结构如下：

| Header (6B) | "hello" (6B) | 1024 (5B) | End Byte (1B) |

二、ListPack 与 Ziplist 的对比

特性	Ziplist	ListPack
内存布局	连续内存块，但元素之间存储前一个元素的长度（`prevlen`）	连续内存块，仅存储当前元素的长度（`len`）
连锁更新问题	插入/更新元素时可能引发连锁更新（性能瓶颈）	无连锁更新问题（避免了 Ziplist 的缺陷）
编码方式	支持有限的编码类型	支持更灵活的编码（如不同长度的整数和字符串）
遍历效率	正向遍历需解析 `prevlen`，效率较低	正向和反向遍历均高效（通过 `len` 和偏移量）
内存利用率	相对较低（因 `prevlen` 占用额外空间）	更高（节省了 `prevlen` 的开销）

三、ListPack 的优势

避免连锁更新问题：
- Ziplist 的 prevlen 字段在插入/更新元素时可能导致后续元素的 prevlen 也需要更新，形成“连锁更新”（性能代价高）。ListPack 通过仅记录当前元素的长度，彻底解决了这一问题。
更高的内存利用率：
- 通过紧凑的编码方式（如不同长度的整数和字符串）减少内存浪费。
高效的增删操作：
- 尾部插入/删除操作时间复杂度为 O(1)。
- 中间插入/删除操作需移动后续元素，但因内存连续性，性能优于链表。
双向遍历支持：
- 支持正向和反向遍历（通过 len 字段和偏移量计算）。
兼容性设计：
- Redis 7.0 保留 Ziplist 兼容模式，确保旧数据可平滑迁移。

四、ListPack 的应用场景

小规模数据存储：
- 作为 Hash、ZSet、List 的底层实现，适合存储字段数少、值小的数据。
- 例如：HSET user:1000 name Alice age 30。
高频读写场景：
- 因避免了连锁更新问题，适合需要频繁修改的场景（如缓存队列、排行榜）。
内存敏感场景：
- 通过紧凑编码和连续内存布局，减少内存碎片，提升内存利用率。

五、ListPack 的代码实现

ListPack 的实现基于 C 语言的内存操作，关键函数包括：

lpNew：创建新的 ListPack。
lpAppend：向 ListPack 尾部追加元素。
lpInsert：在指定位置插入元素。
lpDelete：删除指定元素。
lpGet：获取指定索引的元素。

以下是一个简化示例（伪代码）：

// 创建 ListPack
unsigned char *listpack = lpNew(1024); // 初始容量 1024 字节

// 插入元素
lpAppend(listpack, "hello", 5);       // 插入字符串 "hello"
lpAppend(listpack, (void*)&1024, 4);  // 插入整数 1024

// 获取元素
unsigned char *element = lpGet(listpack, 0); // 获取第一个元素

六、总结

ListPack 是 Redis 7.0 为优化内存管理和性能引入的核心数据结构，其设计解决了 Ziplist 的连锁更新问题，并通过紧凑编码和连续内存布局提升了内存利用率和操作效率。

在实际应用中，ListPack 广泛用于 Hash、ZSet、List 等数据类型的底层实现，是 Redis 高性能和低内存占用的重要保障。

THE END

Redis 面试题