在Redis中，一般都会禁用keys 这种命令，因为它会遍历整个数据库，Redis是单线程的处理方式，在key很多的情况下，会严重影响redis的性能。而替代的是建议使用 scan 命令以及不同类型的scan命令:

scan(遍历当前数据库中的键)、 hscan(遍历hash表)、sscan （遍历集合中的元素）、zscan（遍历有序集合）

使用方式：

// cursor: 游标
// pattern: 扫描的key的匹配模式
// count:   返回的数据集个数
scan cursor [MATCH pattern] [COUNT count] [TYPE type]

原理分析

scanCommand 是scan的统一入口，这里处理了 scan/hscan/sscan 这三个命令的逻辑

从上面的源码中可以看出，分成4个步骤

1. 解析命令参数
2. 选择需要遍历的数据集，并进行scan数据
3. 依据match的参数进行过滤数据
4. 将结果返回给客户端

解析命令参数

scan数据

依据传入的o对象来决定要遍历的数据集，以遍历整个数据库的数据集为例，则是整个ht_table.

注意： 为了防止scan时间过于长，这里会限制遍历的次数，默认是count * 10

来看下dictScan方法的处理方式，需要分成两种情况

1. 非rehash过程的处理

这里是通过高位加1的方式：假设是以 ht_table的大小为4为例，则遍历的顺序为 0 2 1 3

二进制为 00 10 01 11

2. rehash过程

这里会以扩容或是缩容后的其中一个作为大表(以数据量大为准)，以扩容为例

这里假设以大小为 4 扩容到 8 ，则原来的每个位置的数据会一分为二(都是以2倍进行扩容)，分散在0xx 和 1xx上，那如果当前是在rehash的过程中，scan也要在两个表中进行查找，会先进行小表的扫描，再进行大表的扫描，比如当前是在ht_table[0]索引到01上进行查找,则在 ht_table[1]中，会首先查找 001，经过反向加1后，再进行反向后的数据是 101，最后通过 v&(m0^m1) 进行判断最高位是否为1 ，这里也就是会按上面的图依次 01 -> 001 -> 101来进行scan ，遍历到数据后，则调用fn 即 scanCallback 进行将数据写入keys列表中，而用户线程与后台线程可能会同时在处理，当在扫描完小表后，后台线程将小表的数据迁移了部分数据到扩容后的列表中，再进行扫描大表的数据时，就有可能读取到重复key了，在客户端处理的时候，如果对于数据的唯一性有要求，则需要特殊处理。

后台线程主要是在 databaseCron()->incrementallyRehash->dictRehashMilliseconds中实现

依据match过滤

当scan中获取了结果后，因为这个结果是没有经过匹配的，需要进行过滤

主要处理：

1. 按 key的匹配规则

2. 按type 进行过滤

3. 将未匹配的数据进行删除

总结

1. 在scan中的算法，在rehash过程中，使用高位加1的方式，可以比较好的处理扩容或是缩容后，对应位置的数据处理
2. scan的流程中的过滤是在获取了指定的数量的数据后，再进行过滤的，所以指定数量，实际不一定会返回相应的数据量
3. scan 时间复杂度也是 O(N)，但它是进行多次迭代，通过count来控制，不会长时间的阻塞线程

Tags：jedis scan