一致性哈希要解決的問(wèn)題很常見(jiàn)：如何將許多鍵值（譬如md5的值域空間）分布到多個(gè)服務(wù)器節(jié)點(diǎn)。

直接的做法是一個(gè)普通的哈希（譬如取模），但如果服務(wù)器節(jié)點(diǎn)可能會(huì)動(dòng)態(tài)變化，每次節(jié)點(diǎn)的變化都會(huì)導(dǎo)致絕大多數(shù)映射的失效，不好。

一致性哈希的做法是，將key的值域看做是一個(gè)環(huán)，每個(gè)服務(wù)器映射為多個(gè)環(huán)上的點(diǎn)（virtual node），所有服務(wù)器的點(diǎn)的集合將環(huán)分成多個(gè)區(qū)段，key->server的映射過(guò)程是：根據(jù)key找到對(duì)應(yīng)的點(diǎn)，然后順時(shí)針（逆時(shí)針也行，但要統(tǒng)一順或者逆）找到最近的虛擬節(jié)點(diǎn)，該vnode對(duì)應(yīng)的server，將用來(lái)處理這個(gè)key。

值得注意的是，一個(gè)服務(wù)器要映射為多個(gè)virtual node（例如100-200個(gè)），而且virtual node要均勻分布在環(huán)上（要是這100個(gè)都挨著，就失去意義了）。考慮一個(gè)極端情況，每個(gè)服務(wù)器都映射為一個(gè)vnode，那么某服務(wù)器失效的時(shí)候，它的負(fù)載都被下一臺(tái)服務(wù)器承擔(dān)去了，失去了均衡負(fù)載的效果了。

實(shí)踐上，還可以根據(jù)服務(wù)器的能力和當(dāng)前負(fù)載來(lái)動(dòng)態(tài)的調(diào)整某服務(wù)器映射的vnode的個(gè)數(shù)，以更好地平衡負(fù)載。

假設(shè)環(huán)的空間為md5的值域，即0-2^128-1，實(shí)現(xiàn)的時(shí)候，要考慮兩個(gè)hash。

1，server->vnode_list的映射，這可以通過(guò)將server的ip地址附加上若干個(gè)編號(hào)（或隨機(jī)數(shù)），md5以后得到對(duì)應(yīng)的vnode列表。

2，resource_key->ring_key的映射，譬如resource key是URL，那么直接md5就行了。

還要考慮一個(gè)區(qū)段劃分關(guān)系，即各個(gè)vnode負(fù)責(zé)的區(qū)段是哪些，這用一個(gè)二叉樹(shù)或者數(shù)組就行了，查找的時(shí)候，對(duì)數(shù)組進(jìn)行二分就可以了。

最后就是一個(gè)vnode到server的從屬關(guān)系，也即上面兩個(gè)hash第一個(gè)的逆映射，記錄就行了。

consistent hashing在許多互聯(lián)網(wǎng)平臺(tái)實(shí)現(xiàn)中都是標(biāo)準(zhǔn)的工具，譬如Amazon的Dynamo（參見(jiàn)論文Dynamo: Amazon's Highly Available Key-value Store）。

對(duì)于memcache，consistent hashing是在client端做的，可以參見(jiàn)last.fm的實(shí)現(xiàn)： http://cn.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients

更多參見(jiàn)wiki條目 http://en.wikipedia.org/wiki/Consistent_hashing

consistent hashing and open-source implementation