prevlen · 连锁更新 · backlen

listpack 与它取代的 ziplist

前两页的紧凑结构都有一项前提：元素定宽。SDS 存的是一整个字符串，intset 存的是定宽整数。可 Redis 的 list、hash、zset 装的是任意长度的字符串，长短不一的元素挨着码进一块连续内存，就得回答一个新问题：怎么知道下一个元素从哪开始。

答案只有一种形状：每个元素自带长度信息。剩下的全是细节，而这些细节里藏着一个能把插入代价推到 $O(n^2)$ 的设计错误。本页讲这个错误怎么来的，以及 listpack 怎么把它消掉。

1 · 变长元素的定位问题

ziplist 的整体布局是四段：

<zlbytes uint32> <zltail uint32> <zllen uint16> <entry> … <entry> <zlend 0xFF>

zlbytes 是整块的总字节数，zltail 是最后一个 entry 相对起点的偏移，zllen 是元素个数，zlend 是固定的 0xFF 结束 sentinel。头部 10 字节加末尾 1 字节，固定开销 11 字节。

正向遍历只需要「当前 entry 有多长」：读出长度，指针往后跳，重复。反向遍历是另一回事，而 Redis 的一大批命令都要它：RPOP 从尾部弹出，LRANGE key -3 -1 从尾部数三个，ZREVRANGE 整个是倒着扫。zltail 只解决了「跳到最后一个 entry」，从最后一个往前走还得有别的办法。

ziplist 给出的办法是让每个 entry 额外记住前一个 entry 有多长。这个字段叫 prevlen，反向遍历就是「读当前 entry 的 prevlen，把指针往前挪这么多字节」。

2 · prevlen 字段与它的变长编码

一个 ziplist entry 由 prevlen、encoding、数据三段拼成。

prevlen 是变长的：前一个 entry 短于 254 字节时用 1 字节直接存这个数；达到 254 时用 5 字节，首字节固定为 0xFE，后跟 4 字节的真实长度。分界值选 254 而不是 255，是因为 255 已经被 zlend 占去当结束 sentinel。

encoding 也是变长的，且对字符串与整数分开处理。字符串按长度分三挡：小于 64 用 1 字节（高 2 位为 00，低 6 位存长度），小于 16384 用 2 字节，再长用 5 字节。整数则一律 1 字节 encoding 加上定宽数据，宽度有 1、2、3、4、8 字节五种；而 0 到 12 这十三个值连数据都不占，ZIP_INT_IMM_MIN 是 0xf1，编码字节本身就是 0xf1 + value。

图 2-1 · 同一串元素在 ziplist 与 listpack 下的逐 entry 字节布局，每段按实际字节数成比例着色。可改元素内容，观察整数与字符串各自选中的编码档次。

两种布局的字节数差在何处，用一批小整数看得最清楚。0 到 99 这一百个元素，ziplist 编出 298 字节，listpack 编出 207 字节，少 31%。差额几乎全来自整数编码的覆盖范围：ziplist 的立即数只管 0 到 12，13 到 99 要用 ZIP_INT_8B，一个 entry 3 字节；listpack 的 LP_ENCODING_7BIT_UINT 一直管到 127，这些元素统统 2 字节。

3 · 连锁更新

现在把两个变长凑在一起看。prevlen 的宽度取决于前一个 entry 有多长，而一个 entry 的长度里包含它自己的 prevlen。这条依赖是可以传播的。

设一段 ziplist 里的 entry 长度都恰好卡在 253：prevlen 1 字节、encoding 2 字节、数据 250 字节。此时每个 entry 的 prevlen 都只要 1 字节。往头部插入一个长度达到 254 的 entry，紧随其后的那个 entry 的 prevlen 必须换成 5 字节，它自己的长度随之变成 257，也达到了 254。于是再下一个 entry 的 prevlen 也要换宽，如此传播到末尾。这就是连锁更新。

图 3-1 · 在一段等长 entry 的 ziplist 里插入一个元素，逐 entry 标出 prevlen 是否被撑宽，并给出重写字节与旧实现的搬迁总量。可改元素长度、元素个数与插入位置。

实测 100 个 250 字节元素、头部插入一个 251 字节的字符串（entry 长度恰好 254）：全部 100 个后继的 prevlen 从 1 字节涨到 5 字节，整块从 25311 字节涨到 25965 字节，其中 400 字节纯粹是 prevlen 膨胀出来的。要重写的字节是 25700，也就是插入点之后的全部内容。

真正的 $O(n^2)$ 在旧实现的做法里。Redis 6 之前的 __ziplistCascadeUpdate 逐个 entry 处理，每处理一个就 realloc 加一次尾部 memmove。按这个口径统计，同一次插入的搬迁总量是 1297850 字节：往一个 25 KB 的 ziplist 里插一个元素，搬了 1.3 MB。元素数从 100 加到 200，这个数从 1297850 涨到 5165700，比值 3.98，与平方关系吻合。

连锁的触发条件比直觉窄得多。要让第一个后继的 prevlen 撑宽，插入的 entry 必须达到 254 字节，这是一条；要让它继续传播，后继 entry 原本的长度加 4 之后也必须达到 254，也就是原长度不小于 250。原以为「元素长度接近 254 就会连锁」，实测边界只有一字节宽：元素 246 字节时 entry 长 249，加 4 是 253，连锁停在第一个后继；元素 247 字节时 entry 长 250，加 4 正好 254，波及全部 100 个。这个数字是先写了「大约 240 字节以上」再跑引擎才改过来的。

方向也有讲究。尾部追加不连锁，新 entry 后面没有东西了。中间插入只波及插入点之后，插在第 50 位时波及 50 个。删除同样会触发：__ziplistDelete 里也有一次 __ziplistCascadeUpdate 调用，删掉一个大 entry 之后，后继的 prevlen 记的数变小了，需要修正。

警示 · ziplist.c 的注释说明了一处故意的不对称：prevlen 只会被撑宽，不会被缩窄。理由是缩窄会导致 flapping——连续几次插入删除会让同一串字段反复胀缩。原文写「一个大的 prevlen 字段意味着这个 ziplist 本来就装着大 entry」，索性放着。

本系列的引擎按元素序列重新编码，算的是「新建出来的 ziplist」；真实的、被编辑过的 ziplist 会比引擎给的数偏大。删掉那个 254 字节的头 entry 之后，引擎报的字节数会掉回去，真实的不会。

4 · backlen 与反向遍历的另一种解法

listpack 换了一个字段的语义。它的 entry 布局是：

<encoding + data> <backlen>

backlen 放在 entry 末尾，记的是这个 entry 里 encoding 加数据的字节数，也就是它自己的长度减去 backlen 本身。

反向遍历照样可行，因为 backlen 用了一种可以倒着读的变长编码。lpEncodeBacklen 每字节存 7 位有效数据，高位当延续标志；关键在于字节序是反的：高位组写在前、低位组写在后，且只有第一个字节的高位标志为 0。lpDecodeBacklen 从末字节开始向左扫，读到高位为 0 的那个字节就停：

do {
    val |= (uint64_t)(p[0] & 127) << shift;
    if (!(p[0] & 128)) break;
    shift += 7;
    p--;
} while(1);

拿到 backlen 的值再加上 backlen 自身占的字节数，就是整个 entry 的长度，指针往前挪这么多即到上一个 entry。反向遍历的能力一分不少。

连锁更新则被消掉了，理由不在实现而在结构：listpack 的每个字段只描述这个 entry 自己，插入或删除一个 entry 不改变任何其他 entry 的任何字节。同一批输入实测下来，listpack 的连锁波及数恒为 0，插入后整块的字节增量恰好等于新 entry 自己的长度。

图 4-1 · 同一次插入在 ziplist 与 listpack 上的并排对照，左右各给出连锁波及数、整块字节变化与旧实现的搬迁总量。可改元素长度、元素个数与插入位置。

前面那次插入的两侧数字：插入前 listpack 反而大 96 字节，因为每个 entry 的 backlen 要 2 字节而 prevlen 只要 1 字节，一百个 entry 多一百字节，扣掉头部少的 4 字节；插入后 listpack 变成 25662 字节，比 ziplist 的 25965 小 303 字节，那 400 字节的 prevlen 膨胀在这边一分没有。

注 · lpEncodeBacklen 的分档边界是 127、16383、2097151、268435455，比 7 位对齐的 $2^{14}$ 、 $2^{21}$ 、 $2^{28}$ 各小一。于是长度恰好等于 16383 时用 3 字节而非 2 字节，多花一字节。解码端按高位标志走，多一字节照样读得对，只是白占。实测一个 16378 字节的字符串 entry 总长 16386，而 16377 字节的只要 16384：数据少一字节，总长少两字节。这条边界的来历没找到说明，看着像是把「小于」写成了「不大于」的笔误，但它不影响正确性，改了反而破坏格式兼容。

5 · 未被消除的那部分代价

listpack 消掉的是连锁，不是 $O(n)$ 。往连续内存的中间插一个元素，插入点之后的全部字节都要往后挪一格，这一次 memmove 两种布局都躲不过。消掉的是那个额外的乘数 $n$ ：连锁一次都不发生，memmove 只做一次。

Redis 7.0 把 hash、zset、list 的紧凑编码全部换成 listpack，ziplist.c 只留下 RDB 加载路径上的兼容代码——rdbLoadObject 读到旧格式的 ziplist 会当场转成 listpack。OBJECT ENCODING 从此不再返回 ziplist。

留下的问题是紧凑编码在元素多起来之后仍然要挪整块内存，无论 prevlen 还是 backlen 都不解决这一条。这就是把它切段的动机，见 quicklist：链表串起来的 listpack。

6 · 参考文献

Sanfilippo, S. listpack 规范. antirez/listpack（listpack.md）：格式定义与 backlen 的逆向解码。
Sanfilippo, S. ziplist.c. redis/src/ziplist.c（Redis 7.4）：__ziplistCascadeUpdate 及其上方注释。
Sanfilippo, S. listpack.c. redis/src/listpack.c（Redis 7.4）：lpEncodeBacklen 与 lpDecodeBacklen。
Redis. (2022). Redis 7.0 release notes：listpack 取代 ziplist 的范围与 RDB 兼容处理。