一致性哈希算法原理設計

一.前言

一致性哈希(Consistent Hashing)，最早由MIT的Karger于1997年提出，主要用于解決易變的分布式Web系統中，由于宕機和擴容導致的服務震蕩。現在這個算法思路被大量應用，并且在實踐中得到了很大的發展。

二.算法設計

1.問題來源

一個由6臺服務器組成的服務，每臺Server負責存儲1/6的數據，當Server1出現宕機之后，服務重新恢復可用時的場景。

如下表格可以很清楚的看到，當Server1宕機時，Hash1的服務完全不可用了，所以需要ReHash由剩余5臺機器提供所有的數據服務，但由于每臺機器負責的數據段大小不相同，那么需要在不同的服務器之間大量遷移數據，并且數據遷移完成之前服務會不可用。

2.經典一致性哈希算法

針對ReHash的弊端，Karger提出了一種算法，算法的核心是”虛擬節點”。

將所有的數據映射成一組大于服務器數量的虛擬節點，虛擬節點再映射到真實的服務器。所以當服務器宕機時，由于虛擬節點的數量固定不變，所有不需要ReHash，而只需要將服務不可用的虛擬節點重新遷移，這樣只需要遷移宕機節點的數據。

經典的算法中，宕機服務器的下一個真實節點將提供服務。

三.算法改進

1.經典一致性哈希算法的問題

經典的算法只是解決了ReHash算法的缺陷，當本身并不完美。主要存在以下幾個問題：

(1)Server1宕機會導致Server2的服務承受一倍的數據服務，且如果Server1就此退役，那么整個系統的負載完全不均衡了。

(2)如果所有的Server都能承受一倍的數據讀寫，那么如果在正常情況下所有的數據寫兩份到不同的服務器，主備或者負載均衡，宕機時直接讀備份節點的數據，根本不需要出現經典算法中的數據遷移。

2.Dynamo改進實踐

Amazon的大數據存儲平臺”Dynamo”使用了一致性哈希，但它并沒有使用經典算法，而是使用了故障節點ReHash的思路。

系統將所有的虛擬節點和真實服務器的對應關系保存到一個配置系統，當某些虛擬節點的服務不可用時，重新配置這些虛擬節點的服務到其他真實服務器，這樣既不用大量遷移數據，也保證了所有服務器的負載相對均衡。

四.算法擴展

一致性哈希算法本身是用于解決服務器宕機與擴容的問題，但”虛擬節點”的算法思想有所發展，一些分布式的系統用于實現系統的負載均衡和最優訪問策略。

在真實的系統情況下，相同部署的兩套系統可能不能提供相同的服務，主要原因：

(1)硬件個體差異導致服務器性能不同。

(2)機房交換機和網絡帶寬導致IDC服務器之間的網絡通信效率不同。

(3)用戶使用不同的網絡運營商導致電信IDC和聯通IDC提供的服務性能不同。

(4)服務器所在網絡或機房遭遇攻擊。

所以完全相同的兩套系統可能也需要提供差異化的服務，通過使用虛擬節點可以靈活的動態調整，達到系統服務的最優化。

對于由2個節點，每個節點3臺服務器組成的分布式系統，S0-1為分布式系統1的Server0，系統配置管理員可以根據系統真實的服務效率動態的調整虛擬節點與真實服務器的映射關系，也可以由客戶系統自身根據響應率或響應時間等情況調整自身的訪問策略。

五.Reference

(1)一致哈希(wiki)
(2)Consistent hashing
(3)Dynamo: Amazon’s Highly Available Key-value Store