最近在开发redioxy,主要用于跨机房双写做高可用,由于要支持集群模式下的scan命令,所以对scan的细节做了一下了解。

我们都知道,在很早版本的redis中,keys命令可以获取所有的key,不过这个命令会堵塞之后的所有操作,所以在key很大的情况下执行此命令那会有很大的麻烦,在一般的线上系统中,此命令一般都是禁止使用的。

随后redis新增了scan命令来分段获取key,由于不是一次性获取所有的key而是分批来获取,可以最大情况的减少线上服务的压力。该命令主要是要提供一个cursor,然后会返回下一次的cursor以及当前扫描到的key的列表,当cursor为0的时候,代表所有的key被扫描完。

这个cursor到底是什么东西呢?首先我们必须得了解一下redis中key的存储模式。

redis中所有的kv都存储于哈希表中,哈希表的尺寸为最小的能容纳目前key的2^N,也就是说假设key只有一个,则大小为2的哈希表已经足够了;当key有15个,则哈希表需要扩容为16来容纳所有的键值对。当空间不足的时候,整个哈希表的长度会扩容为原先的两倍。

然后我们需要知道key的哈希策略,该策略比较简单,为:

slot = hash(key) & (size - 1)

其中size为哈希表的长度。

由此我们可以引申出rehash,也就是扩容的时候的哈希重分布的阶段了。

当一个key需要重分布,则肯定是根据上述的分布算法来确定落到哪一个槽位。在这里我们假设之前的哈希表的尺寸为4,要扩容为8,那么就可能会引发一下的重分布:

  • 槽位0的key,可能会重分布到4上
  • 槽位1的key,可能会重分布到5上
  • 槽位2的key,可能会重分布到6上
  • 槽位3的key,可能会重分布到7上

假设一个key原先落到槽位0上,那么根据上述的算法,hash(key) & b11的值为0,则可以推导出来该key的哈希值低两位肯定都是0,而高位不确定,那么假设高位为1,扩容后则会落到b100上,也就是原先的值加上size-1的二进制值保留最高位,其它低位取0的值,或者简单的说也可以以以下的算法算出:

off = size / 2

所以我们可以简单的推断出,当扩容的时候会多一倍的空间出来,原先0槽位的,可能会落到新扩展的0槽位中,如此类推。

为什么要提到哈希表扩容呢?因为扩容会影响scan,因为它依赖cursor,假设不对扩容做处理,很有可能在扩容的过程中丢失或者重复数据。

redis在这里使用了一种称之为reverse binary iterator的设计算法,核心的思想在于迭代游标的时候,不从低位新增,而是从高位新增。这里可能有点儿晦涩,简单的说假如从低位增加,则假设有4个元素,那么游标的顺序分别为b00,b01,b10,b11,也就是0,1,2,3这种游标的顺序。而从低位新增,则是b00,b10,b01,b11,也就是0,2,1,4这种顺序,为什么要这样设计呢?

我们来以size分别为4,8,16三种情况来看游标值:

|    0    |    2    |    1    |    3    |
| 0  | 4  |  2 |  6 |  1 | 5  | 3  | 7  |
|0|8 |4|12|2|10|6|14|1|9 |5|13|3|11|7|15|

我们可以很清楚的看到,假设我们在size为4的时候当前游标为2,并且扩容size为8完成,则在之前的游标0,4不会被扫描到,而0,4则都是由原先size为4时候分裂开来的,所以不会进行重复的扫描。其实继续往下推导,无论扩容为多大,原先的扫描过的游标分裂出来的新的槽都不会被扫描到,所以数据不会重复。

下面再谈谈游标的计算算法,网上给出的都比较麻烦,我这里就按原先设计的原理,大致说一下我这里的算法。算法首先需要明确当前哈希表的尺寸,然后将size-1作为mask,这个mask代表了当前游标的有效二进制位数,我们在反向加法的时候需要用到。

然后就非常的简单了,我们在高位+1,这个高位需要根据mask来计算,假设mask有7位,则最高位需要加到第七个比特位上。若进位则高位置0,次高位+1,如此类推。当然这里只是说逆向加法的规则,实际编码肯定还是二进制反转方便。

由此我们也可以看见游标的最大值为哈希表的尺寸-1。

比如当前哈希表的尺寸为8,则maskb111也就是7,假设当前的游标为1,则我们首先将其转为二进制b001,记住需要扩展为和mask相同位数,然后将其高位加1则为b101,也就是十进制的5。而我们再次+1,则变为了b011也就是3,完全符合上述的游标值。

当然这里只是简单的做了分析,实际上在哈希表变小的情况下,会造成若干槽的重复读取。

共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day