跳到主要内容
锦木信息 JINMU INFO
Redis 博客
Redis · 内核内部

一边扩容,一边服务

渐进式 rehash:哈希表怎么不停服地长大

Redis 的键全放在一张巨大的哈希表(dict)里。键越来越多,这张表迟早要扩容。可"把几千万键重新摆进更大的表"要花很久——单线程的 Redis 若停下来一次性搬完,就是几秒卡死。它的解法很优雅:搬家不一次搬完,每次操作顺手挪一点。

▲ 两张表并存:每次读写顺手把一个旧桶迁到新表,rehashidx 游标前移progressive rehash
ht[0] 旧表(size 8) 0 空 1 空 2 空 3 ▶ 4 5… rehashidx = 3(已搬 0~2) 逐桶迁移 → ht[1] 新表(size 16,容量翻倍) 0 1 2 … 8 9 … 15 rehash 期间的读写规则 读/删:先查 ht[0],没有再查 ht[1] 新写入:一律放进 ht[1](旧表只减不增)
01 · 底座

一切的底座:全局哈希表

Redis 的键空间,本质就是一张大哈希表(dict):键经哈希函数(4.0 起用 SipHash,带随机种子防碰撞攻击)定位到某个桶(bucket);多个键撞进同一个桶,就用链表串起来(链地址法),新项插在链头。不只键空间——hashtable 编码的 Hash/Set、命令表、Pub/Sub 订阅表,底层都是这个 dict。

哈希表的性能命脉是负载因子 = 元素数 ÷ 桶数。因子太大,每个桶的链表变长,查找从 O(1) 退化;所以当负载因子到 1(有 fork 子进程在跑时放宽到 5,避免写时复制额外拷贝),Redis 就要扩容:新建一张约两倍大的表,把所有键重新摆进去。缩容同理,表太空时减半。

打个比方

像图书馆的书架:书越来越多,每格塞得满满当当,找书越来越慢。于是要换一排两倍长的新书架,把书重新上架。问题是——几千万本书,一次性搬完,图书馆就得闭馆好几天。

02 · 难点

一次性搬完 = 卡死全场

重新摆放是 O(N) 的:要遍历旧表每个键、重算它在新表的位置、再挂过去。几千万键,这一趟可能要几百毫秒到几秒。而 Redis 命令是单线程串行执行的——如果它停下来一口气搬完,这期间所有客户端请求全被阻塞,就是一次灾难性的延迟毛刺。

所以 Redis 绝不"stop-the-world"地 rehash。它的策略是把这趟大搬家拆成无数个微小步骤,摊到后续的每一次操作里慢慢完成——这就是渐进式(progressive / incremental)rehash。

03 · 核心机制

两张表 + 一个游标

渐进式 rehash 的全部奥秘,在于 dict 里同时存在两张表 ht[0](旧)和 ht[1](新),外加一个游标 rehashidx 记录"旧表搬到第几个桶了"。平时 rehashidx = -1 表示没在 rehash。

1

开始:建好新表

触发扩容时,给 ht[1] 分配约两倍大的空间,把 rehashidx 置为 0。此刻一个键都还没搬。

2

每次操作,顺手搬一点

之后每次对 dict 的增删改查,Redis 都顺带把 rehashidx 指向的那个(些)桶从 ht[0] 迁到 ht[1],然后 rehashidx++。把大工程分摊成"随手做的小动作"。

3

后台也帮忙推进

光靠请求驱动,冷门实例可能迟迟搬不完。所以后台定时任务(serverCron)也会主动搬一批,每次有时间上限(约 1ms),绝不长时间占用主线程。

4

搬完:两表合一

当 ht[0] 彻底空了,释放它,把 ht[1] 变成新的 ht[0],rehashidx 重置为 -1。搬家结束,一切回归单表。

04 · 过渡期的规矩

两张表并存时,读写怎么走

rehash 进行中,一个键可能在旧表、也可能已搬到新表。为保证不出错,Redis 定了几条铁律:

操作规则
查找 / 删除先查 ht[0],没找到再查 ht[1]——两张表都要照顾到
新增(写入)一律写进 ht[1](新表)。这样旧表的元素只减不增,保证 rehash 必然收敛、总能搬完
每次操作顺带迁移 rehashidx 当前的桶,推进进度
i

"新增只进新表"这条很关键:它保证了旧表的键数单调递减,rehash 不会因为边搬边塞而永远搬不完。而"读查两表",则保证了过渡期间任何键都不会因为搬到一半而丢失——不管它此刻在哪张表,都能被找到。

05 · 连带影响

它正是 SCAN "可能重复"的根源

渐进式 rehash 带来一个微妙的后果:遍历(SCAN)期间,表的大小可能正在从 8 变 16,桶的位置全在动。普通的顺序游标会在这种动态下漏键或乱套。

Redis 的解法是 SCAN 用"反向二进制"游标(高位进位):它让"已扫区"和"未扫区"的边界,在表翻倍/减半时依然清晰,从而保证"全程存在的键至少返回一次"。代价就是——同一个键可能被返回多次,所以 SCAN 的结果要按幂等处理。这正是"SCAN 为什么可能重复"那条规则的底层来历。

串起来看

渐进式 rehash 是"地基",SCAN 的游标设计是"上层建筑"。正因为底层随时可能在扩容搬家,上层的遍历才必须用那个绕来绕去的反向二进制游标,才能在"地动山摇"中不漏键。

06 · 运维视角

这对你意味着什么

要点说明
扩容几乎无感千万级键扩容也不会卡死,成本被摊薄到每次操作里——这是单线程 Redis 能平滑长大的关键之一
rehash 期间内存更高两张表同时存在,会短暂占用额外内存(最多约多一张表)。内存逼近上限时的大扩容要留意余量
fork 时暂缓扩容有 BGSAVE/AOF 重写的子进程在跑时,负载因子阈值放宽到 5,尽量不触发 rehash,避免写时复制拷贝大量页
别和"集群重分片"混淆这里的 rehash 是单实例内哈希表扩容;集群把槽在节点间搬是另一回事(MIGRATE)。两者都叫"搬",层次不同
!

一个推论:大量 key 同时过期或被删可能触发缩容 rehash;短时间灌入海量 key 会触发扩容 rehash。这些时刻内存和 CPU 都会有波动——理解了 rehash,你就能把这类"莫名的小毛刺"对上号。

收尾 · 一句话

把大搬家,拆成随手小动作

渐进式 rehash 用两张表 + 一个游标,把"给千万键换更大的哈希表"这件 O(N) 的重活,摊成每次操作顺手搬一个桶的小事,再加后台限时推进——单线程也能边扩容边服务,全程不卡。它还是 SCAN"可能重复"的根源。这正是 Redis 把复杂度藏进优雅设计的典范。

全局 dict(SipHash+链地址)· 负载因子 1(fork 时放宽到 5)触发扩容 · 两张表 ht[0]/ht[1] + rehashidx 游标 · 每次操作顺手迁一个桶 + 后台限时(~1ms)推进 · 读查两表、新写只进 ht[1](旧表只减不增,必然收敛)· SCAN 反向二进制游标正源于此

内容依据 Redis 源码实现(dict.c / dict.h)与官方资料整理 · redis.io/docs

阈值与步进细节以对应 Redis 版本的源码为准;示例表大小为说明性示意。

聊聊您的数据难题

告诉我们业务现状,资深技术顾问一对一给出选型与实施建议,咨询免费。