# 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;
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,按如下步骤进行:
- 新建哈希表
ht[1]
,大小为ht[0]
的 2 倍。 - 标记进入 rehash 状态(
dict->rehashidx = 0
)。 - 后续操作逐步迁移数据:
- 每次对
dict
进行增、删、改、查时,额外迁移ht[0]
的少量数据到ht[1]
。 - 迁移的 单位 是若干个哈希桶,而非单个键。
- 每次对
- 迁移完成后,
ht[1]
替换ht[0]
,rehashidx
设为 -1,完成 Rehash。
# 4. 渐进式 Rehash 示例
假设 ht[0]
存在 4 个桶,开始扩容:
ht[0]: [A] -> [B] -> [C] -> [D] # 旧哈希表
ht[1]: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] # 新哈希表(2 倍大小)
2
- 第一次操作时,迁移
ht[0][0]
到ht[1]
。 - 第二次操作时,迁移
ht[0][1]
到ht[1]
。 - 依次进行,直到
ht[0]
为空,完成 Rehash。
# 🔹 常见错误
误以为 Redis 扩容是一次性完成的:
实际上是渐进式迁移,避免 Redis 停顿,保持低延迟。误解负载因子规则:
used / size > 1
时触发扩容,但如果有 BGSAVE,负载因子需达 5 才会扩容。
误以为查询操作不受影响:
在渐进式 Rehash 期间,查询可能同时访问ht[0]
和ht[1]
,未迁移的数据仍在ht[0]
,需要查询两个表。
# 🔹 最佳实践
避免频繁扩容
- 预估 Redis 哈希表大小,初始化时指定合适
size
,减少扩容次数。 - 使用
hash-max-ziplist-entries
控制小哈希表存储优化。
- 预估 Redis 哈希表大小,初始化时指定合适
优化查询
- 在 Rehash 过程中,查询会访问
ht[0]
和ht[1]
,为了降低影响,尽量减少哈希表操作。
- 在 Rehash 过程中,查询会访问
高并发优化
- 在数据量较大时,避免 Redis 在 BGSAVE 期间进行哈希表扩容,可手动调整扩容策略:
CONFIG SET hash-max-ziplist-entries 512
1
- 在数据量较大时,避免 Redis 在 BGSAVE 期间进行哈希表扩容,可手动调整扩容策略:
# 🔍 深入追问
为什么 Rehash 采用 “渐进式” 而不是 “一次性” 完成?
- 避免单次大规模数据迁移造成 Redis 线程阻塞,影响 QPS 和响应时间。
- 通过 增量迁移 方式,在正常请求处理中分批完成哈希表扩容,提高实时性。
如果在 Rehash 过程中新增键,存放在哪个哈希表?
- 迁移前的键仍在
ht[0]
,迁移后的键在ht[1]
,新增的键只会存入ht[1]
,保证一致性。
- 迁移前的键仍在
Rehash 过程如何影响 Redis 读写性能?
- 读操作可能需要访问
ht[0]
和ht[1]
,影响查询效率。 - 写入新键不会影响 Rehash,但扩容期间会有额外的迁移消耗。
- 读操作可能需要访问
# 相关面试题
- Redis Hash 何时从 ZipList 结构切换为哈希表?
- 渐进式 Rehash 的迁移步长如何调整?
- Redis 如何避免 Rehash 期间的阻塞?
- Rehash 过程中如何保证数据一致性?
- Redis 采用单线程模型,为什么还能高效进行 Rehash?