key的存储结构

redis所有的key都存储在一个很大的字典中，这个字典的结构就是hashtable。

hashtable的结构之前有提过，简单来说它就是一维数组+二维list结构，如下：

第一维数组的大小总是2^n(n>=0)，扩容一次，数组的空间大小就加倍，即n++。

高位进位加法

之前提到可替换keys的scan指令，从字面上来讲，scan就是扫描指令，所谓扫描，就是遍历所有的元素，那么遍历的顺序是怎样的呢？是从小到大，还是从大到小？

注意：这里说的“遍历顺序”针对的是hashtable的一维数组，二维链表就是简单的链表遍历。

在redis的实现中，采用了一种神奇的遍历方式：高位进位加法。

什么是高位进位加法？其实是相对于低位进位加法来说的。二者的区别如上图所示，低位进位加法的进位方向是由右向左，而高位进位加法的进位方向是由左向右。

我们以n=4，hashtable的桶数（一维数组的长度）为16为例，通过以下对比表格来说明下高低位的区别。

桶下标	低位进位加法	高位进位加法
0	0000 (0)	0000 (0)
1	0001 (1)	1000 (8)
2	0010 (2)	0100 (4)
3	0011 (3)	1100 (12)
4	0100 (4)	0010 (2)
5	0101 (5)	1010 (10)
6	0110 (6)	0110 (6)
7	0111 (7)	1110 (14)
8	1000 (8)	0001 (1)
9	1001 (9)	1001 (9)
10	1010 (10)	0101 (5)
11	1011 (11)	1101 (13)
12	1100 (12)	0011 (3)
13	1101 (13)	1011 (11)
14	1110 (14)	0111 (7)
15	1111 (15)	1111 (15)

低位进位加法的遍历顺序为：0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15。

高位进位加法的遍历顺序为：0，8，4，12，2，10，6，14，1，9，5，13，3，11，7，15。

我们知道，用scan替换keys指令后，之所以高效，是因为不再锁住了整个字典，而是可以通过指令参数指定读取的cursor和count，相当于把大锁替换为小锁，分页读取。

但是换成小锁，引出一个问题：在遍历的同时，会有其他的线程对hashtable进行增删改，进而可能触发hashtable的扩容或者缩容。如果按照低位进位加法的方式进行遍历，将很容易出现元素的重复读取或者遗漏，导致之前的已完成的遍历内容变得不可靠。高位进位加法遍历，就能够很好地避免这个问题。

请参看下图：

hashtable是按照2^n的长度进行扩容，例如原来的数组长度为8位，扩容后将变更为16位，原来16位的长度，缩容后的长度为8位。而后所有的元素要进行rehash操作，将元素的hash运算值按照新的长度进行取模mod运算。

从图示可以发现，rehash后的桶在高位进位加法遍历顺序上是相邻的。例如110(6)这个桶，在扩容后，rehash的桶为0110（6）和1110（14），这两个桶在高位进位加法遍历顺序上是相邻的；反之，0110（6）和1110（14）这两个桶，在缩容后，rehash的桶为110(6)。

奇妙之处就在这里：也就是在rehash前遍历过的元素，rehash之后，按照新的数组长度，继续从之前遍历的断点处继续往下遍历，将不会出现大面积的重复遍历或者遗漏。

这里之所以说不会“出现大面积”而不是“不出现”，是因为在缩容的情况下，有可能出现重复扫描。例如：当前即将扫描1110(14)桶的数据，发生了缩容，则会从缩容后的110（6）桶开始扫描，而这个桶内的元素包含了缩容前的0110(6)中的元素，结果集中就会出现重复元素了。

总结

本文介绍了scan遍历使用的高位进位加法，这是redis实现hashtable高效扫描的核心机制，值得推敲学习。