Redis List类型解析

在 Redis 3.2 版本之前，List 类型的实现方式有两种：

ziplist（压缩列表）：当元素数量少、元素体积小时使用，旨在节省内存。
linkedlist（双向链表）：当不满足 ziplist 条件时使用，支持高效的节点增删。

自 Redis 3.2 版本起，List 类型的实现被统一并优化为一种结构：quicklist（快速列表）。 它本质上是 ziplist 和 linkedlist 的混合体，将一个大的 linkedlist 拆分成多个小的 ziplist，然后用双向指针把它们连接起来。这种设计在时间效率和空间效率上取得了完美的平衡。

因此，我们的分析将围绕 quicklist 展开，并深入其基础——ziplist。

一、底层数据结构详解

1. Ziplist (压缩列表)

ziplist 是 Redis 为了极致地节省内存而设计的一种紧凑的、连续内存存储的数据结构。它不是一个基础数据结构（如链表或数组），而是一系列特殊编码的内存块。

a) 内存布局：

一个 ziplist 在内存中的结构如下所示：

1	<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

zlbytes (uint32_t)：整个 ziplost 占用的内存字节数，包括它本身。用于调整内存大小或快速计算长度。
zltail (uint32_t)：到达列表中最后一个 entry 的偏移量（字节）。这使得对列表尾部进行操作（如 RPOP）不需要遍历整个列表，时间复杂度为 O(1)。
zllen (uint16_t)： entry 的数量。如果这个值等于 2^16-1，则需要遍历整个列表才能知道真实的元素个数。
entry：存储具体数据的节点，长度可变。
zlend (uint8_t)：一个特殊的常量（255/0xFF），标记 ziplist 的结束。

b) Entry 的编码：

每个 entry 自身的结构也很有讲究：<prevlen> <encoding> <content>

prevlen：前一个 entry 的长度（字节数）。
- 如果前一个 entry 的长度 < 254 字节，则 prevlen 用 1 个字节存储。
- 否则，用 5 个字节：第一个字节固定是 0xFE (254)，后四个字节存储实际长度。
  这个字段使得 ziplist 能够从后向前遍历（反向解码）。
encoding：指示当前 content 的类型和长度。
- 编码方式非常灵活，可以存储整数或字符串。
- 例如：|11000000| 表示 content 是一个 int16_t 类型的整数；|00pppppp| 表示 content 是一个长度小于等于 63 字节的字符串（长度信息直接包含在 encoding 的低 6 位中）。
  这种设计避免了存储额外的“长度”字段，进一步节省了空间。
content：实际存储的数据内容。

c) Ziplist 的优缺点：

优点：极其节省内存，因为所有数据都存储在一块连续的内存中，没有指针带来的额外开销（64位系统下指针占8字节），并且避免了内存碎片。
缺点：
- 连锁更新（Cascade Update）：这是最著名的缺点。假设一个所有 entry 长度都在 250-253 字节之间的 ziplist，此时每个 prevlen 都只用 1 字节存储。如果在头部插入一个大于 254 字节的新 entry，会导致其后的第一个 entry 的 prevlen 需要从 1 字节扩展为 5 字节。这个扩展操作又会导致该 entry 的总长度超过 254 字节，进而引发再后面一个 entry 的更新… 最坏情况下会触发连续的多次重新分配内存，性能很差。不过，这种情况在实际中非常罕见。

2. Quicklist (快速列表)

quicklist 是 List 类型的终极实现，它在宏观上是一个双向链表，而链表的每个节点（quicklistNode）都是一个 ziplist。

a) 数据结构（源码 quicklist.h）：

/* quicklistNode 是一个 32字节 的结构体（在 64位系统上） */
typedef struct quicklistNode {
    struct quicklistNode *prev; // 指向前一个节点的指针
    struct quicklistNode *next; // 指向后一个节点的指针
    unsigned char *zl;          // 指向该节点对应的 ziplist 的指针
    unsigned int sz;            // 该 ziplist 占用的字节大小
    unsigned int count : 16;    // ziplist 中 entry 的个数（16位）
    unsigned int encoding : 2;  // 编码方式：1 是原生，2 是 LZF 压缩存储
    unsigned int container : 2; // 容器类型：目前固定为 2，表示使用 ziplist
    unsigned int recompress : 1; // 之前是否被压缩过？（用于临时解压）
    unsigned int attempted_compress : 1; // 测试用
    unsigned int extra : 10;    // 预留字段
} quicklistNode;

/* quicklist 本身的结构体 */
typedef struct quicklist {
    quicklistNode *head;        // 指向头节点（ziplist）
    quicklistNode *tail;        // 指向尾节点（ziplist）
    unsigned long count;        // 所有 ziplist 中 entry 数量的总和
    unsigned long len;          // quicklistNode 节点的个数
    int fill : QL_FILL_BITS;    // 单个 ziplist 的大小限制（由 list-max-ziplist-size 配置）
    unsigned int compress : QL_COMP_BITS; // 压缩深度（由 list-compress-depth 配置，头尾不压缩的节点数）
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark *bookmarks;
} quicklist;

b) 核心设计思想：

分治思想：将一个巨大的 linkedlist 拆分存储在多个小的 ziplist 中。这限制了任何一次操作可能带来的性能影响（如连锁更新）的范围，只会发生在单个 ziplist 内。
可配置的fill参数： list-max-ziplist-size 参数决定了每个 ziplist 节点的大小。
- 正值：表示每个 ziplist 最多可包含的 entry 个数。例如 -5 表示每个 ziplist 最多 64Kb。
- 负值：表示每个 ziplist 的最大 内存大小（字节）：
  - -1: 4 Kb
  - -2: 8 Kb (Redis 默认值)
  - -3: 16 Kb
  - -4: 32 Kb
  - -5: 64 Kb
压缩功能： list-compress-depth 参数可以配置对位于中间位置的 quicklistNode 进行 LZF 算法压缩（头尾的节点不压缩，以保证高效的 push/pop 操作）。例如，设置为 1 表示头尾各有一个节点不压缩，中间的节点全部压缩。这对于非常长的列表可以节省大量内存。

二、关键操作源码分析（伪代码逻辑）

我们看看几个典型操作在 quicklist 上是如何实现的。

1. LPUSH / RPUSH (头部/尾部插入)

以 LPUSH key value 为例：

查找 Key：在全局哈希表中找到对应的 key，其值对象 robj 的 ptr 指向一个 quicklist 结构。
定位头部节点：访问 quicklist->head，找到第一个 quicklistNode。
尝试插入 Ziplist：
- 调用 quicklistPushHead(quicklist, value)。
- 该函数会检查 head 节点指向的 ziplist 是否尚未满（根据 fill 参数判断）。
- 如果未满：直接调用 ziplistPush(char *zl, char *s, unsigned int slen, int where) 函数。这个函数会在 ziplist 的头部（where=0）分配新的内存空间，写入新的 entry，并更新 zltail、zllen 等元信息。
- 如果已满：需要创建一个新的空的 quicklistNode（包含一个新的 ziplist），然后将其插入到 quicklist 的双向链表的头部，最后再将新的 value 插入到这个新节点的 ziplist 中。
更新计数：增加 quicklist->count 和 quicklist->head->count。

2. LRANGE (范围查询)

以 LRANGE key start stop 为例：

查找 Key：找到对应的 quicklist。
定位起始位置：
- 这是一个遍历过程。首先根据 start 下标找到它所在的 quicklistNode。由于每个 quicklistNode 都记录了其 ziplist 中的 entry 数量 (count)，算法可以高效地跳跃式定位，而无需遍历每一个 entry。
遍历并返回数据：
- 一旦找到起始的 quicklistNode 和其中的具体 ziplist entry，就从这个点开始，顺序遍历 ziplist 中的 entry。
- 对于每个 entry，调用 ziplistGet 函数（根据 encoding）来获取其实际的值（可能是整数或字符串）。
- 将值添加到返回给客户的数组中。
- 遍历会跨越多個 quicklistNode，直到达到 stop 下标或列表末尾。

3. LINSERT (在某个元素前/后插入)

这个操作相对低效，因为它涉及查找。

查找元素：必须遍历整个 quicklist（依次遍历每个 node 中的每个 ziplist entry）来找到目标元素 pivot。
执行插入：
- 找到目标后，确认插入位置所在的 quicklistNode (假设为 node) 和 ziplist。
- 检查 node 的 ziplist 是否已满。
- 如果未满：直接在找到的位置调用 ziplistInsert 插入新的 entry。这可能导致该 ziplist 内发生内存重分配和后续 entry 的 prevlen 更新（可能触发小范围的连锁更新）。
- 如果已满：策略会比较复杂。可能会分裂（split）当前的 ziplist：将当前 ziplist 一分为二，一个新的 quicklistNode 会被创建并插入到链表中，然后新的值插入到合适的那一半中。

总结

Redis 的 List 类型通过 quicklist 实现，是其工程智慧的杰出体现：

空间与时间的平衡：它巧妙地结合了 ziplist 省内存和 linkedlist 易更新的优点，同时规避了它们各自的极端缺点（ziplist 的连锁更新、linkedlist 的指针空间开销和内存碎片）。
高性能的核心操作：对于最常见的 push/pop 操作，它们通常发生在头部或尾部的第一个 ziplist 上，效率极高，时间复杂度是 O(1)。这与操作一个普通的双向链表无异。
可配置的策略：通过 list-max-ziplist-size 和 list-compress-depth 参数，用户可以根据实际应用场景（是偏向性能还是偏向内存）来精细调整 List 的内部行为。
分层设计：将复杂的操作分解到 quicklist 和 ziplist 两个层次，quicklist 负责宏观的链表管理和配置策略，ziplist 负责微观的、紧凑的数据存储。这种抽象使得代码更易于维护和优化。

从源码角度看，Redis 的 List 绝不是一个简单的数据结构，而是一个经过深度优化、高度适应其作为数据库和缓存场景的复杂工程实现。