# Redis 的哈希表扩容(渐进式 Rehash)过程

# 标准答案

Redis 的哈希表(dict)采用渐进式 Rehash(Progressive Rehash)机制,在扩容或缩容时避免一次性重分配导致的卡顿。具体过程是:创建新的哈希表 ht[1],逐步将 ht[0] 中的数据迁移到 ht[1],每次 Redis 处理数据时都会迁移少量键值对,直到迁移完成后 ht[1] 替换 ht[0],这样保证了扩容不会影响 Redis 的高性能响应。

# 答案解析

# 🔹 核心原理

Redis 使用 字典(dict) 存储许多键值对数据(如普通 KV、Hash 类型字段等)。底层基于 哈希表 实现,并采用 动态扩容与渐进式 Rehash 机制,以优化哈希冲突和内存利用率。

# 1. 哈希表的基本结构

Redis 字典 dict 由两个哈希表 ht[0]ht[1] 组成:

typedef struct dictht {
    dictEntry **table;  // 哈希桶数组(存储链表的指针)
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 掩码,用于计算索引
    unsigned long used; // 当前已使用的桶数量
} dictht;
1
2
3
4
5
6
  • table: 指向哈希桶数组,每个桶存储一个链表(解决哈希冲突)。
  • size: 哈希桶的总数(总是 2^n)。
  • sizemask: 计算哈希索引的掩码 index = hash & sizemask
  • used: 当前存储的键值对数量。

Redis 采用 拉链法 解决哈希冲突,多个键可能落在同一个桶里,以链表存储。

# 2. 触发哈希表扩容

Redis 哈希表会动态扩容,当满足以下条件之一时触发扩容:

  • 负载因子 > 1 且 Redis 不是 BGSAVE/BGREWRITEAOF(正常模式)。
  • 负载因子 > 5(强制模式,在 BGSAVE/REWRITE 时仍然扩容)。

    负载因子 = used / size,衡量哈希表的稀疏程度。

扩容后,哈希桶的数量 size 变为 原来的 2 倍,减少哈希冲突,提高查询效率。

# 3. 渐进式 Rehash 过程

如果一次性迁移所有数据,会导致卡顿。因此 Redis 采用 渐进式 Rehash,按如下步骤进行:

  1. 新建哈希表 ht[1],大小为 ht[0]2 倍
  2. 标记进入 rehash 状态dict->rehashidx = 0)。
  3. 后续操作逐步迁移数据
    • 每次对 dict 进行增、删、改、查时,额外迁移 ht[0] 的少量数据到 ht[1]
    • 迁移的 单位 是若干个哈希桶,而非单个键。
  4. 迁移完成后ht[1] 替换 ht[0]rehashidx 设为 -1,完成 Rehash。

# 4. 渐进式 Rehash 示例

假设 ht[0] 存在 4 个桶,开始扩容:

ht[0]:  [A] -> [B] -> [C] -> [D]   # 旧哈希表
ht[1]:  [ ]  [ ]  [ ]  [ ]  [ ]  [ ]  [ ]  [ ]   # 新哈希表(2 倍大小)
1
2
  • 第一次操作时,迁移 ht[0][0]ht[1]
  • 第二次操作时,迁移 ht[0][1]ht[1]
  • 依次进行,直到 ht[0] 为空,完成 Rehash。

# 🔹 常见错误

  1. 误以为 Redis 扩容是一次性完成的
    实际上是渐进式迁移,避免 Redis 停顿,保持低延迟。

  2. 误解负载因子规则

    • used / size > 1 时触发扩容,但如果有 BGSAVE,负载因子需达 5 才会扩容。
  3. 误以为查询操作不受影响
    在渐进式 Rehash 期间,查询可能同时访问 ht[0]ht[1],未迁移的数据仍在 ht[0],需要查询两个表。

# 🔹 最佳实践

  1. 避免频繁扩容

    • 预估 Redis 哈希表大小,初始化时指定合适 size,减少扩容次数。
    • 使用 hash-max-ziplist-entries 控制小哈希表存储优化。
  2. 优化查询

    • 在 Rehash 过程中,查询会访问 ht[0]ht[1],为了降低影响,尽量减少哈希表操作。
  3. 高并发优化

    • 在数据量较大时,避免 Redis 在 BGSAVE 期间进行哈希表扩容,可手动调整扩容策略:
      CONFIG SET hash-max-ziplist-entries 512
      
      1

# 🔍 深入追问

  1. 为什么 Rehash 采用 “渐进式” 而不是 “一次性” 完成?

    • 避免单次大规模数据迁移造成 Redis 线程阻塞,影响 QPS 和响应时间。
    • 通过 增量迁移 方式,在正常请求处理中分批完成哈希表扩容,提高实时性。
  2. 如果在 Rehash 过程中新增键,存放在哪个哈希表?

    • 迁移前的键仍在 ht[0],迁移后的键在 ht[1],新增的键只会存入 ht[1],保证一致性。
  3. Rehash 过程如何影响 Redis 读写性能?

    • 读操作可能需要访问 ht[0]ht[1],影响查询效率。
    • 写入新键不会影响 Rehash,但扩容期间会有额外的迁移消耗。

# 相关面试题

  • Redis Hash 何时从 ZipList 结构切换为哈希表?
  • 渐进式 Rehash 的迁移步长如何调整?
  • Redis 如何避免 Rehash 期间的阻塞?
  • Rehash 过程中如何保证数据一致性?
  • Redis 采用单线程模型,为什么还能高效进行 Rehash?