redis中scan命令的基本实现方法

前言

在一个天朗气清的日子,小灰登上了线上的redis打算查询数据。然而他只记得前缀而不知道整个键是多少,于是在命令行敲入了“keys xxx*”命令。

瞬间服务卡死,报警邮件堆满了邮箱,而小灰,只能目瞪狗呆的等待着即将降临的case study。

基本上,keys *命令都是在线上是被运维禁止的。

redis的键在键值对大小大于hash-max-ziplist-value且个数小于hash-max-ziplist-entries的时候,是存放在散列表数据结构中的,在运行keys命令的时候,需要遍历数据库键空间,把所有键都取出来后与keys后面的pattern匹配。

在键很多的情况下,redis可能的卡顿会在秒级以上,导致所有流量都打到数据库,使得数据库雪崩。

那我们怎么才能够在查找到目标键呢?在redis2.8.0的时候加入了scan命令,可以分批次扫描redis键。虽然在应用的时候会使得要查询到全部符合要求的key的时间变长,但是大大大大减少了redis卡顿的几率

在这里先补充一下背景:

redis中的字典rehash是渐进式哈希,即不是一次性把所有的键都迁移到新的哈希表,而是在下面两种情况下迁移数据:
每次哈希表操作的时候,如果当前正在rehash,则迁移一个节点;
服务空闲时,会rehash一百个节点。

scan命令可以保证在(没有键修改的)字典正在rehash的过程中做到以下两点:

  • 不出现重复数据
  • 不遗漏数据

那scan命令是怎么做到在rehash过程中都能不重复不遗漏地遍历所有节点的呢?让我们来一起走读一下源码。

Let's GO!

在使用scan命令的时候,我们每次传入一个游标(从0开始),然后下一轮继续使用本轮redis返回的游标。scan字典的核心函数是dictScan,而dictScan的更新游标的核心代码如下:

v |= ~m0;//或者m1
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);

其中m0、m1为当前哈希表大小减一,rev是二进制逆序。

看到这里,不知道在座的各位是不是也是跟我一样是下面这个表情

让我们来模拟一下问题,就清楚了。

我们假设现在在一个四个节点的哈希表中遍历,如下图,游标的遍历节点为:0 -> 2 -> 1 -> 3 :

再来模拟8节点的情况:

看到这里是不是稍微明白了,上面那段代码就是在当前的有效位数(比如四节点则有效位数2)范围内,从左到右进一位。

假设在遍历了0,返回2之后,字典进行了扩容,则接下来应该访问 2 -> 6 -> 1 -> 5 -> 3 -> 7。

小灰:咦,那4不是遗漏了吗?

4已经在第一轮遍历0的时候,把扩容后的4的数据也访问了。

所以,假设扩容前有效位为m,因为redis的哈希表扩容每次都是当前节点满了( use==size)的时候扩容为大于size的2^N,所以扩容后有效位则为m+1。

上面那段代码其实是保持低位的m位不变,高位一个为0一个为1。这样就保证了扩容后,跳过了的节点已经在之前被访问过,因为跳过的节点是被访问过的节点分出来的。

缩容同理,可以自己推一下。

看到这里,是不是觉得redis的scan游标设计的很巧妙呢?

小灰:原来如此,看来我又可以去查数据了呢!

最后附上完整的rehash过程中scan的代码:

// 指向两个哈希表
t0 = &d->ht[0];
t1 = &d->ht[1];

/* Make sure t0 is the smaller and t1 is the bigger table */
// 确保 t0 比 t1 要小
if (t0->size > t1->size) {
 t0 = &d->ht[1];
 t1 = &d->ht[0];
}

// 记录掩码
m0 = t0->sizemask;
m1 = t1->sizemask;

/* Emit entries at cursor */
// 指向桶,并迭代桶中的所有节点
de = t0->table[v & m0];
while (de) {//迭代第一张小hash表
 next = de->next;
 fn(privdata, de);
 de = next;
}

/* Iterate over indices in larger table that are the expansion
 * of the index pointed to by the cursor in the smaller table */
do {//迭代第二张大hash表
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
 de = t1->table[v & m1];
 while (de) {
  next = de->next;
  fn(privdata, de);
  de = next;
 }

 //计算一个哈希表节点索引的方法 是 hash(key)&mask。哈希表容量为 8,则 mask 为 111,因此,节点的索引值就取决于哈希值的低 3 bit,
 // 设索引值是 abc。如果哈希表容量为 16,则 mask 为 1111,该节点的哈希值不变,而索引值是 ?abc,其中 ? 取 0 或 1 中的一个,
 // 也就是说,该节点在容量为 16 的哈希表中,索引要么是 0abc 要么是 1abc。以此类推,如果哈希表容量为32,
 // 则该节点的索引可能是 00abc,01abc,10abc 或者 11abc 中的一个。/* Increment the reverse cursor not covered by the smaller mask.*/
 v |= ~m1;//用于保留 v 的低 n 位数,其余位全置为 1
 //下面这一段,最终得到的新 v,就是向最高位加 1,且向低位方向进位
 v = rev(v);//将 v 的二进制位进行翻转,所以,v的低 n 位数成了高 n 位数,并且进行了翻转
 v++;
 v = rev(v);//再次二进制翻转

 /* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));//终止条件是 v的高位区别位没有1了,其实就是说到头了。

总结

到此这篇关于redis中scan命令的基本实现方法的文章就介绍到这了,更多相关redis中scan命令实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2020-10-03

Redis中scan命令的深入讲解

前言 熟悉Redis的人都知道,它是单线程的.因此在使用一些时间复杂度为O(N)的命令时要非常谨慎.可能一不小心就会阻塞进程,导致Redis出现卡顿. 有时,我们需要针对符合条件的一部分命令进行操作,比如删除以test_开头的key.那么怎么获取到这些key呢?在Redis2.8版本之前,我们可以使用keys命令按照正则匹配得到我们需要的key.但是这个命令有两个缺点: 没有limit,我们只能一次性获取所有符合条件的key,如果结果有上百万条,那么等待你的就是"无穷无尽"的字符串输出

Redis中Scan命令的基本使用教程

前言 Redis中有一个经典的问题,在巨大的数据量的情况下,做类似于查找符合某种规则的Key的信息,这里就有两种方式, 一是keys命令,简单粗暴,由于Redis单线程这一特性,keys命令是以阻塞的方式执行的,keys是以遍历的方式实现的复杂度是 O(n),Redis库中的key越多,查找实现代价越大,产生的阻塞时间越长. 二是scan命令,以非阻塞的方式实现key值的查找,绝大多数情况下是可以替代keys命令的,可选性更强 以下写入100000条key***:value***格式的测试数据(

php redis扩展支持scan命令实现方法

在使用阿里云的kvstore的时候,刚开始是属于公测,不收费,后来要成商业模式,收费了,8块钱一小时,太贵了,于是想到了删除部分无用的数据,但是数据量过于庞大,又不是使用keys * 来匹配(使用keys * 会直接把你redis卡死的),后期了解到了scan可以游标的找到所有的keys,于是开始捣鼓(发现我好多废话).. 开干.. [codesyntax lang="python"] # git clone https://github.com/phpredis/phpredis #

Redis中Scan命令的踩坑实录

1.原本以为自己对redis命令还蛮熟悉的,各种数据模型各种基于redis的骚操作.但是最近在使用redis的scan的命令式却踩了一个坑,顿时发觉自己原来对redis的游标理解的很有限.所以记录下这个踩坑的过程,背景如下: 公司因为redis服务器内存吃紧,需要删除一些无用的没有设置过期时间的key.大概有500多w的key.虽然key的数目听起来挺吓人.但是自己玩redis也有年头了,这种事还不是手到擒来? 当时想了下,具体方案是通过lua脚本来过滤出500w的key.然后进行删除动作.lu

详解Redis SCAN命令实现有限保证的原理

SCAN命令可以为用户保证:从完整遍历开始直到完整遍历结束期间,一直存在于数据集内的所有元素都会被完整遍历返回,但是同一个元素可能会被返回多次.如果一个元素是在迭代过程中被添加到数据集的,又或者是在迭代过程中从数据集中被删除的,那么这个元素可能会被返回,也可能不会返回. 这是如何实现的呢,先从Redis中的字典dict开始.Redis的数据库是使用dict作为底层实现的. 字典数据类型 Redis中的字典由dict.h/dict结构表示: typedef struct dict { dictTy

Redis Scan命令的基本使用方法

1. 概述 SCAN 命令以及比较相近的 SSCAN.HSCAN 和 ZSCAN 命令都用于增量迭代数据集元素: SCAN 命令用于迭代当前数据库中的数据库键. SSCAN 命令用于迭代集合(Set)中的元素. HSCAN 命令用于迭代哈希(Hash)中的字段以及对应的值. ZSCAN 命令用于迭代有序集合(Sorted Set)中的元素以及对应的得分. 由于这些命令都可以增量迭代,每次调用都只会返回少量元素,所以这些命令可以用于生产环境中,不用担心像使用 KEYS.SMEMBERS 命令带来的

redis实现加锁的几种方法示例详解

前言 本文主要给大家介绍了关于redis实现加锁的几种方法,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 1. redis加锁分类 redis能用的的加锁命令分表是INCR.SETNX.SET 2. 第一种锁命令INCR 这种加锁的思路是, key 不存在,那么 key 的值会先被初始化为 0 ,然后再执行 INCR 操作进行加一. 然后其它用户在执行 INCR 操作进行加一时,如果返回的数大于 1 ,说明这个锁正在被使用当中. 1. 客户端A请求服务器获取key的值为1表示

关于redis Key淘汰策略的实现方法

1 配置文件中的最大内存删除策略 在redis的配置文件中,可以设置redis内存使用的最大值,当redis使用内存达到最大值时(如何知道已达到最大值?),redis会根据配置文件中的策略选取要删除的key,并删除这些key-value的值.若根据配置的策略,没有符合策略的key,也就是说内存已经容不下新的key-value了,但此时有不能删除key,那么这时候写的话,将会出现写错误. 1.1 最大内存参数设置 若maxmemory参数设置为0,则分两种情况: *在64位系统上,表示没有限制.

Linux下Redis允许远程连接的实现方法

Linux安装好Redis之后,使用Java进行连接,Java代码如下 package com.wzj.demo.test; import redis.clients.jedis.Jedis; /** * Created by wzj on 2018/3/29. */ public class RedisJava { public static void main(String[] args) { //连接本地的 Redis 服务 Jedis jedis = new Jedis("192.168

异步redis队列实现 数据入库的方法

业务需求 app客户端向服务端接口发送来json 数据 每天 发一次 清空缓存后会再次发送 出问题之前业务逻辑: php 接口 首先将 json 转为数组 去重 在一张大表中插入不存在的数据 该用户已经存在 和新增的id 入另一种详情表 问题所在: 当用户因特殊情况清除缓存 导致app 发送json串 入库并发高 导致CPU 暴增到88% 并且居高不下 优化思路: 1.异步队列处理 2.redis 过滤(就是只处理当天第一次请求) 3.redis 辅助存储app名称(验证过后批量插入数据app名