Redis集群之scan命令

一、背景

在生产业务中，有时需要从海量的key中获取带有特定前缀的key，那么如何获取这些特定的key呢？开源Redis提供了简单粗暴的方法—keys命令，通过keys [pattern] 可以列出满足正则字符串的所有key。

虽说简单粗暴，但是同样存在的问题也不可小嘘，keys采用的算法是遍历算法，时间复杂度O(n)，大家都知道，redis是单线程的，如果该条keys [pattern]命令获取的是上千万的级别的数据，那么其他执行就会被阻塞，直到该条命令执行完成！

针对keys存在的缺点，redis引入了scan指令，相对于keys命令来说，具备以下几个优势：

• 时间复杂度也是O(n)， 分游标进行，不会阻塞线程
• 提供了limit参数，可以控制每次返回的最大条数

目前开源的redis标准库的scan遍历指令只支持标准版的redis数据库，集群版使用scan指令时不支持全局遍历。那么集群版如何做到支持全局遍历呢？

二、Redis标准库中的scan命令

首先介绍一下redis标准库中的scan，该指令的使用方法为：SCAN cursor [pattern] [count]

• cursor：游标，表示结果集合中的特定位置。范围0-18446744073709551616 ,最大长度为20。每次被调用之后， 都会向用户返回一个新的游标， 用户在下次迭代时需要使用这个新游标作为 SCAN 命令的游标参数， 以此来延续之前的迭代过程。服务器返回0则表示迭代过程结束。
• pattern：可选参数，类似正则表达式的查询条件。
• count：可选参数，返回符合条件的最大值。

                                                                         图1  redis的存储结构

其实Redis中的key都是存储在一个很大的字典中，类似于hashMap，一维数组，二维链表，如图1所示。执行SCAN cursor [pattern] [count] 返回的游标就是第一维数组的位置索引，这个索引位置也称为槽（slot）,而limit则表示要遍历的槽位数。在遍历的过程中返回的结果可能有多有少，这是因为不是每一个槽位上都存在数据，每一次遍历会将槽位上所有链表元素进行模式匹配过滤后返回给客户端。

三、Redis集群的scan命令

如果是redis集群模式，就不能用普通的单节点redis的scan方式扫描了，那么集群版该如何支持scan命令呢？可以针对cursor做一些变化设计：

在redis数据库中，一个db存储在一个数组中，cursor就是表达数组的下标位置。一般数据库中的单节点记录数很少大于10亿（11位），因此cursor的最大值远大于存储中实际用到的值。因此在集群版中的scan中，可以让cursor 表达可分为两部分，第一部分为n位数表示的集群节点序号，第二部分为m位数表示的单节点的数组下标，N为集群节点数， 且n + m = 20，n = floor( log₁₀（N）)+1， floor即取整。

例如：对于16节点的Redis集群实例，n = floor( log₁₀（16）) + 1 = 2， m = 18，

如果cursor=06000000000000010000，即表示节点6下标10000。如此完全兼容开源标准库。

同时pattern、count参数和Redis标准库中的scan命令用法一样，保持不变。

具体流程为：