写点什么

Redis Scan 原理

作者:宁静知行者
  • 2023-10-11
    福建
  • 本文字数:1134 字

    阅读完需:约 4 分钟

在 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

  1. 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 来控制,不会长时间的阻塞线程

发布于: 刚刚阅读数: 4
用户头像

作有温度的分享 2019-01-18 加入

还未添加个人简介

评论

发布
暂无评论
Redis Scan原理_redis 底层原理_宁静知行者_InfoQ写作社区