动态数组与紧凑编码 · 从摊还扩容到 listpack

地基：一块内存装不下之后

成倍扩容让 $n$ 次 push 的总搬迁量停在 $O(n)$。倍数取 2 还是 1.5 不只是常数之争——2 倍的容量阶梯是 2 的幂，前面所有已释放的块加起来永远差一块装不下下一次分配；1.5 倍从第 6 次分配起就能吃回自己扔掉的内存。

1.5 倍的复用论证有前提

folly 的 fbvector 选 1.5 而非 2，公开论据是内存复用：倍数小于黄金分割 $\varphi \approx 1.618$ 时，此前释放的块合起来迟早装得下下一次分配，倍数为 2 则永远差一块。这个论证成立的前提是分配器会把相邻的空闲块合并成一整块。 实践中这个前提未必满足。jemalloc 与 tcmalloc 对中小尺寸走 size class 分桶，同一桶内的空闲块不与邻桶合并；大尺寸走 mmap，回收后归还给内核而不是留在堆里。所以「1.5 倍能复用旧块」更接近 dlmalloc 那类会合并空闲块的分配器上的结论。本系列的引擎只判前缀和够不够（见 扩容的摊还与增长因子 §3），判不了分配器肯不肯合并。

摊还与增长因子 · 延伸阅读

• folly · FBVector 设计说明 github.com 1.5 倍增长的原始论证：为什么 2 倍永远无法复用此前释放的内存块，以及 relocation 与 std::vector 的差异。
• std::vector — cppreference cppreference.com 标准只规定 push_back 的摊还常数复杂度，不规定增长因子；libstdc++ 用 2，MSVC STL 用 1.5。
• 摊还分析讲义 · Brown CS cs.brown.edu 聚合法、记账法、势能法三种手法，动态数组的成倍扩容与缩容滞后是标准例题。
• jemalloc(3) jemalloc.net size class 的划分方式。要判断「释放的旧块能否被复用」，绕不开分配器怎么分桶与合并。

紧凑：把结构信息压进字节流

SDS 用三个头部字段换来 $O(1)$ 取长度与二进制安全，再按长度分五档头部把开销压到 1 字节；intset 用定宽整数数组换来二分查找；ziplist 与 listpack 则把变长元素挨个码进一块内存。三者的共同代价是「每个元素得自带多少描述」，而这一笔账的算法决定了插入是 $O(1)$ 还是 $O(n^2)$。

紧凑编码的适用边界

连续字节块省的是指针与元数据，不是数据本身。一个 dict entry 要 key 指针、value 指针、next 指针加桶数组的份额，几十字节起步；listpack 的一个 entry 可以只要 2 字节。元素少时这笔差价是数量级的。 但它同时把查找从 $O(1)$ 变成 $O(n)$ 的顺序扫描，把插入从 $O(1)$ 变成整块 memmove。判据因此是元素个数的绝对值而非渐近复杂度：几十个元素扫一遍还没有一次 cache miss 贵，几千个就完全不同。Redis 的各个 *-max-listpack-entries 定在 128 到 512 之间，量级正是从这里来的。

Redis 紧凑编码 · 一手实现

• redis/src/sds.h github.com 五种头部的 struct 定义与 sdslen / sdsavail 的分派；sdshdr5 的注释直言它「从不被使用」，只是记录布局。
• redis/src/sds.c github.com _sdsMakeRoomFor 的贪心预分配：1 MB 以下翻倍、以上定量加 1 MB，以及头部换档时为何不能用 realloc。
• redis/src/intset.c github.com intsetUpgradeAndAdd 的从尾向头重排，以及为什么触发升级的值一定落在两端。
• redis/src/ziplist.c github.com __ziplistCascadeUpdate 与它前面那段注释——连锁更新的成因，以及「缩回去会导致 flapping，故意不做」的取舍。
• redis/src/listpack.c github.com lpEncodeBacklen 的五档变长编码与逆向解码，以及 listpack 的十种元素编码。
• listpack 规范 · antirez github.com listpack 的格式说明书，含 backlen 为何要从高位往低位写才能反向读。

组合：链表分段与编码切换

紧凑编码在元素多起来之后会崩：一次插入要挪整块内存。quicklist 的解法是把它切段再用链表串起来，也就是展开链表的工业形态。至于什么时候该切换，Redis 把判据做成了七八个配置项，而它们的出厂值与常见说法出入不小。

出厂值与常见说法的出入

「hash 超过 128 个字段转 hashtable」「list 超过 128 个元素转 quicklist」这两句在中文资料里很常见，但对 Redis 7.x 都不成立。config.c 里 hash-max-listpack-entries 的出厂值是 512（128 是 Redis 6 及更早 hash-max-ziplist-entries 的值），list-max-listpack-size 的出厂值是 -2——负数表示按字节封顶，-2 对应 8 KB，与元素个数无关。 实测口径见 编码切换的阈值 §3：item-0 到 item-829 这 830 个短字符串的 listpack 是 8197 字节，刚过 8192，于是转 quicklist；829 个则是 8187 字节，仍是 listpack。同一批数据换成长一点的元素，临界点就落在几十个上。

quicklist 与编码切换 · 延伸阅读

• redis/src/quicklist.c github.com _quicklistNodeAllowInsert 的准入判据、optimization_level 五档字节上限，以及 LZF 压缩节点的两端豁免。
• Redis · Memory optimization redis.io 官方的紧凑编码调参指南：各阈值的含义、调大之后的 CPU 代价，以及为什么不建议无限调高。
• OBJECT ENCODING — Redis 命令手册 redis.io 各类型可能返回的编码名，以及 listpack 取代 ziplist 之后旧名的兼容处理。
• redis/src/t_list.c github.com listTypeTryConvertQuicklist：list 是唯一会从 quicklist 转回 listpack 的类型，判据取上限的一半。