一文搞懂一致性 hash 的原理和實現

在 go-zero 的分佈式緩存系統分享裏，Kevin 重點講到過一致性 hash 的原理和分佈式緩存中的實踐。本文來詳細講講一致性 hash 的原理和在 go-zero 中的實現。

以存儲爲例，在整個微服務系統中，我們的存儲不可能說只是一個單節點。

那麼問題來了，多節點情況下，數據應該寫入哪個節點呢？

hash

所以本質來講：我們需要一個可以將輸入值 “壓縮” 並轉成更小的值，這個值通常狀況下是唯一、格式極其緊湊的，比如 uint64：

這個就是 hash 算法完成的。

但是採取普通的 hash 算法進行路由，如：key % N 。有一個節點由於異常退出了集羣或者是心跳異常，這時再進行 hash route ，會造成大量的數據重新 分發到不同的節點 。節點在接受新的請求時候，需要重新處理獲取數據的邏輯：如果是在緩存中，容易引起 緩存雪崩。

此時就需要引入 consistent hash 算法了。

consistent hash

我們來看看 consistent hash 是怎麼解決這些問題的：

rehash

先解決大量 rehash 的問題：

如上圖，當加入一個新的節點時，影響的 key 只有 key31，新加入（剔除）節點後，只會影響該節點附近的數據。其他節點的數據不會收到影響，從而解決了節點變化的問題。

這個正是：單調性。這也是 normal hash 算法無法滿足分佈式場景的原因。

數據傾斜

其實上圖可以看出：目前多數的 key 都集中在 node 1 上。如果當 node 數量比較少的情況下，可能引發多數 key 集中在某個 node 上，監控時發現的問題就是：節點之間負載不均。

爲了解決這個問題，consistent hash 引入了 virtual node 的概念。

既然是負載不均，我們就人爲地構造一個均衡的場景出來，但是實際 node 只有這麼多。所以就使用 virtual node 劃分區域，而實際服務的節點依然是之前的 node。

具體實現

先來看看 Get()：

Get

先說說實現的原理：

  1. 計算 key 的 hash

  2. 找到第一個匹配的 virtual node 的 index，並取到對應的 h.keys[index] ：virtual node hash 值

  3. 對應到這個 ring 中去尋找一個與之匹配的 actual node

其實我們可以看到 ring 中獲取到的是一個 []node 。這是因爲在計算 virtual node hash ，可能會發生 hash 衝突，不同的 virtual node hash 對應到一個實際 node。

這也說明：node 與 virtual node 是一對多的關係。而裏面的 ring 就是下面這個設計：

這個其實也就表明了一致性 hash 的分配策略：

  1. virtual node 作爲值域劃分。key 去獲取 node ，從劃分依據上是以 virtual node 作爲邊界

  2. virtual node 通過 hash ，在對應關係上保證了不同的 node 分配的 key 是大致均勻的。也就是 打散綁定

  3. 加入一個新的 node，會對應分配多個 virtual node。新節點可以負載多個原有節點的壓力，從全局看，較容易實現擴容時的負載均衡。

Add Node

看完 Get 其實大致就知道整個一致性 hash 的設計：

type ConsistentHash struct {
  hashFunc Func       // hash 函數
  replicas int       // 虛擬節點放大因子
  keys     []uint64     // 存儲虛擬節點hash
  ring     map[uint64][]interface{}     // 虛擬節點與實際node的對應關係
  nodes    map[string]lang.PlaceholderType // 實際節點存儲【便於快速查找，所以使用map】
  lock     sync.RWMutex
}

好了這樣，基本的一個一致性 hash 就實現完備了。

具體代碼：https://github.com/tal-tech/go-zero/blob/master/core/hash/consistenthash.go

使用場景

開頭其實就說了，一致性 hash 可以廣泛使用在分佈式系統中：

  1. 分佈式緩存。可以在 redis cluster 這種存儲系統上構建一個 cache proxy，自由控制路由。而這個路由規則就可以使用一致性 hash 算法

  2. 服務發現

  3. 分佈式調度任務

以上這些分佈式系統中，都可以在負載均衡模塊中使用。

項目地址

https://github.com/tal-tech/go-zero

歡迎使用 go-zero 並 star 支持我們！

微信交流羣

關注『微服務實踐』公衆號並點擊 交流羣 獲取社區羣二維碼。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/JiO8kUaufV53u3p_TUBhBQ

猜你喜歡