Redis遍历方式思考--字典扩容方式

小鱼儿 2022-12-20 05:36 112阅读 0赞

#### 全量遍历keys ####

*  工作中线上Redis维护，有时候我们需要查询特定前缀的缓存key列表来手动处理数据。可能是修改值，删除key。那么怎么才能快速的从海量的key中查找到对应的前缀匹配项。
 *  Redis提供了一下简单的指令，例如keys用来满足特定正则下的key如下：

//查找nettyim前缀的key
    keys nettyim*
    //查询所有key
    keys *

*  以上命令特别简单，只需要提供一个简单的正则字符串即可，但是缺点明显：
    
     *  没有offset，limit参数，一次查询所有满足条件的key，如果实例中有几百万key匹配到，那查询到了也没有任何意义。
     *  keys算法是遍历算法，复杂度是O(n)，如果Redis实例中有千万级数据key，这个指令就会导致Redis服务器卡顿，所有读写Redis的其他指令都会被延后甚至会超时报错，因为Redis是单线程，顺序执行所有指令，其他指令必须等到当前keys指令执行完才可以继续

#### 大海捞针指令scan ####

*  scan 指令有一下几个特点：
    
     *  复杂度也是O(n)。但是scan命令可以通过游标分布进行查询，不会阻塞线程，相当于分页查找
     *  提供limit参数，可以控制每次放回结果的条数，limit只是一个hint，返回的结果可多可少。
     *  同keys一样，他提供了模式匹配功能
     *  服务器不需要为游标保存状态，右边的唯一状态就是scan返回给客户端的游标整数
     *  返回的结果可能会重复，需要客户端去重
     *  变量过程如果有数据修改，改动后的数据能否查询到是不确定的
     *  单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零

##### scan基本用法 #####

*  sacn提供三个参数，第一个cursor整数值，第二个是key的正则模式，第三个是遍历limit hint。scan每次查询会返回一个游标值，标识现在已经遍历到此处游标位置，我们下一次遍历可以按照游标开始，如下

scan 0 match nettyim* count 1000
    scan 641024 match nettyim* count 100
    scan 1812480 match nettyim* count 100
    scan 7071744 match nettyim* count 100
    ....

*  查询过程中，我们设定limit = 1000，但是并不是每次都能查询到一千条数据，因为limit不是限制返回的数量，二手限制服务器每次遍历的Redis服务器存储数据的字典槽个数。如果将limit设置为10，可能返回0个数据，但是游标值不为0 ，那是因为前10个槽中没有数据而已。

#### 字典结构 ####

*  Redis中所有key存储在一个很大的字典中，这个字典结构和java中HashMap类似，如下图中所示，他是一位数组结构，加上二维链表结构。第一位数组的大小总数(2 ^ n) 扩容一次数组，大小空间加倍 (2^n+1)
 *  scan指令返回的游标就是第一位数组的位置索引，这个就是上面说的数据槽（slot），如果不考虑字典的扩容，缩容直接按数组下标逐个遍历就行。limit参数标识需要遍历的槽位数，之所以返回的结果可能多可能少，是因为不是所有的槽位上都挂载了链表，有可能槽位是空的，每次遍历都会将limit数量的槽位上挂接的所有链表元素进行模式匹配过滤后一起返回客户端。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70_pic_center]

#### scan遍历顺序 ####

*  scan遍历的凡是不是从一维数组的第0 位开始遍历，而是采用高位进位的方法来遍历。之所以用这样的方式是考虑到Redis的扩容规则，当扩容的时候这样遍历就能避免槽位的重复遍历，和遗漏
 *  如下图，是普通的加法和高位进位加法的区别：

##### 普通遍历 #####

![在这里插入图片描述][20201110192825654.png_pic_center]

##### 高位进位遍历 #####

![在这里插入图片描述][20201110192939709.png_pic_center]

*  上图中看出高位进位加法也是一样遵循二进制的规则，只不过进位从左边开始增加移动，同普通加法正好相反，但是最终还是可以遍历所有槽位并且没有重复。

#### 字典扩容 ####

*  java中HashMap也有扩容的概念，当LoadFactor达到阀值的时候，需要重新分配一个新的2倍大小的数组，然后将所有元素全部rehash挂到新的数组下面。rehash是将原始的hash值对数组长度取模运算，因为长度变量，所有每个元素挂载的位置槽就可能变化。有因为数组长度是2的n次方，取模运算等价于位与操作（&）;
 *  Redis中扩容方法如下图中所示，当字典长度由8 为扩容到16位，那么3号槽的数据011 将会被rehash到3号槽和11号槽中。也就是该槽位链表中大约有一半的元素还在3号槽位中，其他元素被放到11号槽位中，11 这个数字正好是1011，就是3 的二进制数011 高位添加一个1.  
    ![在这里插入图片描述][20201110195543964.png_pic_center]
 *  **按如上方式加上槽位二进制是XXX，你们该槽位中元素将被rehash到0XXX和1XXX中（XXX+8），如果字典长度由16 扩容到  
    32，你们XXXX中元素rehash后到0XXXX 和1XXXX（XXXX+16）**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70_pic_center 1]

*  如上扩容缩容示意图，我们发现用高位进位加法的遍历方式，rehash后的槽位在遍历顺序上是相邻的，
 *  扩容情况：如上加入我们要遍历100 这个槽位，那么扩容后，当前槽位上所有元素到新的槽位0100,1100，也就是在槽位二进制高位添加0,1。这时候，我们可以直接从0100开始往后遍历，而按照scan的变量规则，下一个正好是1100（高位加1），之前的已经都遍历完了之后的按照这个变量方式也不会遗漏。
 *  缩容情况：加入当前变量101，那么缩容后当前槽位所有的元素对应的01，也就是去掉高位的1，这个时候我们可以直接从01这个槽位继续向后遍历，01 之前的槽位已经遍历完了，这样就可以避免缩容重复遍历，缩容有一点不一样的地方是，会对101中的元素进行遍历，因为缩容的时候01 中的数据是结合了001 和101 链表中所有的数据。

#### 渐进式rehash ####

*  java中HashMap在扩容时候，会一次性将旧的数据数组下挂载的元素全部转移到新的数组下，如果Hashmap中元素特别多，线程会出现卡顿现象。Redis为了解决这个问题采用渐进式rehash
 *  同事保留新旧数组。让后在定时任务中对后续hash的指令操作渐渐的将数组中挂载的元素迁移到新的数组中区。scan此时遍历处于rehash阶段的字典需要同时访问新旧两个数组结构。如果在就数组下面找不到元素，需要到新数组中在找一次。

#### 更多scan指令 ####

*  scan指令是一系列指令，除了可以遍历所有key，还有其他指定数据结构的特定指令。例如zscan遍历zset集合元素，hscan遍历hash字典元素，sscan遍历set集合元素
 *  原理同scan类似，因为hash底层就是字典，set也是特殊hash（所有value都是null）zset内部也是使用字典来存储所有元素内容

#### 大key扫描 ####

*  有时候因为业务使用不当，在Redis实例中存在一个很大的对象，比如一个很大的zset。这样的对象给Redis继续数据迁移带来很大的问题。在数据迁移过程中集群环境下key太大，导致迁移数据变慢造成服务卡顿。同时扩容时候会一次性申请更大的一块内存，也会导致卡顿。如果这个key被删除内存会被一次性回收卡顿现象也会再次产生
 *  平时应该避免大key的产生
 *  如果Redis内存波动大，极有可能因为大key导致的，这时候需要定位具体那个key，进一步定位出具体的业务，然后在改进。
 *  scan指令遍历，用type指令获取key类型，size或者len得到大小，用脚本扫描出来，不过此方法比较繁琐
 *  Redis官方在redis-cli指令中提供这样的扫描功能，我们可以直接用如下：

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

*  以上命令会自动的查询大key，但是会导致Redis的ops（operation pre seconds 每秒操作次数）大幅提高，我们可以增加一个休眠时间，如下：

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

*  上面指令每隔100条scan指令休眠0.1秒，这样ops就不会剧烈提高，只是扫描时间变长而已。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c4b31f71d87542978e1daf4be7d01bb3.png
[20201110192825654.png_pic_center]: https://img-blog.csdnimg.cn/20201110192825654.png#pic_center
[20201110192939709.png_pic_center]: https://img-blog.csdnimg.cn/20201110192939709.png#pic_center
[20201110195543964.png_pic_center]: https://img-blog.csdnimg.cn/20201110195543964.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201110200853186.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy,size_16,color_FFFFFF,t_70#pic_center