一致性哈希要解決的問題很常見：如何將許多鍵值（譬如md5的值域空間）分布到多個服務器節點。
直接的做法是一個普通的哈希（譬如取模），但如果服務器節點可能會動態變化，每次節點的變化都會導致絕大多數映射的失效，不好。
一致性哈希的做法是，將key的值域看做是一個環，每個服務器映射為多個環上的點（virtual node），所有服務器的點的集合將環分成多個區段，key->server的映射過程是：根據key找到對應的點，然后順時針（逆時針也行，但要統一順或者逆）找到最近的虛擬節點，該vnode對應的server，將用來處理這個key。
值得注意的是，一個服務器要映射為多個virtual node（例如100-200個），而且virtual node要均勻分布在環上（要是這100個都挨著，就失去意義了）?？紤]一個極端情況，每個服務器都映射為一個vnode，那么某服務器失效的時候，它的負載都被下一臺服務器承擔去了，失去了均衡負載的效果了。
實踐上，還可以根據服務器的能力和當前負載來動態的調整某服務器映射的vnode的個數，以更好地平衡負載。
假設環的空間為md5的值域，即0-2^128-1，實現的時候，要考慮兩個hash。
1，server->vnode_list的映射，這可以通過將server的ip地址附加上若干個編號（或隨機數），md5以后得到對應的vnode列表。
2，resource_key->ring_key的映射，譬如resource key是URL，那么直接md5就行了。
還要考慮一個區段劃分關系，即各個vnode負責的區段是哪些，這用一個二叉樹或者數組就行了，查找的時候，對數組進行二分就可以了。
最后就是一個vnode到server的從屬關系，也即上面兩個hash第一個的逆映射，記錄就行了。
consistent hashing在許多互聯網平臺實現中都是標準的工具，譬如Amazon的Dynamo（參見論文Dynamo: Amazon's Highly Available Key-value Store）。
對于memcache，consistent hashing是在client端做的，可以參見last.fm的實現： 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
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
