哈希與一致性哈希

在分散式系統中，哈希和一致性哈希是數據索引或者數據分佈的常見實現方式。

數據分佈設計原則

在分散式數據存儲系統中，做存儲方案選型時，一般會考慮以下因素：

• 數據均勻
• 數據穩定
• 節點異構性
• 隔離故障域
• 性能穩定性

數據均勻有兩重含義：

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

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

節點異構性是指不同存儲節點的硬體配置可能差別很大，這樣平均分配數據就是一種不均衡。

隔離故障域是指為了保證數據的可用和可靠性，需要做數據備份，但是如果主數據和備份數據都放到了同一個硬碟或者節點，就違背了備份的初衷。一個好的數據分佈演算法，應該為每個數據映射一組存儲節點，這些節點應該儘量在不同的故障域。

性能穩定是指數據存儲和查詢的效率要有保證，不能因為節點的添加或者刪除，造成存儲或者訪問性能的嚴重下降。

數據分佈方法

我們會涉及4種不同的數據分佈方法。

哈希

哈希是指將數據按照提前規定好的函數映射到相應的存儲節點，即進行一個哈希計算，得到的結果就是數據應該存儲的節點。

它是一種非常常用的數據分佈方法，核心思想是：1）確定一個哈希函數，2）通過計算得到數據對應的存儲節點。

哈希演算法的一個優點是只要哈希函數設置得當，可以很好的保證數據均勻性，但缺點是穩定性差，當節點數量發生變化時，需要大規模數據遷移。

哈希方法適用於同類型節點且節點數量比較固定的場景。

一致性哈希

一致性哈希也是採取哈希函數，但是進行兩步哈希：

1. 對存儲節點進行哈希計算，即對存儲節點進行哈希映射。
2. 當對數據進行存儲或者訪問時，首先對數據進行映射得到一個結果，然後找到比該結果大的第一個存儲節點，就是該數據應該存儲的節點。

一致性哈希將存儲節點和數據都映射到一個首尾相連的哈希環上，存儲節點可以根據IP地址進行哈希，數據通常按照順時針方向尋找的方式，來確定自己所屬的存儲節點，即從數據映射在環上的位置開始，順時針方向找到的第一個存儲節點。

一致性哈希是對哈希方法的改進，在數據存儲時採用哈希方式確定存儲位置的基礎上，又增加了一層哈希，也就是在數據存儲前，對存儲節點預先進行了哈希映射。

這種改進很好的解決哈希方法存在的穩定性問題，當節點加入或退出時，僅影響該節點在哈希環上順時針相鄰的後繼節點。

一致性哈希帶來的主要問題是均勻性問題，即對後繼節點的負載會變大，當有節點退出時，該節點的後繼節點需要承擔該節點的所有負載，如果後繼節點承受不住，便會出現節點故障，導致後繼節點的後繼節點也面臨同樣的問題。

一致性哈希方法比較適合同類型節點、節點規模會發生變化的場景。

帶有限負載的一致性哈希

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

帶有限負載的一致性哈希方法適合同類型節點、節點規模會發生變化的場景。

帶虛擬節點的一致性哈希

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

帶虛擬節點的一致性哈希方法比較適合異構節點、節點規模會發生變化的場景。

這種方法不僅解決了節點異構性問題，還提高了系統穩定性，當節點發生變化時，會有多個節點共同分擔系統的變化。但是這種方法需要維護虛擬節點，增加了維護和管理的複雜度，同時，節點變化帶來的數據遷移等操作也會變得複雜。

下麵是4種不同的數據分片方法的詳細比較。

數據分區和數據分片的區別

數據分區是從數據存儲塊的維度進行劃分，不同的分區在物理上歸屬於不同的節點。數據分區中可以存儲不同的數據，也可以存儲相同的數據來實現數據備份。

數據分片是從數據維度進行劃分，它將一個數據結合按照一定的方式劃分成多個數據子集，不同的數據子集存儲在不同的存儲塊上，這些存儲塊可以在不同的節點上，也可以在同一個節點上。

數據分區和數據分片是兩個不同的概念，屬於分散式存儲系統中不同角色的技術。數據分區是“數據存儲”相關的技術，數據分片是“數據索引”現骨幹的技術。