quicklist实现

Redis quicklist 实现详解（基于 6.0.10 版本）

Redis 的 List 类型在 3.2 版本后引入了 quicklist 作为底层实现，替代了此前的 “ziplist + linkedlist” 混合策略。quicklist 结合了 ziplist 的内存紧凑性和 linkedlist 的灵活扩展性，是 Redis 对列表结构的一次重要优化。本文结合源码结构和设计思路，详解 quicklist 的实现机制。

quicklist 的设计背景：为何替代旧方案？

在 3.2 版本前，Redis List 采用自适应编码：

• 元素少时用 ziplist（压缩列表）：连续内存存储，节省空间，但插入 / 删除大元素时需移动大量数据（O (N) 时间复杂度）。
• 元素多时用 linkedlist（双向链表）：节点独立分配内存，插入 / 删除高效（O (1)），但指针开销大（每个节点的 prev/next 指针占 16 字节），且内存碎片化严重。

旧方案的核心问题：

• ziplist 过大时（如存储 10 万个元素），一次插入 / 删除操作可能阻塞主线程（需移动大量内存）。
• linkedlist 节点分散存储，内存利用率低，且缓存命中率差（CPU 缓存难以命中连续数据）。

quicklist 的改进思路：
将 List 拆分为多个小段，每段用 ziplist 存储（保持紧凑性），段之间用双向指针连接（保持灵活性）。既避免了单个 ziplist 过大的性能问题，又减少了 linkedlist 的指针开销和碎片化。

quicklist 核心结构解析

quicklist 的实现依赖两个核心结构体：quicklist（列表本身）和 quicklistNode（列表节点）。

1. quicklist 结构体（列表整体）

typedef struct quicklist {
    quicklistNode *head;        // 头节点指针
    quicklistNode *tail;        // 尾节点指针
    unsigned long count;        // 所有节点中元素的总数量（List 的长度，对应 LLEN 命令）
    unsigned long len;          // quicklistNode 的数量（段数）
    int fill : QL_FILL_BITS;    // 单个节点的 ziplist 大小限制（由 list-max-ziplist-size 配置）
    unsigned int compress : QL_COMP_BITS; // 两端节点的压缩深度（0 表示不压缩）
    unsigned int bookmark_count: QL_BM_BITS; // 书签数量（用于快速定位节点）
    quicklistBookmark bookmarks[]; // 书签数组（优化大列表的随机访问）
} quicklist;

关键字段说明：

• fill：控制单个quicklistNode中 ziplist 的最大大小（或元素数量），取值来自配置list-max-ziplist-size：
  • 负数：表示 ziplist 最大字节数（如 -2 对应 8KB，-1 对应 4KB）。
  • 正数：表示 ziplist 最多存储的元素数量（如 5 表示每个节点最多 5 个元素）。
• compress：控制列表两端节点是否压缩（中间节点默认压缩），减少内存占用：
  • 0：不压缩（默认）。
  • 1：压缩两端各 1 层节点。
  • 2：压缩两端各 2 层节点（以此类推）。

2. quicklistNode 结构体（列表节点）

typedef struct quicklistNode {
    struct quicklistNode *prev; // 前一个节点指针
    struct quicklistNode *next; // 后一个节点指针
    unsigned char *zl;          // 指向 ziplist 内存（存储当前段的元素）
    unsigned int sz;            // ziplist 的总字节数（包括自身结构开销）
    unsigned int count : 16;    // 当前 ziplist 中的元素数量（最多 65535 个）
    unsigned int encoding : 2;  // 编码方式（1=RAW 未压缩，2=LZF 压缩）
    unsigned int container : 2; // 存储容器类型（2=ZIPLIST，固定值）
    unsigned int recompress : 1; // 标记该节点是否需要重新压缩（如被访问后解压）
    unsigned int attempted_compress : 1; // 标记该节点是否尝试过压缩（小节点可能压缩失败）
    unsigned int extra : 10;    // 预留字段（未来扩展）
} quicklistNode;

关键字段说明：

• zl：核心字段，指向当前节点的 ziplist 内存。若节点被压缩（encoding=2），则 zl 存储 LZF 压缩后的 ziplist 数据。
• sz：ziplist 的字节数（无论是否压缩，均记录原始大小），用于快速判断是否需要拆分节点。
• count：当前 ziplist 中的元素数量，用于快速计算 List 总长度（quicklist.count 是所有节点 count 的总和）。

quicklist 的核心工作机制

1. 元素的存储与分段

• List 的元素被分散存储在多个 quicklistNode 的 ziplist 中，每个 ziplist 的大小由 fill 控制（默认 8KB）。
• 例如：若 fill=-2（8KB），每个 ziplist 最多存储 8KB 的元素，超出则创建新节点（quicklistNode），通过 prev/next 指针串联。

2. 插入与删除操作

• 插入元素：
  1. 定位目标节点（如头部、尾部或指定索引）。
  2. 检查该节点的 ziplist 是否还有空间（未超过fill限制）：
     • 有空间：直接插入到 ziplist 中（ziplist 内部调整内存）。
     • 无空间：创建新节点，插入元素到新节点，并调整 prev/next 指针。
• 删除元素：
  1. 定位元素所在的 ziplist。
  2. 从 ziplist 中删除元素，若删除后 ziplist 为空，回收该 quicklistNode。
  3. 若相邻节点的 ziplist 较小，可能合并（减少节点数量，节省指针开销）。

3. 压缩机制（节省内存）

对于不常访问的中间节点，quicklist 会用 LZF 算法压缩其 ziplist（encoding=2）：

• 压缩触发：当节点长时间未被访问，且 compress 配置大于 0 时，自动压缩。
• 解压访问：当需要访问压缩节点时，临时解压（recompress=1 标记后续需重新压缩）。
• 优势：大幅减少内存占用（尤其长列表），且不影响两端常用节点的访问速度。

4. 与配置的关联（list-max-ziplist-size）

该配置直接决定 fill 字段的值，是平衡性能与内存的关键：

# 配置示例（默认值）
list-max-ziplist-size -2  # 单个节点的 ziplist 最大 8KB

• 推荐配置：
  • 若 List 元素小且访问频繁：-1（4KB）—— 更小的 ziplist 减少插入 / 删除时的内存移动。
  • 若 List 元素大或访问稀疏：-2（8KB）—— 减少节点数量，降低指针开销。

quicklist 与旧方案的对比

特性	quicklist（3.2+）	旧方案（ziplist + linkedlist）
内存效率	高（ziplist 紧凑存储 + 分段减少指针开销）	中（小数据 ziplist 高效，大数据 linkedlist 低效）
插入 / 删除性能	优（分段 ziplist 减少内存移动）	差（大 ziplist 移动成本高，linkedlist 指针开销大）
内存碎片化	低（ziplist 连续 + 节点数量可控）	高（linkedlist 节点分散分配）
配置灵活性	高（通过 fill 调整分段大小）	低（仅通过阈值切换编码）
适用场景	所有 List 场景（小列表到大列表均优化）	仅适合极小列表（ziplist）或纯遍历场景（linkedlist）