欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解Redis SCAN命令實現(xiàn)有限保證的原理

 更新時間:2019年07月29日 16:47:12   作者:再見紫羅蘭  
這篇文章主要介紹了Redis SCAN命令實現(xiàn)有限保證的原理,本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值 ,需要的朋友可以參考下

SCAN命令可以為用戶保證:從完整遍歷開始直到完整遍歷結(jié)束期間,一直存在于數(shù)據(jù)集內(nèi)的所有元素都會被完整遍歷返回,但是同一個元素可能會被返回多次。如果一個元素是在迭代過程中被添加到數(shù)據(jù)集的,又或者是在迭代過程中從數(shù)據(jù)集中被刪除的,那么這個元素可能會被返回,也可能不會返回。

這是如何實現(xiàn)的呢,先從Redis中的字典dict開始。Redis的數(shù)據(jù)庫是使用dict作為底層實現(xiàn)的。

字典數(shù)據(jù)類型

Redis中的字典由dict.h/dict結(jié)構(gòu)表示:

typedef struct dict {
 dictType *type;
 void *privdata;
 dictht ht[2];
 long rehashidx; /* rehashing not in progress if rehashidx == -1 */
 unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
 dictEntry **table;
 unsigned long size;
 unsigned long sizemask;
 unsigned long used;
} dictht;

字典由兩個哈希表dictht構(gòu)成,主要用做rehash,平常主要使用ht[0]哈希表。

哈希表由一個成員為dictEntry的數(shù)組構(gòu)成,size屬性記錄了數(shù)組的大小,used屬性記錄了已有節(jié)點的數(shù)量,sizemask屬性的值等于size - 1。數(shù)組大小一般是2n,所以sizemask二進制是0b11111...,主要用作掩碼,和哈希值一起決定key應(yīng)該放在數(shù)組的哪個位置。

求key在數(shù)組中的索引的計算方法如下:

index = hash & d->ht[table].sizemask;

也就是根據(jù)掩碼求低位值。

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]設(shè)置為ht[0],新創(chuàng)建一個空白哈希表當(dāng)做ht[1]。rehash不是一次完成的,而是分多次、漸進式地完成。

舉個例子,現(xiàn)在將一個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,以此類推,對應(yīng)關(guān)系為:

 ht[0] -> ht[1]
 ----------------
  0 -> 0,4 
  1 -> 1,5
  2 -> 2,6
  3 -> 3,7

如果SCAN命令采取0->1->2->3的順序進行遍歷,就會出現(xiàn)如下問題:

•擴展操作中,如果返回游標(biāo)1時正在進行rehash,ht[0]中的bucket0中的部分數(shù)據(jù)可能已經(jīng)rehash到ht[1]中的bucket[0]或者bucket[4],在ht[1]中從bucket1開始遍歷,遍歷至bucket4時,其中的元素已經(jīng)在ht[0]中的bucket0中遍歷過,這就產(chǎn)生了重復(fù)問題。
•縮小操作中,當(dāng)返回游標(biāo)5,但縮小后哈希表的size只有4,如何重置游標(biāo)?

SCAN的遍歷順序

SCAN命令的遍歷順序,可以舉一個例子看一下:

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 or set)

可以看出順序是0->2->1->3,很難看出規(guī)律,轉(zhuǎn)換成二進制觀察一下:

00 -> 10 -> 01 -> 11

二進制就很明了了,遍歷采用的順序也是加法,但每次是高位加1的,也就是從左往右相加、從高到低進位的。

SCAN源碼

SCAN遍歷字典的源碼在dict.c/dictScan,分兩種情況,字典不在進行rehash或者正在進行rehash。

不在進行rehash時,游標(biāo)是這樣計算的:

m0 = t0->sizemask;
// 將游標(biāo)的umask位的bit都置為1
v |= ~m0;
// 反轉(zhuǎn)游標(biāo)
v = rev(v);
// 反轉(zhuǎn)后+1,達到高位加1的效果
v++;
// 再次反轉(zhuǎn)復(fù)位
v = rev(v);

當(dāng)size為4時,sizemask為3(00000011),游標(biāo)計算過程:

   v |= ~m0 v = 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時的游標(biāo)狀態(tài)轉(zhuǎn)移為0->2->1->3。

同理,size為8時的游標(biāo)狀態(tài)轉(zhuǎn)移為0->4->2->6->1->5->3->7,也就是000->100->010->110->001->101->011->111。

再結(jié)合前面的rehash:

  ht[0] -> ht[1]
  ----------------
   0  ->  0,4 
   1  ->  1,5
   2  ->  2,6
   3  ->  3,7

可以看出,當(dāng)size由小變大時,所有原來的游標(biāo)都能在大的哈希表中找到相應(yīng)的位置,并且順序一致,不會重復(fù)讀取并且不會遺漏。

當(dāng)size由大變小的情況,假設(shè)size由8變?yōu)榱?,分兩種情況,一種是游標(biāo)為0,2,1,3中的一種,此時繼續(xù)讀取,也不會遺漏和重復(fù)。

但如果游標(biāo)返回的不是這四種,例如返回了7,7&11之后變?yōu)榱?,所以會從size為4的哈希表的bucket3開始繼續(xù)遍歷,而bucket3包含了size為8的哈希表中的bucket3與bucket7,所以會造成重復(fù)讀取size為8的哈希表中的bucket3的情況。

所以,redis里rehash從小到大時,SCAN命令不會重復(fù)也不會遺漏。而從大到小時,有可能會造成重復(fù)但不會遺漏。

當(dāng)正在進行rehash時,游標(biāo)計算過程:

  /* Make sure t0 is the smaller and t1 is the bigger table */
    if (t0->size > t1->size) {
      t0 = &d->ht[1];
      t1 = &d->ht[0];
    }
    m0 = t0->sizemask;
    m1 = t1->sizemask;
    /* Emit entries at cursor */
    if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
    de = t0->table[v & m0];
    while (de) {
      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 {
      /* 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;
      }
      /* Increment the reverse cursor not covered by the smaller mask.*/
      v |= ~m1;
      v = rev(v);
      v++;
      v = rev(v);
      /* Continue while bits covered by mask difference is non-zero */
    } while (v & (m0 ^ m1));

算法會保證t0是較小的哈希表,不是的話t0與t1互換,先遍歷t0中游標(biāo)所在的bucket,然后再遍歷較大的t1。

求下一個游標(biāo)的過程基本相同,只是把m0換成了rehash之后的哈希表的m1,同時還加了一個判斷條件:

v & (m0 ^ m1)

size4的m0為00000011,size8的m1為00000111,m0 ^ m1取值為00000100,即取二者mask的不同位,看游標(biāo)在這些標(biāo)志位是否為1。

假設(shè)游標(biāo)返回了2,并且正在進行rehash,此時size由4變成了8,二者mask的不同位是低第三位。

首先遍歷t0中的bucket2,然后遍歷t1中的bucket2,公式計算出的下一個游標(biāo)為6(00000110),低第三位為1,繼續(xù)循環(huán),遍歷t1中的bucket6,然后計算游標(biāo)為1,結(jié)束循環(huán)。

所以正在rehash時,是兩個哈希表都遍歷的,以避免遺漏的情況。

總結(jié)

以上所述是小編給大家介紹的Redis SCAN命令實現(xiàn)有限保證的原理,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持!
如果你覺得本文對你有幫助,歡迎轉(zhuǎn)載,煩請注明出處,謝謝!

相關(guān)文章

  • Redis集群新增、刪除節(jié)點以及動態(tài)增加內(nèi)存的方法

    Redis集群新增、刪除節(jié)點以及動態(tài)增加內(nèi)存的方法

    本文主要介紹了Redis集群新增、刪除節(jié)點以及動態(tài)增加內(nèi)存的方法,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • Redis解決跨域存取Session問題

    Redis解決跨域存取Session問題

    本文主要介紹了Redis解決跨域存取Session問題,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-04-04
  • 關(guān)于Redis數(shù)據(jù)庫入門詳細介紹

    關(guān)于Redis數(shù)據(jù)庫入門詳細介紹

    大家好,本篇文章主要講的是關(guān)于Redis數(shù)據(jù)庫入門詳細介紹,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽
    2021-12-12
  • Redis安全策略詳解

    Redis安全策略詳解

    緩存穿透是指當(dāng)用戶在查詢一條數(shù)據(jù)的時候,而此時數(shù)據(jù)庫和緩存卻沒有關(guān)于這條數(shù)據(jù)的任何記錄,而這條數(shù)據(jù)在緩存中沒找到就會向數(shù)據(jù)庫請求獲取數(shù)據(jù)。用戶拿不到數(shù)據(jù)時,就會一直發(fā)請求,查詢數(shù)據(jù)庫,這樣會對數(shù)據(jù)庫的訪問造成很大的壓力
    2022-07-07
  • RedisDesktopManager無法遠程連接Redis的完美解決方法

    RedisDesktopManager無法遠程連接Redis的完美解決方法

    下載RedisDesktopManager客戶端,輸入服務(wù)器IP地址,端口(缺省值:6379);點擊Test Connection按鈕測試連接,連接失敗,怎么回事呢?下面小編給大家?guī)砹薘edisDesktopManager無法遠程連接Redis的完美解決方法,一起看看吧
    2018-03-03
  • 阿里云服務(wù)器安裝配置redis的方法并且加入到開機啟動(推薦)

    阿里云服務(wù)器安裝配置redis的方法并且加入到開機啟動(推薦)

    這篇文章主要介紹了阿里云服務(wù)器安裝配置redis并且加入到開機啟動,需要的朋友可以參考下
    2017-12-12
  • 分布式架構(gòu)Redis中有哪些數(shù)據(jù)結(jié)構(gòu)及底層實現(xiàn)原理

    分布式架構(gòu)Redis中有哪些數(shù)據(jù)結(jié)構(gòu)及底層實現(xiàn)原理

    這篇文章主要為大家介紹了分布式架構(gòu)Redis中有哪些數(shù)據(jù)結(jié)構(gòu)及底層的實現(xiàn)原理解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步
    2022-03-03
  • 使用Grafana監(jiān)控Redis的操作方法

    使用Grafana監(jiān)控Redis的操作方法

    這篇文章主要介紹了使用Grafana監(jiān)控Redis,號稱下一代可視化監(jiān)控系統(tǒng),結(jié)合SpringBoot使用,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-04-04
  • 64位Windows下安裝Redis教程

    64位Windows下安裝Redis教程

    這篇文章主要介紹了64位Windows下安裝Redis教程,本文使用Microsoft Open Tech group 在 GitHub上開發(fā)的一個Win64版本的Redis,需要的朋友可以參考下
    2014-09-09
  • 攔截Redis命令導(dǎo)致的Lua腳本執(zhí)行失敗的問題解決

    攔截Redis命令導(dǎo)致的Lua腳本執(zhí)行失敗的問題解決

    本文主要介紹了攔截Redis命令導(dǎo)致的Lua腳本執(zhí)行失敗的問題解決,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06

最新評論