redis中一个db就是一个大dict,也就是实现的可伸缩hash表。其操作支持遍历scan类操作,按stl容器中场景的逻辑,如果一个迭代器在迭代过程中被修改(插入或删除)元素,迭代器可能失效。

redis中,由于在scan操作时,整个dict会有大量的增加和删除操作,如果失效迭代器重新遍历可能永远无法完成scan操作,所以其实现的scan遍历操作使用了Reverse Binary Iteration算法,意思是遍历的顺序递增操作是二进制反向的,也就是该数字递增是二进制高位加1,向低位进位。

因为dict的具体实现是通过索引找到bucket,bucket中可以容纳多个key,并且会进行rehash操作,要实现的目标是:

  • 在迭代开始时刻起,没有被删除的key都能被遍历。
  • 在迭代器rehash操作后,没有被删除的key尽可能少的被重复遍历。

dict的rehash长度是都是2倍增加或半数减少,在遍历过程中cursor的变化是采用反向二进制增加的,在hash长度为8和16时,cursor的增长如下:

8: 000 --> 100 --> 010 --> 110 --> 001 --> 101 --> 011 --> 111 --> 000   
16: 0000 --> 1000 --> 0100 --> 1100 --> 0010 --> 1010 --> 0110 --> 1110 --> 0001 --> 1001 --> 0101 --> 1101 --> 0011 --> 1011 --> 0111 --> 1111 --> 0000   
  • rehash增长

如果cursor是2,在长度8的hash表中下标是010,在长度16的hash表中下标是0010和1010,这两个是相邻的,这个特性很重要,能够保证在rehash之后,0010之前的bucket都是已经遍历过的,不需要再重复遍历。在增长到16后,下次迭代的cursor为0110,所以不会漏掉也不会重复遍历。

  • rehash缩小

在16缩小成8的情况下,当在长度16时,在迭代完成1010后,rehash成8大小,cursor变成010。在大小为16时已经完成0000,1000,0100,1100,0010和1010迭代,大小变为8后,为了防止漏掉bucket,下次迭代从010开始,0010和1010已经迭代过,所以会出现重复。

链接 1. Add SCAN command by pietern · Pull Request #579 · antirez/redis · GitHub 2. Redis源码解析:04字典的遍历dictScan