?

轉(zhuǎn)載：http://blog.csdn.net/sparkliang/article/details/5279393 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?張亮

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

1?基本場景

比如你有?N?個(gè)?cache?服務(wù)器（后面簡稱?cache?），那么如何將一個(gè)對(duì)象?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?的對(duì)象都會(huì)失效，怎么辦，需要把?cache m?從?cache?中移除，這時(shí)候?cache?是?N-1?臺(tái)，映射公式變成了?hash(object)%(N-1)?；

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

1?和?2?意味著什么？這意味著突然之間幾乎所有的?cache?都失效了。對(duì)于服務(wù)器而言，這是一場災(zāi)難，洪水般的訪問都會(huì)直接沖向后臺(tái)服務(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?把對(duì)象映射到hash?空間

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

hash(object1) = key1;

… …

hash(object4) = key4;

?

圖?2 4?個(gè)對(duì)象的?key?值分布

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

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

假設(shè)當(dāng)前有?A,B?和?C?共?3?臺(tái)?cache?，那么其映射結(jié)果將如圖?3?所示，他們在?hash?空間中，以對(duì)應(yīng)的?hash值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

?

圖?3 cache?和對(duì)象的?key?值分布

?

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

3.4?把對(duì)象映射到cache

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

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

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

3.5?考察cache?的變動(dòng)

前面講過，通過?hash?然后求余的方法帶來的最大問題就在于不能滿足單調(diào)性，當(dāng)?cache?有所變動(dòng)時(shí)，cache?會(huì)失效，進(jìn)而對(duì)后臺(tái)服務(wù)器造成巨大的沖擊，現(xiàn)在就來分析分析?consistent hashing?算法。

3.5.1?移除?cache

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

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

?

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

3.5.2?添加?cache

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

?

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

?

圖?5?添加?cache D?后的映射關(guān)系

4?虛擬節(jié)點(diǎn)

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

平衡性

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

hash?算法并不是保證絕對(duì)的平衡，如果?cache?較少的話，對(duì)象并不能被均勻的映射到?cache?上，比如在上面的例子中，僅部署?cache A?和?cache C?的情況下，在?4?個(gè)對(duì)象中，?cache A?僅存儲(chǔ)了?object1?，而?cache C?則存儲(chǔ)了?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)對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對(duì)應(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í)，對(duì)象到“虛擬節(jié)點(diǎn)”的映射關(guān)系為：

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

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

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

?

圖?7?查詢對(duì)象所在?cache

?

“虛擬節(jié)點(diǎn)”的?hash?計(jì)算可以采用對(duì)應(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

轉(zhuǎn)載于:https://www.cnblogs.com/persist/archive/2013/03/21/2972715.html

總結(jié)

以上是生活随笔為你收集整理的转载：一致性 hash 算法（ consistent hashing ）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。