iT邦幫忙

2022 iThome 鐵人賽

DAY 11
0
Software Development

NoSQL: Not Only SQL系列 第 11

[Day 11] Consistent Hashing 一致性雜湊

  • 分享至 

  • xImage
  •  

延續上一篇 Round-Robin 的作法,其中一個關鍵弱點在於節點數量異動時會造成大量資料需要進行搬移,而一致性雜湊法希望在節點數量異動時,盡可能的讓舊資料待在舊機器。

首先,假設 Hash 算出的結果在 0 ~ 8 之間,將結果頭尾相接形成一個圓,這時所有 Hash 過後的結果都會在這個圓上找到屬於自己的的那個點,接著我們將所有資料進行 Hash 計算,這時所有的資料都可以在這個圓上找到屬於它們放置的點。

https://ithelp.ithome.com.tw/upload/images/20220913/20151137lGe4NWIIRU.png

除了資料外,將節點也進行相同的 Hash 算出它的位置,一樣擺上這個圓。

https://ithelp.ithome.com.tw/upload/images/20220913/20151137QBb7d2NGEU.png

接著利用他們在圓上的位置來決定哪些資料存放在哪個節點上,所有的資料都被存放在沿著圓順時針遇到的第一個節點中,如下圖所示。

https://ithelp.ithome.com.tw/upload/images/20220913/20151137ClaM5uDa1a.png

使用這種切分方式時,增減節點不再造成大量資料的搬移,像是減少一個節點 B 只有兩筆資料搬移,增加一個節點 D 也只有一筆資料需要搬移。

https://ithelp.ithome.com.tw/upload/images/20220913/20151137zQ80vhbzDz.png

https://ithelp.ithome.com.tw/upload/images/20220913/20151137TrYBX9bznS.png

需要注意的是,當節點數量很少時,資料切分是很容易分配不平均的,像是下圖中的節點 A 僅負擔兩筆資料,節點 C 卻要處理五筆資料,是節點 A 的 2.5 倍。

https://ithelp.ithome.com.tw/upload/images/20220913/20151137S1CWGcFzgg.png

這樣的狀況可以透過新增虛擬節點解決,像是下圖所示,節點 A 和 C 各自建立了 2 個虛擬節點,同樣透過 Hash 計算出他們在圓上的位置,這時被分配到 A' 和 A'' 節點的資料真正儲存的位置一樣在 A 節點,而被分配到 C' 和 C'' 節點的資料則存到節點 C 上,於是節點 A 和 C 各自處理 4 和 3 筆資料,有著差不多的負擔。

https://ithelp.ithome.com.tw/upload/images/20220913/201511378kLRsWcUd5.png


上一篇
[Day 10] Round-Robin Sharding
下一篇
[Day 12] Key-Value Database: 簡介
系列文
NoSQL: Not Only SQL30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言