Redis渐进式rehash
Redis渐进式rehash
渐进式 rehash 是 Redis 为了避免在扩容或收缩哈希表（Dict）时导致服务器“卡死”而设计的一种高明策略。
如果 Redis 像传统方式那样一次性完成百万级键值的搬迁，会导致主线程长时间阻塞，对于追求高并发、低延迟的 Redis 来说，这显然是不可接受的。
1. 核心数据结构
在 Redis 的字典结构中，实际上维护了两个哈希表：
- ht[0]：平时使用的哈希表。
- ht[1]：只在 rehash 期间使用的哈希表（通常大小是 ht[0] 的两倍）。
2. 搬迁过程：化整为零
核心思想：将巨大的计算成本，平摊到了每一次请求和后台空闲时间中。这避免了集中式处理带来的长耗时，保证了 Redis 的 响应时间 始终保持在极低水平。
Redis 不会一次性把 ht[0] 的所有数据搬到 ht[1]，而是采取了“分而治之”的办法：
触发式搬迁
每当客户端对该字典执行 添加、删除、查找或更新 操作时，Redis 除了执行指定操作外，还会顺带将 ht[0] 在 rehashidx 索引上的所有键值对搬迁到 ht[1]。
定时同步
即便没有客户端访问，Redis 也会利用 定时任务，在系统空闲时主动搬迁一部分数据，确保 rehash 最终能完成。
3. rehash的触发条件
在 Redis 中，rehash 的触发主要取决于负载因子（Load Factor）。负载因子的计算公式非常简单：
$$\text{Load Factor} = \frac{\text{ht[0].used}}{\text{ht[0].size}}$$
即：已保存节点的数量与哈希表大小的比值
3.1 扩容（Expand）的触发条件
Redis 会根据当前是否在执行后台指令，采取不同的扩容阈值：
- 常规状态：当负载因子 $\ge 1$ 时，Redis 可能会触发扩容
- 强制状态：当负载因子 $> 5$ 时，无论是否有后台进程，Redis 都会立即开始扩容（因为出现hash冲突时使用拉链法解决，所以实际保存的节点数可能会超过哈希表大小）
3.2 为什么有两个标准？
这涉及到 Redis 的 Copy-On-Write (COW) 机制。当 Redis 正在执行 BGSAVE（生成 RDB 快照）或 BGREWRITEAOF（AOF 重写）时，会创建子进程。
- 为了尽可能减少父子进程间的内存页写入，Redis 会提高扩容门槛（从 1 提升到 5）。
- 这样可以避免在子进程工作期间发生大规模的内存地址变动，从而节省系统内存并提高效率。
3.3 收缩（Shrink）的触发条件
当数据库中的键值对大量减少时，为了不浪费内存，Redis 会对哈希表进行收缩。
- 触发条件：当负载因子 $< 0.1$ 时（即已用空间不足 10%），Redis 会自动开始收缩操作。
3.4 rehash 的空间分配规则
无论是扩容还是收缩，新哈希表 ht[1] 的大小都是有讲究的：
- 如果是扩容：
ht[1]的大小为第一个大于等于ht[0].used * 2的 $2^n$。- 例如：当前用了 100 个空间，扩容大小就是 $2^8 = 256$
- 如果是收缩：
ht[1]的大小为第一个大于等于ht[0].used的 $2^n$。- 例如：当前只剩 10 个键，收缩大小就是 $2^4 = 16$
4. rehash 的详细步骤
⚠️：图中ht[1]大小应为16，即首个大于2 * 6 = 12 的2次幂
- 分配空间：为
ht[1]分配空间：- 如果是扩容，大小通常是第一个大于等于
ht[0].used * 2的 $2^n$（首个大于已使用空间两倍的2次幂）； - 如果是收缩，则是第一个大于等于
ht[0].used的 $2^n$（首个大于已使用空间的2次幂）
- 如果是扩容，大小通常是第一个大于等于
- 设置索引：将变量
rehashidx设置为 0，代表 rehash 正式开始。 - 分步搬迁：
- 每次操作字典，将
ht[0]中rehashidx索引位置上的桶（Bucket）移动到ht[1]。 - 搬迁完成后，
rehashidx自增 1。
- 每次操作字典，将
- 完成收尾：当
ht[0]的所有数据都迁移到ht[1]后，将rehashidx设为 -1。释放ht[0]，将ht[1]设置为新的ht[0]，并创建一个空的ht[1]为下次做准备。
5. rehash 期间的特殊行为
在搬迁过程中，字典处于一个“过渡状态”，其行为如下：
- 查找操作：程序会先在
ht[0]找，如果没找到，再去ht[1]找。 - 添加操作：所有新键值对一律直接插入
ht[1]。这样可以保证ht[0]的数据只减不增，直到变空。 - 删除/更新：同样会在两个表上进行，确保数据一致性。