Java八股文面试网 – Java2Top.cn

# 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？

← 10. 跳表（SkipList）的时间复杂度与实现细节？ →