consistent hashing算法早在1997年就在論文Consistent hashing and random trees中被提出，目前在cache系統(tǒng)中應(yīng)用越來(lái)越廣泛；1基本場(chǎng)景比如你有N個(gè)cache服務(wù)器（后面簡(jiǎn)稱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由于訪問(wèn)加重，需要添加cache，這時(shí)候cache是N+1臺(tái)，映射公式變成了hash(object)%(N+1)；1和2意味著什么？這意味著突然之間幾乎所有的cache都失效了。對(duì)于服務(wù)器而言，這是一場(chǎng)災(zāi)難，洪水般的訪問(wèn)都會(huì)直接沖向后臺(tái)服務(wù)器；再來(lái)考慮第三個(gè)問(wèn)題，由于硬件能力越來(lái)越強(qiáng)，你可能想讓后面添加的節(jié)點(diǎn)多做點(diǎn)活，顯然上面的hash算法也做不到。有什么方法可以改變這個(gè)狀況呢，這就是consistent hashing...2 hash算法和單調(diào)性Hash算法的一個(gè)衡量指標(biāo)是單調(diào)性（Monotonicity），定義如下：?jiǎn)握{(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。容易看到，上面的簡(jiǎn)單hash算法hash(object)%N難以滿足單調(diào)性要求。3 consistent hashing算法的原理consistent hashing是一種hash算法，簡(jiǎn)單的說(shuō)，在移除/添加一個(gè)cache時(shí)，它能夠盡可能小的改變已存在key映射關(guān)系，盡可能的滿足單調(diào)性的要求。下面就來(lái)按照5個(gè)步驟簡(jiǎn)單講講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空間接下來(lái)考慮4個(gè)對(duì)象object1~object4，通過(guò)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所示，他們?cè)趆ash空間中，以對(duì)應(yīng)的hash值排列。hash(cache A) = key A;… …hash(cache C) = key C;
圖3 cache和對(duì)象的key值分布說(shuō)到這里，順便提一下cache的hash計(jì)算，一般的方法可以使用cache機(jī)器的IP地址或者機(jī)器名作為hash輸入。3.4把對(duì)象映射到cache現(xiàn)在cache和對(duì)象都已經(jīng)通過(guò)同一個(gè)hash算法映射到hash數(shù)值空間中了，接下來(lái)要考慮的就是如何將對(duì)象映射到cache上面了。在這個(gè)環(huán)形空間中，如果沿著順時(shí)針?lè)较驈膶?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)前面講過(guò)，通過(guò)hash然后求余的方法帶來(lái)的最大問(wèn)題就在于不能滿足單調(diào)性，當(dāng)cache有所變動(dòng)時(shí)，cache會(huì)失效，進(jìn)而對(duì)后臺(tái)服務(wù)器造成巨大的沖擊，現(xiàn)在就來(lái)分析分析consistent hashing算法。3.5.1移除cache考慮假設(shè)cache B掛掉了，根據(jù)上面講到的映射方法，這時(shí)受影響的將僅是那些沿cache B逆時(shí)針遍歷直到下一個(gè)cache（cache C）之間的對(duì)象，也即是本來(lái)映射到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ì)象（它們是也本來(lái)映射到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分布并不均勻�，F(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)換到了{(lá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 A1Hash(“202.168.14.241#2”);// cache A25小結(jié)Consistent hashing的基本原理就是這些，具體的分布性等理論分析應(yīng)該是很復(fù)雜的，不過(guò)一般也用不到。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.aspxC語(yǔ)言版本一些參考資料地址：http://portal.acm.org/citation.cfm?id=258660http://en.wikipedia.org/wiki/Consistent_hashinghttp://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/http://weblogs.java.net/blog/2007/11/27/consistent-hashinghttp://tech.idv2.com/2008/07/24/memcached-004/http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx
