Redis知识梳理(9) [ scan 检索 ]

以你之姓@ 2022-02-03 13:27 191阅读 0赞

在平时线上 Redis 维护工作中，有时候需要从 Redis 实例成千上万的 key 中找

出特定前缀的 key 列表来手动处理数据，可能是修改它的值，也可能是删除 key。

这里就有一个问题，如何从海量的 key 中找出满足特定前缀的 key 列表 来?

Redis 提供了一个简单暴力的指令 keys 用来列出所有满足特定正则字符串规则 的 key。

>  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”

这个指令使用非常简单，提供一个简单的正则字符串即可，但是有很明显的两个 **缺点**。

1.  没有 offset、limit 参数，一次性吐出所有满足条件的 key，万一实例中有 几百 w 个 key 满足条件，当你看到满屏的字符串刷的没有尽头时，你就知 道难受了。
2.  keys 算法是遍历算法，复杂度是 O(n)，如果实例中有千万级以上的 key， 这个指令就会导致 Redis 服务卡顿，所有读写 Redis 的其它的指令都会被 延后甚至会超时报错，因为 Redis 是单线程程序，顺序执行所有指令，其 它指令必须等到当前的 keys 指令执行完了才可以继续。

Redis 为了解决这个问题，它在 2.8 版本中加入了大海捞针的指令—— scan 。

**scan 相比 keys 具备有以下特点:**

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

### scan 基础使用 ###

# scan 参数提供了三个参数，第一个是 cursor 整数值 ，第二个是 key 的正则模 式 ，第三个是 遍历的 limit hint 。 #

第一次遍历时，cursor 值为 0，然后将返回 结果中第一个整数值作为下一次遍历的 cursor。一直遍历到返回的 cursor 值为 0 时结束。

>  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 都存储在一个很大的字典中，这个字典的结构和 Java 中 的 HashMap 一样，是一维数组 + 二维链表结构，

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

![img][]

scan 指令返回的游标就是第一维数组的位置索引，我们将这个位置索引称为槽 (slot)。

如果不考虑字典的扩容缩容，直接按数组下标挨个遍历就行了。

limit 参 数就表示需要遍历的槽位数，之所以返回的结果可能多可能少，是因为不是所有 的槽位上都会挂接链表，

有些槽位可能是空的，还有些槽位上挂接的链表上的元 素可能会有多个。每

一次遍历都会将 limit 数量的槽位上挂接的所有链表元素进 行模式匹配过滤后，一次性返回给客户端。

# scan 遍历顺序 #

scan 的遍历顺序非常特别。它不是从第一维数组的第 0 位一直遍历到末尾，而 是采用了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历，是考虑到 字典的扩容和缩容时避免槽位的遍历重复和遗漏。

首先我们用动画演示一下普通加法和高位进位加法的区别。

![img][img 1]

从动画中可以看出高位进位法从左边加，进位往右边移动，同普通加法正好相反。但是最终它们都会遍历所有的槽位并且没有重复。

# 字典扩容 #

Java 中的 HashMap 有扩容的概念，当 loadFactor 达到阈值时，需要重新分配 一个新的 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 前后元素槽位的变化。

假设当前的字典的数组长度由 8 位扩容到 16 位，那么 3 号槽位 011 将会被 rehash 到 3 号槽位和 11 号槽位，

也就是说该槽位链表中大约有一半的元素还 是 3 号槽位，其它的元素会放到 11 号槽位，

11 这个数字的二进制是 1011，就 是对 3 的二进制 011 增加了一个高位 1。

![img][img 2]

抽象一点说，假设开始槽位的二进制数是 xxx，

那么该槽位中的元素将被 rehash 到 0xxx 和 1xxx(xxx+8) 中。

如果字典长度由 16 位扩容到 32 位，

那么 对于二进制槽位 xxxx 中的元素将被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。

# 对比扩容缩容前后的遍历顺序 #

![img][img 3]

# 渐进式 rehash #

Java 的 HashMap 在扩容时会一次性将旧数组下挂接的元素全部转移到新数组 下面。

如果 HashMap 中元素特别多，线程就会出现卡顿现象。

Redis 为了解决 这个问题，它采用**渐进式 rehash**。

它会同时保留旧数组和新数组，然后在定时任务中以及后续对 hash 的指令操作 中渐渐地将旧数组中挂接的元素迁移到新数组上。

这意味着要操作处于 rehash 中的字典，需要同时访问新旧两个数组结构。

如果在旧数组下面找不到元素，还 需要去新数组下面去寻找。

scan 也需要考虑这个问题，对与 rehash 中的字典，它需要同时扫描新旧槽位， 然后将结果融合后返回给客户端。

# 更多的 scan 指令 #

scan 指令是一系列指令，除了可以遍历所有的 key 之外，还可以对指定的容器 集合进行遍历。

比如 zscan 遍历 zset 集合元素，hscan 遍历 hash 字典的元 素、sscan 遍历 set 集合的元素。

# 大 key 扫描 #

在平时的业务开发中，要尽量避免大 key 的产生。

那如何定位大 key 呢?

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

如果你当心这个指令会大幅抬升 Redis 的 ops 导致线上报警，还可以增加一个 休眠参数。

>     redis-cli -h 127.0.0.1 -p 7001 –bigkeys -i 0.1

上面这个指令每隔 100 条 scan 指令就会休眠 0.1s，ops 就不会剧烈抬升，但 是扫描的时间会变长。

[img]: /images/20220203/8afe82759e5f41a2a6b6a795898f8cfc.png
[img 1]: /images/20220203/2363aa3addc349ab8c3e51d6ac0e0c55.png
[img 2]: /images/20220203/bdfc5edaa21f477987c19f26e7fca2de.png
[img 3]: /images/20220203/0c404c94710b4396ac748763f3637c57.png