分布式一致性哈希

分佈式一致性哈希#

內容來自

極客時間專欄:《分佈式技術原理與算法解析》

5 分鐘理解一致性哈希算法

數據分佈設計原則#

在分佈式數據存儲系統中，存儲方案選型時，通常會考慮數據均勻、數據穩定和節點異構性這三個維度。
從數據均勻的維度考慮，主要包括兩個方面：

不同存儲節點中存儲的數據要盡量均衡，避免讓某一個或某幾個節點存儲壓力過大，而其他節點卻幾乎沒什麼數據。
另外，用戶訪問也要做到均衡，避免出現某一個或某幾個節點的訪問量很大，但其他節點卻無人問津的情況。

從數據穩定的維度考慮，當存儲節點出現故障需要移除或者擴增時，數據按照分佈規則得到的結果應該盡量保持穩定，不要出現大範圍的數據遷移。

從節點異構性的維度考慮，不同存儲節點的硬體配置可能差別很大，導致性能差別就很大，但是分到的數據量、用戶訪問量都差不多，這本質就是一種不均衡。所以，一個好的數據分佈算法應該考慮節點異構性。

一致性哈希#

一致性哈希是指將存儲節點和數據都映射到一個首尾相連的哈希環上，存儲節點可以根據 IP 地址進行哈希（相當於兩次哈希），數據通常通過順時針方向尋找的方式，來確定自己所屬的存儲節點，即從數據映射在環上的位置開始，順時針方向找到的第一個存儲節點。目前，Cassandra 就使用了一致性哈希方法。

在使用一致哈希算法後，哈希表槽位數（大小）的改變平均只需要對 K/n 個關鍵字重新映射，其中 K 是關鍵字的數量， n 是槽位數量。然而在傳統的哈希表中，添加或刪除一個槽位的幾乎需要對所有關鍵字進行重新映射。比如 Node2 節點宕機後，干擾的只有前面的數據（原數據被保存到順時針的下一個伺服器節點 Node3），而不會干擾到其他的數據。

這種方法雖然提升了穩定性，但隨之而來的均勻性問題也比較明顯，有節點退出後，該節點的後繼節點需要承擔該節點的所有負載，如果後繼節點承受不住，便會出現節點故障，導致後繼節點的後繼節點也面臨同樣的問題。Google 在 2017 年提出了帶有限負載的一致性哈希算法，就對這個問題做了一些優化。

帶有限負載的一致性哈希#

帶有限負載的一致性哈希方法的核心原理是，給每個存儲節點設置了一個存儲上限值來控制存儲節點添加或移除造成的數據不均勻。當數據按照一致性哈希算法找到相應的存儲節點時，要先判斷該存儲節點是否達到了存儲上限；如果已經達到了上限，則需要繼續尋找該存儲節點順時針方向之後的節點進行存儲。

該算法的詳細內容，參考“Consistent Hashing with Bounded Loads”這篇論文。

帶有限負載的一致性哈希方法比較適合同類型節點、節點規模會發生變化的場景。目前，在 Google Cloud Pub/Sub、HAProxy 中已經實現該方法，應用於 Google、Vimeo 等公司的負載均衡項目中。

帶虛擬節點的一致性哈希#

一致性哈希、帶有限負載的一致性哈希，都沒有考慮節點異構性的问题。如果存儲節點的性能好壞不一，數據分佈方案還按照這些方法的話，其實還是沒做到數據的均勻分佈。

帶虛擬節點的一致性哈希方法，核心思想是根據每個節點的性能，為每個節點劃分不同數量的虛擬節點，並將這些虛擬節點映射到哈希環中，然後再按照一致性哈希算法進行數據映射和存儲。

帶虛擬節點的一致性哈希方法比較適合異構節點、節點規模會發生變化的場景。目前 Memcached 緩存系統實現了該方法。

總結拓展#

幾種哈希算法的總結#

數據分片和數據分區，有何區別？#

數據分區是從數據存儲塊的維度進行劃分，不同的分區物理上歸属于不同的節點。比如，現在有 2 個節點 Node1 和 Node2，2 個數據分區 Partition1 和 Partition2，Partition1 屬於 Node1、Partition2 屬於 Node2。
數據分片是從數據的維度進行劃分，是指將一個數據集合按照一定的方式劃分為多個數據子集，不同的數據子集存在不同的存儲塊上，而這些存儲塊可以在不同的節點上，也可以在同一節點上。