redis专题10 海量数据扫描神器之scan

文章目录

1. 1. 字典结构
2. 2. 定位大key
3. 3. 总结

用redis模糊匹配key时，官方建议不要使用keys或smembers，他们的时间复杂度都是O(N),使用scan，zscan，hscan等。scan系列增量式迭代命令每次执行的复杂度为O(1)， 对数据集进行一次完整迭代的复杂度为O(N)， 其中N为数据集中的元素数量。相比keys命令执行时会阻塞掉整个redis线程而言，scan系列则是通过游标分步进行的，不会阻塞redis线程, 且在同一时间，可以有任意多个客户端对同一数据集进行迭代。

keys有两个显著缺点,

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

redis为了解决这个问题, 它在2.8版本中加入了scan系列增量式迭代命令。scan相比keys具备有以下特点:

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

当然增量式迭代命令也不是没有缺点, 如使用SMEMBERS命令可以返回集合键当前包含的所有元素， 但是对于SCAN这类增量式迭代命令来说， 因为在对键进行增量式迭代的过程中，键可能会被修改，所以增量式迭代命令只能对被返回的元素提供有限的保证(offer limited guarantees about the returned elements)。

同一个元素可能会被返回多次。scan系列命令无法保证同一元素被多次返回, 所以处理重复元素的工作交由应用程序负责处理(过滤/幂等操作)。

scan

命令: SCAN cursor [MATCH pattern] [COUNT count]

count表示每次迭代中应该从数据集里最多返回多少元素, 默认值为10, 用户可以在每次迭代时随机修改此值;

在迭代一个足够大的、由哈希表实现的数据库、集合键、哈希键或者有序集合键时, 如果用户没有使用match选项, 那么命令返回的元素数量通常和COUNT选项指定的一样, 或者比COUNT选项指定的数量稍多一些。

在迭代一个编码为整数集合(intset, 一个只由整数值构成的小集合), 或者编码为压缩列表ziplist, 由不同值构成的一个小哈希或者一个小有序集合)时, 增量式迭代命令通常会无视COUNT选项指定的值， 在第一次迭代就将数据集包含的所有元素都返回给用户。

match表示对返回的元素再进行模式匹配并将匹配结果最终返回, 需要注意的是, 对元素的模式匹配工作是在命令从数据集中取出元素之后, 向客户端返回元素之前的这段时间内进行的, 所以如果被迭代的数据集中只有少量元素和模式相匹配, 那么迭代命令或许会在多次执行中都不返回任何元素。

功能: 用于迭代当前数据库中的数据库键;

返回值: SCAN命令的回复是一个包含两个元素的数组, 第一个数组元素是用于进行下一次迭代的新游标, 而第二个数组元素则是一个数组, 这个数组中包含了所有被迭代的元素。

当返回的新游标为0 表示当前迭代全部完成;

127.0.0.1:6379> keys key*
1) "key11"
2) "key2"
3) "key22"
4) "key222"
5) "key1"
6) "key111"
127.0.0.1:6379> scan 0 match key1* count 10
1) "0"
2) 1) "key111"
   2) "key11"
   3) "key1"
127.0.0.1:6379>

字典结构

在redis中所有的key都存储在一个很大的字典中, 即一维数组 + 二维链表结构, 示例,

0
1 ->e->f->h
2
3 ->g->x
4
5 ->a->c

scan指令返回的游标就是第一维数组的位置索引，我们将这个位置索引称为槽(slot)。如果不考虑字典的扩容缩容，直接按数组下标挨个遍历就行了。count参数就表示需要遍历的槽位数，之所以返回的结果可能多可能少，是因为不是所有的槽位上都会挂接链表，有些槽位可能是空的，还有些槽位上挂接的链表上的元素可能会有多个。每一次遍历都会将count数量的槽位上挂接的所有链表元素进行模式匹配过滤后，一次性返回给客户端。

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

redis字典扩容采用了·渐进式rehash`操作。

渐进式rehash会同时保留旧数组和新数组，然后在定时任务中以及后续对hash的指令操作中渐渐地将旧数组中挂接的元素迁移到新数组上。这意味着要操作处于rehash中的字典，需要同时访问新旧两个数组结构。如果在旧数组下面找不到元素，还需要去新数组下面去寻找。

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

scan系列命令目前共计4条,

SCAN 命令用于迭代当前数据库中的数据库键;
SSCAN 命令用于迭代集合键中的元素;
HSCAN 命令用于迭代哈希键中的键值对;
ZSCAN 命令用于迭代有序集合中的元素(包括元素成员和元素分值);

定位大key

为了避免对线上redis带来卡顿，这就要用到scan指令，对于扫描出来的每一个key，使用type指令获得key的类型，然后使用相应数据结构的size或者len方法来得到它的大小，对于每一种类型，保留大小的前N名作为扫描结果展示出来。

上面这样的过程redis官方已经在redis-cli指令中提供了这样的扫描功能，我们可以直接拿来即用。

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

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

redis-cli -h 127.0.0.1 -p 6370 –-bigkeys -i 0.1

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

可进一步参考 美团针对Redis Rehash机制的探索和实践

总结

• 从redis模糊匹配场景分析入手，引入keys和scan系列增量迭代式命令方法，结合使用场景对其优劣进行了比较说明;
• 阐述了scan遍历方法，并对字典扩容进行了简单探讨;
• 从定位大key场景出发，引出了redis-cli已支持的 --bigkeys命令， 可以非常方便的协助用户定位大key问题;