Redis 遍历

摘要

Redis官方文档：https://redis.io/documentation (opens new window)

一：前言

Redis提供了两个命令遍历所有的键，分别是 keys 和 scan

二：全量遍历键

keys pattern

keys 命令是支持 pattern 匹配的，可使用 glob 风格的通配符：

1. *：代表匹配任意字符；
2. ?：代表匹配一个字符；
3. []：代表匹配部分字符，例如[1，3]代表匹配1，3，[1-10]代表匹配1到10 的任意数字；
4. \x：用来做转义，例如要匹配星号、问号需要进行转义。

> dbsize
(integer) 0
> mset hello world redis best jedis best hill high
OK

## 获取所有的键
> keys * 
1) "hill" 
2) "jedis" 
3) "redis" 
4) "hello"

## 匹配以j，r开头，紧跟edis字符串的所有键
> keys [j,r]edis 
1) "jedis" 
2) "redis"

## 匹配hello和hill这两个键
> keys h?ll* 
1) "hill" 
2) "hello"

当需要遍历所有键时（例如检测过期或闲置时间、寻找大对象等），keys 是一个很有帮助的命令，例如想删除所有以 video 字符串开头的键，可以执行如下操作：

redis-cli keys video* | xargs redis-cli del

两个明显缺点：

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

但有时候确实有遍历键的需求该怎么办？可以在以下三种情况使用：

1. 在一个不对外提供服务的 Redis 从节点上执行，这样不会阻塞到客户端的请求，但是会影响到主从复制；
2. 如果确认键值总数确实比较少，可以执行该命令；
3. scan 命令渐进式的遍历所有键，可以有效防止阻塞。

三：渐进式遍历

Redis 为了解决 keys 确定，在2.8版本中加入了 scan 指令。具备以下特点：

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

那么每次执行scan，可以想象成只扫描一个字典中的一部分键，直到将字典中的所有键遍历完毕。Redis 存储键值对实际使用的是 hashtable 的数据结构，简化模型如下：

scan cursor [match pattern] [count number]

• cursor：必需参数，实际上 cursor 是一个游标，第一次遍历从 0 开始，每次scan遍历完都会返回当前游标的值，直到游标值为 0，表示遍历结束。
• match pattern：可选参数，作用是做模式的匹配，这点和 keys 的模式匹配很像。
• count number：可选参数，它的作用是表明每次要遍历的键个数，默认值是 10，此参数可以适当增大。

例子，现Redis仅有26个键（英文16个字母），遍历所有的键

## 第一次
> scan 0
1) "6" 
2) 1) "w" 
   2) "i"
   3) "e" 
   4) "x" 
   5) "j"
   6) "q" 
   7) "y" 
   8) "u" 
   9) "b" 
   10) "o"

## 第二次，使用第一次cursor="6"
> scan 6
1) "11" 
2) 1) "h" 
   2) "n"
   3) "m"
   4) "t" 
   5) "c"
   6) "d" 
   7) "g" 
   8) "p"
   9) "z"
   10) "a"

## 第三次，使用第二次cursor="11"，得到结果 cursor 变成 0，说明所有的键已经被遍历过了
> scan 11 
1) "0" 
2) 1) "s"
   2) "f"
   3) "r"
   4) "v"
   5) "k"
   6) "l"

除了 scan 以外，Redis 提供了面向哈希类型、集合类型、有序集合的扫描遍历命令，解决诸如 hgetall、smembers、zrange 可能产生的阻塞问题，对应的命令分别是 hscan、sscan、zscan，它们的用法和 scan 基本类似，

渐进式遍历可以有效的解决 keys 命令可能产生的阻塞问题，但是 scan 并非完美无瑕，如果在 scan 的过程中如果有键的变化（增加、删除、修改），那么遍历效果可能会碰到如下问题：新增的键可能没有遍历到，遍历出了重复的键等情况，也就是说 scan 并不能保证完整的遍历出来所有的键，这些是我们在开发时需要考虑的。

四：字典结构

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

scan 指令返回的游标就是第一维数组的位置索引，我们将这个位置索引称为槽 (slot)。如果不考虑字典的扩容缩容，直接按数组下标挨个遍历就行了。limit 参数就表示需要遍历的槽位数，之所以返回的结果可能多可能少，是因为不是所有的槽位上都会挂接链表，有些槽位可能是空的，还有些槽位上挂接的链表上的元素可能会有多个。每一次遍历都会将 limit 数量的槽位上挂接的所有链表元素进行模式匹配过滤后，一次性返回给客户端。

五：遍历顺序

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

普通加法和高位进位加法的区别

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

六：字典扩容

Java 中的 HashMap 有扩容的概念，当 loadFactor 达到阈值时，需要重新分配一个新的2 倍大小的数组，然后将所有的元素全部 rehash 挂到新的数组下面。rehash 就是将元素的hash 值对数组长度进行取模运算，因为长度变了，所以每个元素挂接的槽位可能也发生了变化。又因为数组的长度是 2^n 次方，所以取模运算等价于位与操作。

a mod 8 = a & (8-1) = a & 7
a mod 16 = a & (16-1) = a & 15
a mod 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。

抽象一点说，假设开始槽位的二进制数是 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

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

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

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

九：大 key 扫描

有时候会因为业务人员使用不当，在 Redis 实例中会形成很大的对象，比如一个很大的hash，一个很大的 zset 这都是经常出现的。这样的对象对 Redis 的集群数据迁移带来了很大的问题，因为在集群环境下，如果某个 key 太大，会数据导致迁移卡顿。另外在内存分配上，如果一个 key 太大，那么当它需要扩容时，会一次性申请更大的一块内存，这也会导致卡顿。如果这个大 key 被删除，内存会一次性回收，卡顿现象会再一次产生。

在平时的业务开发中，要尽量避免大 key 的产生。

如果你观察到 Redis 的内存大起大落，这极有可能是因为大 key 导致的，这时候你就需要定位出具体是那个 key，进一步定位出具体的业务来源，然后再改进相关业务代码设计。

那如何定位大 key 呢？

为了避免对线上 Redis 带来卡顿，这就要用到 scan 指令，对于扫描出来的每一个key，使用 type 指令获得 key 的类型，然后使用相应数据结构的 size 或者 len 方法来得到它的大小，对于每一种类型，保留大小的前 N 名作为扫描结果展示出来。

上面这样的过程需要编写脚本，比较繁琐，不过 Redis 官方已经在 redis-cli 指令中提供了这样的扫描功能，我们可以直接拿来即用。

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys

如果你担心这个指令会大幅抬升 Redis 的 ops 导致线上报警，还可以增加一个休眠参数。

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys -i 0.1

上面这个指令每隔 100 条 scan 指令就会休眠 0.1s，ops 就不会剧烈抬升，但是扫描的时间会变长。

十：参考文献

• 《Redis深度历险：核心原理和应用实践 - 钱文品》
• 《Redis 开发与运维 - 付磊、张益军》
• 官方文档 (opens new window)