一致性哈希

一致性哈希算法是1997年在論文Consistenthashingandrandomtrees中被提出 ^[3]  ，在分佈式系統中應用非常廣泛。一致性哈希是一種哈希算法，簡單地説在移除或者添加一個服務器時，此算法能夠儘可能小地改變已存在的服務請求與處理請求服務器之間的映射關係，儘可能滿足單調性的要求。在普通分佈式集羣中，服務請求與處理請求服務器之間可以一一對應，也就是説固定服務請求與處理服務器之間的映射關係，某個請求由固定的服務器去處理。這種方式無法對整個系統進行負載均衡，可能會造成某些服務器過於繁忙以至於無法處理新來的請求。而另一些服務器則過於空閒，整體系統的資源利用率低，並且當分佈式集羣中的某個服務器宕機，會直接導致某些服務請求無法處理 ^[4]  。

進一步的改進可以利用hash算法對服務請求與處理服務器之間的關係進行映射，以達到動態分配的目的。通過hash算法對服務請求進行轉換，轉換後的結果對服務器節點值進行取模運算，取模後的值就是服務請求對應的請求處理服務器。這種方法可以應對節點失效的情況，當某個分佈式集羣節點宕機，服務請求可以通過hash算法重新分配到其他可用的服務器上。避免了無法處理請求的狀況出現 ^[4]  。

但這種方法的缺陷也很明顯，如果服務器中保存有服務請求對應的數據，那麼如果重新計算請求的hash值，會造成大量的請求被重定位到不同的服務器而造成請求所要使用的數據失效，這種情況在分佈式系統中是非常糟糕的。一個設計良好的分佈式系統應該具有良好的單調性，即服務器的添加與移除不會造成大量的哈希重定位，而一致性哈希恰好可以解決這個問題 ^[4]  。

一致性哈希算法將整個哈希值空間映射成一個虛擬的圓環，整個哈希空間的取值範圍為0~2³²-1。整個空間按順時針方向組織。0~2^32-1在零點中方向重合。接下來使用如下算法對服務請求進行映射，將服務請求使用哈希算法算出對應的hash值，然後根據hash值的位置沿圓環順時針查找，第一台遇到的服務器就是所對應的處理請求服務器。當增加一台新的服務器，受影響的數據僅僅是新添加的服務器到其環空間中前一台的服務器（也就是順着逆時針方向遇到的第一台服務器）之間的數據，其他都不會受到影響。綜上所述，一致性哈希算法對於節點的增減都只需重定位環空間中的一小部分數據，具有較好的容錯性和可擴展性 ^[4]  。

一致性哈希算法是當前較主流的分佈式哈希表協議之一，它對簡單哈希算法進行了修正，解決了熱點(hotPot)問題，它的原理分為兩步 ^[5]  ：

首先，對存儲節點的哈希值進行計算，其將存儲空間抽象為一個環，將存儲節點配置到環上。環上所有的節點都有一個值。其次，對數據進行哈希計算，按順時針方向將其映射到離其最近的節點上去。當有節點出現故障離線時，按照算法的映射方法，受影響的僅僅為環上故障節點開始逆時針方向至下一個節點之間區間的數據對象，而這些對象本身就是映射到故障節點之上的。當有節點增加時，比如，在節點A和B之間重新添加一個節點H，受影響的也僅僅是節點H逆時針遍歷直到B之間的數據對象，將這些重新映射到H上即可，因此，當有節點出現變動時，不會使得整個存儲空間上的數據都進行重新映射，解決了簡單哈希算法增刪節點，重新映射所有數據帶來的效率低下的問題 ^[5]  。

一致性哈希算法作為分佈式存儲領域的一個重要算法，它基本解決了以P2P為代表的存儲環境中一個關鍵的問題——如何在動態的網絡拓撲中對數據進行分發和選擇路由。在算法所構成的存儲拓撲中，每個存儲節點僅需維護少量相鄰節點的信息，並且在節點加入/退出系統時，僅有相關的少量節點參與到拓撲的維護中，這使得一致性哈希算法成為一個具有實用意義的DHT（DistributedHashTable，分佈式哈希表）算法。但是一致性哈希算法尚有不足之處。第一，在查詢過程中，查詢消息要經過O(n)步(n代表系統內的節點總數)才能到達被查詢的節點。不難想象，當系統規模非常大時，節點數量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。第二，當應用一致性哈希算法的分佈式存儲系統中添加或者刪除新的物理節點時，要將下一個節點與之相關的數據遷移過來，查詢命中率和存儲效率下降，影響系統的整體性能 ^[5]  。

一致性哈希算法是在哈希算法基礎上提出的，在動態變化的分佈式環境中，哈希算法應該滿足的幾個條件:平衡性、單調性和分散性 ^[4]  。

①平衡性是指hash的結果應該平均分配到各個節點，這樣從算法上解決了負載均衡問題 ^[4]  。

②單調性是指在新增或者刪減節點時，不影響系統正常運行 ^[4]  。

③分散性是指數據應該分散地存放在分佈式集羣中的各個節點(節點自己可以有備份)，不必每個節點都存儲所有的數據 ^[4]  。

分佈式存儲系統HepyCloud是中科院高能所自主開發的一套海量數據存儲系統，該系統採用key-value技術，實現海量數據的快速存儲、定位和高可擴展性，支持EB級存儲。系統提出統一佈局的思想，對一致性哈希算法進行改進 ^[6]  。

HepyCloud系統採用改進的一致性哈希算法，實現數據的均勻分佈和快速定位，在對哈希函數的選擇時主要從以下兩個方面考慮：（1）運行效率；（2）散列均勻。運行效率指所選擇的哈希函數有較高的計算效率，實現數據的快速定位，達到很好的用户體驗；散列均勻指所選的哈希函數具有很好的分佈性，保證數據在存儲設備上的均勻分佈。Davies-Meyer算法是一種較好的選擇。一方面高效的運行效率，保證了快速定位數據；另一方面均勻的散列分佈性，確保了數據均勻分佈。從實際使用看，將改進的一致性哈希和Davies-Meyer算法應用到HepyCloud系統中，實現數據在存儲設備上的均勻分佈。系統共有23個存儲設備，存儲容量186TB，14478054個文件，每個設備上的文件數約為629410（總文件數/設備數）。在數據定位方面，經測試和實際使用其表現與其他分佈式文件系統相當，足以滿足存儲系統的性能要求 ^[6]  。