Redis渐进式rehash原理：从双哈希表到延迟尖刺的排查实践

先说我前阵子处理过的线上问题。某个Redis实例平时p99延迟稳定在几百微秒，晚高峰却突然出现了几次上百毫秒的尖刺，慢查询日志一片空白，大key扫描也没发现问题。查到最后，真正的原因既不是慢命令也不是网络抖动，而是主键空间的dict在做渐进式rehash。很多业务同学听到这个结论是懵的——rehash不是内部机制吗？怎么会影响线上延迟？这恰恰说明，Redis里最基础的dict结构，以及它那套渐进式迁移的设计，远比表面看起来更有讲究。

这篇文章我就围绕dict的渐进式rehash原理展开，把双哈希表结构、触发条件、迁移路径、遍历兼容这些核心细节一次讲透。适合想深入理解Redis内部实现的研发同学，也适合排查过莫名延迟尖刺、想搞清楚"为什么Redis扩容不会卡死"的人。文章里涉及的计算和结论，我会尽量用一线排查时的视角来描述。

1. 为什么Redis的哈希表扩容必须"一点点来"

1.1 单线程事件循环下的再哈希代价

Redis的主线程是单线程事件循环，所有命令都在这一个线程里执行。这意味着任何一个命令的耗时都会被后续命令排队等待，直接影响整体延迟分布。哈希表扩容这种操作，天然是O(n)的：要申请一块更大的桶数组，把所有已存在的entry重新计算哈希索引，再迁移过去，最后释放旧桶数组。如果这一整套动作放在一次事件循环里完成，n一旦上百万，就是几十毫秒甚至上百毫秒的停顿。

几十毫秒是什么概念？对于正常的Redis实例，p99延迟通常要求在几毫秒以内，晚高峰每秒几万次操作，一次80ms的停顿意味着大量请求排队超时、客户端连接堆积，甚至触发上游熔断。所以Redis不能采用"一次性rehash"这种简单粗暴的做法，必须把把rehash的工作量打散到多次操作里，这就是渐进式rehash的由来。

1.2 一次性迁移百万个entry的账本

很多人低估了迁移的耗时，以为就是搬指针。实际上每个entry迁移都要做一次完整的哈希计算，Redis从4.0开始使用SipHash-2-4作为默认哈希函数，它在短key上大约需要几十纳秒。再加上取模、链表头插、指针赋值这些操作，一个entry的迁移成本大概在50到80纳秒。

我做过一个粗略估算：假设主键空间有800万个key，负载因子达到扩容阈值，需要把table从2^23扩容到2^24。一次性迁移800万entry，按每entry 60纳秒计算，就是480毫秒。换句话说，如果Redis采用阻塞式扩容，线上会出现半秒级别的“假死”，这对任何业务都是灾难。

渐进式rehash的本质，就是用"时间换延迟"：把480毫秒的集中开销，摊到数百万次命令操作和数百个定时任务周期里，让每次事件循环只付出纳秒或微秒级的代价，对p99延迟的影响几乎不可感知。理解了这一点，再看dict的双表设计和rehashidx字段，逻辑就非常顺了。

2. dict的内存布局与触发策略

2.1 双哈希表结构与迁移状态机

dict的核心结构非常精简，主要有两个哈希表和一个迁移索引。以常见版本为参考，简化后的定义大致如下：

typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; // 拉链法解决冲突 } dictEntry; typedef struct dictht { dictEntry **table; // 桶数组，每个桶是链表头 unsigned long size; // 桶的数量，始终是2的幂 unsigned long sizemask; // size - 1，用来快速计算索引 unsigned long used; // 已使用的entry数量 } dictht; typedef struct dict { dictht ht[2]; // 两张哈希表，rehash期间同时存在 long rehashidx; // -1表示没有在rehash，否则表示迁移进度 // 省略type、privdata等字段 } dict;

平时只有ht[0]在工作，ht[1]是空的。一旦需要扩容或缩容，Redis会为ht[1]分配目标大小的桶数组，然后把rehashidx从-1改成0，表示从ht[0]的第0个桶开始迁移。每迁移完一个桶，rehashidx就加1。当rehashidx推进到ht[0]的size，且ht[0].used变成0时，说明全部entry都搬完了，此时释放ht[0]的桶数组，把ht[0]整体切换成ht[1]，ht[1]重置为空表，rehashidx回到-1。这就是完整的迁移状态机。

2.2 负载因子阈值与扩容/缩容的决策逻辑

哈希表不能无限增长，但也不能频繁扩容。Redis对扩容和缩容的触发条件有明确的数值控制，核心指标是负载因子（load factor），即used / size。

为什么Redis把正常扩容阈值设为1而不是Java HashMap常用的0.75？因为Redis采用拉链法解决冲突，桶数组里存的是链表头指针，负载因子为1时平均每个桶只有1个entry，查找时平均只需比较1次，性能完全可接受。把阈值设高一点，能减少扩容次数，降低内存峰值和迁移频率。这是典型的“用一点链表遍历成本，换更少的扩容开销”的权衡。

缩容条件值得单独说。Redis不会在每次删除后就缩容，而是等到used降到size的10%以下，由定时任务统一处理。这样设计是为了避免“扩容-删除-缩容-再插入-再扩容”的抖动。比如一个dict曾经有100万entry，扩容到2^20大小，后来删到只剩8万，此时才触发缩容，缩容到2^17左右。这个10%的阈值在源码里是HASHTABLE_MIN_LOAD_FACTOR，是个经典的滞回区间设计。

2.3 与RDB/AOF持久化的协同约束

渐进式rehash还有一个很微妙的协同对象，就是RDB持久化和AOF重写。Redis在生成RDB快照或执行AOF重写时，通常通过fork子进程来实现。fork之后，父子进程共享物理内存页，依靠操作系统的写时复制（COW）机制来隔离。

如果这个期间主进程还在rehash，问题就来了：rehash会不断写入新桶数组、搬动entry指针，这些写操作会让对应的内存页在父子进程间分裂，造成RSS快速增长。在极端情况下，内存占用可能翻倍，甚至触发OOM。所以Redis在BGSAVE和BGREWRITEAOF执行期间，会把全局变量dict_can_resize置为0，暂停大部分扩容。但暂停扩容又会带来哈希冲突链变长的问题，于是Redis又设了一道强制阈值：即使dict_can_resize为0，只要负载因子达到5，就必须扩容。这是"内存安全优先，但也不能让查询退化成链表遍历"的底线。

3. 渐进式rehash的运作机制拆解

3.1 一次命令迁移一个bucket是怎么回事

渐进式rehash的核心入口是dictRehash函数，它接收一个参数n，表示本次最多迁移多少个桶。实际命令路径上触发的是dictRehashStep，它每次只调用dictRehash(d, 1)，也就是最多迁移一个桶。简化后的逻辑如下：

int dictRehash(dict *d, int n) { int empty_visits = n * 10; // 最多跳过多少个空桶 while (n-- && d->ht[0].used != 0) { while (d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; // 当前桶是空的，直接跳过 if (--empty_visits == 0) return 1; // 空桶太多，先返回 } dictEntry *de = d->ht[0].table[d->rehashidx]; while (de) { dictEntry *next = de->next; uint64_t h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; // 头插法放入新桶 d->ht[0].used--; d->ht[1].used++; de = next; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } if (d->ht[0].used == 0) { zfree(d->ht[0].table); // 旧表空了，释放 d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; // 迁移完成复位 return 0; } return 1; }

这里有几个容易被忽略的细节。第一，empty_visits = n * 10这个限制很关键：如果rehashidx前面恰好遇到连续空桶，不可能让一次调用无限往后扫空桶，那会白白消耗CPU。所以一次调用最多跳过10n个空桶，扫到空桶太多就提前返回，等下个操作继续。第二，rehash是按"桶"为粒度迁移的，一个桶里可能有多个entry（链上的都一起搬），所以一次dictRehashStep实际迁移的entry数量取决于冲突链长度，平均是1个左右。第三，迁移完成后ht[0].used归零才释放旧表，保证迁移期间旧数据完全可读。

3.2 定时任务如何兜底推进

光靠命令触发的dictRehashStep还不够。设想一个场景：一个大dict刚触发扩容，rehashidx指向0，但接下来的业务主要是读多写少，每次读操作虽然也会触发dictRehashStep，可如果读命令频率不高，迁移进度会非常慢。更糟的是，读操作频繁访问的key已经被搬到ht[1]，旧表里大量桶一直没迁，两张表就这么一直并存，内存白花。

为此，Redis的定时任务serverCron在每次事件循环周期里会调用incrementallyRehash，用时间预算来推进迁移。核心是dictRehashMilliseconds，它设定一个目标时间上限，比如1毫秒，在这个预算内反复调用dictRehash，直到预算耗尽或迁移完成。默认hz配置是10，所以每秒最多有10次机会，每次最多1毫秒，理论上每秒最多花10毫秒在rehash上。

这就是渐进式rehash的完整双引擎：高频但低量的命令触发，加上低频但批量更大的定时任务兜底。一条命令只搬一个桶，几乎不增加单次请求延迟；定时任务则保证没有人访问的dict也能最终完成迁移，不会出现"永远迁不完"的僵尸状态。

3.3 增删改查在rehash中间的完整路径

rehash进行中，同一个key可能还在ht[0]，也可能已经搬到了ht[1]。Redis对四种操作的路径设计得非常清晰：

• 查找：先查ht[0]，没找到再查ht[1]。查找路径上会顺带触发一次dictRehashStep，所以读操作也在为迁移出力。
• 插入：新key一律写入ht[1]。因为ht[0]还在旧size下，如果插入ht[0]，之后还得再搬一次，直接写ht[1]可以保证每个entry最多被迁移一次。
• 删除：先删ht[0]，再删ht[1]，两个表都要检查。
• 更新：查找到entry后直接改value指针，不涉及表结构移动。

这里有一个很优雅的性质：因为新插入的key只进ht[1]，ht[0]的used只会减少不会增加，所以迁移总是有终结的——只要不断有操作推进rehashidx，ht[0].used最终会归零。这也解释了为什么rehash的完成条件只看ht[0].used == 0，不用额外追踪新插入的key。我在看这段源码时，觉得这个"老表只出不进"的约定是整个设计的点睛之笔。

4. 遍历、扫描与迭代器的配合关系

4.1 SCAN游标的反向二进制进位原理

渐进式rehash把迁移打散之后，一个棘手的问题是遍历：如果用普通的index++方式从头扫ht[0]，扫到一半发现key已经被搬到ht[1]怎么办？漏数据是绝对不行的。Redis的SCAN命令之所以能在rehash期间保证"从遍历开始到结束这一时间段内存在的key不遗漏"，靠的是游标按反向二进制进位递增的算法。

游标从一个二进制数v开始，每次迭代后按这个规则更新：

v |= ~m0; // m0是旧表的sizemask v = rev(v); // 把v的二进制位反转 v++; v = rev(v); // 再次反转回来

直观理解是：游标不是从低地址往高地址线性推进，而是从"最高位方向"动态变化。扩容时，旧表的一个桶会对应新表的两个桶（因为size翻倍，多出来一个低位bit决定去哪个新桶），反向进位能保证：当游标扫到旧表的某个桶时，它在新表中对应的两个桶都已经或者将要被访问到，顺序安排得严丝合缝。这个算法的数学性质是：在表从N扩容到2N的过程中，旧桶和新桶的访问顺序始终满足"不会出现某个已迁移元素被跳过"的条件。代价是可能返回重复元素，所以官方文档明确说SCAN允许重复，但不允许遗漏已存在元素。实际使用时，如果业务对重复key敏感，客户端需要自己做去重。

4.2 迭代器计数与rehash暂停的条件

和SCAN的巧妙兼容不同，dict的普通迭代器走的是另一套逻辑。dict里有个iterators计数器，调用dictGetIterator或dictGetSafeIterator创建迭代器时会加1，释放时减1。而dictRehashStep开头就有个判断：

static void dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d, 1); }

也就是说，只要存在活跃的迭代器，命令触发的渐进rehash就会暂停。原因很实际：迭代器是按桶index遍历的，如果遍历过程中entry被搬到另一张表，迭代器会漏数据。Redis宁可暂停迁移，也要保证这些遍历结果的准确性。SCAN不需要暂停是因为它的游标算法本身就兼容rehash，而普通迭代器没有这个能力。

这个细节顺带解释了一个真实的坑：如果某个模块或Lua脚本里长期持有一个大的hash对象迭代器，那这个dict的rehash会被卡住，内存一直维持双表状态。我遇到过类似场景，排查半天才发现是某个扩展模块在遍历一个上百万字段的hash时没有及时释放迭代器，导致内存异常上涨。在高负载实例上，任何长期持有的迭代器都是潜在的rehash"刹车"。

5. 边界条件、观测手段与工程避坑

5.1 rehash过程的异常与临界场景

渐进式rehash整体设计非常稳健，但有几个临界场景值得记住。

• 大量空桶导致的迁移空转：上面提到empty_visits限制，就是防止迁移在高负载因子低的表上空转。但这也意味着，如果一张表负载因子极低（比如删了大量key后还没来得及缩容），rehash会以非常慢的速度前进。这就是为什么缩容的判断阈值是10%，而不是等used归零。
• 从listpack升级到hashtable的瞬间：Redis的hash类型对象，在字段数少于512且每个字段长度较短时，使用的是紧凑的listpack编码。一旦超过阈值，Redis需要把整个listpack一次性转换成dict。这次转换不是渐进式的，是一次性O(n)操作。好在listpack最大也就512个字段，一次转换通常不到1毫秒，普通业务感知不到。但如果你有大量刚好超过阈值的hash对象，这里会形成一次集中的CPU消耗。
• 内存峰值：迁移期间，ht[0]和ht[1]的桶数组同时存在。比如一个2^23大小的桶数组是64MB，扩容到2^24后新桶数组128MB，迁移完成的瞬间会释放旧表，峰值内存比正常多出旧表的大小。如果旧表很大，RSS会出现明显的“凸起”，容易被误判为内存泄漏。

5.2 如何确认实例正在rehash以及影响评估

排查延迟问题时，怎么确认实例真的在rehash？我常用的手段是DEBUG HTSTATS命令。对主键空间执行：

redis-cli debug htstats 0

输出里会给出ht[0]和ht[1]的桶数、entry数、冲突链分布，以及关键的一行Rehashing: 1或Rehashing: 0。如果正在rehash，还能看到rehashidx推进的位置，配合前后两次执行可以算出迁移速度。另一个观察点是MEMORY STATS里的overhead.hashtable.main和overhead.hashtable.expires，rehash期间这一项会比平时高，因为两张表的桶数组都算在hashtable开销里。

评估影响时，把它和慢查询日志、大key扫描结果对照。如果延迟尖刺的时间点与DEBUG HTSTATS显示rehash正在进行的时段吻合，且当时内存RSS有明显上升，基本可以断定延迟来自rehash。这种问题通常不需要干预，等迁移完成就自动恢复。但如果是大dict反复扩容缩容造成的周期性抖动，就要从业务侧减少key的剧烈波动，比如避免一次性灌入海量key随后又大批量删除。

5.3 从dict学到的几条工程原则

看完整个dict的渐进式rehash设计，我觉得它对日常后端开发有不少可迁移的启示。

第一，大任务的分片粒度要结合调用频率。Redis把rehash分成"每条命令搬一个桶"和"定时任务跑1毫秒预算"两个引擎，前者利用高频调用天然分散成本，后者保证低活跃状态也能推进。我们在做数据迁移、批量任务分片时，可以借鉴这种“请求路径顺带干活 + 后台定时兜底”的双通道模式。

第二，迁移方向要让增量数据只走新路。rehash期间新插入只进ht[1]，保证旧表只减不增，迁移必然收敛。很多双写迁移方案中，如果新旧两路都允许写入，就难以判断什么时候可以安全切换。Redis这个"新数据只写新表"的思路，可以直接套用到自己的双写演进设计里。

第三，哈希函数的随机化不是可选项。Redis在4.0改用SipHash并加入每个进程随机生成的密钥，是为了抵御哈希碰撞攻击：攻击者如果知道哈希函数，可以构造大量同hash的key，把哈希表查询退化成O(n)链表遍历，瞬间打垮Redis。这是很多自研哈希表容易忽略的安全维度。

另外，关于看源码的方法论，我自己的体会是：先看数据结构字段，再看负载因子的数值，最后才看循环代码。dict结构里ht[2]和rehashidx两个字段，已经透露了80%的设计意图。数值阈值（1、5、10%）则藏着作者对性能和内存之间的取舍判断。真正理解这些，比背下来几个函数名有用得多。

回到文章开头的那个实例：确认了rehash之后，我没有做任何干预，只是观察了二十分钟，等迁移自然完成，延迟尖刺消失。之后我养成了一个习惯，排查Redis延迟问题的时候，除了慢查询和大key，一定会顺手看一眼rehash状态。这个内部机制平时安静得让人察觉不到，但它确实是Redis能在单线程下支撑超高吞吐的重要基石。如果你也想彻底搞懂手上的中间件，从dict的渐进式rehash开始，是个性价比很高的切入点。