第一代分佈式系統採用的是中心化的系統，對於存貯大量數據的分佈式系統來說它的缺點就是中央節點成為了整個個分佈式系統的單點故障.
第二代分佈式系統，節點之間通行採用的是廣播，每個節點都向自己相連的所有節點進行詢問，被詢問的節點如果不知道這個文件在哪裡,就再次進行廣播……如此往復,直至找到所需文件。請求變多就意味著會產生廣播風暴，這會嚴重佔用帶寬和系統資源。
第三代分佈式系統開始採用DHT(Distrbuted Hash Table)，也就是一致性HASH算法.
算法背景
一致性 HASH 算法在 1997 年由麻省理工學院的 Karger 等人在解決分佈式 Cache 中提出的,設計目標是為了 解決因特網中的熱點(Hot spot)問題,初衷和 CARP 十分類似。一致性 HASH 修正了 CARP 使用的簡單哈希 算法帶來的問題,使得 DHT 可以在 P2P 環境中真正得到應用。
但現在一致性 hash 算法在分佈式系統中也得到了廣泛應用,研究過 memcached 緩存數據庫的人都知道,
memcached 服務器端本身不提供分佈式 Cache 的一致性,而是由客戶端來提供,具體在計算一致性 HASH 時採用如下步驟:
首先求出 memcached 服務器(節點)的哈希值,並將其配置到
0 ~ 2^32的圓(continuum)上。然後採用同樣的方法求出存儲數據的鍵的哈希值,並映射到相同的圓上。
然後從數據映射到的位置開始順時針查找,將數據保存到找到的第一個服務器上。如果超過 2^32 仍然找不到服務器,就會保存到第一臺 memcached 服務器上。
從上圖的狀態中添加一臺 memcached 服務器。餘數分佈式算法由於保存鍵的服務器會發生巨大變化
而影響緩存的命中率,但一致性Hashing 中,只有在圓(continuum)上增加服務器的地點逆時針方向
的第一臺服務器上的鍵會受到影響。
性質
因為考慮到整個系統的節點數量是動態的，每時每刻有新節點加入和舊節點的失效。
在這類情況下依然要保證系統的可用性，這是值得思考的，尤其是在設計分佈式緩存系統的時候。
如果不採用一致性HASH算法, 客戶端在計算數據的 hash 時往往要重新計算(通常這個 Hash 算法和系統中的節點數量有關),
由於 Hash 值已經改變，所以很有可能找不到在整個系統中所對應的節點，導致不可用。所以一致性HASH算法，在分佈式系統中十分重要。
良好的一致性HASH算法需要滿足一下特點：
平衡性(Balance)
平衡性是指哈希的結果能夠儘可能分佈到所有的緩衝中去,這樣可以使得所有的緩衝空間都得到利用。很多哈希算法都能夠滿足這一條件。
單調性(Monotonicity)
單調性是指如果已經有一些內容通過哈希分派到了相應的緩衝中,又有新的緩衝區加入到系統中,那麼哈 希的結果應能夠保證原有已分配的內容可以被映射到新的緩衝區中去,而不會被映射到舊的緩衝集合中的 其他緩衝區。簡單的哈希算法往往不能滿足單調性的要求,如最簡單的線性哈希:x = (ax + b) mod (P), 在上式中,P 表示全部緩衝的大小。不難看出,當緩衝大小發生變化時(從 P1 到 P2),原來所有的哈希結果 均會發生變化,從而不滿足單調性的要求。哈希結果的變化意味著當緩衝空間發生變化時,所有的映射關 系需要在系統內全部更新。而在 P2P 系統內,緩衝的變化等價於 Peer 加入或退出系統,這一情況在 P2P 系 統中會頻繁發生,因此會帶來極大計算和傳輸負荷。單調性就是要求哈希算法能夠應對這種情況。
分散性(Spread)
在分佈式環境中,終端有可能看不到所有的緩衝,而是隻能看到其中的一部分。當終端希望通過哈希過程 將內容映射到緩衝上時,由於不同終端所見的緩衝範圍有可能不同,從而導致哈希的結果不一致,最終的 結果是相同的內容被不同的終端映射到不同的緩衝區中。這種情況顯然是應該避免的,因為它導致相同內 容被存儲到不同緩衝中去,降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈 希算法應能夠儘量避免不一致的情況發生,也就是儘量降低分散性。
負載(Load)
負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩衝區 中,那麼對於一個特定的緩衝區而言,也可能被不同的用戶映射為不同的內容。與分散性一樣,這種情況 也是應當避免的,因此好的哈希算法應能夠儘量降低緩衝的負荷。
平滑性(Smoothness)
平滑性是指緩存服務器的數目平滑改變和緩存對象的平滑改變是一致的。
虛擬節點
假設在圓上Node A和Node B距離過近，按照以上的環形一致 HASH 算法就會發生兩個節點所擁有的數據數量不一致的問題。
為了解決這種數據傾斜問題，一致性哈希算法引入了虛擬節點機制，即對每一個服務節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛擬節點。具體做法可以在服務器 ip 或主機名的後面增加編號來實現。例如上面的情況，可以為每臺服務器計算三個虛擬節點，於是可以分別計算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，於是形成六個虛擬節點：
同時數據定位算法不變，只是多了一步虛擬節點到實際節點的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三個虛擬節點的數據均定位到 Node A 上。這樣就解決了服務節點少時數據傾斜的問題。在實際應用中，通常將虛擬節點數設置為 32 甚至更大，因此即使很少的服務節點也能做到相對均勻的數據分佈。