用c#實(shí)現(xiàn)一致性Hash算法(KetamaHash)

abylon FREEHASH1.5 安裝版

• 類型：密碼相關(guān)大�。�9.4M語言：英文 評(píng)分：5.0
• 標(biāo)簽：

立即下載

 最近在研究"一致性HASH算法"（Consistent Hashing），用于解決memcached集群中當(dāng)服務(wù)器出現(xiàn)增減變動(dòng)時(shí)對(duì)散列值的影響。后來 在JAVAEYE上的一篇文章中，找到了其中的 KetamaHash 算法的JAVA實(shí)現(xiàn)（一種基于虛擬結(jié)點(diǎn)的HASH算法），于是為了加深理解，對(duì)照 JAVA版本，用C#重寫了一個(gè)。放到這里，如果大家感興趣的話， 可以下載測(cè)試一下，如果發(fā)現(xiàn)寫法有問題請(qǐng)及時(shí)告之我，以便我及時(shí)修正。
 
      下面是對(duì)Ketama的介紹：
 Ketama is an implementation of a consistent hashing algorithm, meaning you can add or remove servers from the memcached pool without causing a complete remap of all keys.
 Here’s how it works:
 * Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
 * Hash each server string to several (100-200) unsigned ints
 * Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
 * Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.
 * To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.
 * If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.
 If you then add or remove a server from the list, only a small proportion of keys end up mapping to different servers.
 

           我的理解，這類方法其實(shí)有點(diǎn)像大學(xué)里的微積分的思想（通過連續(xù)函數(shù)的取值區(qū)間來計(jì)算圖形面積）。通過把已知的實(shí)結(jié)點(diǎn)（memcached服務(wù)IP端口）列表結(jié)成一個(gè)圓，然后在兩兩實(shí)結(jié)點(diǎn)之間“放置”盡可能多的虛擬節(jié)點(diǎn)(上面文中的unsigned ints)， 假設(shè)用戶數(shù)據(jù)映射在虛擬節(jié)點(diǎn)上（用戶數(shù)據(jù)真正存儲(chǔ)位置是在該虛擬節(jié)點(diǎn)代表的實(shí)際物理服務(wù)器上），這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時(shí)的緩存重新分布。如下圖：

             下面是添加結(jié)點(diǎn)時(shí)：

    
                  
         如這篇文章所說（總結(jié)一致性哈希(Consistent Hashing) ）：
   
      Consistent Hashing最大限度地抑制了hash鍵的重新分布。另外要取得比較好的負(fù)載均衡的效果，往往在服務(wù)器數(shù)量比較少的時(shí)候需要增加虛擬節(jié)點(diǎn)來保證服務(wù)器能均勻的分布在圓環(huán)上。因?yàn)槭褂靡话愕膆ash方法，服務(wù)器的映射地點(diǎn)的分布非常不均勻。使用虛擬節(jié)點(diǎn)的思想，為每個(gè)物理節(jié)點(diǎn)（服務(wù)器）在圓上分配100～200個(gè)點(diǎn)。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時(shí)的緩存重新分布。用戶數(shù)據(jù)映射在虛擬節(jié)點(diǎn)上，就表示用戶數(shù)據(jù)真正存儲(chǔ)位置是在該虛擬節(jié)點(diǎn)代表的實(shí)際物理服務(wù)器上。

       了解了原理，下面看一下具體實(shí)現(xiàn)。

       JAVA實(shí)現(xiàn)代碼取自Spy Memcached client中的類，原文的作者也盡可能的對(duì)代碼進(jìn)行注釋說明，所以讓我剩了不少時(shí)間。