写点什么

2023-06-17:说一说 redis 中渐进式 rehash?

  • 2023-06-17
    北京
  • 本文字数:779 字

    阅读完需:约 3 分钟

2023-06-17:说一说 redis 中渐进式 rehash?


答案 2023-06-17:


在 Redis 中,如果哈希表的数组一直保持不变,就会增加哈希冲突的可能性,从而降低检索效率。为了解决这个问题,Redis 会对数组进行扩容,通常是将数组大小扩大为原来的两倍。然而,这个扩容过程会引起元素在哈希桶中的分散,导致元素的移动。由于元素移动会涉及 IO 操作,所以这个重新哈希(ReHash)过程可能会导致许多请求被阻塞。

渐进式 rehash

为了避免这个问题,Redis 采用了渐进式 rehash。


在 Redis 中,默认使用两个全局哈希表:哈希表 1 和哈希表 2。最初,当你开始插入数据时,只使用哈希表 1,而哈希表 2 没有分配空间。随着数据逐渐增多,Redis 开始执行渐进式 rehash 的过程。


1、为哈希表 2 分配更大的空间,例如是当前哈希表 1 大小的两倍。


2、将哈希表 1 中的数据重新映射并拷贝到哈希表 2 中,确保每个元素都被正确地存储在新的哈希桶位置上。


3、释放哈希表 1 的空间,将其回收以便于系统的正常运行。


在上述的第二步中,涉及到大量的数据迁移和拷贝操作。如果一次性将哈希表 1 中的所有数据都迁移到哈希表 2,将导致 Redis 线程被阻塞,无法提供对其他请求的服务。这将导致 Redis 无法快速地访问数据。



在 Redis 开始执行 rehash 时,Redis 仍然可以正常处理客户端请求。然而,在处理每个请求时,Redis 还会额外执行以下操作:


  • 处理第一个请求时,将哈希表 1 中第一个索引位置上的所有条目拷贝到哈希表 2 中。

  • 处理第二个请求时,将哈希表 1 中第二个索引位置上的所有条目拷贝到哈希表 2 中。

  • 如此循环,直到将所有索引位置上的数据都成功拷贝到哈希表 2 中。


通过将大量数据拷贝的操作分摊到处理请求的过程中,Redis 巧妙地避免了一次性的大量数据拷贝开销,从而保证了数据的快速访问。这种处理方式确保了根据键寻找值的操作大致在 O(1)的时间复杂度范围内进行。通过渐进式 rehash 和分步式数据迁移,Redis 能够在维持性能的同时,实现平滑的哈希表扩容和数据迁移。

发布于: 刚刚阅读数: 2
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-06-17:说一说redis中渐进式rehash?_redis_福大大架构师每日一题_InfoQ写作社区