美文网首页
Redis字典的渐进式rehash

Redis字典的渐进式rehash

作者: cbhe | 来源:发表于2020-06-17 20:17 被阅读0次

采用渐进式 rehash 的原因

扩展或收缩哈希表需要将ht[0]中的所有键值对rehash到ht[1]中。不过,这个rehash的动作不一定是一次性、集中式完成的,而是分多次、渐进式完成的。

这样做的原因在于,避免当ht[0]中保存了太多的键值对时,一次性集中式rehash让服务器在较长的时间内停止服务。rehash动作的过程中肯定是不能对外提供增删改查的操作的,如果ht[0]中只有四个键值对的话,那么一次性完成rehash也不会对服务器的运行造成太多延迟,但如果是四百万、四千万的话一次性完成rehash将会严重阻塞服务器运行。

渐进式 rehash 的过程

以下是哈希表渐进式rehash的详细步骤:

  1. 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维护一个rehashidx变量,来标记当前rehash到了ht[0] 的 dictEntry table哪个位置。
  3. 在渐进式rehash进行期间,每次对字典执行增删改查操作时,除了执行指定操作外还要讲ht[0]中的rehashidx索引位置上的键值对 rehash 到ht[1]上,当本次rehash完成时,rehashidx加一。
  4. 随着字典操作的不断进行,最终在某个时间点上,ht[0]上的键值对都 rehash 到了ht[1]上,这时程序将 rehashidx 设置为-1,表示 rehash 操作已经完成。
  5. rehash 完所有键值对后,ht[1]和ht[0]将交换位置,即ht[1]将成为新的ht[0]。

渐进式 rehash 采用了分治的思想,将 rehash 键值对所需的工作分摊到了每次对字典的增删改查操作上,虽然降低了 redis 服务器的整体吞吐量,但提升了响应速度,不会出现在某次操作时特别慢的情况。

渐进式 rehash 期间的哈希表操作

因为在渐进式 rehash 的过程中,字典会同时使用 ht[0] 和 ht[1] 两个哈希表,所以在这个过程中对字典的增删改查操作会在两个哈希表上进行。例如在字典上查找一个键时,程序会先查询ht[0],如果没有查到就再查 ht[1]。
新添加到字典上的键值对只会保存在ht[1]上,而ht[0]上不再进行任何添加操作,这样就保证了ht[0]中包含的键值对的数量只减不增,并随着rehash的进行而逐渐变成空表。

总结

  • 原因:数据太多的话一次rehash可能让服务器长时间停止服务,渐进式就是将停止服务的时间分散给一段时间内的每次增删改查上。
  • 渐进:rehashidx 从0开始到ht[0].length-1,每次增删改查时 将对ht[rehashidx]进行rehash。
  • 操作:查询操作同时查询ht[0]和ht[1],新增操作只新增ht[1]

相关文章

  • redis笔记

    数据结构 SDS 字典 index确定 渐进式rehash 为了缓解一次性rehash带来的性能问题,redis提...

  • Redis字典的渐进式rehash

    采用渐进式 rehash 的原因 扩展或收缩哈希表需要将ht[0]中的所有键值对rehash到ht[1]中。不过,...

  • Redis笔记

    Redis核心技术与实战 rehash·装载因子(entry个数 除以 hash桶个数) 渐进式rehash·每处...

  • 2. 浅析Redis底层数据结构

    概要1)Redis中的字符串-sds2)Redis中的HashMap-dict3)dict的渐进式rehash4)...

  • redis

    1.Redis与Memorycache的区别? 2.Redis的五种数据结构? 3.渐进式rehash过程? 4....

  • java 从零开始手写redis(15)实现自己的 HashMa

    回顾 我们在 从零手写缓存框架(14)redis渐进式rehash详解[https://houbb.github....

  • Redis中渐进式rehash

    Redis一共支持5种数据结构,hash是其中的一种,在hash扩容的时候采用的是渐进式rehash的方式。要想深...

  • Redis的渐进式ReHash实现

    The Implication of Incremental Rehashing in Redis 本文适合Jav...

  • redis-hash

    hash 字典 类似于java中的hashmap,数组加链表,碰撞进链表 区别: rehash过程不同,redis...

  • Redis深度历险 - dict的rehash

    Redis深度历险 - dict的rehash 字典是Redis中非常重要的一个数据结构,本质就是一个hash表;...

网友评论

      本文标题:Redis字典的渐进式rehash

      本文链接:https://www.haomeiwen.com/subject/kmzsxktx.html