Redis scan命令解析——替代keys命令可以在生产环境使用实现遍历

一、什么是scan命令

• scan 命令用于迭代数据库中的数据库键。
• 也就是实现数据库键的遍历操作，可能大家都熟知一个keys命令，但它存在一些缺陷，在生产环境中scan是更好的选择。

二、scan命令和keys命令的对比

2.1 时间复杂度

scan命令和keys命令的时间复杂度都是O(N)，这里是一致的。

2.2 是否可以部分遍历

• keys命令是不支持类似limit的操作的，只能一次性取出符合所有条件的key
• scan命令提供了limit参数，可以控制每次返回结果的最大条数。

2.3 scan与keys比优势

虽然时间复杂度都是O(N)，但scan是分次进行的，不会阻塞线程。

三、scan命令用法

3.1 基本语法

SCAN cursor [MATCH pattern] [COUNT count]
1

• cursor：游标
• pattern：匹配的模式
• count：指定从数据集里返回多少元素，默认值为10

3.2 实例

redis 127.0.0.1:6379> scan 0   # 使用 0 作为游标，新开始一次迭代
1) "17"                        # 本次迭代返回的游标
2)  1) "key-12"
    2) "key-8"
    3) "key-4"
    4) "key-14"
    5) "key-16"
    6) "key-17"
    7) "key-15"
    8) "key-10"
    9) "key-3"
   10) "key-7"
   11) "key-1"
redis 127.0.0.1:6379> scan 17  # 使用的是第一次迭代时返回的游标 17 可以接着上一次迭代，继续迭代
1) "0" # 这次迭代返回0，表示数据集已经被完整遍历过了
2) 1) "key-5"
   2) "key-18"
   3) "key-0"
   4) "key-2"
   5) "key-19"
   6) "key-13"
   7) "key-6"
   8) "key-9"
   9) "key-11"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四、scan命令要点

4.1 scan命令的保证

从完整遍历开始直到完整遍历结束期间， 一直存在于数据集内的所有元素都会被完整遍历返回； 这意味着， 如果有一个元素， 它从遍历开始直到遍历结束期间都存在于被遍历的数据集当中， 那么 SCAN 命令总会在某次迭代中将这个元素返回给用户。

一些缺点

由于使用游标来记录迭代状态，因此scan命令是有一些缺陷的

• 同一个元素可能会被返回多次。
• 如果一个元素是在迭代过程中被添加到数据集的， 又或者是在迭代过程中从数据集中被删除的， 那么这个元素可能会被返回， 也可能不会。

4.2 scan命令每次执行返回的元素数量

• 增量式迭代命令并不保证每次执行都返回某个给定数量的元素。
• 增量式命令甚至可能会返回零个元素， 但只要命令返回的游标不是 0 ， 应用程序就不应该将迭代视作结束。

一些规则

• 对于一个大数据集来说， 增量式迭代命令每次最多可能会返回数十个元素；
• 而对于一个足够小的数据集来说， 如果这个数据集的底层表示为编码数据结构（encoded data structure，适用于是小集合键、小哈希键和小有序集合键）， 那么增量迭代命令将在一次调用中返回数据集中的所有元素。

4.3 游标为何不是按顺序的

scan命令是使用游标来遍历的，游标返回0说明整个数据集都遍历完成。

4.3.1 Redis结构

• Redis有String、List等数据结构，不过这些数据结构都是value的数据结构，Redis的Key-Value映射是通过哈希表来实现的，类似于HashMap的数组+链表形式。
• scan命令就是对这个数组进行遍历，每次返回的游标值就是数组的索引值。

4.3.2 scan遍历顺序

• 如果不考虑Redis数据结构的扩容和缩容，直接按顺序遍历就可以得到所有的key值，但如果有扩容和缩容，就需要考虑到是否有重复的遍历或遗漏的遍历。
• 如果我们按照低位加法,即从前向后遍历,当扩容或者缩容时进行的rehash操作使得数据分散到不同的槽位,这就有可能发生重复遍历与遗漏遍历的情况。
  如下图所示：
  

扩容解析

上图是高位进位的图示，如果我们此时遍历到10时发生扩容，我们接下来会继续遍历

010->110->001->101->011->111
1

也就是说扩容后也不会重复遍历到之前遍历过的元素。

这张图是正常的低位进位，如果遍历到01发生扩容，接下来继续遍历：

001->010->011->100->101->110->111
1

可以发现100这个元素被重复遍历了，因此使用高位进位是更好的选择。

4.3.3 Redis渐进式rehash

定义

随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。

过程

• 为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是 ht[0].used 属性的值）：
  如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
  如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。
• 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。
• 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。

渐进式rehash

为了避免 rehash 对服务器性能造成影响， 服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1]，而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1]。

• 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
• 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
• 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
• 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
  渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

五、参考资料

• https://www.runoob.com/redis/keys-scan.html
• 《Redis设计与实现》