Redis 为什么不建议使用 keys 命令

本贴最后更新于 1905 天前,其中的信息可能已经东海扬尘

前言

从 Redis 实例成千上万的 key 中找出特定前缀的 key 列表来手动处理数据,可能是修改它的值,也可能是删除 key。这里就有一个问题,如何从海量的 key 中找出满足特定前缀的 key 列表来?

Redis 提供了一个简单暴力的指令 keys 用来列出所有满足特定正则字符串规则的 key。

127.0.0.1:6379> set  stupid1
OK 
127.0.0.1:6379> set  stupid2
OK 
127.0.0.1:6379> set stupid3
OK 
127.0.0.1:6379> keys * 
1) "stupid1" 
2) "stupid2" 
3) "stupid3" 

这个指令使用非常简单,指令后面跟着简单的正则字符串即可,但是有很明显的两个缺点

  1. 没有 offset、limit 参数,一次性吐出所有满足条件的 key,万一实例中有几百 w 个 key 满足条件,当你看到满屏的字符串刷的没有尽头时,你就知道难受了。
  2. keys 算法是遍历算法,复杂度是 O(n),如果实例中有千万级以上的 key,这个指令就会导致 Redis 服务卡顿,所有读写 Redis 的其它的指令都会被延后甚至会超时报错,因为 Redis 是单线程程序,顺序执行所有指令,其它指令必须等到当前的 keys 指令执行完了才可以继续。

面对这两个显著的缺点该怎么办呢?

Redis 为了解决这个问题,它在 2.8 版本中加入了大海捞针的指令——scanscan 相比 keys 具备有以下特点:

  1. 复杂度虽然也是 O(n),但是它是通过游标分步进行的,不会阻塞线程;
  2. 提供 limit 参数,可以控制每次返回结果的最大条数,limit 只是一个 hint,返回的结果可多可少;
  3. 同 keys 一样,它也提供模式匹配功能;
  4. 服务器不需要为游标保存状态,游标的唯一状态就是 scan 返回给客户端的游标整数;
  5. 返回的结果可能会有重复,需要客户端去重复,这点非常重要;
  6. 遍历的过程中如果有数据修改,改动后的数据能不能遍历到是不确定的;
  7. 单次返回的结果是空的并不意味着遍历结束,而要看返回的游标值是否为零;

字典的结构

Redis 中所有的 key 都存储在一个很大的字典中,这个字典的结构和 Java 中的 HashMap 一样,是一维数组 + 二维链表结构,第一维数组的大小总是 2^n(n>=0),扩容一次数组大小空间加倍,也就是 n++。
字典结构

scan 指令返回的游标就是第一维数组的位置索引,我们将这个位置索引称为槽 (slot)。如果不考虑字典的扩容缩容,直接按数组下标挨个遍历就行了。

limit 参数就表示需要遍历的槽位数,之所以返回的结果可能多可能少,是因为不是所有的槽位上都会挂接链表,有些槽位可能是空的,还有些槽位上挂接的链表上的元素可能会有多个。每一次遍历都会将 limit 数量的槽位上挂接的所有链表元素进行模式匹配过滤后,一次性返回给客户端。

scan 遍历顺序

scan 的遍历顺序非常特别。它不是从第一维数组的第 0 位一直遍历到末尾,而是采用了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历,是考虑到字典的扩容和缩容时避免槽位的遍历重复和遗漏。

首先我们用动画演示一下普通加法和高位进位加法的区别。
普通加法和高位进位加法

从 gif 中可以看出高位进位法从左边加,进位往右边移动,同普通加法正好相反。但是最终它们都会遍历所有的槽位并且没有重复。

字典扩容

Java 中的 HashMap 有扩容的概念,当 loadFactor 达到阈值时,需要重新分配一个新的 2 倍大小的数组,然后将所有的元素全部 rehash 挂到新的数组下面。

rehash 就是将元素的 hash 值对数组长度进行取模运算,因为长度变了,所以每个元素挂接的槽位可能也发生了变化。又因为数组的长度是 2^n 次方,所以取模运算等价于位与操作。这样速度就会快很多。

a % 8 = a & (8-1) = a & 7
a % 16 = a & (16-1) = a & 15
a % 32 = a & (32-1) = a & 31

这里的 7, 15, 31 称之为字典的 mask 值,mask 的作用就是保留 hash 值的低位,高位都被设置为 0。

接下来我们看看 rehash 前后元素槽位的变化。

假设当前的字典的数组长度由 8 位扩容到 16 位,那么 3 号槽位 011 将会被 rehash 到 3 号槽位和 11 号槽位,也就是说该槽位链表中大约有一半的元素还是 3 号槽位,其它的元素会放到 11 号槽位,11 这个数字的二进制是 1011,就是对 3 的二进制 011 增加了一个高位 1。
rehash

抽象一点说,假设开始槽位的二进制数是 xxx,那么该槽位中的元素将被 rehash 到 0xxx 和 1xxx(xxx+8) 中。 如果字典长度由 16 位扩容到 32 位,那么对于二进制槽位 xxxx 中的元素将被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。

对比扩容缩容前后的遍历顺序

比较扩容缩容前后的遍历顺序
观察这张图,我们发现采用高位进位加法的遍历顺序,rehash 后的槽位在遍历顺序上是相邻的。

假设当前要即将遍历 110 这个位置 (橙色),那么扩容后,当前槽位上所有的元素对应的新槽位是 0110 和 1110(深绿色),也就是在槽位的二进制数增加一个高位 0 或 1。这时我们可以直接从 0110 这个槽位开始往后继续遍历,0110 槽位之前的所有槽位都是已经遍历过的,这样就可以避免扩容后对已经遍历过的槽位进行重复遍历。

再考虑缩容,假设当前即将遍历 110 这个位置 (橙色),那么缩容后,当前槽位所有的元素对应的新槽位是 10(深绿色),也就是去掉槽位二进制最高位。这时我们可以直接从 10 这个槽位继续往后遍历,10 槽位之前的所有槽位都是已经遍历过的,这样就可以避免缩容的重复遍历。不过缩容还是不太一样,它会对图中 010 这个槽位上的元素进行重复遍历,因为缩容后 10 槽位的元素是 010 和 110 上挂接的元素的融合。

渐进式 rehash

JavaHashMap 在扩容时会一次性将旧数组下挂接的元素全部转移到新数组下面。如果 HashMap 中元素特别多,线程就会出现卡顿现象。Redis 为了解决这个问题,它采用渐进式 rehash

它会同时保留旧数组和新数组,然后在定时任务中以及后续对 hash 的指令操作中渐渐地将旧数组中挂接的元素迁移到新数组上。这意味着要操作处于 rehash 中的字典,需要同时访问新旧两个数组结构。如果在旧数组下面找不到元素,还需要去新数组下面去寻找。

scan 也需要考虑这个问题,对与 rehash 中的字典,它需要同时扫描新旧槽位,然后将结果融合后返回给客户端。

  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    286 引用 • 248 回帖 • 62 关注
  • Scan
    2 引用

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...