Redis---渐进式哈希

  • 时间:
  • 浏览:
  • 来源:互联网

Redis支持的数据结构有很多,其中dict的使用非常频繁,其实Redis的每一个数据库结构都是一个dict。dict使用哈希表实现,这也是Redis性能十分强悍的原因之一,增删改查的时间复杂度为O(1).

在这里插入图片描述

上图是我根据Redis源码中定义的数据结构及网上资料参考画的参考图。

随着Redis的操作越来越多,dict中保存的数据量也会动态变化,当数据量增加或者减少到一定的程度,为了让负载因子维持在一个合理的范围内,Redis就会对dict的大小进行相应的扩容或者收缩。而这一过程正是通过渐进式哈希(rehash)操作来完成的。

渐进式哈希的原理:

将原哈希表中的数据以少量多次的方式,rehash到新的哈希表中,避免一次性数据迁移导致堵塞问题,通过rehashidx记录rehash的进度,在rehash结束后,新的哈希表将替代原哈希表。

在这里插入图片描述

在正式了解渐进式哈希之前,我们先来看几个重要的概念:

负载因子:ht[0].used / ht[0].size,即哈希表的填满程度。它决定了哈希表的元素多少、空间利用率高低、哈希冲突机会的大小以及操作开销程度等,本质上是数据结构中有名的“时-空”矛盾。
sizemask:也叫大小掩码,用来计算索引值,其值等于哈希表size - 1。
rehashidx:当rehash结束时,其值为-1,rehash进行时,其值为rehash的进度,以bucket为单位,一个bucket可能有多个元素。
iterators:当前正在运行的安全迭代器数量。
渐进式哈希的步骤:

  1. 判断负载因子,进行rehash操作。
  2. 申请ht[1]的内存空间,此时dict同时拥有ht[0]和ht[1]。
    扩容:ht[1]的大小为大于等于ht[0].used * 2的且为2^n的值。
    收缩:ht[1]的大小为大于等于ht[0].used 的且为2^n的值。
  3. 将dict.rehashidx置为0,开始对dict.ht[0].table[0]的bucket进行rehash。
    因为一个bucket是一个链表式结构,所以循环遍历这个bucket上的元素。
    计算每一个元素中key的新哈希值,与dict.ht[1].sizemask进行位与运算,得到索引h。
  4. 根据索引h,将元素插入ht[1].table[h]。
  5. 更新ht[0].used–,ht[1].used++。
  6. 继续处理bucket上的下一个元素。
  7. 处理完一个bucket后,将ht[0].table[dict.rehashidx] 置为 NULL。
  8. 将dict.rehashidx加1,处理下一个bucket:ht[0].table[dict.rehashidx]。
  9. 直到ht[0].used 为 0,说明ht[0]中的所有元素完成数据迁移。
    释放ht[0].table内存,将ht[1]赋值给ht[0],然后重置ht[1],为下一次rehash做准备。
  10. 将dict.rehashidx置为-1,rehash工作正式结束。

渐进式哈希的控制:

/d为需要rehash的字典,n为bucket的个数/

int dictRehash(dict *d, int n)

/在ms时间段内进行rehash操作/

int dictRehashMilliseconds(dict *d, int ms)

rehash操作默认是分步的,即一次只rehash一个bucket:n = 1。
如果bucket为null,则继续处理下一个,但是不能超过10n个为null的bucket:
按时间段rehash,在时间段内每次rehash 100个bucket:n = 100,直到超时。
连续的10
n个为null的bucket算为一个bucket。
渐进式哈希过程中访问元素:

rehash操作非一蹴而就,在rehash的过程中,ht[0]和ht[1]同时存放着数据,但是有dict.rehashidx变量标识着rehash的进度,即可以通过dict.rehashidx判断哈希值存在于ht[0]还是ht[1]。

如果是新增元素,会直接操作ht[1],保证ht[0]的数据只减不增。
如果dict.rehashidx值为-1,则当前没有rehash操作,直接操作ht[0]。
如果dict.rehashidx值大于等于0,则表示正在进行rehash操作。
将计算的ht[0]中的索引与dict.rehashidx比较,如果索引大于dict.rehashidx,表示索引还未rehash,直接操作ht[0]。
如果索引不大于dict.rehashidx,则表示索引已经rehash到ht[1]。
根据ht[1]重新计算索引,根据索引操作ht[1]。
结束。

总结:

渐进式哈希的设计无疑是优秀的,在动态扩容收缩空间的同时,保证了Redis的服务能力,避免了阻塞;但是在rehash期间,dict同时拥有ht[0]和ht[1],申请内存空间后内存会瞬间增长,此时可能会触发Redis的过期机制或者内存淘汰策略以释放更多的内存,尤其是Redis作为lru cache长期处于maxmemory状态,势必会删除大量的key

参考资料
https://baijiahao.baidu.com/s?id=1663870339713597715&wfr=spider&for=pc

本文链接http://www.dzjqx.cn/news/show-617416.html