为什么要渐进式rehash?
在Redis中,哈希表是实现快速键值对查找的关键数据结构,但随着数据的增加,哈希表可能会因为冲突过多或空间不足而需要扩容;相反,当数据大量删除后,哈希表也可能因为空间利用率过低而需要缩容。在扩容和缩容过程中,由于长度变化会导致key的索引变化,为了避免一次性rehash操作带来的长时间阻塞和性能影响,Redis采用了渐进式rehash策略。
渐进式rehash的基本原理
- 分步迁移:渐进式rehash不是一次性将所有键值对从旧哈希表迁移到新哈希表,而是将这个迁移过程分散到多个时间片中,每次只迁移一小部分数据。
- 双哈希表:在rehash过程中,Redis会同时使用两个哈希表(通常称为ht[0]和ht[1]),其中ht[0]是原始哈希表,ht[1]是新分配的哈希表(容量更大或更小)。
- 逐步迁移:在Redis处理客户端请求的过程中,每次操作前都会检查是否需要执行rehash。如果需要,就会从ht[0]中迁移一部分数据到ht[1]。
渐进式rehash的实现过程
- 触发条件:
-
- 当哈希表的负载因子(已存储键值对数量 / 哈希表大小)超过预设的扩容阈值时(如5),Redis会触发扩容rehash。
- Redis的定时任务(如serverCron)会定期检查哈希表的使用情况,当负载因子低于缩容阈值(如10%)时,会触发缩容rehash。
- 迁移过程:
-
- Redis会设置一个全局变量rehashidx来记录当前rehash的进度。
- 在处理每个客户端请求时,如果rehashidx小于ht[0]的大小,Redis就会从ht[0]的rehashidx索引位置所对应的链表中的所有键值对迁移到ht[1]相应的哈希桶中,并将rehashidx加1。
- 这个过程会持续进行,直到ht[0]中的所有键值对都被迁移到ht[1]。
- 完成rehash:
-
- 当rehashidx达到ht[0]的大小时,说明rehash过程已完成。
- Redis会将ht[1]替代ht[0]成为新的主哈希表,并释放掉旧的ht[0],同时重置rehashidx为-1,等待下次需要rehash时再次启用。
渐进式rehash的优点
- 减少阻塞:通过将rehash过程分散到多个时间片中,避免了单次操作带来的长时间阻塞。
- 提高性能:在rehash过程中,Redis仍然可以正常处理客户端请求,保证了服务的连续性和性能。
- 空间利用:通过及时的扩容和缩容,保证了哈希表的空间利用率和查询效率。