給面試官講明白：一致性hash的原理和實踐

「一致性hash的設計初衷是解決分散式緩存問題，它不僅能起到hash作用，還可以在伺服器宕機時，盡量少地遷移數據。因此被廣泛用於狀態服務的路由功能」

01分散式系統的路由演算法

假設有一個消息推送系統，其簡易架構如下

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

02什麼是一致性hash演算法

一致性hash由對象、資源、演算法和機器組成。它要做的是：對象通過演算法判斷連哪台機器。在如上系統中：設備id(userID)為對象;其對應的狀態數據(cache)為資源;伺服器為機器。

在一致性hash演算法中，這些資源圍成了一個閉環，每台機器又保存著一個資源段，每個資源段對應一批對象/設備;這樣如果某台機器掛了，那它對應的資源轉移到離它較近的機器x，這台dead server對應的設備連接到機器x就行。

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

03一致性hash在系統中的應用

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

首先根據不同號段選擇對應的集群，這部分是可配置的

確定集群後，根據一致性hash把設備匹配到server的某個instance上(每台server部署多個設備接入層實例(1.每個instance保存的狀態信息更分散;2.服務的gc問題會有緩解)

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

記錄每台server鎖服務的設備數，如果機器A掛了，挑選服務設備數最少的機器去承接kicked-device

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

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

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！