Redis渐进式哈希

Redis数据结构中dist使用的非常多

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

渐进式哈希原理

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

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

负载因子：即哈希表的填满的程度。它决定了哈希表的元素多少，空间利用率高低，哈希冲突的机会大小以及操作开销程度等，本质是数据结构汇总有名的时-空矛盾

sizemask：也叫大小掩码，用来计算索引值，其值等于哈希表size-1

rehashidx：当rehash结束时，其值为-1，rehash进行时，其值为rehash的进度，以bucket为单位，一个bucket可能有多个元素。

iterators：当前正在运行的安全迭代器数量

渐进式哈希的步骤

判断负载因子，进行rehash操作(redis的负载因子是1)

申请ht[1]的内存空间，此时dict同时有dict[0]和ht[1]

• 扩容：ht[1]的大小为大于等于ht[0].used*2的且为2^n的值
• 收缩：ht[1]的大小为大于等于ht[0].used 的且为2^n的值。

和java不同的是redis的字典底层有俩个数组，还有rehashidx用来控制rehash，默认是-1

扩容就是把数组2号初始化为一个2倍的数组并且把rehashidx修改为0，此时当前字典就进入了rehash状态

之后对该字典进行增删改查操作都会进行一次单步的rehash

假设现在要添加一个元素，单步的rehash会从当前的rehashidx开始，把当前索引位置的元素一个个从数组1号迁移至数组2号，迁移完索引后rehashidx+1，然后再进行添加操作，处于rehash中的添加操作，都会直接把元素添加到数组2号中，假设之后的操作是查询，也会进行同样的单步rehash操作，一只反复知道数组1号元素数为0代表rehash完成。此时需要把数组1号的指针替换成数组2号，再把数组2号重新置为null，最后把rehashindex-1，之后的情况就和rehash之前是一样的