10_redis_scan

在key中找到特定的key来进行处理数据。

1. 使用keys*，找到所有的key
   如果数据量太大的话就会导致问题：

• 一次性吞吐太多的数据，难以排查
• keys是遍历算法，时间复杂度0(n)，会导致redis卡顿，其他的指令就会被延后甚至报错，

127.0.0.1:6379> set codehole1 a
OK
127.0.0.1:6379> set codehole2 b
OK
127.0.0.1:6379> set codehole3 c
OK
127.0.0.1:6379> set code1hole a
OK
127.0.0.1:6379> set code2hole b
OK
127.0.0.1:6379> set code3hole b
OK
127.0.0.1:6379> keys *
1) "codehole1"
2) "code3hole"
3) "codehole3"
4) "code2hole"
5) "codehole2"
6) "code1hole"
127.0.0.1:6379> keys codehole*
1) "codehole1"
2) "codehole3"
3) "codehole2"
127.0.0.1:6379> keys code*hole
1) "code3hole"
2) "code2hole"
3) "code1hole"

scan指令就是来解决这个问题。
相比之下：

1. 时间复杂度虽然也是o(n)，但是他是通过游标分步进行的，不会阻塞线程。
2. 提供limit参数，控制每次返回结果的最大条数，limit只是一个hint，返回的结果可多可少
3. 和keys一样，提供了模式匹配功能
4. 服务器不需要为游标保存状态，游标的唯一状态就是 scan 返回给客户端的游标整数;
5. 返回的结果可能会有重复，需要客户端去重复，这点非常重要;
6. 遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的;
7. 单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零;

使用

scan 参数提供了三个参数，第一个是 cursor 整数值，第二个是 key 的正则模式，第三个是遍历的 limit hint。第一次遍历时，cursor 值为 0，然后将返回结果中第一个整数值作为下一次遍历的 cursor。一直遍历到返回的 cursor 值为 0 时结束

for i in range(10000):
 client.set("key%d" % i, i)

127.0.0.1:6379> scan 0 match key99* count 1000
1) "13976"
2) 1) "key9911"
 2) "key9974"
 3) "key9994"
 4) "key9910"
 5) "key9907"
 6) "key9989"
 7) "key9971"
 8) "key99"
 9) "key9966"
 10) "key992"
 11) "key9903"
 12) "key9905"
127.0.0.1:6379> scan 13976 match key99* count 1000
1) "1996"
2) 1) "key9982"
 2) "key9997"
 3) "key9963"
 4) "key996"
 5) "key9912"
 6) "key9999"
 7) "key9921"
 8) "key994"
 9) "key9956"
 10) "key9919"
127.0.0.1:6379> scan 1996 match key99* count 1000
1) "12594"
2) 1) "key9939"
 2) "key9941"
 3) "key9967"
 4) "key9938"
 5) "key9906"
 6) "key999"
 7) "key9909"
 8) "key9933"
 9) "key9992"
......
127.0.0.1:6379> scan 11687 match key99* count 1000
1) "0"
2) 1) "key9969"
 2) "key998"
 3) "key9986"
 4) "key9968"
 5) "key9965"
 6) "key9990"
 7) "key9915"
 8) "key9928"
 9) "key9908"
 10) "key9929"
 11) "key9944"

虽然提供的 limit 是 1000，但是返回的结果只有 10 个左右。因为这个 limit 不是限定返回结果的数量，而是限定服务器单次遍历的字典槽位数量(约等于)。
如果将 limit 设置为 10，你会发现返回结果是空的，但是游标值不为零，意味着遍历还没结束。

127.0.0.1:6379> scan 0 match key99* count 10
1) "3072"
2) (empty list or set)

字典的结构

redis中的key也是存在一个大的字典中，字典结构和HashMap是一样的。一维数组+二维链表
一维数组的大小总是2^n(n>=0)，扩容一次空间加倍，n++
scan的游标就是一维数组的下标，将这个下标称之为槽。
如果不考虑字典的扩容，只需要遍数组下标就ok了，limit的参数就是代表需要遍历的槽位数，返回的结果可多可少是因为不是所有的槽位都挂有链表，有些槽位可能是空的。有些槽位的链表可能有多个元素。每一次遍历会将槽位以及槽位上面的链表数据一起返回给客户端。

scan遍历顺序

遍历顺训不是从数据的第一个元素进行遍历到末尾，而是 采用高位进位加法来进行遍历，是为了考虑扩容和缩容避免槽位重复遍历
普通加法和高位进位加法的区别：
高位进位法从左边加，进位往右边移动，同普通加法正好相反。但是最终它们都会遍历所有的槽位并且没有重复。

字典扩容

当字典的容量达到阈值时，需要重新分配一个2倍大的数组，将原来的元素重新rehash到新的数组中。
rehash就是将元素的hash值对数组的长度进行重新取模，因为长度变了，所有槽位也可能会发生变化。因为数组的长度是2^n次方，所以取模就相当于位于操作

a mod 8 = a & (8-1) = a & 7
a mod 16 = a & (16-1) = a & 15
a mod 32 = a & (32-1) = a & 31

这里的 7, 15, 31 称之为字典的 mask 值，mask 的作用就是保留 hash 值的低位，高位都被设置为 0。

渐进式rehash

HashMap扩容会将将旧的元素一次性放到新数组中，如果元素太多就会造成线程卡顿的现象。redis 采用渐进式rehash来解决这个问题。
会同时保留新旧两个数组，然后在定时任务中逐步的将旧数组的元素复制到新数组中。这意味中操作处于rehash的字典的时候，会访问新旧两个数组。
scan的时候也要考虑到这个问题。

更多scan指令

scan遍历key以外，还可以对指定容器集合进行遍历，zscan遍历zset，hscan遍历hash，sscan遍历set。原理都类似

大key扫描

平时业务中尽量避免大key的出现。
集群中有大key，迁移的时候会造成卡顿，扩容的时候会造成卡顿，删除造成卡顿。
下面命令用于定位大key

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys