最近在开发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，则mask为b111也就是7，假设当前的游标为1，则我们首先将其转为二进制b001，记住需要扩展为和mask相同位数，然后将其高位加1则为b101，也就是十进制的5。而我们再次+1，则变为了b011也就是3，完全符合上述的游标值。
当然这里只是简单的做了分析，实际上在哈希表变小的情况下，会造成若干槽的重复读取。
作者
