基本介紹
- 中文名：一致性哈希
- 外文名：Consistent hashing
- 時間：1997年
- 類別：哈希算法
- 條件：平衡性、單調性和分散性
- 套用：分散式系統
- 提出人：David Karger 等人
簡介,工作原理,與哈希算法的關係,優點,套用,
簡介
一致性哈希算法是1997年在論文Consistenthashingandrandomtrees中被提出，在分散式系統中套用非常廣泛。一致性哈希是一種哈希算法，簡單地說在移除或者添加一個伺服器時，此算法能夠儘可能小地改變已存在的服務請求與處理請求伺服器之間的映射關係，儘可能滿足單調性的要求。在普通分散式集群中，服務請求與處理請求伺服器之間可以一一對應，也就是說固定服務請求與處理伺服器之間的映射關係，某個請求由固定的伺服器去處理。這種方式無法對整個系統進行負載均衡，可能會造成某些伺服器過於繁忙以至於無法處理新來的請求。而另一些伺服器則過於空閒，整體系統的資源利用率低，並且當分散式集群中的某個伺服器宕機，會直接導致某些服務請求無法處理。
進一步的改進可以利用hash算法對服務請求與處理伺服器之間的關係進行映射，以達到動態分配的目的。通過hash算法對服務請求進行轉換，轉換後的結果對伺服器節點值進行取模運算，取模後的值就是服務請求對應的請求處理伺服器。這種方法可以應對節點失效的情況，當某個分散式集群節點宕機，服務請求可以通過hash算法重新分配到其他可用的伺服器上。避免了無法處理請求的狀況出現。
但這種方法的缺陷也很明顯，如果伺服器中保存有服務請求對應的數據，那么如果重新計算請求的hash值，會造成大量的請求被重定位到不同的伺服器而造成請求所要使用的數據失效，這種情況在分散式系統中是非常糟糕的。一個設計良好的分散式系統應該具有良好的單調性，即伺服器的添加與移除不會造成大量的哈希重定位，而一致性哈希恰好可以解決這個問題。
一致性哈希算法將整個哈希值空間映射成一個虛擬的圓環，整個哈希空間的取值範圍為0~232-1。整個空間按順時針方向組織。0~232-1在零點中方向重合。接下來使用如下算法對服務請求進行映射，將服務請求使用哈希算法算出對應的hash值，然後根據hash值的位置沿圓環順時針查找，第一台遇到的伺服器就是所對應的處理請求伺服器。當增加一台新的伺服器，受影響的數據僅僅是新添加的伺服器到其環空間中前一台的伺服器（也就是順著逆時針方向遇到的第一台伺服器）之間的數據，其他都不會受到影響。綜上所述，一致性哈希算法對於節點的增減都只需重定位環空間中的一小部分數據，具有較好的容錯性和可擴展性。
工作原理
首先，對存儲節點的哈希值進行計算，其將存儲空間抽象為一個環，將存儲節點配置到環上。環上所有的節點都有一個值。其次，對數據進行哈希計算，按順時針方向將其映射到離其最近的節點上去。當有節點出現故障離線時，按照算法的映射方法，受影響的僅僅為環上故障節點開始逆時針方向至下一個節點之間區間的數據對象，而這些對象本身就是映射到故障節點之上的。當有節點增加時，比如，在節點A和B之間重新添加一個節點H，受影響的也僅僅是節點H逆時針遍歷直到B之間的數據對象，將這些重新映射到H上即可，因此，當有節點出現變動時，不會使得整個存儲空間上的數據都進行重新映射，解決了簡單哈希算法增刪節點，重新映射所有數據帶來的效率低下的問題。
一致性哈希算法作為分散式存儲領域的一個重要算法，它基本解決了以P2P為代表的存儲環境中一個關鍵的問題——如何在動態的網路拓撲中對數據進行分發和選擇路由。在算法所構成的存儲拓撲中，每個存儲節點僅需維護少量相鄰節點的信息，並且在節點加入/退出系統時，僅有相關的少量節點參與到拓撲的維護中，這使得一致性哈希算法成為一個具有實用意義的DHT（DistributedHashTable，分散式哈希表）算法。但是一致性哈希算法尚有不足之處。第一，在查詢過程中，查詢訊息要經過O(n)步(n代表系統內的節點總數)才能到達被查詢的節點。不難想像，當系統規模非常大時，節點數量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。第二，當套用一致性哈希算法的分散式存儲系統中添加或者刪除新的物理節點時，要將下一個節點與之相關的數據遷移過來，查詢命中率和存儲效率下降，影響系統的整體性能。
與哈希算法的關係
①平衡性是指hash的結果應該平均分配到各個節點，這樣從算法上解決了負載均衡問題。
②單調性是指在新增或者刪減節點時，不影響系統正常運行。
③分散性是指數據應該分散地存放在分散式集群中的各個節點(節點自己可以有備份)，不必每個節點都存儲所有的數據。
優點
- 可擴展性。一致性哈希算法保證了增加或減少伺服器時，數據存儲的改變最少，相比傳統哈希算法大大節省了數據移動的開銷。
- 更好地適應數據的快速增長。採用一致性哈希算法分布數據，當數據不斷增長時，部分虛擬節點中可能包含很多數據、造成數據在虛擬節點上分布不均衡，此時可以將包含數據多的虛擬節點分裂，這種分裂僅僅是將原有的虛擬節點一分為二、不需要對全部的數據進行重新哈希和劃分。虛擬節點分裂後，如果物理伺服器的負載仍然不均衡，只需在伺服器之間調整部分虛擬節點的存儲分布。這樣可以隨數據的增長而動態的擴展物理伺服器的數量，且代價遠比傳統哈希算法重新分布所有數據要小很多。
套用
分散式存儲系統HepyCloud是中科院高能所自主開發的一套海量數據存儲系統，該系統採用key-value技術，實現海量數據的快速存儲、定位和高可擴展性，支持EB級存儲。系統提出統一布局的思想，對一致性哈希算法進行改進。
HepyCloud系統採用改進的一致性哈希算法，實現數據的均勻分布和快速定位，在對哈希函式的選擇時主要從以下兩個方面考慮：（1）運行效率；（2）散列均勻。運行效率指所選擇的哈希函式有較高的計算效率，實現數據的快速定位，達到很好的用戶體驗；散列均勻指所選的哈希函式具有很好的分布性，保證數據在存儲設備上的均勻分布。Davies-Meyer算法是一種較好的選擇。一方面高效的運行效率，保證了快速定位數據；另一方面均勻的散列分布性，確保了數據均勻分布。從實際使用看，將改進的一致性哈希和Davies-Meyer算法套用到HepyCloud系統中，實現數據在存儲設備上的均勻分布。系統共有23個存儲設備，存儲容量186TB，14478054個檔案，每個設備上的檔案數約為629410（總檔案數/設備數）。在數據定位方面，經測試和實際使用其表現與其他分散式檔案系統相當，足以滿足存儲系統的性能要求。
