redis scan反向二进制位迭代原理

scan反向二进制位迭代原理：

顺序遍历会有什么问题？

在Redis中，key是使用Hash结构存储的，使用链表法解决hash冲突，需要遍历所有的key最直观的想法就是遍历hash数组，假设数组长度为8，则从0-7遍历取值即可。

但hash是会自动扩容缩容的，如果按照顺序遍历，在遍历一半的时候发生扩容缩容会发生什么？

如上图所示，原始数据遍历到index=5的位置。发生扩容后：从index=6的位置继续遍历，将会有8、10、27、12这四个元素被重复遍历；发生缩容后：7、12这两个元素将不会被遍历到。

何为反向二进制位迭代？

Redis的scan命令使用反向二进制位迭代顺序来解决这个问题，那这个反向二进制迭代顺序是怎样的？

假设数组长度为8，那么可以使用3个二进制位表示index，依次遍历顺序为：

# 第一次遍历依旧从0开始，下一次index为本次index的高位加一
000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

按照这个顺序我们再结合上一张图看看，假设原数组已经遍历了0、4、2，问题是否解决：

已经遍历元素：0、8、12、10

1）缩容

缩容后的遍历顺序如下，上一次缩容前遍历完了2，那么传入的index应该是6。这里缩容时的index需要做一个转换：去掉最高位保留有效位。0110 -> 110，即从3开始遍历。

00 -> 0
10 -> 2
01 -> 1
11 -> 3

index=3 -> 27、7

可见缩容前后遍历的key是完整的。

什么原理？想象一下缩容，从8缩容到4，那么原先的5、6、7、8位置的元素去哪里了？重新计算的规则：index%4，也就是去掉最高位。

2）扩容

扩容后的遍历顺序如下，上一次扩容前遍历完了2，那么传入的index应该是6，扩容后二进制位从3位变为4位，

110 -> 0110，还是从6开始

0000 -> 0
1000 -> 8
0100 -> 4
1100 -> 12
0010 -> 2
1010 -> 10
0110 -> 6
1110 -> 14
0001 -> 1
1001 -> 9
0101 -> 5
1101 -> 13
0011 -> 3
1011 -> 11
0111 -> 7
1111 -> 15

index=6/14/9/5/13/3 -> 空
index=11 -> 27
index=7 -> 7
index=15 -> 空

扩容前：0、8、12、10

扩容后：27、7

可以看到没有出现重复元素。

注意点

1. scan并不能完全保证key不会重复，比如上面缩容过程中，若传入的index为5，去掉高位则从1开始遍历，而实际上缩容前已经遍历过1，这种情况依旧会出现重复。