[Redis] 渐进式rehash

为了实现从键到值的快速访问,Redis 使用了一个哈希表来保存所有键值对,我也把它称为全局哈希表
一个哈希表,其实就是一个数组,数组的每个元素称为一个哈希桶。所以,我们常说,一个哈希表是由多个哈希桶组成的,每个哈希桶中保存了键值对数据。

需要注意的是,哈希桶中的元素保存的并不是值本身,而是指向具体值的指针。

  • Redis的全局哈希表

WechatIMG9.jpeg

  • Redis使用链式哈希解决hash冲突(指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接)

WechatIMG10.jpeg

为了使rehash操作更高效,Redis默认使用了两个全局哈希表ht[0]ht[1]。一开始,当你刚插入数据时,默认使用ht[0],此时的ht[1]并没有被分配空间。随着数据逐步增多,使用链式哈希解决hash冲突导致链表过长,Redis越来越慢,此时Redis开始执行rehash,整个过程分为三步:

  1. ht[1]分配更大的空间,例如是当前ht[0]大小的两倍;

  2. ht[0]中的数据重新映射并拷贝到ht[1]中;

  3. 释放ht[0]的空间

渐进式rehash

在Redis中,rehash需要将ht[0]里面的所有键值对rehash到ht[1]里面,但是,这个rehash动作并不是一次性、集中式地完成的,而是分多次、渐进式地完成的。为了避免rehash对服务器性能造成影响,服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1],而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]

以下是哈希表渐进式rehash的详细步骤:
  1. ht[1]分配空间,让字典同时持有ht[0]ht[1]两个哈希表;

  2. 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始;

  3. 在rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后,程序将rehashidx属性的值增1,这就是操作辅助rehash;

  4. 在rehash进行期间,如果服务器比较空闲,在Redis周期函数中,如果发现有字典正在进行渐进式rehash操作,则会花费1毫秒的时间,帮助一起进行渐进式rehash操作,这就是定时辅助rehash

  5. 随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成;

  6. 释放ht[0]的空间

渐进式rehash的好处在于它采取分而治之的方式,将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,从而避免了集中式rehash而带来的庞大计算量。

  • Redis的渐进式rehash

WechatIMG11.jpeg

因为在进行渐进式rehash的过程中,字典会同时使用ht[0]ht[1]两个哈希表,所以在渐进式rehash进行期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行:比如说,要在字典里面查找一个键的话,程序会先在ht[0]里面进行查找,如果没找到的话,就会继续到ht[1]里面进行查找,诸如此类。
另外,在渐进式rehash执行期间,新添加到字典的键值对一律会被保存到ht[1]里面,而ht[0]则不再进行任何添加操作:这一措施保证了ht[0]包含的键值对数量会只减不增,并随着rehash操作的执行而最终变成空表。

问题:
  • 同时有两个hash表在使用,会使得redis内存使用量瞬间突增
  • 在Redis满容状态下,Rehash会导致大量Key驱逐

Q.E.D.


Stay focused and work hard!