來源 | 靳剛同學

作者 | 靳剛

“一致性hash的設(shè)計初衷是解決分布式緩存問題，它不僅能起到hash作用，還可以在服務(wù)器宕機時，盡量少地遷移數(shù)據(jù)。因此被廣泛用于狀態(tài)服務(wù)的路由功能”

01

—

分布式系統(tǒng)的路由算法

假設(shè)有一個消息推送系統(tǒng)，其簡易架構(gòu)如下

設(shè)備接入層不僅要接收設(shè)備的登錄、下線等狀態(tài)命令，還要把開發(fā)者的消息推送給設(shè)備。這個時候設(shè)備接入層就需要維護設(shè)備的狀態(tài)信息（當然可以專門拆一個狀態(tài)服務(wù)去維護這些信息，要求這部分必須少有代碼更新，具體原因自己去想哦=_=）。這個時候設(shè)備接入層的每臺server都保留一批設(shè)備的狀態(tài)信息cache，設(shè)備應(yīng)該連接哪臺server去獲取數(shù)據(jù)，同時中間層的消息又該發(fā)往哪個server去推送呢？這就用到了一致性hash算法。

02

—

什么是一致性hash算法

一致性hash由對象、靜態(tài)資源段、算法和機器組成。它要做的是：對象通過算法判斷連哪臺機器。在如上系統(tǒng)中：設(shè)備id（userID）為對象；固定號段(cache)為資源段；服務(wù)器為機器。

在一致性hash算法中，這些資源段圍成了一個閉環(huán)，每臺機器又保存著目標資源段的數(shù)據(jù)，每個資源段對應(yīng)一批對象/設(shè)備；這樣如果某臺機器掛了，那它對應(yīng)的資源段轉(zhuǎn)移到離它較近的機器x，這臺dead server對應(yīng)的設(shè)備連接到機器x就行。

現(xiàn)在假設(shè)這四個資源段對應(yīng)的設(shè)備，活躍情況相差較大。比如說資源段1、2對應(yīng)的設(shè)備特別活躍，而資源段3和4幾乎沒活動。這樣機器1-2需要保存大量的狀態(tài)數(shù)據(jù)，而3-4則有大量的空置，顯然是不合理的。改進版的一致性hash算法是這樣操作的：它不再是每臺機器去保存一個連續(xù)的資源段，而是讓每臺機器都保存多個區(qū)域的部分資源段。如機器1保存每個資源段的1/4，機器2保存每個資源段的1/4，機器3、4同樣如此。這樣即使個別號段有熱點，也會均攤到不同的機器。

03

—

一致性hash在系統(tǒng)中的應(yīng)用

如上介紹了一致性hash的概念和改進，在系統(tǒng)實踐中，我們用戶量非常大，往往不只一個集群。我們是如此使用一致性hash：

• 首先根據(jù)不同號段選擇對應(yīng)的集群，這部分是可配置的

• 確定集群后，根據(jù)一致性hash把設(shè)備匹配到server的某個instance上(每臺server部署多個設(shè)備接入層實例（1.每個instance保存的狀態(tài)信息更分散;2.服務(wù)的gc問題會有緩解）

• 建立機器虛擬節(jié)點：把user逆序(打亂之前連續(xù)userId)，組成新的資源段;相當于建立了server虛擬節(jié)點

• 記錄每臺server鎖服務(wù)的設(shè)備數(shù)，如果機器A掛了，挑選服務(wù)設(shè)備數(shù)最少的機器去承接kicked-device

04

—

不是所有情況都適合一致性hash

以上介紹了一致性Hash的原理和實踐，但不是所有的服務(wù)都適合用一致性hash來路由。比如01節(jié)中的消息推送系統(tǒng)，中間層是無狀態(tài)的，開發(fā)者接入層請求cluter-A的哪臺機器都行，它只要做完基本校驗后，把消息異步發(fā)給MQ即可，無需等待結(jié)果直接返回; 而設(shè)備接入層是有狀態(tài)的，且對較高時延無法忍受，更適合一致性Hash選擇好server-instance，然后通過TCP/UDP來通信。