摘要：情况看看如何处理情况需要从和中都取出数据主要的难点在于如何在大的哈希表中找到应该取哪些代码如下判断条件为的为的为二者异或之后取值为即取二者高位的值然后看游标是否在高位还有值下一个游标的取值方法为右半部分取的低位左半部分取的高位。
顺风车运营研发团队 张仕华
1.scan类型命令
SCAN cursor [MATCH pattern] [COUNT count] SSCAN KEY cursor [MATCH pattern] [COUNT count] HSCAN KEY cursor [MATCH pattern] [COUNT count] ZSCAN KEY cursor [MATCH pattern] [COUNT count]
scan:迭代当前库
sscan:迭代一个 set 类型
hscan:迭代一个hash类型,并返回相应的值
zscan:迭代一个sorted set，并且返回相应的分数
redis是单进程单线程模型,keys和smembers这种命令可能会阻塞服务器,所以出现了scan系列的命令,通过返回一个游标，可以增量式迭代.
2.scan类型命令的实现
scan,sscan,hscan,zsan分别有自己的命令入口,入口中会进行参数检测和游标赋值,然后进入统一的入口函数:scanGenericCommand,以hscan命令为例:
scanGenericCommand主要分四步:
解析count和match参数.如果没有指定count,默认返回10条数据
开始迭代集合,如果是key保存为ziplist或者intset,则一次性返回所有数据,没有游标(游标值直接返回0).由于redis设计只有数据量比较小的时候才会保存为ziplist或者intset,所以此处不会影响性能.
游标在保存为hash的时候发挥作用,具体入口函数为dictScan,下文详细描述。
根据match参数过滤返回值,并且如果这个键已经过期也会直接过滤掉(redis中键过期之后并不会立即删除)
返回结果到客户端,是一个数组,第一个值是游标,第二个值是具体的键值对
3.dictScan中游标的实现
当迭代一个哈希表时,存在三种情况：
从迭代开始到结束,哈希表没有进行rehash
从迭代开始到结束,哈希表进行了rehash,但是每次迭代时,哈希表要么没开始rehash,要么已经结束了rehash
从迭代开始到结束,某次或某几次迭代时哈希表正在进行rehash
redis中进行rehash时会存在两个哈希表，ht[0]与ht[1],并且是渐进式rehash(即不会一次性全部rehash);新的键值对会存放到ht[1]中并且会逐步将ht[0]的数据转移到ht[1].全部rehash完毕后,ht[1]赋值给ht[0]然后
清空ht[1].
因此游标的实现需要兼顾以上三种情况,以上三种情况的游标实现要求如下:
第一种情况比较简单,假设redis的哈希表大小为4,则第一次游标为0,读取第一个bucket的数据,然后游标返回1,下次读取第二个bucket的位置,依次遍历
第二种情况比较复杂,假设redis的哈希表大小为4,如果rehash完后size变成了8.如果仍然按照上边的思路返回游标,则如下图:
假设bucket0读完之后返回了游标1,当客户端再次带着游标1返回时哈希表已经进行完rehash,并且size扩大了一倍变成了8.redis按如下方法计算一个键的bucket:
hash(key)&(size-1)
即如果size是4时,hash(key)&11,如果size是8时,hash(key)&111.因此当从4扩容到8时,原先在0bucket的数据会分散到0(000)与4(100)两个bucket,bucket对应关系表如下:
从二进制来看,当size为4时,hash(key)之后取低两位即 hash(key)&11即key的bucket位置,如果size为8时,bucket位置为 hash(key)&111，即取低三位,当低两位为00时,如果第三位为0,则为000,如果第三位为1,则为100,正好是4.其他槽位的类似
所以如果此时继续按第一种方法遍历,第四个bucket取到的值全部为重复值
第三种情况，如果返回游标1时正在进行rehash,ht[0]中的bucket 1中的部分数据可能已经rehash到
ht[1]中的bucket[1]或者bucket[5]，此时必须将ht[0]和ht[1]中的相应bucket全部遍历,否则可能会有遗漏数据
所以为了兼顾以上三种情况,做到不漏数据并且尽量不重复,redis使用了一种叫做reverse binary iteration的方法.具体的游标计算代码如下:
代码逻辑很简单,下面示例从4变为8和从4变为16以及从8变为4和从16变为4时,这种方法为何能够做到不重不漏
遍历size为4时的游标状态转移为0-2-1-3.
同理,size为8时的游标状态转移为0-4-2-6-1-5-3-7.
size为16时的游标状态转义为0-8-4-12-2-10-6-14-1-9-5-13-3-11-7-15
可以看出，当size由小变大时,所有原来的游标都能在大的hashTable中找到相应的位置,并且顺序一致,不会重复读取并且不会遗漏
例如size原来是4变为了8,且第二次遍历时rehash已经完成.此时游标为2,根据图2,我们知道size为4时的bucket2会rehash到size为8时的2和6.而size为4时的bucket0rehash到size为8时的0和4
由于bucket 0 已经遍历完,也即size为8时的0,4已经遍历,正好开始从2开始继续遍历,不重复也不会遗漏
继续考虑size由大变小的情况.假设size由16变为了4,分两种情况,一种是游标为0,2,1,3中的一种,此时继续读取,也不会遗漏和重复
但如果游标返回的不是这四种,例如返回了10,10&11之后变为了2,所以会从2开始继续遍历.但由于size为16时的bucket2已经读取过,并且2,10,6,14都会rehash到size为4的bucket2,所以会造成重复读取
size为16时的bucket2。即有重复但不会遗漏
总结一下:redis里边rehash从小到大时，scan系列命令不会重复也不会遗漏.而从大到小时,有可能会造成重复但不会遗漏。
截止目前,情况1和情况2已经比较完美的处理了。情况3看看如何处理
情况3需要从ht[0]和ht[1]中都取出数据,主要的难点在于如何在size大的哈希表中找到应该取哪些bucket.redis代码如下:
判断条件为:
v&(m0^m1)
size 4的m0为00000011,size8的m1为00000111,二者异或之后取值为00000100,即取二者mask高位的值,然后&v,看游标是否在高位还有值
下一个游标的取值方法为
v = ( ((v | m0) +1)& ~m0) | ( v & m0)
右半部分 取v的低位,左半部分取v的高位。 （v&m0)取出v的低位 例如size = 4时为 v&00000011
左半部分 （v|m0) + 1即将v的低位都置为1,然后+1之后会进位到v的高位,再次 & ~m0之后即取出了v的高位
整体来看每次将游标v的高位加1.下边举例来看:
假设游标返回了2,并且正在进行rehash,此时size由4变成了8 .则m0 = 00000011 v = 00000010
根据公式计算出的下一个游标为 ( (( 00000010|00000011) +1 ) & (11111100) )| (00000010 & 00000011) = (00000100)&(11111100)|(00000010) = (00000110) 正好是6
判断条件为 (00000010) & (00000011 ^ 00000111) = (00000010) & (00000100) = (00000000) 为0，结束循环。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/36709.html
摘要：本章将按照单个键遍历键数据库管理三个维度对一些通用命令进行介绍单键管理针对单个键的命令前面几节已经介绍过一部分了例如等下面介绍几个重要命令键重命名例如一个键名为值为下面操作将键改为如果在之前键已经存在那么它的值也将被覆盖为了防止被强行提供了 本章将按照单个键,遍历键,数据库管理三个维度对一些通用命令进行介绍. 1. 单键管理 针对单个键的命令,前面几节已经介绍过一部分了,例如type,...
摘要：顺风车运营研发团队方波遍历算法以上过程可以概括为同余分组超出预期个数问题结果存储分布遍历顺序遍历代码结论按照反转二进制算法形成特殊的遍历顺序保证在扩容时不重不漏，由于按照游标进行遍历，当遇到有冲突时，返回结果可能超过预期。 顺风车运营研发团队 方波1 遍历算法 showImg(https://segmentfault.com/img/bVbcNIR?w=1192&h=492); sho...
摘要：慕课网存储原理剖析学习总结时间年月日星期一说明本文部分内容均来自慕课网。每一列簇包含多个列列标识符。每一列数据包含了版本和值版本。 慕课网《HBase 存储原理剖析》学习总结 时间：2018年06月11日星期一 说明：本文部分内容均来自慕课网。@慕课网：https://www.imooc.com 教学源码：无 学习源码：https://github.com/zccodere/s.....
摘要：用于为做基准性能测试。设置请求总量代表客户端的请求总量，默认为。连接事务和基本概念提供了简单的事务功能以及集成脚本来解决问题。事务提供简单的事务功能，将一组需要一起执行的命令放到和两个命令之间。将结果保存在中。命令添加添加成功返回。 慢查询 基本概念 慢查询日志记录命令执行前后的超时的执行时间。(只记录命令执行时间) 慢查询的两个配置 Redis提供了slowlog-log-slowe...
摘要：全部视频每日学习记录使用录像设备记录每天的学习字典是啥，即字典，也被称为哈希表。通常情况下，一个长这样在这个哈希表中，每个存储单元被称为一个桶。完成之后，新哈希表就会被置为，为线上提供服务。 baiyan 全部视频：【每日学习记录】使用录像设备记录每天的学习 字典是啥 dict，即字典，也被称为哈希表hashtable。在redis的五大数据结构中，有如下两种情形会使用dict结构： ...
阅读 1113·2021-11-25 09:43
阅读 1695·2021-11-12 10:36
阅读 5278·2021-09-22 15:05
阅读 3259·2019-08-30 15:55
阅读 1766·2019-08-26 14:06
阅读 3501·2019-08-26 12:17
阅读 366·2019-08-23 17:55
阅读 2333·2019-08-23 16:23
