我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

redis-scan(九)

发表于 2021-05-29 | 0 | 阅读次数 160

大海捞针——scan

在Redis维护工作中,从实例的成千上万个key中找出特定前缀的key列表手动处理数据。Redis提供了一个简单粗暴的指keys用来列出所有满足特定正则字符串规则的key

这个指令有两个明显的缺点:

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

2.8版本加入了scan指令

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

基本用法

scan提供了三个参数,第一个是cursor整数值,第二个是key的正则模式,第三个是遍历的limit hint。第一次遍历时,cursor值为0,然后将返回结果中第一个整数值作为下一次遍历的cursor,一直遍历到返回的cursor值为0时结束

scan 0 match key99* count 1000
scan 13976 match key99* count 1000

从上面的过程可以看出,虽然提供的limit是1000,但是返回的结果却只有10个左右。因为limit不是限定返回结果的数量,而是限定服务器单词遍历的字典槽位数量(约等于)。如果将limit设置为10,你会发现返回结果是空的,但是游标不为零,意味着遍历还没有结束

字典结构

在Redis中所有的key都存储在一个很大的字典中,它是一维数组,是二维链表结构,第一维数组的大小总是2^n,扩容一次数组,大小空间加倍

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

scan遍历顺序

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

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

字典扩容

扩容,需要重新分配一个新的2倍大小的数组,然后将所有元素全部rehash挂到新的数组下面。rehash是将元素的hash值对数组长度进行取模运算,因为长度变量,所以每个元素挂接的槽位可能也发生了变化。

抽象一点说,假设开始槽位的二进制数是xxx,那么该槽位中的元素将被rehash到0xxx和1xxx

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

假设遍历110这个位置

  1. 扩容后,当前槽位上所有的元素对应新的槽位0110和1110,直接从0110往后遍历,之前的所有槽位已经遍历过了,就避免了扩容后对已遍历过的槽位进行重复遍历

  2. 缩容后,当前槽位对应新槽位10,而10槽位上的是010和110挂接的元素融合,010已经遍历过了会重复遍历

渐进式rehash

redis扩容采用渐进式rehash,需要同时保留旧数组和新数组,scan也要同时扫描旧槽位和新槽位,返回客户端

更多scan指令

除了遍历所有的可以之外,还可以对指定的容器集合进行遍历,比如zscan遍历zset,hscan遍历hash字典元素,sscan遍历set集合元素

大key扫描

  1. 扩容的时候回一次性申请更大的一块内存,导致卡顿
  2. 内存一次性回收,也会卡顿
  3. 数据迁移卡顿

如何定位大key

使用scan指令,对于扫描出来的每一个key,使用type指令获取key的类型,然后使用对应数据结构的size或者len来得到大小,进行排序展示

redis官方在redis-cli指令中提供扫描功能

redis-cli -h 127.0.0.1 -p 6379 --bigkeys -i 0.1
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/redis-scan
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
redis-GeoHash(八)
redis-线程IO模型(十)
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号