listpack 与 ziplist：级联更新灾难与修复

第六章：listpack 与 ziplist——级联更新灾难与修复

6.1 ziplist 完整字节布局

ziplist 是 Redis 在小对象阶段用于存储 Hash、List、ZSet 的内存格式，设计目标是让所有数据紧凑地存放在一块连续内存中，避免指针开销。

6.1.1 整体结构

+----------+----------+--------+---------+-----+---------+--------+
| zlbytes  |  zltail  | zllen  | entry1  | ... | entryN  | zlend  |
|  4 bytes |  4 bytes | 2 bytes|         |     |         | 1 byte |
+----------+----------+--------+---------+-----+---------+--------+

字段含义：

在 ziplist.c 中，访问字段的宏定义如下：

#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

6.1.2 Entry 内部结构

每一个 entry 的布局：

+-------------+----------+------+
| prevrawlen  | encoding | data |
+-------------+----------+------+

prevrawlen（前一个 entry 的长度）：

这是 ziplist 最关键也是最危险的字段。它记录前一个 entry 的总字节数，用于支持从后向前遍历（RPOP 等操作需要找到前一个 entry）。

如果前一个 entry 长度 < 254 字节：
  prevrawlen = 1 字节，直接存储长度值

如果前一个 entry 长度 >= 254 字节：
  prevrawlen = 5 字节：
    第1字节固定为 0xFE（254）
    后4字节存储实际长度（小端序）

encoding 字段（区分整数和字符串）：

字符串编码：
  00xxxxxx  — 长度 0~63 的字符串，6bit 存长度，1字节 encoding
  01xxxxxx xxxxxxxx  — 长度 0~16383 的字符串，14bit 存长度，2字节 encoding
  10000000 [4字节长度] — 长度 0~2^32-1 的字符串，5字节 encoding

整数编码：
  11000000  — int16，2字节数据
  11010000  — int32，4字节数据
  11100000  — int64，8字节数据
  11110000  — int24，3字节数据
  11111110  — int8，1字节数据
  1111xxxx  — 0~12 的极小整数，直接存在 encoding 低4位（xxxx-1）

一个存储整数 12345 的 entry 示意：

prevrawlen=0x05   encoding=0xC0(int16)   data=0x3039(12345 LE)
[05] [C0] [39 30]

6.1.3 内存布局完整示例

存储两个字段的 Hash（{"name": "Alice", "age": "30"}），ziplist 内存如下：

偏移  字节内容                        含义
0000  0E 00 00 00                     zlbytes = 14（整个 ziplist 14字节，仅示意）
0004  08 00 00 00                     zltail = 8（最后 entry 从偏移8开始）
0008  02 00                           zllen = 2（2个 entry）
000A  00 06 41 6C 69 63 65            entry1: prevrawlen=0, enc=0x06(str 6byte?), "Alice"
...   ...                             entry2: prevrawlen=7, enc=..., "30" or int 30
...   FF                              zlend

6.2 级联更新灾难

6.2.1 问题的根源

ziplist 的 prevrawlen 字段是整个结构中最危险的设计。考虑以下场景：

entry1[253 bytes] → entry2[...] → entry3[...] → ...

此时 entry2 的 prevrawlen 只需要 1 字节（存储 253）。

现在将 entry1 扩展到 254 字节（例如追加一个字符）：

entry1[254 bytes] → 其后所有 entry 需要更新 prevrawlen！

entry2 的 prevrawlen 必须从 1 字节扩展为 5 字节（存储 254 需要 0xFE + 4 字节）。这让 entry2 自身的长度增加了 4 字节，从而触发 entry3 也必须更新它的 prevrawlen……

6.2.2 最坏情况分析

场景：1000 个 entry，每个正好 253 字节
      │
      ▼
修改 entry1，使其从 253 字节变成 254 字节
      │
      ▼
entry2 的 prevrawlen：1字节 → 5字节，entry2 总长 = 253+4 = 257字节
      │
      ▼
entry3 的 prevrawlen 需要存 257：1字节 → 5字节，entry3 总长 = 257
      │
      ▼
entry4 的 prevrawlen 需要存 257：已经是5字节，不变（级联终止！）

等等——实际上级联终止得比较快，因为一旦某个 entry 的 prevrawlen 已经是 5 字节，后续就不再触发。真正糟糕的情况是：

所有 entry 原来大小恰好让相邻 entry 的 prevrawlen 在临界值来回波动

__ziplistCascadeUpdate 函数的时间复杂度：

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    while (p[0] != ZIP_END) {
        zipEntry(p, &cur);
        rawlen = cur.headersize + cur.len;
        rawlensize = zipStorePrevEntryLength(NULL, rawlen);

        if (p[rawlen] == ZIP_END) break;
        zipEntry(p + rawlen, &next);

        if (next.prevrawlen == rawlen) break;  // 无需更新，终止

        if (next.prevrawlensize < rawlensize) {
            // prevrawlen 需要从1字节扩展到5字节
            offset = p - zl;
            extra = rawlensize - next.prevrawlensize;
            zl = ziplistResize(zl, curlen + extra);  // 重新分配内存！
            p = zl + offset;
            // ... 移动数据，更新所有偏移量
        }
        // 继续下一个 entry
        p += rawlen;
    }
    return zl;
}

真实性能影响：

测试环境：1000 个 253 字节的 entry，触发级联更新
操作耗时：约 2.3ms（单线程，Redis 被阻塞 2.3ms）
同等场景无级联更新：0.01ms

级联更新导致 QPS 抖动：P99 延迟从 0.5ms 升至 3ms+

6.2.3 内存重分配的代价

每次 prevrawlen 从 1 字节变成 5 字节，都需要调用 ziplistResize 重新分配整个 ziplist 的内存（因为是连续内存块）。1000 个 entry 级联更新 = 最多 1000 次 realloc，每次移动的数据量越来越少，但 CPU 缓存失效、内存碎片等问题持续存在。

6.3 listpack：彻底消除级联更新

6.3.1 设计哲学

Redis 5.0 引入 listpack，Redis 7.0 正式替换所有使用 ziplist 的场景。核心改动只有一个：取消 prevrawlen，改用 backlen。

backlen 放在 entry 末尾，存储当前 entry 的总字节数（不含 backlen 本身）。

ziplist entry:  [prevrawlen][encoding][data]         前向依赖，危险！
listpack entry: [encoding][data][backlen]            自包含，安全！

从后向前遍历时：

// listpack 的后退遍历（lp.c）
unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
    // 读取 p 之前位置的 backlen
    uint64_t prevlen = lpDecodeBacklen(p - 1);  // 从末尾字节读取
    // 跳过整个前一个 entry
    return p - prevlen - lpEncodeBacklen(NULL, prevlen);
}

6.3.2 listpack 整体布局

+-------------+--------------+----------+--------+--------+------+
| total-bytes | num-elements | element1 |  ...   | elemN  | end  |
|   4 bytes   |   2 bytes    |          |        |        | 0xFF |
+-------------+--------------+----------+--------+--------+------+

6.3.3 element 内部结构

+----------+------+---------+
| encoding | data | backlen |
+----------+------+---------+

encoding 字段的 bit 复用设计（精妙之处）：

高位 bit 模式          含义                      数据大小
─────────────────────────────────────────────────────────
0xxxxxxx               7bit 无符号整数 (0-127)    0字节（值在 encoding 内）
10xxxxxx               6bit 字符串长度 (0-63)     0-63字节
110xxxxx xxxxxxxx      13bit 有符号整数            0字节（值在 encoding 内）
11110001               16bit 有符号整数            2字节
11110010               24bit 有符号整数            3字节
11110011               32bit 有符号整数            4字节
11110100               64bit 有符号整数            8字节
11110000               12bit 字符串长度            需 1 额外字节（共12bit）
11111110               8bit 有符号整数             1字节
1111xxxx (x≠1111)      4bit 无符号整数 (0-15)      0字节
11110001               32bit 字符串长度            需 4 额外字节

backlen 字段的变长编码：

元素总字节数 ≤ 127：    backlen = 1字节
元素总字节数 ≤ 16383：  backlen = 2字节（最高位设1）
元素总字节数 ≤ 2097151：backlen = 3字节
...以此类推（类似 LEB128 倒序编码）

6.3.4 listpack 核心 C 代码

// lp.c — 创建空 listpack
unsigned char *lpNew(size_t capacity) {
    unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ?
                                  capacity : LP_HDR_SIZE+1);
    if (lp == NULL) return NULL;
    lpSetTotalBytes(lp, LP_HDR_SIZE+1);
    lpSetNumElements(lp, 0);
    lp[LP_HDR_SIZE] = LP_EOF;  // 0xFF
    return lp;
}

// 读取 backlen（从 entry 末尾字节往前读）
static inline uint64_t lpDecodeBacklen(unsigned char *p) {
    uint64_t val = 0;
    uint64_t shift = 0;
    do {
        val |= (uint64_t)(p[0] & 127) << shift;
        if (!(p[0] & 128)) break;  // 最高位为0表示最后一个字节
        shift += 7;
        p--;
    } while (shift < 28);
    return val;
}

6.4 listpack vs ziplist 内存对比

6.4.1 100 个 "hello:world" 键值对的对比

测试数据：100 个 key-value 对
key = "hello:XXXX"（10字节），value = "world:XXXX"（10字节）

ziplist 内存布局：
  Header: 4+4+2 = 10 字节
  每个 entry（key）: prevrawlen(1) + encoding(1, 6bit str) + data(10) = 12字节
  每个 entry（val）: prevrawlen(1) + encoding(1) + data(10) = 12字节
  200 个 entry: 200 × 12 = 2400 字节
  zlend: 1 字节
  总计: 2411 字节

listpack 内存布局：
  Header: 4+2 = 6 字节
  每个 element（key）: encoding(1, 6bit str) + data(10) + backlen(1) = 12字节
  每个 element（val）: encoding(1) + data(10) + backlen(1) = 12字节
  200 个 element: 200 × 12 = 2400 字节
  end: 1 字节
  总计: 2407 字节

差异：listpack 节省 4 字节（Header 更紧凑）
主要优势不在内存，而在：消除级联更新风险

6.4.2 整数场景下的优势

存储 100 个整数值（0-127 范围）：

ziplist 每个 entry：
  prevrawlen(1) + encoding(1, 1111xxxx) + data(0) = 2字节

listpack 每个 element：
  encoding(1, 0xxxxxxx) + backlen(1) = 2字节

相同！但 listpack 的 backlen 是自包含的，修改任意元素不影响邻居。

6.5 listpack 的升级阈值

Redis 7.0+ 中，以下数据类型在小对象时使用 listpack，超过阈值则升级：

Hash：
  hash-max-listpack-entries  128   (元素数量)
  hash-max-listpack-value    64    (字段/值的最大字节数)
  升级目标：hashtable（两个 dict + 链地址法）

ZSet：
  zset-max-listpack-entries  128
  zset-max-listpack-value    64
  升级目标：skiplist + hashtable

List：
  list-max-listpack-size     -2    (即每个 quicklistNode 不超过 8KB)
  list-max-ziplist-size      -2    (旧配置名，已废弃)
  升级目标：quicklist（双端链表，每个节点是 listpack）

升级是单向的——一旦超过阈值，Redis 不会自动降级回 listpack（即使你删除了部分元素）。

6.6 listpack 对遍历的影响

6.6.1 正向遍历

// 获取下一个 element（正向）
unsigned char *lpNext(unsigned char *lp, unsigned char *p) {
    // 跳过当前 element 的 encoding+data+backlen
    p = lpSkip(p);
    if (p[0] == LP_EOF) return NULL;
    return p;
}

// lpSkip：计算当前 element 占用的总字节数
unsigned char *lpSkip(unsigned char *p) {
    unsigned long entrylen = lpCurrentEncodedSizeBytes(p);  // encoding+data
    entrylen += lpEncodeBacklen(NULL, entrylen);             // +backlen 字节数
    p += entrylen;
    return p;
}

6.6.2 反向遍历（与 ziplist 的根本差异）

ziplist 反向遍历：读取 prevrawlen → 向前跳 prevrawlen 字节
  问题：依赖前一个 entry 的信息（耦合）

listpack 反向遍历：读取 backlen → 向前跳 backlen+backlen_size 字节
  优点：每个 element 自包含，修改任意 element 不影响邻居

6.7 Redis 7.0 迁移细节

Redis 7.0 使用以下方式完成迁移：

// object.c — 将旧的 ziplist 格式转换为 listpack
robj *hashTypeConvertZiplist(robj *o, int enc) {
    if (enc == OBJ_ENCODING_LISTPACK) {
        unsigned char *zl = o->ptr;
        unsigned char *lp = ziplistToListpack(zl);
        // ...
        o->ptr = lp;
        o->encoding = OBJ_ENCODING_LISTPACK;
    }
    // ...
}

RDB 文件格式也相应变化：新增 RDB_TYPE_HASH_LISTPACK（16）、RDB_TYPE_ZSET_LISTPACK（17）、RDB_TYPE_LIST_LISTPACK（18）类型码，与旧的 ziplist 类型码区分。

6.8 小结

listpack 的核心创新在于：将描述前一个节点的信息（prevrawlen）替换为描述当前节点自身的信息（backlen），这一字段位置的改变从根本上切断了级联更新的传播链。