iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 13
0
自我挑戰組

Linux Inside - Synchronization & Interrupt系列 第 13

Consistent Hashing & Jump Consistent Hashing

參考

這個東西是這樣的,他其實跟 Concurrency 一點關係都沒有,但因為我在思考究竟 Hash Table 可不可以做成 Concurrency 的形式,而之前提到的 kfifo 有使用到環狀結構,Concurrent Therad Pool 有使用到 Load Balance ,綜合以上種種關鍵字,忽然想到有這個演算法存在,那就是 Consistent Hashing

而 Consistent Hashing 也有使用到環狀結構,Match 一堆關鍵字讓我整個興趣都來了,就開始花一堆時間研究~~

因為大家已經做了非常多的介紹,基本上我就只是抄他的或者用我的話再說一次,所以這是目前最水的文章,但是又覺得這兩個演算法很棒,可以介紹一下

原本只打算看 Consistent Hashing,但是又 Google 到 Jump Consistent Hashing,感覺很厲害,就一併閱讀了

至於 Hash Table 能否做成 Concurrency 的形式嗎?我覺得可以,就只是 Concurrent Linked List 的一個變形,但因為碰撞機率本來就很低,如果又發生問題,我認為會直接卡死在 Linked List 中,幾乎是永遠出不來,所以好像也不要這麼作會比較好== 或者要再設計個定時的機制,卡太久幫他換一個 Hash Value???

DHT(Distributed Hashing Table)

  • Hash Table

    location = hash(key) % size
    

    這是建立在我們已知以下兩點的情況

    1. Hash Table 的大小
    2. Hash Table 的索引值不會改變
  • DHT
    如果現在有多個節點共同維護同一個 Hash Table,但是這些節點是動態新增/減少,沒有相對應的機制,繼續使用原先 Hash Table 的機制,那麼只要節點數有變,就代表我們的記憶體大小改變了,所有的索引值都需要作更新,非常的沒有效率

    // 多一台 Server
    location = hash(key) % (size+1)
    
    // 少一台 Server
    location = hash(key) % (size-1)
    

Consistent Hashing

這邊使用的 DHT 機制是使用 Consistent Hashing ,因為他最簡單,而他採取環形空間的方式進行儲存,頭尾相連

範例說明

假設一個情況,有三個節點 node1 node2 node3 以及四份資料 data1 data2 data3 data4

第一個部份沒有問題,就是幫資料找到自己的索引值

location_for_data1 = hash(data1)
location_for_data2 = hash(data2)
location_for_data3 = hash(data3)
location_for_data4 = hash(data4)

但我們現在還不知道,該儲存在哪一個節點上,「我們幫節點也作一次 Hash」,節點所代表的數值,通常是使用 IP 位置或者節點名稱

location_for_node1 = hash(node1) // 40
location_for_node2 = hash(node2) // 5000000
location_for_node3 = hash(node3) // 100000000

那我們知道了這幾個節點位置,接下來要存取在哪裡呢!?假設節點的索引值如我們上述所說,那麼我們一開始知道他是一個環狀架構,如果這段記憶體大小是 2^32 - 1 那這個環狀架構就會根據節點的索引值,被切成三個部份

存取在哪一個節點的規則是「以順時針走訪,儲存在遇到的第一個節點」

node1 (100000000 ~ 2147483648, 0 ~ 40)
node2 (40 ~ 5000000)
node3 (5000000 ~ 100000000)

然後如果有節點掛掉了,那就把該節點的資料,轉移到下一個節點,比如說 node2 掛掉了,那就把 node2 的資料,轉移到 node3,如此只需要轉移部份資料

請注意

  1. 這並不是拿來儲存資料的技巧,而是一個 Cache 相關的服務,所以資料不見了也不會怎樣,我原本一直很疑惑,資料不見了還轉移什麼==

  2. 找到該節點之後,要怎麼儲存是你家的事,可以用 Hash 也可以改用其他資料結構

實作技巧

我們可以知道 Consistent Hashing 算是一種 Load Balance 的方法,所以公平性是非常重要的,但如果只是使用單個 IP 位置來作 Hash ,公平性其實存在一定的問題

所以,實作上可以使用虛擬節點來解決這個問題,因為我們很難保證他會均勻的切割儲存空間

可以使用這種加後綴的方式來作虛擬節點的新增,如此能使得分佈更加均勻

location_for_node1_0 = hash(node1#0)
location_for_node1_1 = hash(node1#1)
location_for_node1_2 = hash(node1#2)
....

Jump Consistent Hashing

Google 天殺的在 2014 年的時候提出了另外一個演算法,叫做 Jump Consistent Hashing A Fast, Minimal Memory, Consistent Hash Algorithm

他使用起來嘛,我覺得跟 Consistent Hashing 真的是一點狗屁關係都沒有,我猜是因為從 Consistent Hashing 開始發想的,所以沿用了這個名字

那麼他想要改善的問題是,在新增/刪除節點的時候,要移動很多資料,而這個動作很浪費效能,因為你要一直在那邊決定,到底要把資料搬到哪裡好呢,其實要花不少時間跟空間,在只有數十個節點的時候,可能還無感,但資料中心動輒幾百幾千個節點,這樣造成的效能影響是可觀的

假設現在有 N 個節點

  • Consistent Hashing

    項目 Big(O)
    時間複雜度 O(log N)
    空間複雜度 O(N)

    時間複雜度的部份,有點像 Binary Search,一直分邊找,所以複雜度是 O(log N)

    空間複雜度的部份,因為我們需要儲存全部節點的索引

  • Jump Consistent Hashing

    項目 Big(O)
    時間複雜度 O(log N)
    空間複雜度 O(1)

    居然可以常數化空間複雜度!!!

第一個版本

  • key Hash Value
  • num_buckets 節點總數,其實在 Consistent Hashing 中,他們很喜歡使用 bucket 來表示節點,像是在論文中還會看到 shard 來表示節點,反正就是節點的意思
  • b 節點索引值,表示最終要到哪個節點
  • j Jump 的意思
int ch(int key, int num_buckets) {
    random.seed(key);
    int b = 0; // This will track ch(key, j+1).
    for (int j = 1; j < num_buckets; j++) {
        if (random.next() < 1.0 / (j + 1))
            b = j;
    }
    return b;
}

可以發現現在 ch 的時間複雜度是 O(N) 而空間複雜度是 O(1),ch 的運算邏輯是隨著 j 的增加,跳躍的可能性越來越低,越來越不可能執行 b = j 這一行程式

PS:會回傳一個節點索引值,所以他不能亂設名字,只能設編號

我們透過一些範例來了解,程式的運行

  1. ch(key, 1)
    只有一個 bucket,所以 b 會等於 0

  2. ch(key, 2)
    b1/2 的機率從 0 變成 1

    b 等於 1 的機率是 1/2
    b 等於 0 的機率是 1/2

  3. ch(key, 3)
    b1/2 的機率從 0 變成 1
    b1/3 的機率從 1 變成 2

    b 等於 2 的機率是 (1/2) * (1/3) = 1/6
    b 等於 1 的機率是 1/2
    b 等於 0 的機率是 2/6

  4. ch(key, N)
    b1/2 的機率從 0 變成 1
    b1/3 的機率從 1 變成 2
    b1/4 的機率從 3 變成 4
    ....
    b1/n+1 的機率從 n 變成 n+1

現在我們把目光放在 b 如何隨著 j 去作變化,每一次變化都只有 1/n+1 的部份會作調整,有 n/n+1 的部份保持原樣

第二個版本

如果使用完全隨機的方式去產生機率,會非常的不準,所以有一種東西叫做 偽隨機性,設計出屬於我們的隨機涵式,根據 (key, j) 去作變化,讓他在每個 key 在每個 j 底下都可以均勻分佈

那要怎麼使用偽隨機性呢??其實就是直接使用 Random 函數就可以了,重點在於把每一個不同的 Hash Value 作為種子丟進去,這樣仍然可以保有 Hash 的特質,就是他的唯一性,而我們又可以根據不同的 Hash Value 得到不同的機率值

想像的是很美好,那該如何設計???這終究是個機率問題,讓我們使用機率來幫問題作定義

  • b 代表上一次的結果,上一個迴圈中選擇哪個節點

  • j 代表 Jump

  • P(j >= i) = P(ch(key, b+1) == ch(key, i))
    這行數學式表示「下一次結果跳到 i 的機率是多少」,也就是從 b+1i 的這段過程,b 都沒有改變的機率是多少,可以理解為「連續多次不變」

    現在還不明白 P(j >= i) 的機率要怎麼算,但可以透過了解「單次不變」,再延伸到「連續多次不變」

  • 單次不變的機率 i/(i+1)
    P(ch(key, i)==ch(key, i+1)) 代表的意義就是單次不變

    b+1 代表下一次結果,我們之前已經推導過了,每次都會有 n/n+1 的機率不變,把 n 替換成 i 就是長這樣

  • 連續多次不變的機率 (b+1)/i

    連續多次不變 = P(ch(key, b+1)==ch(k, b+2)) * P(ch(key, b+2)==ch(key, b+3)) * ... * P(ch(key, i-1)==ch(key, i))
               = (b+1)/(b+2) * (b+2)/(b+3) * ... * (i-1)/i
               = (b+1)/i
    

那我們可以寫出一段新的程式碼,老實說看完上面的推導,我還是不知道可以像下面這樣寫程式,而這甚至還不是最終版本

int ch(int key, int num_buckets) {
    random.seed(key);
    int b = -1;
    int j = 0;
    while (j < num_buckets) {     // j 必須要連續不變,
        b = j;                    // 每次都更新 b
        double r = random.next(); // 取得這一次的隨機結果, 0~1 之間的小數
        
        // 到底是怎麼把 (b+1)/i 轉化為 floor((b+1) / r) ???
        // P(j >= i) = (b+1)/i
        // 因為我們現在沒有 i ,所以要先把他假設出來
        // 
        // 假設 P(j >= i) 若且唯若 r <= (b+1)/i
        // r 是指隨機結果,0~1 之間的小數
        // 這邊可能覺得有點奇怪,為什麼是「小於等於」而不是「等於」
        // 但是他的邏輯是這樣,等於的時候一定對,但是小於的機率更小,所以更對
        // 反正更不可能發生,所以他變得多小都不重要,他就只是個界線,這邊所求的就是一個機率而已
        //
        // 接下來對不等式進行操作,我們現在得到 i <= (b+1)/r
        // 那麼回到原本的式子 P(j >= i) ,可以發現 j = (b+1)/r
        //
        // 可以簡單理解為把連續分佈轉換為離散分佈
        // 那為什麼不用 ceil??
        // 因為如果是 ceil 的話,會把不夠小的 r 一併映射到較大的 j,這樣是不符合 r <= (b+1)/i
        // 
        //
        // 單純從程式碼來看:
        // 因為 r 是一個小數,所以 b+1 一定會大於 r ,那麼就會完全變成一個機率問題,j 可以往後跳多少
        // 隨著 j 變大,下一輪的時候 b+1 也會變得更大,所以往後跳轉的區間會越來越大
        // 這也代表著一個區間中,每個節點被選到的機率,不斷在下降
        j = floor((b + 1) / r);   
    }
    return b;
}

只看上面還是不知道怎麼計算時間複雜度,因為是均勻分佈,所以假設每次 r 的期望值是 0.5

假設現在有 N 個節點,j = floor((b+1)/r)
第一次跳躍 j = 2 跳了 2 個節點
第二次跳躍 j = 6 跳了 4 個節點
第三次跳躍 j = 14 跳了 8 個節點
...
第 Log N 次跳躍,一定可以結束

最終版本

而這段程式碼,可以再做優化,避免調用 random 涵式,最終是使用 線性同餘方法(LCG) 這個偽隨機函數進行實作,我沒有查看系統中的偽函數一般是怎麼實作,但論文中只有提到他希望盡可能的快速,所以...就只是想找一個夠快的偽函數演算法

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

Others

如果在網路上查資料,可以發現更多結果,因為上面講的也都只是理論,但實作 Load Balance 其實有很多要注意的點

  1. 所有的節點都掛掉?
  2. etc.

但我沒有相關經驗,也沒有機器可以實驗,所以這部份我真的是不想作實驗啦@@


上一篇
kfifo 部份原始碼閱讀 & Concurrent Thread Pool
下一篇
RWLock: 只有資料結構以及原理 ......
系列文
Linux Inside - Synchronization & Interrupt18

尚未有邦友留言

立即登入留言