「算法」什麼是一致性哈希

點擊上方"java全棧技術"關注,每天學習一個java知識點,喜歡的也可以關注WX號"ITeye"

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

一年之前——

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

未來兩年內,系統預估的總訂單數量可達一億條左右。

按Mysql單表存儲500萬條記錄來算,暫時不必分庫,單庫30個分表是比較合適的水平分表方案。

於是小灰設計了這樣的分表邏輯:

  1. 訂單表創建單庫30個分表
  2. 對用戶ID和30進行取模,取模結果決定了記錄存於第幾個分表
  3. 查詢時需要以用戶ID作為條件,根據取模結果確定查詢哪一個分表

分表方式如下圖(為了便於描述,簡化為5個分表):

「算法」什麼是一致性哈希

過了兩個月——

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

又過了半年多——

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

小灰的回憶告一段落——

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

1.首先,我們把全量的緩存空間當做一個環形存儲結構。環形空間總共分成2^32個緩存區,在Redis中則是把緩存key分配到16384個slot

「算法」什麼是一致性哈希

2.每一個緩存key都可以通過Hash算法轉化為一個32位的二進制數,也就對應著環形空間的某一個緩存區。我們把所有的緩存key映射到環形空間的不同位置。

「算法」什麼是一致性哈希

3.我們的每一個緩存節點(Shard)也遵循同樣的Hash算法,比如利用IP做Hash,映射到環形空間當中。

「算法」什麼是一致性哈希

4.如何讓key和節點對應起來呢?很簡單,每一個key的順時針方向最近節點,就是key所歸屬的存儲節點。所以圖中key1存儲於node1,key2,key3存儲於node2,key4存儲於node3。

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

1.增加節點

當緩存集群的節點有所增加的時候,整個環形空間的映射仍然會保持一致性哈希的順時針規則,所以有一小部分key的歸屬會受到影響。

「算法」什麼是一致性哈希

有哪些key會受到影響呢?圖中加入了新節點node4,處於node1和node2之間,按照順時針規則,從node1到node4之間的緩存不再歸屬於node2,而是歸屬於新節點node4。因此受影響的key只有key2。

「算法」什麼是一致性哈希

最終把key2的緩存數據從node2遷移到node4,就形成了新的符合一致性哈希規則的緩存結構。

2.刪除節點

當緩存集群的節點需要刪除的時候(比如節點掛掉),整個環形空間的映射同樣會保持一致性哈希的順時針規則,同樣有一小部分key的歸屬會受到影響。

「算法」什麼是一致性哈希

有哪些key會受到影響呢?圖中刪除了原節點node3,按照順時針規則,原本node3所擁有的緩存數據就需要“託付”給node3的順時針後繼節點node1。因此受影響的key只有key4。

「算法」什麼是一致性哈希

最終把key4的緩存數據從node3遷移到node1,就形成了新的符合一致性哈希規則的緩存結構。

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

如上圖所示,假如node1的ip是192.168.1.109,那麼原node1節點在環形空間的位置就是hash(“192.168.1.109”)。

我們基於node1構建兩個虛擬節點,node1-1 和 node1-2,虛擬節點在環形空間的位置可以利用(IP+後綴)計算,例如:

hash(“192.168.1.109#1”),hash(“192.168.1.109#2”)

此時,環形空間中不再有物理節點node1,node2,只有虛擬節點node1-1,node1-2,node2-1,node2-2。由於虛擬節點數量較多,緩存key與虛擬節點的映射關係也變得相對均衡了。

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希

「算法」什麼是一致性哈希


分享到:


相關文章: