一致性 ? hash ? 算法（ ? consistent hashing ? ）

張亮

consistent hashing ? 算法早在 ? 1997 ? 年就在論文 ? Consistent hashing and random trees ? 中被提出，目前在 ? cache ? 系統(tǒng)中應用越來越廣泛；

1 ? 基本場景

比如你有 ? N ? 個 ? cache ? 服務器（后面簡稱 ? cache ? ），那么如何將一個對象 ? object ? 映射到 ? N ? 個 ? cache ? 上呢，你很可能會采用類似下面的通用方法計算 ? object ? 的 ? hash ? 值，然后均勻的映射到到 ? N ? 個 ? cache ? ；

hash(object)%N

一切都運行正常，再考慮如下的兩種情況；

1 ? 一個 ? cache ? 服務器 ? m down ? 掉了（在實際應用中必須要考慮這種情況），這樣所有映射到 ? cache m ? 的對象都會失效，怎么辦，需要把 ? cache m ? 從 ? cache ? 中移除，這時候 ? cache ? 是 ? N-1 ? 臺，映射公式變成了 ? hash(object)%(N-1) ? ；

2 ? 由于訪問加重，需要添加 ? cache ? ，這時候 ? cache ? 是 ? N+1 ? 臺，映射公式變成了 ? hash(object)%(N+1) ? ；

1 ? 和 ? 2 ? 意味著什么？這意味著突然之間幾乎所有的 ? cache ? 都失效了。對于服務器而言，這是一場災難，洪水般的訪問都會直接沖向后臺服務器；

再來考慮第三個問題，由于硬件能力越來越強，你可能想讓后面添加的節(jié)點多做點活，顯然上面的 ? hash ? 算法也做不到。

? ? 有什么方法可以改變這個狀況呢，這就是 ? consistent hashing...

2 hash ? 算法和單調性

? Hash ? 算法的一個衡量指標是單調性（ ? Monotonicity ? ），定義如下：

　　單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。

容易看到，上面的簡單 ? hash ? 算法 ? hash(object)%N ? 難以滿足單調性要求。

3 consistent hashing ? 算法的原理

consistent hashing ? 是一種 ? hash ? 算法，簡單的說，在移除 ? / ? 添加一個 ? cache ? 時，它能夠盡可能小的改變已存在 ? key ? 映射關系，盡可能的滿足單調性的要求。

下面就來按照 ? 5 ? 個步驟簡單講講 ? consistent hashing ? 算法的基本原理。

3.1 ? 環(huán)形 hash ? 空間

考慮通常的 ? hash ? 算法都是將 ? value ? 映射到一個 ? 32 ? 為的 ? key ? 值，也即是 ? 0~2^32-1 ? 次方的數(shù)值空間；我們可以將這個空間想象成一個首（ ? 0 ? ）尾（ ? 2^32-1 ? ）相接的圓環(huán)，如下面圖 ? 1 ? 所示的那樣。

圖 ? 1 ? 環(huán)形 ? hash ? 空間

3.2 ? 把對象映射到 hash ? 空間

接下來考慮 ? 4 ? 個對象 ? object1~object4 ? ，通過 ? hash ? 函數(shù)計算出的 ? hash ? 值 ? key ? 在環(huán)上的分布如圖 ? 2 ? 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

圖 ? 2 4 ? 個對象的 ? key ? 值分布

3.3 ? 把 cache ? 映射到 hash ? 空間

Consistent hashing ? 的基本思想就是將對象和 ? cache ? 都映射到同一個 ? hash ? 數(shù)值空間中，并且使用相同的 hash ? 算法。

假設當前有 ? A,B ? 和 ? C ? 共 ? 3 ? 臺 ? cache ? ，那么其映射結果將如圖 ? 3 ? 所示，他們在 ? hash ? 空間中，以對應的 ? hash 值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

圖 ? 3 cache ? 和對象的 ? key ? 值分布

?

說到這里，順便提一下 ? cache ? 的 ? hash ? 計算，一般的方法可以使用 ? cache ? 機器的 ? IP ? 地址或者機器名作為 hash ? 輸入。

3.4 ? 把對象映射到 cache

現(xiàn)在 ? cache ? 和對象都已經通過同一個 ? hash ? 算法映射到 ? hash ? 數(shù)值空間中了，接下來要考慮的就是如何將對象映射到 ? cache ? 上面了。

在這個環(huán)形空間中，如果沿著順時針方向從對象的 ? key ? 值出發(fā)，直到遇見一個 ? cache ? ，那么就將該對象存儲在這個 ? cache ? 上，因為對象和 ? cache ? 的 ? hash ? 值是固定的，因此這個 ? cache ? 必然是唯一和確定的。這樣不就找到了對象和 ? cache ? 的映射方法了嗎？！

依然繼續(xù)上面的例子（參見圖 ? 3 ? ），那么根據上面的方法，對象 ? object1 ? 將被存儲到 ? cache A ? 上； ? object2 和 ? object3 ? 對應到 ? cache C ? ； ? object4 ? 對應到 ? cache B ? ；

3.5 ? 考察 cache ? 的變動

前面講過，通過 ? hash ? 然后求余的方法帶來的最大問題就在于不能滿足單調性，當 ? cache ? 有所變動時， cache ? 會失效，進而對后臺服務器造成巨大的沖擊，現(xiàn)在就來分析分析 ? consistent hashing ? 算法。

3.5.1 ? 移除 ? cache

考慮假設 ? cache B ? 掛掉了，根據上面講到的映射方法，這時受影響的將僅是那些沿 ? cache B ? 逆時針遍歷直到下一個 ? cache ? （ ? cache C ? ）之間的對象，也即是本來映射到 ? cache B ? 上的那些對象。

因此這里僅需要變動對象 ? object4 ? ，將其重新映射到 ? cache C ? 上即可；參見圖 ? 4 ? 。

圖 ? 4 Cache B ? 被移除后的 ? cache ? 映射

3.5.2 ? 添加 ? cache

再考慮添加一臺新的 ? cache D ? 的情況，假設在這個環(huán)形 ? hash ? 空間中， ? cache D ? 被映射在對象 ? object2 ? 和 object3 ? 之間。這時受影響的將僅是那些沿 ? cache D ? 逆時針遍歷直到下一個 ? cache ? （ ? cache B ? ）之間的對象（它們是也本來映射到 ? cache C ? 上對象的一部分），將這些對象重新映射到 ? cache D ? 上即可。

?

因此這里僅需要變動對象 ? object2 ? ，將其重新映射到 ? cache D ? 上；參見圖 ? 5 ? 。

圖 ? 5 ? 添加 ? cache D ? 后的映射關系

4 ? 虛擬節(jié)點

考量 ? Hash ? 算法的另一個指標是平衡性 ? (Balance) ? ，定義如下：

平衡性

　　平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

hash ? 算法并不是保證絕對的平衡，如果 ? cache ? 較少的話，對象并不能被均勻的映射到 ? cache ? 上，比如在上面的例子中，僅部署 ? cache A ? 和 ? cache C ? 的情況下，在 ? 4 ? 個對象中， ? cache A ? 僅存儲了 ? object1 ? ，而 ? cache C ? 則存儲了 ? object2 ? 、 ? object3 ? 和 ? object4 ? ；分布是很不均衡的。

為了解決這種情況， ? consistent hashing ? 引入了“虛擬節(jié)點”的概念，它可以如下定義：

“虛擬節(jié)點”（ ? virtual node ? ）是實際節(jié)點在 ? hash ? 空間的復制品（ ? replica ? ），一實際個節(jié)點對應了若干個“虛擬節(jié)點”，這個對應個數(shù)也成為“復制個數(shù)”，“虛擬節(jié)點”在 ? hash ? 空間中以 ? hash ? 值排列。

仍以僅部署 ? cache A ? 和 ? cache C ? 的情況為例，在圖 ? 4 ? 中我們已經看到， ? cache ? 分布并不均勻。現(xiàn)在我們引入虛擬節(jié)點，并設置“復制個數(shù)”為 ? 2 ? ，這就意味著一共會存在 ? 4 ? 個“虛擬節(jié)點”， ? cache A1, cache A2 ? 代表了 ? cache A ? ； ? cache C1, cache C2 ? 代表了 ? cache C ? ；假設一種比較理想的情況，參見圖 ? 6 ? 。

圖 ? 6 ? 引入“虛擬節(jié)點”后的映射關系

?

此時，對象到“虛擬節(jié)點”的映射關系為：

objec1->cache A2 ? ； ? objec2->cache A1 ? ； ? objec3->cache C1 ? ； ? objec4->cache C2 ? ；

因此對象 ? object1 ? 和 ? object2 ? 都被映射到了 ? cache A ? 上，而 ? object3 ? 和 ? object4 ? 映射到了 ? cache C ? 上；平衡性有了很大提高。

引入“虛擬節(jié)點”后，映射關系就從 ? { ? 對象 ? -> ? 節(jié)點 ? } ? 轉換到了 ? { ? 對象 ? -> ? 虛擬節(jié)點 ? } ? 。查詢物體所在 ? cache 時的映射關系如圖 ? 7 ? 所示。

圖 ? 7 ? 查詢對象所在 ? cache

?

“虛擬節(jié)點”的 ? hash ? 計算可以采用對應節(jié)點的 ? IP ? 地址加數(shù)字后綴的方式。例如假設 ? cache A ? 的 ? IP ? 地址為 202.168.14.241 ? 。

引入“虛擬節(jié)點”前，計算 ? cache A ? 的 ? hash ? 值：

Hash(“202.168.14.241”);

引入“虛擬節(jié)點”后，計算“虛擬節(jié)”點 ? cache A1 ? 和 ? cache A2 ? 的 ? hash ? 值：

Hash(“202.168.14.241#1”); ? ? // cache A1

Hash(“202.168.14.241#2”); ? ? // cache A2

5 ? 小結

Consistent hashing ? 的基本原理就是這些，具體的分布性等理論分析應該是很復雜的，不過一般也用不到。

http://weblogs.java.net/blog/2007/11/27/consistent-hashing ? 上面有一個 ? java ? 版本的例子，可以參考。

http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx ? 轉載了一個 ? PHP ? 版的實現(xiàn)代碼。

http://www.codeproject.com/KB/recipes/lib-conhash.aspx ? C語言版本

?

?

一些參考資料地址：

http://portal.acm.org/citation.cfm?id=258660

http://en.wikipedia.org/wiki/Consistent_hashing

http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

? http://weblogs.java.net/blog/2007/11/27/consistent-hashing

http://tech.idv2.com/2008/07/24/memcached-004/

http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx

?