走进Redis的渐进式Rehash

Redis 的渐进式 Rehash 是一种避免一次性大规模数据迁移导致服务阻塞的优化机制，主要用于哈希表（Hash Table）的扩容（rehash）和缩容操作。它的核心思想是将耗时的 rehash 过程分散到多次请求中逐步完成，从而保证 Redis 服务的响应性。

​​一、为什么需要渐进式 Rehash？​​

1. ​​背景问题​​
   Redis 的哈希表（如字典 dict）是核心数据结构，当元素数量增加时，需要扩容（rehash）以减少哈希冲突；当元素减少时，需要缩容以节省内存。
   ​​一次性 Rehash 的问题​​：如果哈希表非常大（例如百万级键值），一次性迁移所有键值会阻塞主线程，导致 Redis 服务暂停响应。

2. ​​渐进式 Rehash 的优势​​

   • ​​非阻塞​​：将 Rehash 分散到多次操作中，每次只迁移少量数据，避免长时间阻塞。
   • ​​平滑过渡​​：在 Rehash 期间，Redis 仍能正常处理读写请求，保证高可用性。

​​二、Rehash 触发条件​​

Redis 的哈希表（dict）会在以下情况触发 Rehash：

1. ​​扩容​​：当哈希表的负载因子（元素数量 / 哈希桶数量）超过 1（默认阈值）时，触发扩容（通常是翻倍）。
2. ​​缩容​​：当负载因子低于 0.1 时，触发缩容（通常是减半）。

​​三、渐进式 Rehash 的过程​​

​​1. 初始化阶段​​

• 当需要 Rehash 时，Redis 会创建一个新的哈希表（ht[1]），大小为原哈希表（ht[0]）的两倍（扩容）或一半（缩容）。
• 设置 rehashidx = 0，表示从 ht[0] 的第一个桶开始迁移。

​​2. 渐进式迁移​​

• ​​每次操作附带迁移​​：在 Redis 执行命令（如 GET、SET、HGET 等）时，会顺带迁移 ht[0] 中的一部分数据到 ht[1]。
• ​​迁移步骤​​：
  每次迁移一个哈希桶（bucket）中的所有键值对。例如，首次迁移 ht[0] 的第 0 号桶，第二次迁移第 1 号桶，依此类推。
• ​​更新 rehashidx​​：每迁移完一个桶，rehashidx 递增，直到所有桶迁移完成（rehashidx == ht[0].size）。

​​3. 完成 Rehash​​

• 当所有桶迁移完成后，Redis 将 ht[1] 设为新的主哈希表（ht[0] = ht[1]），并释放旧的 ht[0]。
• 此时，Rehash 结束。

​​四、Rehash 期间的数据访问​​

在渐进式 Rehash 过程中，Redis 需要同时处理旧表（ht[0]）和新表（ht[1]）的读写操作：

1. ​​查找操作​​：
   • 先在 ht[0] 的当前 rehashidx 范围内查找，如果未找到，则到 ht[1] 中查找。

   // 伪代码示例
   def get(key):
       if rehashing:
           idx = dict_rehashidx(d)
           bucket = &d->ht[0].table[idx]
           while (bucket->used > 0) {
               if (key matches) return value;
               bucket++;
           }
           // 如果旧表未找到，转向新表
           return lookup_in_ht1(key);
       else:
           return lookup_in_ht0(key);

2. ​​写入操作​​：
   • 直接写入 ht[1]，保证新数据不会丢失。
3. ​​删除操作​​：
   • 需同时在 ht[0] 和 ht[1] 中删除（如果存在）。

​​五、关键细节​​

1. ​​Rehash 索引 (rehashidx)​​

   • 记录当前迁移进度，初始为 0，完成时为 ht[0].size。
   • 可通过 INFO keyspace 命令查看 rehashidx 的值（例如 dict_rehashidx:0 表示正在 Rehash）。

2. ​​强制触发 Rehash​​
   可以通过 SHUTDOWN SAVE 或 CONFIG SET active-defrag yes 强制触发 Rehash，但需谨慎使用。

3. ​​性能影响​​

   • 渐进式 Rehash 会略微增加每个请求的处理时间（因为需要同时处理迁移），但避免了阻塞。
   • 在极端情况下（如海量数据），Rehash 可能持续较长时间，但整体影响可控。

​​六、示例流程​​

假设 ht[0] 有 4 个桶，需要扩容到 8 个桶：

1. 初始化 ht[1]（8 个桶），设置 rehashidx = 0。
2. 处理第一个请求时，迁移 ht[0] 的第 0 号桶。
3. 处理第二个请求时，迁移 ht[0] 的第 1 号桶。
4. 重复上述步骤，直到 rehashidx = 4，表示迁移完成。
5. 释放 ht[0]，ht[1] 成为主表。

​​七、总结​​

• ​​渐进式 Rehash​​ 是 Redis 为避免大规模数据迁移导致阻塞而设计的优化机制。
• ​​核心过程​​：分批次迁移哈希桶，每次操作附带迁移一部分数据。
• ​​优点​​：保证服务不中断，适用于高并发场景。
• ​​代价​​：迁移期间每个操作略微变慢，但整体性能影响可接受。

通过这种设计，Redis 在保证高性能的同时，能够安全地处理哈希表的动态扩缩容。