共計 3711 個字符，預計需要花費 10 分鐘才能閱讀完成。
今天就跟大家聊聊有關怎么分析一致性 HASH 算法，可能很多人都不太了解，為了讓大家更加了解，丸趣 TV 小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。
一致性 HASH 算法研究 1. 引言
在研究 Ceph CRUSH 算法時，看到有文章說它是一種特殊的一致性 HASH 算法，于是我便開始研究一致性 HASH 算法做先期準備，發現理念確實接近，區別在于虛擬節點和物理節點的映射辦法不同，這是 Ceph 的核心算法，非常關鍵, 此處不表，下文分解。
2. 一致性 HASH 的出現背景及其優勢
在分布式系統中，常常利用 HASH 算法進行數據分布，目的是希望將數據均勻的分布到各節點，分擔壓力，尤其是在緩存系統中。一個典型的設計如下：
2.1 場景說明
為了提升系統性能，解決數據庫的性能瓶頸，設置 N 個緩存服務器，將應用和數據庫進行隔離，每個緩存服務器負責數據庫 1 / N 的數據。應用程序在訪問數據時，根據關鍵字計算得到 hash 值，并根據一定規則找到數據所在的緩存節點。
2.2 最簡單模型
最簡單的辦法是，采用 hash(key) mode N 的辦法計算文件落在的服務器位置，那么在 Find Cache Server 步驟中，需要增加一個取摸操作，存在的問題是：
集群添加機器，計算公式變為 hash(key) / (N + newAddedCount)
集群退出機器，計算公式變為 hash(key) / (N – removedCount)
由于計算公式的分母變化，計算值也都將發生變化。通過取摸運算，找到的節點錯誤，緩存將失效。我們需要一種方法，當對集群擴容，或者從集群中移除失效機器時，只會導致少量的數據失效，可以很快的在正常的機器或者新增的機器上重新構建起緩存。
2.3 一致性 HASH 模型
基于這個想法，一些專業人士更提出了明確的要求，并形成論文 一致性 HASH 論文
2.3.1 一致性 HASH 基本設計思路
一致性哈希構造了一個 hash 環，將服務器節點映射到環上，將 obj 也映射到環上，將他們至于同一個空間中（0~2^32-1），針對每一個對象，順時針查找第一個 =hash(obj) 的節點，就是它要存放的目標系統，如果沒有找到，按照順時針，就回歸到第一個服務器。
![在上圖實例中，根據一致性 HASH 規則，分配后的結果如下：
obj1 ~ obj3 歸屬于 Cache Server B；
obj4 ~ obj7 歸屬于 Cache Server C;
obj8~obj11 歸屬于 Cache Server A. 正是按照上述規則分析下來的結果。
但是存在一個數據分布不均衡的問題，在下圖中可以看到，大量的數據會落在服務器 A 上，但是 B,C 上只有少量數據。數據分布明顯不平衡。
為了解決數據不均衡的問題，一致性 HASH 中引入了虛擬節點，將對象均勻的映射到虛擬節點，再將虛擬節點映射到物理節點。
通過設置大量的虛擬節點，將數據平均分布到虛擬節點上，最終達到平均分布到物理節點上的效果。此處的關鍵點是：通過為每個物理節點配置虛擬節點，所有的虛擬節點可以平均的散布到 hash 環上此處一看使用的 hash 函數；另外看物理節點設置的虛擬節點數量；
此處，一致性 hash 是符合我們的期望的：
1、平衡性 (Balance)：hash 后的結果能夠平均分布，比如在存儲中，數據可以平均分布到各節點，不會出現個別節點數據量特別少，個別特別多的情況；
2、單調性 (Monotonicity)：當新增或者移除節點時，要么映射到原來的位置，或者映射到新節點；不會映射到無效節點；
2.3.2 數據分布均衡測試
為了測試一致性 hash 算法的特性以及虛擬節點對數據分布平衡的影響，我用 C ++ 實現了一個一致性 hash 算法，進行統計試驗。
在相同的測試數據，相同的物理節點下，測試不同虛擬節點數量下，數據的分布情況：測試樣本：10000 條 URL 記錄，用作對象名稱，作為 hash 函數的輸入 采用的 hash 函數：c++11 中默認的 std::hash() 數據中虛擬節點數量參數是指每個物理節點對應的虛擬節點數量。
1 節點
101.71.4.31:80 764
101.71.4.32:80 2395
101.71.4.33:80 1478
101.71.4.34:80 786
101.71.4.35:80 4577
101.71.4.31:80 1139
101.71.4.32:80 4862
101.71.4.33:80 1484
101.71.4.34:80 1243
101.71.4.35:80 1272
100 節點
101.71.4.31:80 2646
101.71.4.32:80 2576
101.71.4.33:80 1260
101.71.4.34:80 705
101.71.4.35:80 2813
512 虛擬節點
101.71.4.31:80 2015
101.71.4.32:80 2038
101.71.4.33:80 1948
101.71.4.34:80 2128
101.71.4.35:80 1871
1024 虛擬節點
101.71.4.31:80 2165
101.71.4.32:80 1389
101.71.4.33:80 2045
101.71.4.34:80 2123
101.71.4.35:80 2278
2048 節點
101.71.4.31:80 1976
101.71.4.32:80 1939
101.71.4.33:80 1892
101.71.4.34:80 2164
101.71.4.35:80 2029
101.71.4.34:80 1879
101.71.4.35:80 1915從數據可以看到，隨著對應的虛擬節點越來越多，數據的分布也越來越平衡，但是虛擬節點到達一定數量后，到達了瓶頸，畢竟不可能實現絕對的平衡。
2. 通過增加或者移除節點，查看數據的移動情況：移除節點 采用 1024 虛擬節點的情況下，使 32 節點失效，得到如下的統計結果：
101.71.4.31:80 2392
101.71.4.33:80 2374
101.71.4.34:80 2635
101.71.4.35:80 2599我對記錄文件進行了對比，發現 31,33,34,35 原來各自屬于自身的數據沒變，多出來的是 32 上的數據，被平均分布到了還有效的四臺機器。
增加節點，采用 1024 虛擬節點的情況下，增加 36 節點，得到如下結果：
101.71.4.31:80 1726
101.71.4.32:80 1271
101.71.4.33:80 1776
101.71.4.34:80 1743
101.71.4.35:80 1768
101.71.4.36:80 1716我對記錄文件進行了對比，發現 31,32，33,34,35 上的數據還是以前屬于他的數據，但是各自有部分遷移到了 36 機器上。
這兩個實驗都說明了一致性 Hash 的單調性。
2.3.3 一致性 hash 算法實現
// 構建帶虛擬節點的 hash 環，對每個真實的物理節點，配置若干虛擬節點，并進行排序
for (RNode node : rnodes)
for (int i = 1; i = virtual_node_count; i++)
VNode vnode;
vnode.ip_port = node.ip_port + # + to_string(i);
vnode.id = myhash(vnode.ip_port); // 虛擬節點在 hash 環上的映射
circle.push_back(vnode);
node.virtual_nodes.push_back(vnode);
sort(circle.begin(), circle.end(), cmpVNode);// 計算每個 URL 落在那個虛擬節點
VNode getLocation(string url, vector VNode vnodes)
VNode tmp;
tmp.id = myhash(url.c_str());
vector VNode ::iterator iter = std::lower_bound(vnodes.begin(), vnodes.end(), tmp, cmpVNode);
if (iter == vnodes.end())
return vnodes[0];
}else
return *iter;
// 根據虛擬節點，找到對應物理節點
string real_node = getRealNodeInfo(vnode);3.CRUSHMAP 的進一步研究
研究一致性 HASH 的目的是為了更好的理解 Ceph CRUSHMAP 算法，此處簡單說明 Ceph 中對象是如何映射到具體設備的某塊硬盤上。在 Ceph 中，每個對象都屬于某個 PG，我把這些 PG 理解為一致性哈希中的虛擬節點，目的是為了讓對象分布更均勻。而 pg 是如何映射到 OSD 呢。在上文中，這種映射關系比較簡單，就是多對一，在 ceph 中則比較復雜，因為映射關系依賴于集群的拓撲結構, 而每個對象都還有多副本, 需要指定的映射算法，計算出 pg 所在的主 OSD 以及副本 OSD。
看完上述內容，你們對怎么分析一致性 HASH 算法有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注丸趣 TV 行業資訊頻道，感謝大家的支持。
