怎么在复述中使用扫描命令实现有限保证

　　介绍

这篇文章将为大家详细讲解有关怎么在复述中使用扫描命令实现有限保证,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。

扫描命令可以为用户保证:从完整遍历开始直到完整遍历结束期间,一直存在于数据集内的所有元素都会被完整遍历返回,但是同一个元素可能会被返回多次。如果一个元素是在迭代过程中被添加到数据集的,又或者是在迭代过程中从数据集中被删除的,那么这个元素可能会被返回,也可能不会返回。

这是如何实现的呢,先从复述中的字典dict开始.Redis的数据库是使用dict作为底层实现的。

<强>字典数据类型

复述中的字典由dict类型。h/dict结构表示:

typedef  struct  dict  { 　　,dictType  *类型; 　　,void  * privdata; 　　,dictht  ht [2]; 　　,long  rehashidx;/*, rehashing  not 拷贝progress  if  rehashidx ==1, */,unsigned  long 迭代器,/*,number  of  iterators  currently  running  */},dict类型; 　　 　　typedef  struct  dictht  { 　　,dictEntry  * *表; 　　,unsigned  long 规模; 　　,unsigned  long  sizemask; 　　,unsigned  long 使用; 　　},dictht;

字典由两个哈希表dictht构成,主要用做重新处理,平常主要使用ht[0]哈希表。

哈希表由一个成员为dictEntry的数组构成,大小属性记录了数组的大小,使用属性记录了已有节点的数量,sizemask属性的值等于大小- 1。数组大小一般是2 n,所以sizemask二进制是0 b11111…,主要用作掩码,和哈希值一起决定关键应该放在数组的哪个位置。

求关键在数组中的索引的计算方法如下:

<代码>指数=散列,d→ht .sizemask(表);

也就是根据掩码求低位值。

<强>重复的问题

字典重复时会使用两个哈希表,首先为ht[1]分配空间,如果是扩展操作,ht[1]的大小为第一个大于等于2倍ht [0] .used的2 n,如果是收缩操作,ht[1]的大小为第一个大于等于ht [0]。使用的2 n。然后将ht[0]的所有键值对重复到ht[1]中,最后释放ht[0],将ht[1]设置为ht[0],新创建一个空白哈希表当做ht [1] .rehash不是一次完成的,而是分多次,渐进式地完成。

举个例子,现在将一个大小为4的哈希表ht [0] (sizemask为11日指数=散列,0 b11)重复至一个大小为8的哈希表ht [1] (sizemask为111年指数=散列,0 b111)。

ht[0]中处于bucket0位置的关键的哈希值低两位为00,那么重复至ht[1]时指数取低三位可能为000(0)和100(4)。也就是ht[0]中bucket0中的元素改变之后分散于ht[1]的bucket0与bucket4,以此类推,对应关系为:

, ht [0],→, ht [1] 　　,- - - - - - - - - - - - - - - - - 　　0,才能→,0,4, 　　1,才能→1,5 　　2,才能→2,6 　　3,才能→,3、7

如果扫描命令采取0→1→2→3的顺序进行遍历,就会出现如下问题:

?扩展操作中,如果返回游标1时正在进行重复,ht[0]中的bucket0中的部分数据可能已经重复到ht[1]中[0]的桶或者斗[4],在ht[1]中从bucket1开始遍历,遍历至bucket4时,其中的元素已经在ht[0]中的bucket0中遍历过,这就产生了重复问题。
?缩小操作中,当返回游标5,但缩小后哈希表的大小只有4,如何重置游标?

<强>扫描的遍历顺序

扫描命令的遍历顺序,可以举一个例子看一下:

127.0.0.1:6379[3]祝辞keys  * 　　1),“bar" 　　2),“qux" 　　3),“baz" 　　4),“foo" 　　127.0.0.1:6379[3]祝辞,scan  0, count  1 　　1),“2”; 　　2),1),“bar" 　　127.0.0.1:6379[3]祝辞,scan  2, count  1 　　1),“1”; 　　2),1),“foo" 　　127.0.0.1:6379[3]祝辞,scan  1, count  1 　　1),“3”; 　　2),1),“qux" 　　,2)“baz" 　　127.0.0.1:6379[3]祝辞,scan  3, count  1 　　1),“0”; 　　2),(empty  list 或是集)

可以看出顺序是0→2→1→3,很难看出规律,转换成二进制观察一下:

00→10→01→11

二进制就很明了了,遍历采用的顺序也是加法,但每次是高位加1的,也就是从左往右相加,从高到低进位的。

<强>扫描源码

扫描遍历字典的源码在字典c/dictScan,分两种情况,字典不在进行重复或者正在进行重复。

不在进行重复时,游标是这样计算的:

m0 =, t0→sizemask;//,将游标的umask位的位都置为1 　　v  |=, ~ m0;//,反转游标 　　时间=v 牧师(v);//,反转后+ 1,达到高位加1的效果 　　v + +;//,再次反转复位 　　v =,牧师(v);

怎么在复述中使用扫描命令实现有限保证