详解Redis SCAN命令实现有限保证的原理
SCAN命令可以为用户保证:从完整遍历开始直到完整遍历结束期间,一直存在于数据集内的所有元素都会被完整遍历返回,但是同一个元素可能会被返回多次。如果一个元素是在迭代过程中被添加到数据集的,又或者是在迭代过程中从数据集中被删除的,那么这个元素可能会被返回,也可能不会返回。
这是如何实现的呢,先从Redis中的字典dict开始。Redis的数据库是使用dict作为底层实现的。
字典数据类型
Redis中的字典由dict.h/dict结构表示:
typedefstructdict{ dictType*type; void*privdata; dicththt[2]; longrehashidx;/*rehashingnotinprogressifrehashidx==-1*/ unsignedlongiterators;/*numberofiteratorscurrentlyrunning*/ }dict; typedefstructdictht{ dictEntry**table; unsignedlongsize; unsignedlongsizemask; unsignedlongused; }dictht;
字典由两个哈希表dictht构成,主要用做rehash,平常主要使用ht[0]哈希表。
哈希表由一个成员为dictEntry的数组构成,size属性记录了数组的大小,used属性记录了已有节点的数量,sizemask属性的值等于size-1。数组大小一般是2n,所以sizemask二进制是0b11111...,主要用作掩码,和哈希值一起决定key应该放在数组的哪个位置。
求key在数组中的索引的计算方法如下:
index=hash&d->ht[table].sizemask;
也就是根据掩码求低位值。
rehash的问题
字典rehash时会使用两个哈希表,首先为ht[1]分配空间,如果是扩展操作,ht[1]的大小为第一个大于等于2倍ht[0].used的2n,如果是收缩操作,ht[1]的大小为第一个大于等于ht[0].used的2n。然后将ht[0]的所有键值对rehash到ht[1]中,最后释放ht[0],将ht[1]设置为ht[0],新创建一个空白哈希表当做ht[1]。rehash不是一次完成的,而是分多次、渐进式地完成。
举个例子,现在将一个size为4的哈希表ht[0](sizemask为11,index=hash&0b11)rehash至一个size为8的哈希表ht[1](sizemask为111,index=hash&0b111)。
ht[0]中处于bucket0位置的key的哈希值低两位为00,那么rehash至ht[1]时index取低三位可能为000(0)和100(4)。也就是ht[0]中bucket0中的元素rehash之后分散于ht[1]的bucket0与bucket4,以此类推,对应关系为:
ht[0]->ht[1] ---------------- 0->0,4 1->1,5 2->2,6 3->3,7
如果SCAN命令采取0->1->2->3的顺序进行遍历,就会出现如下问题:
•扩展操作中,如果返回游标1时正在进行rehash,ht[0]中的bucket0中的部分数据可能已经rehash到ht[1]中的bucket[0]或者bucket[4],在ht[1]中从bucket1开始遍历,遍历至bucket4时,其中的元素已经在ht[0]中的bucket0中遍历过,这就产生了重复问题。
•缩小操作中,当返回游标5,但缩小后哈希表的size只有4,如何重置游标?
SCAN的遍历顺序
SCAN命令的遍历顺序,可以举一个例子看一下:
127.0.0.1:6379[3]>keys* 1)"bar" 2)"qux" 3)"baz" 4)"foo" 127.0.0.1:6379[3]>scan0count1 1)"2" 2)1)"bar" 127.0.0.1:6379[3]>scan2count1 1)"1" 2)1)"foo" 127.0.0.1:6379[3]>scan1count1 1)"3" 2)1)"qux" 2)"baz" 127.0.0.1:6379[3]>scan3count1 1)"0" 2)(emptylistorset)
可以看出顺序是0->2->1->3,很难看出规律,转换成二进制观察一下:
00->10->01->11
二进制就很明了了,遍历采用的顺序也是加法,但每次是高位加1的,也就是从左往右相加、从高到低进位的。
SCAN源码
SCAN遍历字典的源码在dict.c/dictScan,分两种情况,字典不在进行rehash或者正在进行rehash。
不在进行rehash时,游标是这样计算的:
m0=t0->sizemask; //将游标的umask位的bit都置为1 v|=~m0; //反转游标 v=rev(v); //反转后+1,达到高位加1的效果 v++; //再次反转复位 v=rev(v);
当size为4时,sizemask为3(00000011),游标计算过程:
v|=~m0v=rev(v)v++v=rev(v) 00000000(0)->11111100->00111111->01000000->00000010(2) 00000010(2)->11111110->01111111->10000000->00000001(1) 00000001(1)->11111101->10111111->11000000->00000011(3) 00000011(3)->11111111->11111111->00000000->00000000(0)
遍历size为4时的游标状态转移为0->2->1->3。
同理,size为8时的游标状态转移为0->4->2->6->1->5->3->7,也就是000->100->010->110->001->101->011->111。
再结合前面的rehash:
ht[0]->ht[1] ---------------- 0->0,4 1->1,5 2->2,6 3->3,7
可以看出,当size由小变大时,所有原来的游标都能在大的哈希表中找到相应的位置,并且顺序一致,不会重复读取并且不会遗漏。
当size由大变小的情况,假设size由8变为了4,分两种情况,一种是游标为0,2,1,3中的一种,此时继续读取,也不会遗漏和重复。
但如果游标返回的不是这四种,例如返回了7,7&11之后变为了3,所以会从size为4的哈希表的bucket3开始继续遍历,而bucket3包含了size为8的哈希表中的bucket3与bucket7,所以会造成重复读取size为8的哈希表中的bucket3的情况。
所以,redis里rehash从小到大时,SCAN命令不会重复也不会遗漏。而从大到小时,有可能会造成重复但不会遗漏。
当正在进行rehash时,游标计算过程:
/*Makesuret0isthesmallerandt1isthebiggertable*/ if(t0->size>t1->size){ t0=&d->ht[1]; t1=&d->ht[0]; } m0=t0->sizemask; m1=t1->sizemask; /*Emitentriesatcursor*/ if(bucketfn)bucketfn(privdata,&t0->table[v&m0]); de=t0->table[v&m0]; while(de){ next=de->next; fn(privdata,de); de=next; } /*Iterateoverindicesinlargertablethataretheexpansion *oftheindexpointedtobythecursorinthesmallertable*/ do{ /*Emitentriesatcursor*/ if(bucketfn)bucketfn(privdata,&t1->table[v&m1]); de=t1->table[v&m1]; while(de){ next=de->next; fn(privdata,de); de=next; } /*Incrementthereversecursornotcoveredbythesmallermask.*/ v|=~m1; v=rev(v); v++; v=rev(v); /*Continuewhilebitscoveredbymaskdifferenceisnon-zero*/ }while(v&(m0^m1));
算法会保证t0是较小的哈希表,不是的话t0与t1互换,先遍历t0中游标所在的bucket,然后再遍历较大的t1。
求下一个游标的过程基本相同,只是把m0换成了rehash之后的哈希表的m1,同时还加了一个判断条件:
v&(m0^m1)
size4的m0为00000011,size8的m1为00000111,m0^m1取值为00000100,即取二者mask的不同位,看游标在这些标志位是否为1。
假设游标返回了2,并且正在进行rehash,此时size由4变成了8,二者mask的不同位是低第三位。
首先遍历t0中的bucket2,然后遍历t1中的bucket2,公式计算出的下一个游标为6(00000110),低第三位为1,继续循环,遍历t1中的bucket6,然后计算游标为1,结束循环。
所以正在rehash时,是两个哈希表都遍历的,以避免遗漏的情况。
总结
以上所述是小编给大家介绍的RedisSCAN命令实现有限保证的原理,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!