張亮
consistent hashing 算法早在 1997 年就在論文 Consistent hashing and random trees 中被提出寝凌，目前在 cache 系統(tǒng)中應(yīng)用越來越廣泛再沧；
1 基本場景
比如你有 N 個(gè) cache 服務(wù)器（后面簡稱 cache ），那么如何將一個(gè)對象 object 映射到 N 個(gè) cache 上呢馒闷，你很可能會(huì)采用類似下面的通用方法計(jì)算 object 的 hash 值绽乔，然后均勻的映射到到 N 個(gè) cache 笛匙；
hash(object)%N
一切都運(yùn)行正常猬错，再考慮如下的兩種情況；
1 一個(gè) cache 服務(wù)器 m down 掉了（在實(shí)際應(yīng)用中必須要考慮這種情況）盐固，這樣所有映射到 cache m 的對象都會(huì)失效荒给，怎么辦，需要把 cache m 從 cache 中移除刁卜，這時(shí)候 cache 是 N-1 臺志电，映射公式變成了 hash(object)%(N-1) ；
2 由于訪問加重蛔趴，需要添加 cache 挑辆，這時(shí)候 cache 是 N+1 臺，映射公式變成了 hash(object)%(N+1) 孝情；
1 和 2 意味著什么鱼蝉？這意味著突然之間幾乎所有的 cache 都失效了。對于服務(wù)器而言箫荡，這是一場災(zāi)難魁亦，洪水般的訪問都會(huì)直接沖向后臺服務(wù)器；
再來考慮第三個(gè)問題羔挡，由于硬件能力越來越強(qiáng)洁奈，你可能想讓后面添加的節(jié)點(diǎn)多做點(diǎn)活间唉，顯然上面的 hash 算法也做不到。
有什么方法可以改變這個(gè)狀況呢利术，這就是 consistent hashing...
2 hash 算法和單調(diào)性
Hash 算法的一個(gè)衡量指標(biāo)是單調(diào)性（ Monotonicity ）呈野，定義如下：
單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中印叁。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去被冒，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。
容易看到喉钢，上面的簡單 hash 算法 hash(object)%N 難以滿足單調(diào)性要求姆打。
3 consistent hashing 算法的原理
consistent hashing 是一種 hash 算法良姆，簡單的說肠虽，在移除 / 添加一個(gè) cache 時(shí)，它能夠盡可能小的改變已存在 key 映射關(guān)系玛追，盡可能的滿足單調(diào)性的要求税课。
下面就來按照 5 個(gè)步驟簡單講講 consistent hashing 算法的基本原理。
3.1 環(huán)形hash 空間
考慮通常的 hash 算法都是將 value 映射到一個(gè) 32 為的 key 值痊剖，也即是 0~2^32-1 次方的數(shù)值空間韩玩；我們可以將這個(gè)空間想象成一個(gè)首（ 0 ）尾（ 2^32-1 ）相接的圓環(huán)，如下面圖 1 所示的那樣陆馁。
圖 1 環(huán)形 hash 空間
3.2 把對象映射到hash 空間
接下來考慮 4 個(gè)對象 object1~object4 找颓，通過 hash 函數(shù)計(jì)算出的 hash 值 key 在環(huán)上的分布如圖 2 所示。
hash(object1) = key1;
… …
hash(object4) = key4;
圖 2 4 個(gè)對象的 key 值分布
3.3 把cache 映射到hash 空間
Consistent hashing 的基本思想就是將對象和 cache 都映射到同一個(gè) hash 數(shù)值空間中叮贩，并且使用相同的 hash 算法击狮。
假設(shè)當(dāng)前有 A,B 和 C 共 3 臺 cache ，那么其映射結(jié)果將如圖 3 所示益老，他們在 hash 空間中彪蓬，以對應(yīng)的 hash 值排列。
hash(cache A) = key A;
… …
hash(cache C) = key C;
圖 3 cache 和對象的 key 值分布
說到這里捺萌，順便提一下 cache 的 hash 計(jì)算档冬，一般的方法可以使用 cache 機(jī)器的 IP 地址或者機(jī)器名作為 hash 輸入。
3.4 把對象映射到cache
現(xiàn)在 cache 和對象都已經(jīng)通過同一個(gè) hash 算法映射到 hash 數(shù)值空間中了桃纯，接下來要考慮的就是如何將對象映射到 cache 上面了酷誓。
在這個(gè)環(huán)形空間中，如果沿著順時(shí)針方向從對象的 key 值出發(fā)态坦，直到遇見一個(gè) cache 呛牲，那么就將該對象存儲在這個(gè) cache 上，因?yàn)閷ο蠛?cache 的 hash 值是固定的驮配，因此這個(gè) cache 必然是唯一和確定的娘扩。這樣不就找到了對象和 cache 的映射方法了嗎着茸？！
依然繼續(xù)上面的例子（參見圖 3 ）琐旁，那么根據(jù)上面的方法涮阔，對象 object1 將被存儲到 cache A 上； object2 和 object3 對應(yīng)到 cache C 灰殴； object4 對應(yīng)到 cache B 敬特；
3.5 考察cache 的變動(dòng)
前面講過，通過 hash 然后求余的方法帶來的最大問題就在于不能滿足單調(diào)性牺陶，當(dāng) cache 有所變動(dòng)時(shí)伟阔， cache 會(huì)失效，進(jìn)而對后臺服務(wù)器造成巨大的沖擊掰伸，現(xiàn)在就來分析分析 consistent hashing 算法皱炉。
3.5.1 移除 cache
考慮假設(shè) cache B 掛掉了，根據(jù)上面講到的映射方法狮鸭，這時(shí)受影響的將僅是那些沿 cache B 逆時(shí)針遍歷直到下一個(gè) cache （ cache C ）之間的對象合搅，也即是本來映射到 cache B 上的那些對象。
因此這里僅需要變動(dòng)對象 object4 歧蕉，將其重新映射到 cache C 上即可灾部；參見圖 4 。
圖 4 Cache B 被移除后的 cache 映射
3.5.2 添加 cache
再考慮添加一臺新的 cache D 的情況惯退，假設(shè)在這個(gè)環(huán)形 hash 空間中竿裂， cache D 被映射在對象 object2 和 object3 之間许蓖。這時(shí)受影響的將僅是那些沿 cache D 逆時(shí)針遍歷直到下一個(gè) cache （ cache B ）之間的對象（它們是也本來映射到 cache C 上對象的一部分）吱窝，將這些對象重新映射到 cache D 上即可虫碉。
因此這里僅需要變動(dòng)對象 object2 ，將其重新映射到 cache D 上叠荠；參見圖 5 匿沛。
圖 5 添加 cache D 后的映射關(guān)系
4 虛擬節(jié)點(diǎn)
考量 Hash 算法的另一個(gè)指標(biāo)是平衡性 (Balance) ，定義如下：
平衡性
平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去榛鼎，這樣可以使得所有的緩沖空間都得到利用逃呼。
hash 算法并不是保證絕對的平衡，如果 cache 較少的話者娱，對象并不能被均勻的映射到 cache 上抡笼，比如在上面的例子中，僅部署 cache A 和 cache C 的情況下黄鳍，在 4 個(gè)對象中推姻， cache A 僅存儲了 object1 ，而 cache C 則存儲了 object2 框沟、 object3 和 object4 藏古；分布是很不均衡的增炭。
為了解決這種情況， consistent hashing 引入了“虛擬節(jié)點(diǎn)”的概念拧晕，它可以如下定義：
“虛擬節(jié)點(diǎn)”（ virtual node ）是實(shí)際節(jié)點(diǎn)在 hash 空間的復(fù)制品（ replica ）隙姿，一實(shí)際個(gè)節(jié)點(diǎn)對應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”厂捞，“虛擬節(jié)點(diǎn)”在 hash 空間中以 hash 值排列输玷。
仍以僅部署 cache A 和 cache C 的情況為例，在圖 4 中我們已經(jīng)看到靡馁， cache 分布并不均勻∮簦現(xiàn)在我們引入虛擬節(jié)點(diǎn)，并設(shè)置“復(fù)制個(gè)數(shù)”為 2 臭墨，這就意味著一共會(huì)存在 4 個(gè)“虛擬節(jié)點(diǎn)”赔嚎， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C 裙犹；假設(shè)一種比較理想的情況尽狠，參見圖 6 衔憨。
圖 6 引入“虛擬節(jié)點(diǎn)”后的映射關(guān)系
此時(shí)叶圃，對象到“虛擬節(jié)點(diǎn)”的映射關(guān)系為：
objec1->cache A2 ； objec2->cache A1 践图； objec3->cache C1 掺冠； objec4->cache C2 ；
因此對象 object1 和 object2 都被映射到了 cache A 上码党，而 object3 和 object4 映射到了 cache C 上德崭；平衡性有了很大提高。
引入“虛擬節(jié)點(diǎn)”后揖盘，映射關(guān)系就從 { 對象 -> 節(jié)點(diǎn) } 轉(zhuǎn)換到了 { 對象 -> 虛擬節(jié)點(diǎn) } 眉厨。查詢物體所在 cache 時(shí)的映射關(guān)系如圖 7 所示。
圖 7 查詢對象所在 cache
“虛擬節(jié)點(diǎn)”的 hash 計(jì)算可以采用對應(yīng)節(jié)點(diǎn)的 IP 地址加數(shù)字后綴的方式兽狭。例如假設(shè) cache A 的 IP 地址為 202.168.14.241 憾股。
引入“虛擬節(jié)點(diǎn)”前，計(jì)算 cache A 的 hash 值：
Hash(“202.168.14.241”);
引入“虛擬節(jié)點(diǎn)”后箕慧，計(jì)算“虛擬節(jié)”點(diǎn) cache A1 和 cache A2 的 hash 值：
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2
5 小結(jié)
Consistent hashing 的基本原理就是這些服球，具體的分布性等理論分析應(yīng)該是很復(fù)雜的，不過一般也用不到颠焦。
http://weblogs.java.net/blog/2007/11/27/consistent-hashing 上面有一個(gè) java 版本的例子斩熊，可以參考。
http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx 轉(zhuǎn)載了一個(gè) PHP 版的實(shí)現(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
