dict.c · rehashidx · 尾延迟

渐进式 rehash：Redis 的双表

一次性 rehash 的问题不在总量而在形状：负载因子与扩容 §3 的实测里，10 万次插入摊还每次 2.97 次写入，最贵的那一次却写了 98305 次。对吞吐无所谓，对尾延迟是灾难——Redis 是单线程的，那一次 rehash 期间整个进程什么都干不了。

Redis 的 dict.c 给出的答案是把这一坨代价切碎：扩容时只分配新表，一个 key 也不搬；此后每次读写各搬一格，让旧表在正常流量里自己排空。

1 · 双表与一个游标

结构上只多了两样东西：ht[1]（rehash 期间的新表）与 rehashidx（下一个待搬的旧表槽号， $-1$ 表示不在 rehash）。

图 1-1 · 8 槽的 dict 手动走完一次扩容。可点「开始扩容」只建表不搬，再逐槽搬迁，中途插入新 key 或查找任意 key，观察它落在哪张表。

三条规则合起来保证了正确性与终止性：

定义 1.1（渐进式 rehash 的三条规则） 查找要查两张表——key 可能还没搬过去，只查 ht[0] 会漏。插入一律进 ht[1]——若新 key 还能进旧表，旧表就永远搬不空。每次读写附带搬一个非空槽，搬完即 ht[1] 升为 ht[0]、旧表释放、rehashidx 复位。

第三条是全部的要点：搬一个槽就是搬一整条链，链长期望是 $\alpha$ ，与表有多大无关。所以单次操作的额外代价是 $O(\alpha)$ 而非 $O(n)$ 。

Redis 7 的 dictFind 里还有一句省事的优化：落在 rehashidx 之前的槽已经搬空，那些下标不必再查 ht[0]——

for (table = 0; table <= 1; table++) {
    idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
    if (table == 0 && (long)idx < d->rehashidx) continue;
    /* 沿这条链比较 */
    if (!dictIsRehashing(d)) return NULL;
}

末尾那句 if (!dictIsRehashing(d)) return NULL; 同样重要：不在 rehash 时根本不碰 ht[1]，于是这套双表机制对绝大多数请求是零开销的。

2 · 单次峰值与总搬迁量

图 2-1 · 同一串插入分别走一次性与渐进式 rehash，每次操作搬走的 key 数（两图共用同一条对数纵轴）。下方是分位数对照与各 rehash 阶段的明细。可改插入次数。

从 $m = 4$ 起插入 4096 个 key，扩容阈值 $\alpha \ge 1$ 的实测：一次性 rehash 的单次峰值是 2048（容量 2048 翻到 4096 那一次），渐进式的单次峰值是 6——降了三百四十倍。而两者的总搬迁量完全相同，因为该搬的 key 一个都没少。

那个 6 值得解释： $\alpha$ 阈值是 1，链长的期望就是 1，泊松分布下最长的链在 4096 个 key 的规模上是 6 左右（见链地址法 §2）。换句话说，渐进式 rehash 的单次峰值等于当时的最长链长，而最长链只随 $n$ 以 $\log n / \log\log n$ 的速度增长。表从四千涨到四千万，峰值也只从 6 涨到 9 上下。

3 · 正常流量自己就把它推完了

原先以为这套机制需要一个后台任务来兜底，实测发现在持续写入下并不需要。

4096 次插入触发了 10 次扩容，每一次的搬迁都在下一次扩容到来之前干净地结束了：

起始于第几次插入	新表容量	持续多少次操作	单步峰值
129	256	81	4
257	512	163	4
513	1024	327	4
1025	2048	634	6
2049	4096	1316	6

规律很整齐：容量 $m$ 的表大约有 $m/2$ 个非空槽（ $\alpha = 1$ 时空槽占 $1/e$ ），每次操作搬一个非空槽，于是搬完要约 $m/2$ 次操作；而下一次扩容要等到 key 数再翻一倍，即再来 $m$ 次插入。 $m/2 < m$ ，永远追得上。

代价藏在另一个数字里：这 4096 次操作中有 63.3% 处于「两张表并存」的状态。也就是说大部分时间里，一次未命中的查找要走两条链而不是一条。渐进式 rehash 不是免费的，它把「少数操作付出巨大代价」换成了「多数操作各付出一点」。对 Redis 这种单线程、以 p99 为生命线的服务，这笔交易划算；对一个批处理程序，一次性 rehash 反而更快。

那个后台任务确实存在，但用途不同。server.c 的 databasesCron 会调 incrementallyRehash，针对的是没有流量的 dict：一个数据库刚扩容完就再无请求，旧表会一直挂着占内存。有流量时它几乎无事可做。

4 · 两处必须暂停的时刻

dict.c 里有两个开关会让 rehash 停下来，理由都不在算法本身。

其一是 fork。Redis 做 RDB 快照或 AOF 重写时 fork 出子进程，父子共享物理内存页，走 copy-on-write。rehash 会大规模改写内存，每改一页就复制一页，子进程存盘期间父进程的内存占用可能翻倍。所以 dictExpandIfNeeded 在有子进程时把扩容阈值从 1 提到 5——不是禁止扩容，而是把它推迟到实在装不下为止。

其二是迭代器。dictScan 遍历期间表结构不能乱动，否则会漏元素或重复返回。Redis 的做法很有意思：它不禁止 rehash，而是设计了一种反向二进制迭代的游标，使得即便遍历途中发生了扩容或缩容，已返回的元素也不会重复、未返回的不会遗漏（可能重复返回的只是 rehash 期间新旧表都扫到的那部分，规范允许）。这是 SCAN 命令能做到「不阻塞且保证覆盖」的基础。

5 · 参考文献

Redis. src/dict.c：dictRehash、dictRehashStep、dictExpandIfNeeded、dictScan。
Redis. src/server.c：databasesCron 中的 incrementallyRehash。
Redis 文档. SCAN 命令的保证与 cursor 语义（反向二进制迭代）。
Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed., §17). MIT Press.