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

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

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

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

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

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

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

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

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

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

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

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

更多參見wiki條目 http://en.wikipedia.org/wiki/Consistent_hashing

consistent hashing and open-source implementation