文章目录
  1. 1. 字典结构
  2. 2. 定位大key
  3. 3. 总结

redis模糊匹配key时,官方建议不要使用keyssmembers,他们的时间复杂度都是O(N),使用scanzscanhscan等。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 表示当前迭代全部完成;

1
2
3
4
5
6
7
8
9
10
11
12
13
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都存储在一个很大的字典中, 即一维数组 + 二维链表结构, 示例,

1
2
3
4
5
6
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指令中提供了这样的扫描功能,我们可以直接拿来即用。

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

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

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

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

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

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

作者署名:朴实的一线攻城狮
本文标题:redis专题10 海量数据扫描神器之scan
本文出处:http://researchlab.github.io/2018/10/07/redis-10-scan/
版权声明:本文由Lee Hong创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处, 否则保留追究法律责任的权利。

@全栈炼狱之路

关注微信公众号 @全栈炼狱之路

总访问:
总访客: