当你向 Redis 执行一条 LPUSH mylist "hello" 命令时，你有没有想过，这个 "hello" 究竟被存放在了哪里？Redis 为了让这次看似简单的操作尽可能快、尽可能省内存，在底层做了哪些令人惊叹的优化？

大多数开发者止步于 API 的使用，但真正的技术专家，善于运用第一性原理，探究其设计背后的本质。今天，我们将从最基础的数据结构和计算机体系结构出发，层层剥茧，彻底解构 Redis List 的进化史，并最终通过阅读 Redis 8.2.1 的源码，来印证我们所有的推论。

路线图

我们的探索将遵循 Redis List 自身真实的进化路径：

  1. 创世纪：linkedlist - 教科书式的完美与现实的代价。
  2. 激进探索：ziplist - 对内存的极致压榨与性能的隐患。
  3. 伟大妥协：quicklist - 平衡空间与时间的工程奇迹。
  4. 完美进化：listpack - quicklist 的新内核，理论与现实的最终统一。

1. 创世纪：linkedlist 的优雅与代价

从计算机科学的角度看，List (列表) 的最直观实现就是一个双向链表 (Doubly Linked List)。早期的 Redis (2.0时代) 正是这样做的。

第一性原理：数据结构

一个双向链表由一系列独立的节点构成，每个节点除了保存数据外，还拥有两个指针，分别指向其前驱和后继节点。

1
2
3
4
5
          +------+     +------+     +------+
... <---- | prev | <-> | prev | <-> | prev | ----> ...
          | data |     | data |     | data |
... <---- | next | <-> | next | <-> | next | ----> ...
          +------+     +------+     +------+

优点：完美的 O(1) 头尾操作

  • 在链表的头部或尾部插入/删除一个节点，只需要修改相邻的 2-3 个指针即可，这个过程消耗的时间是常数，与链表长度无关。这对于 LPUSH/RPUSH/LPOP/RPOP 这样的操作来说，是理论上最完美的数据结构。

缺点：现实世界的双重代价

  1. 高昂的内存开销：这是 linkedlist 被淘汰的首要原因。在一个 64 位系统中，一个指针占用 8 字节。这意味着每个节点，除了存储你的数据，仅 prev 和 next 两个指针就要额外消耗 16 字节！当你存储大量小数据时（比如整数），指针占用的空间会远超数据本身，这是对宝贵内存的巨大浪费。
  2. 糟糕的 CPU 缓存局部性：链表的节点在内存中是离散分布的。当 CPU 遍历链表时，它需要不断地从内存的不同区域加载节点数据，这种指针跳转的行为极易导致 CPU Cache Miss (缓存未命中)。CPU 无法有效利用其高速缓存来预读数据，导致遍历性能远不如连续内存的数组。

2. 激进探索：ziplist 对内存的极致压榨

为了克服 linkedlist 的双重代价，Redis 的设计者们创造了一种极其紧凑的数据结构：压缩列表 (ziplist)。

第一性原理：连续内存布局

ziplist 的核心思想是，用一块连续的、完整的内存块来存储所有元素，从而彻底消除指针开销，并最大化利用 CPU 缓存。

1
<zlbytes> <zltail> <zllen> <entry_1> <entry_2> ... <entry_N> <zlend>
  • <zlbytes>: 整个 ziplist 占用的总字节数。
  • <zltail>: 到最后一个 entry 的偏移量，用于快速定位到表尾。
  • <zllen>: entry 的数量。
  • <entry>: 真正的列表元素，每个 entry 也是变长的。
  • <zlend>: 特殊的结束标记 0xFF。

ziplist 的精髓在于 entry 的设计。每个 entry 的头部会记录前一个 entry 的长度 (prev-len)，这使得 ziplist 可以从后向前遍历。

优点：极致的内存效率

  • ziplist 是 Redis 为了节省内存而设计的典范。它没有指针，并对小整数和短字符串使用变长编码，是内存使用最经济的序列型数据结构。同时，连续内存对 CPU 缓存极为友好。

缺点：连锁更新 (Cascading Updates)

  • 这是 ziplist 的阿喀琉斯之踵。由于每个 entry 记录了前一个 entry 的长度，当在前一个 entry 发生大小变化时，可能会导致当前 entry 需要用更多的字节来存储 prev-len，这又可能导致当前 entry 自身总长度变化，从而级联影响到下一个 entry... 在最坏的情况下，一次插入可能导致后续所有 entry 都需要重新分配空间，时间复杂度从 O(N) 退化到 O(N2)。

3. 伟大妥协：quicklist 的平衡之道

既然 linkedlist 和 ziplist 各有优劣，能否将它们结合起来，取其精华，去其糟粕？快速列表 (quicklist) 应运而生，并从 Redis 3.2 开始成为 List 的默认实现。

第一性原理：混合数据结构

quicklist 的本质，就是一个由 ziplist（或后来的 listpack）节点组成的双向链表。

1
2
3
4
5
6
7
+----------------+     +----------------+     +----------------+
| quicklistNode  | <-> | quicklistNode  | <-> | quicklistNode  |
| (ziplist/pack) |     | (ziplist/pack) |     | (ziplist/pack) |
+----------------+     +----------------+     +----------------+
         ^                    ^                      ^
         |                    |                      |
   [ e1, e2, e3 ]       [ e4, e5 ]           [ e6, e7, e8, e9 ]

它在宏观上是一个 linkedlist，保持了 O(1) 的头尾插入性能和灵活性。而在微观上，每个节点内部是一个 ziplist 或 listpack，存储了多个元素，极大地节省了内存，并提升了缓存局部性。quicklist 通过将连锁更新的风险限制在一个个独立的小节点内部，完美地规避了 ziplist 最大的风险。

4. 完美进化：listpack 的最终形态

quicklist 已经非常优秀，但它的内核 ziplist 依然存在理论上的连锁更新风险。为了追求极致的理论完备性，Redis 开发者设计了 ziplist 的继任者：listpack。从 Redis 7.0 开始，quicklist 的内部节点默认已由 ziplist 替换为 listpack。

listpack 的目标与 ziplist 一样：用一块连续内存来存储数据。但它通过一个绝妙的设计，彻底根除了连锁更新。

第一性原理：信息自包含与回溯机制

ziplist 连锁更新的根源在于：后一个节点存储了前一个节点的信息 (prev-len)。listpack 的设计哲学是：每个节点只存储与自身相关的信息。

一个 listpack entry 的结构如下：

1
2
3
+----------------+----------------+----------------+
| encoding-type  | element-data   |    back-len    |
+----------------+----------------+----------------+

要理解 listpack 的精髓，我们必须深度剖析其灵魂设计——back-len 字段。

  • 命名：源码中称之为 backlen，它最核心的功能是用于向后 (Backward) 遍历。
  • 存储内容：back-len 字段里物理存储的数值，等于该条目自身的 <encoding-type> 和 <element-data> 两部分加起来的长度（我们称之为“部分长度”）。
  • 作用：当需要从后向前遍历时，解析器会从前一个条目的尾部，反向解析出这个“部分长度”，然后再动态计算出 <back-len> 字段自身的长度，两者相加得到前一个条目的总长度，从而实现精确的回溯跳转。

源码佐证：lpPrev 函数及其"秘术" (Redis 8.2.1)

让我们直接阅读 Redis 8.2.1 版本的 listpack.c 源码，看看 lpPrev 函数是如何实现回溯的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* from: https://github.com/redis/redis/blob/8.2.1/src/listpack.c */
unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
    assert(p);

    /* 边界检查：如果已经是第一个元素，无法再回溯 */
    if (p-lp == LP_HDR_SIZE) return NULL;

    /* 关键一步(1)：从当前条目p的开头，后退一字节，来到前一个条目的末尾 */
    p--; 

    /* 关键一步(2)：从前一个条目的末尾，反向解析出其“部分长度” */
    uint64_t prevlen = lpDecodeBacklen(p);

    /* 关键一步(3)：计算<back-len>字段自身的长度，并加到“部分长度”上，得到“总长度” */
    prevlen += lpEncodeBacklenBytes(prevlen);

    /* 关键一步(4)：执行跳转。p指针当前在前一个条目的末尾，
     * 回退 (总长度 - 1) 的距离，就来到了前一个条目的开头 */
    p -= prevlen-1; 
    
    lpAssertValidEntry(lp, lpBytes(lp), p);
    return p;
}

要完全看懂这段代码，我们必须潜入它调用的两个核心函数：lpDecodeBacklen 和 lpEncodeBacklenBytes。

lpDecodeBacklen - 优雅的"盲人摸象"

lpDecodeBacklen 的任务是，在不知道 <back-len> 字段有多长的情况下，从它的最后一个字节开始，反向、完整地把它读出来。这是如何做到的？答案是可变长度整数编码。

<back-len> 的每个字节中，最高位 (MSB) 是一个"延续位"：

  • MSB = 1：表示"我不是开头，前面还有字节"。
  • MSB = 0：表示"我就是开头，到我为止"。

lpDecodeBacklen 的算法就像“盲人摸象”，但极其高效：

  1. 从 p 指针（前一个条目的末尾）开始，读取 1 个字节。
  2. 检查它的最高位。如果是 0，说明 <back-len> 只有 1 字节长，其余 7 位就是长度值，任务完成。
  3. 如果是 1，说明这是多字节长度的一部分，记下其余 7 位，然后 p--，继续向前读下一个字节，重复此过程，直到找到那个最高位为 0 的“领头”字节。
  4. 最后，将所有收集到的 7 位数据块拼接起来，还原出完整的“部分长度”。

以下是 lpDecodeBacklen 的核心源码片段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* from: https://github.com/redis/redis/blob/8.2.1/src/listpack.c */
static inline uint64_t lpDecodeBacklen(unsigned char *p) {
    uint64_t val = 0;
    uint64_t shift = 0;
    do {
        /* 从 p 指针开始，向低地址（左）移动 */
        val |= (uint64_t)(p[0] & 127) << shift;
        /* 如果最高位是 0，表示这是最后一个字节，循环终止 */
        if ((p[0] & 128) == 0) break;
        shift += 7;
        p--;
        /* 安全检查，防止无限循环 */
        if (shift > 63) return UINT64_MAX;
    } while(1);
    return val;
}

lpEncodeBacklenBytes - 未卜先知的计算

lpPrev 在得到"部分长度" prevlen 后，还需要知道 <back-len> 字段本身占了几个字节，才能算出总长度。lpEncodeBacklenBytes 的作用就是回答这个问题。

它的逻辑很简单，就是一系列的范围判断，这正是可变长度整数编码的逆过程。

1
2
3
4
5
6
7
8
/* from: https://github.com/redis/redis/blob/8.2.1/src/listpack.c */
static inline uint64_t lpEncodeBacklenBytes(uint64_t len) {
    if (len < 128) return 1;
    else if (len < 16384) return 2;
    else if (len < 2097152) return 3;
    else if (len < 268435456) return 4;
    else return 5;
}

例如，如果 lpDecodeBacklen 返回的 prevlen 是 100，lpEncodeBacklenBytes(100) 就会返回 1。lpPrev 随即将两者相加得到总长度 101，完成最终的回溯跳转。

结论：永不休止的优化之路

Redis List 的演进史，是软件工程领域追求极致性能和效率的缩影：

  1. linkedlist：一个优雅的理论起点，但在现实的内存和 CPU 面前显得脆弱。
  2. ziplist：一次激进的、向内存效率极限发起的冲锋，但留下了性能抖动的隐患。
  3. quicklist：一次伟大的工程妥协，在宏观与微观层面取得了精妙的平衡，成为稳定服务多年的基石。
  4. listpack：一次对理论完美的最终追求，通过改变节点内部的信息记录方式，彻底根除了历史遗留问题，让 List 的实现达到了新的高度。

作为 Redis 的使用者，我们享受着 LPUSH/RPOP 的简洁与高效。但作为技术的探索者，我们更应欣赏这背后长达十余年的、对每一个字节、每一次 CPU 缓存命中、每一种风险场景的极致思考与打磨。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~