一緻性hash

轉載：http://blog.huanghao.me/?p=14

一緻性hash算法簡介

Posted on  June 10, 2011  by  huanghao

一緻性雜湊演算法在1997年由麻省理工學院提出的一種分布式哈希（DHT）實作算法，設計目标是為了解決網際網路中的熱點(Hot spot)問題，初衷和CARP十分類似。一緻性哈希修正了CARP使用的簡單雜湊演算法帶來的問題，使得分布式哈希（DHT）可以在P2P環境中真正得到應用。

一緻性hash算法提出了在動态變化的Cache環境中，判定雜湊演算法好壞的四個定義：

1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多雜湊演算法都能夠滿足這一條件。

2、單調性(Monotonicity)：單調性是指如果已經有一些内容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已配置設定的内容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是隻能看到其中的一部分。當終端希望通過哈希過程将内容映射到緩沖上時，由于不同終端所見的緩沖範圍有可能不同，進而導緻哈希的結果不一緻，最終的結果是相同的内容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導緻相同内容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的雜湊演算法應能夠盡量避免不一緻的情況發生，也就是盡量降低分散性。

4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能将相同的内容映射到不同的緩沖區中，那麼對于一個特定的緩沖區而言，也可能被不同的使用者映射為不同的内容。與分散性一樣，這種情況也是應當避免的，是以好的雜湊演算法應能夠盡量降低緩沖的負荷。

普通的雜湊演算法（也稱硬哈希）采用簡單取模的方式，将機器進行散列，這在cache環境不變的情況下能取得讓人滿意的結果，但是當cache環境動态變化時，這種靜态取模的方式顯然就不滿足單調性的要求（當增加或減少一台機子時，幾乎所有的存儲内容都要被重新散列到别的緩沖區中）。

一緻性雜湊演算法有多種具體的實作，包括Chord算法，KAD算法等實作，以上的算法的實作都比較複雜，這裡介紹一種網上廣為流傳的一緻性雜湊演算法的基本實作原理，感興趣的同學可以根據上面的連結或者去網上查詢更詳細的資料。

一緻性雜湊演算法的基本實作原理是将機器節點和key值都按照一樣的hash算法映射到一個0~2^32的圓環上。當有一個寫入緩存的請求到來時，計算Key值k對應的哈希值Hash(k)，如果該值正好對應之前某個機器節點的Hash值，則直接寫入該機器節點，如果沒有對應的機器節點，則順時針查找下一個節點，進行寫入，如果超過2^32還沒找到對應節點，則從0開始查找(因為是環狀結構)。如圖1所示



圖 1

圖1中Key K的哈希值在A與B之間，于是K就由節點B來處理。

另外具體機器映射時，還可以根據處理能力不同，将一個實體節點映射到多個虛拟節點。

經過一緻性雜湊演算法散列之後，當有新的機器加入時，将隻影響一台機器的存儲情況，例如新加入的節點H的散列在B與C之間，則原先由C處理的一些資料可能将移至H處理，而其他所有節點的處理情況都将保持不變，是以表現出很好的單調性。而如果删除一台機器，例如删除C節點，此時原來由C處理的資料将移至D節點，而其它節點的處理情況仍然不變。而由于在機器節點散列和緩沖内容散列時都采用了同一種雜湊演算法，是以也很好得降低了分散性和負載。而通過引入虛拟節點的方式，也大大提高了平衡性。

最後附一個c語言一緻性hash的代碼實作。