一边扩容,一边服务
Redis 的键全放在一张巨大的哈希表(dict)里。键越来越多,这张表迟早要扩容。可"把几千万键重新摆进更大的表"要花很久——单线程的 Redis 若停下来一次性搬完,就是几秒卡死。它的解法很优雅:搬家不一次搬完,每次操作顺手挪一点。
一切的底座:全局哈希表
Redis 的键空间,本质就是一张大哈希表(dict):键经哈希函数(4.0 起用 SipHash,带随机种子防碰撞攻击)定位到某个桶(bucket);多个键撞进同一个桶,就用链表串起来(链地址法),新项插在链头。不只键空间——hashtable 编码的 Hash/Set、命令表、Pub/Sub 订阅表,底层都是这个 dict。
哈希表的性能命脉是负载因子 = 元素数 ÷ 桶数。因子太大,每个桶的链表变长,查找从 O(1) 退化;所以当负载因子到 1(有 fork 子进程在跑时放宽到 5,避免写时复制额外拷贝),Redis 就要扩容:新建一张约两倍大的表,把所有键重新摆进去。缩容同理,表太空时减半。
像图书馆的书架:书越来越多,每格塞得满满当当,找书越来越慢。于是要换一排两倍长的新书架,把书重新上架。问题是——几千万本书,一次性搬完,图书馆就得闭馆好几天。
一次性搬完 = 卡死全场
重新摆放是 O(N) 的:要遍历旧表每个键、重算它在新表的位置、再挂过去。几千万键,这一趟可能要几百毫秒到几秒。而 Redis 命令是单线程串行执行的——如果它停下来一口气搬完,这期间所有客户端请求全被阻塞,就是一次灾难性的延迟毛刺。
所以 Redis 绝不"stop-the-world"地 rehash。它的策略是把这趟大搬家拆成无数个微小步骤,摊到后续的每一次操作里慢慢完成——这就是渐进式(progressive / incremental)rehash。
两张表 + 一个游标
渐进式 rehash 的全部奥秘,在于 dict 里同时存在两张表 ht[0](旧)和 ht[1](新),外加一个游标 rehashidx 记录"旧表搬到第几个桶了"。平时 rehashidx = -1 表示没在 rehash。
开始:建好新表
触发扩容时,给 ht[1] 分配约两倍大的空间,把 rehashidx 置为 0。此刻一个键都还没搬。
每次操作,顺手搬一点
之后每次对 dict 的增删改查,Redis 都顺带把 rehashidx 指向的那个(些)桶从 ht[0] 迁到 ht[1],然后 rehashidx++。把大工程分摊成"随手做的小动作"。
后台也帮忙推进
光靠请求驱动,冷门实例可能迟迟搬不完。所以后台定时任务(serverCron)也会主动搬一批,每次有时间上限(约 1ms),绝不长时间占用主线程。
搬完:两表合一
当 ht[0] 彻底空了,释放它,把 ht[1] 变成新的 ht[0],rehashidx 重置为 -1。搬家结束,一切回归单表。
两张表并存时,读写怎么走
rehash 进行中,一个键可能在旧表、也可能已搬到新表。为保证不出错,Redis 定了几条铁律:
| 操作 | 规则 |
|---|---|
| 查找 / 删除 | 先查 ht[0],没找到再查 ht[1]——两张表都要照顾到 |
| 新增(写入) | 一律写进 ht[1](新表)。这样旧表的元素只减不增,保证 rehash 必然收敛、总能搬完 |
| 每次操作 | 顺带迁移 rehashidx 当前的桶,推进进度 |
"新增只进新表"这条很关键:它保证了旧表的键数单调递减,rehash 不会因为边搬边塞而永远搬不完。而"读查两表",则保证了过渡期间任何键都不会因为搬到一半而丢失——不管它此刻在哪张表,都能被找到。
它正是 SCAN "可能重复"的根源
渐进式 rehash 带来一个微妙的后果:遍历(SCAN)期间,表的大小可能正在从 8 变 16,桶的位置全在动。普通的顺序游标会在这种动态下漏键或乱套。
Redis 的解法是 SCAN 用"反向二进制"游标(高位进位):它让"已扫区"和"未扫区"的边界,在表翻倍/减半时依然清晰,从而保证"全程存在的键至少返回一次"。代价就是——同一个键可能被返回多次,所以 SCAN 的结果要按幂等处理。这正是"SCAN 为什么可能重复"那条规则的底层来历。
渐进式 rehash 是"地基",SCAN 的游标设计是"上层建筑"。正因为底层随时可能在扩容搬家,上层的遍历才必须用那个绕来绕去的反向二进制游标,才能在"地动山摇"中不漏键。
这对你意味着什么
| 要点 | 说明 |
|---|---|
| 扩容几乎无感 | 千万级键扩容也不会卡死,成本被摊薄到每次操作里——这是单线程 Redis 能平滑长大的关键之一 |
| rehash 期间内存更高 | 两张表同时存在,会短暂占用额外内存(最多约多一张表)。内存逼近上限时的大扩容要留意余量 |
| fork 时暂缓扩容 | 有 BGSAVE/AOF 重写的子进程在跑时,负载因子阈值放宽到 5,尽量不触发 rehash,避免写时复制拷贝大量页 |
| 别和"集群重分片"混淆 | 这里的 rehash 是单实例内哈希表扩容;集群把槽在节点间搬是另一回事(MIGRATE)。两者都叫"搬",层次不同 |
一个推论:大量 key 同时过期或被删可能触发缩容 rehash;短时间灌入海量 key 会触发扩容 rehash。这些时刻内存和 CPU 都会有波动——理解了 rehash,你就能把这类"莫名的小毛刺"对上号。
把大搬家,拆成随手小动作
渐进式 rehash 用两张表 + 一个游标,把"给千万键换更大的哈希表"这件 O(N) 的重活,摊成每次操作顺手搬一个桶的小事,再加后台限时推进——单线程也能边扩容边服务,全程不卡。它还是 SCAN"可能重复"的根源。这正是 Redis 把复杂度藏进优雅设计的典范。
