场景
在平时线上Redis维护工作中，有事需要从Redis实例中成千上万个key中找出特定前缀的key列表来手动维护数据，Redis提供了一个keys的命令列出满足特定正则字符串规则的key。
keys有两个缺点，一是无法做返回值限制，一次性会返回所有满足条件的key，万一实例中有几百万个key满足条件，就麻烦了，
二是keys是遍历算法，复杂度是O(n)，如果有实例中的key非常的多，这个指令会导致redis卡顿，所有其他读写redis的指令都会被延后甚至超时报错，
因为redis是单线程程序，顺序执行所有指令，其他指令必须等到当前的keys指令执行完了才能继续执行。
127.0.0.1:6379> keys *
1) "codehole3"
2) "codehole2"
3) "codehole1"
4) "company"
127.0.0.1:6379> keys codehole*
1) "codehole3"
2) "codehole2"
3) "codehole1"
redis在2.8版本中加入了scan指令，解决了keys的缺点，有如下特点：
- 复杂度虽然也是O(n)，但它是通过游标分布进行的，不会阻塞线程。
- 提供limit参数，可以控制每次返回的最大结果数，limit只是一个hint，返回的结果可多可少。
- 通keys一样，提供模式匹配功能。
- 服务器不需要为游标保存状态，游标的唯一状态是scan返回给客户端的游标整数。
- 返回的结果可能会重复，需要客户端去重。
- 遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的。
- 单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为0。
scan基本用法
首先在redis中插入 10000 条数据做测试。
我们通过scan查找key99开头的key列表，scan提供了三个参数，第一个是cursor整数值，第二个是key的正则模式，第三个是遍历的limit hint，
第一次遍历时，cursor的值为0，然后将返回结果中第一个整数值作为下一次遍历的cursor，一直遍历到返回的cursor值为0时结束。
下面是遍历结果，使用....代替太多的输出。
127.0.0.1:6379> scan 0 match key99* count 1000
1) "15832"
2) 1) "key9937"
........
127.0.0.1:6379> scan 15832 match key99* count 1000
1) "12396"
2) 1) "key993"
........
127.0.0.1:6379> scan 12396 match key99* count 1000
1) "6154"
2) 1) "key9934"
........
127.0.0.1:6379> scan 6154 match key99* count 1000
1) "11286"
2) 1) "key9986"
........
127.0.0.1:6379> scan 6529 match key99* count 1000
1) "13657"
2) 1) "key9975"
........
127.0.0.1:6379> scan 14797 match key99* count 1000
1) "7379"
2) 1) "key9905"
........
127.0.0.1:6379> scan 7379 match key99* count 1000
1) "8999"
2) 1) "key9984"
........
127.0.0.1:6379> scan 8999 match key99* count 1000
1) "12799"
2) 1) "key9971"
2) "key9926"
3) "key9968"
......
127.0.0.1:6379> scan 12799 match key99* count 1000
1) "0"
2) (empty array)
从上面的过程中可以看出，虽然提供的limit是1000，但是返回的结果只有10个左右，因为这个limit不是限定返回结果的数量，而是限定服务器单次遍历的字典槽位数量(约等于)，如果将limit设置为10，你会发现返回结果是空的，但是游标值不为0，意味着遍历还没有结束。
127.0.0.1:6379> scan 0 match key99* count 10
1) "2560"
2) (empty array)字典的结构
在redis中所有的key都存储在一个很大的字典中，这个字典的结构和java中的HashMap一样，是一个一维数组，二维链表的结构，
第一维数组的大小总是2的n次方(n>=0)，扩容一次数组，大小空间加倍，也就是2的n次方+1。
scan指令返回的游标就是一维数组的位置索引，我们称这个位置索引为槽(slot)，如果不考虑字典的扩容缩容，直接按数组下标挨个遍历即可，
limit参数表示需要遍历的槽位数，之所以返回的结果或多或少，因为不是所有槽位上都会存在链表，有些槽位可能是空的，还有些槽位上挂接的链表上的元素可能有多个，每次遍历都会将limit数量的槽位上挂接的所有链表元素进行模式匹配过滤后，一次性返回给客户端。
scan遍历顺序
scan的遍历顺序非常特别，它并不是从一维数组的第0位一直遍历到末尾，而是采用了高位进位加法来遍历，用这种方式是为了在字典拓容和缩容时避免槽位的遍历重复和遗漏。
下图是普通加法和高位进位加法的区别。
字典拓容 rehash
当 LoadFactor 达到阈值时，需要重新分配一个新的2倍大小的数组，然后所有的元素将被重新rehash挂到新的数组下面，
rehash就是将元素的hash值对数组长度进行取模运算，这时每个元素挂接的槽位可能会发生变化，因为数组的长度是2的n次方，所以取模运算等价于位与操作。
下面的7、15、31称为字典的mask值，mask的作用就是保留hash值的低位，高位都被设置为0。
a mod 8 = a & (8 - 1) = a & 7
a mod 16 = a & (16 - 1) = a & 15
a mod 32 = a & (32 - 1) = a & 31如下图，假设一个字典的长度由8位扩容到16位，3号槽位011将被rehash到3号槽位和11号槽位，即部分元素留在3号槽位，部分移动到11号槽位，
11的二进制是1011，即对3的二进制011增加了一个高位1，变成了1011，
也就是说，如果一个槽位的二进制数是xxx，数组长度由8位拓容到16位，rehash后的槽位将是 0xxx 和 1xxx (xxx + 8)，
由16位拓容到32位时，二进制xxxx的元素将被rehash到 0xxxx 和 1xxxx(xxxx + 16)中，你会发现很有规律的是，rehash后的元素所在槽位，都是原有槽位的二进制数在高位加了一个0和一个1的两个槽位里。
拓容前后的遍历顺序
如下图所示，使用高位进位加法的遍历方式，会使的我们的槽位在rehash之后遍历起来也是相邻的，即原本是在同一个槽位的元素，在rehash后，依然是可以连续的进行遍历到的。
假如要遍历110(橙色)这个位置的链表，此时拓容了，拓容后，原本110里的元素被放到了0110和1110这两个元素里了（你会发现拓容后的槽位就是上面说的在高位加一个0和1），
此时我们可以直接从0110这里进行遍历，随后遍历到1110，这样即将原本在一个槽位里的元素也顺序紧凑的遍历掉了，0110前面的槽位也都是遍历过的，同时避免了对已经遍历过的槽位进行重复遍历的问题，为什么这么说呢？
如果我们不按照高位进位加法的方式进行遍历，而是按照数组的下标进行遍历，从0-7进行遍历，此时遍历到3这个下标了，发生了拓容，之前 0 1 2下标里的我们已经遍历过了，由于发生了拓容，0 1 2拓容后的部分元素又被放到了 8 9 10中，
但其实他们已经被我们扫描过了，此时我们继续从3开始往后遍历，遍历到了8 9 10的时候，则有扫了一遍之前已经扫过的元素，这就是为啥用高位进位加法的顺序了，
缩容也是，如果下标是0-15，扫描到3的时候，此时进行缩容，只剩下0-7了，之前在8 9 10的元素被缩到了0 1 2里面去，这时候按照下标顺序的话，就无法扫到8 9 10了，导致漏扫的情况，
由于缩容后例如10这个槽位，是010和110上两个链表的元素结合，所以可能会导致010已经scan过的元素再次重新被scan一次，就出现了返回重复结果的情况。
渐进式hash
Java的HashMap在拓容时，会一次性将旧数组下的全部元素转移到新数组中，如果HashMap中的元素特别多，线程就会出现卡顿的情况，redis为了解决卡顿的问题，使用了渐进式rehash，
渐进式rehash就是，同时保留旧数组和新数组，在定时任务中以及后续对hash的指令操作中渐渐的将旧数组中挂接的元素迁移到新数组上，处于rehash中的字典，需要同时访问新旧两个数组结构，如果在旧数组中找不到，就去新数组中查找，
scan对于rehash中的字典，需要同时扫描新旧槽位，然后将结果整合返回给客户端。
集合的scan指令
scan除了可以遍历redis中的所有key，也可以对指定的容器集合进行遍历，
对于 zset 使用 zscan，对于 hash 使用 hscan，对于 set 使用 sscan，原理与scan类似，因为hash底层是字典，set也是特殊的hash，zset内部也使用了字典存储所有元素内容。
大key扫描
如果不慎在redis当中形成了一个很大的对象，例如一个很大的hash或很大的zset，这对redis会有一些影响，
例如集群环境下，某个key太大，导致数据迁移卡顿，在内存分配的情况下，key太大，拓容时，将一次性申请更大的内存，也会导致redis卡顿，如果这个key被删除，内存会被一次性回收，又会导致卡顿，
在业务开发中，尽量减少大可以的产生，如果发现redis的内存大起大落，可能是大key导致的，定位大key也可以用scan进行扫描，
对于扫描出来的key，使用type获得key的类型，然后使用相应的数据结构的size或者len方法得到key的大小，对于每种类型，将大小排名的前若干名作为扫描结果展示出来，这种方式需要编写脚本，比较繁琐，redis直接提供了大key扫描功能
# 这个命令可能会导致 redis 的 ops大幅度提升
redis-cli -h 127.0.0.1 -p 7001 --bigkeys
# 使用 -i 0.1, 让指令每隔100条scan指令就休眠0.1s，ops将不会大幅度提升，但是扫描时间将会变长
redis-cli -h 127.0.0.1 -p 7001 --bigkeys -i 0.1
