最近在研究一致性HASH算法（Consistent Hashing）用於解決memcached集群中當服務器出現增減變動時對散列值的影響後來 在JAVAEYE上的一篇文章中找到了其中的 KetamaHash 算法的JAVA實現（一種基於虛擬結點的HASH算法）於是為了加深理解對照 JAVA版本用C#重寫了一個放到這裡如果大家感興趣的話 可以下載測試一下如果發現寫法有問題請及時告之我以便我及時修正
下面是對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
Heres how it works:
* Take your list of servers (eg: : : :)
* Hash each server string to several () unsigned ints
* Conceptually these numbers are placed on a circle called the continuum (imagine a clock face that goes from to ^)
* 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 ^ 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
我的理解這類方法其實有點像大學裡的微積分的思想（通過連續函數的取值區間來計算圖形面積）通過把已知的實結點（memcached服務IP端口）列表結成一個圓然後在兩兩實結點之間放置盡可能多的虛擬節點(上面文中的unsigned ints) 假設用戶數據映射在虛擬節點上（用戶數據真正存儲位置是在該虛擬節點代表的實際物理服務器上）這樣就能抑制分布不均勻最大限度地減小服務器增減時的緩存重新分布如下圖
下面是添加結點時
Consistent Hashing最大限度地抑制了hash鍵的重新分布另外要取得比較好的負載均衡的效果往往在服務器數量比較少的時候需要增加虛擬節點來保證服務器能均勻的分布在圓環上因為使用一般的hash方法服務器的映射地點的分布非常不均勻使用虛擬節點的思想為每個物理節點（服務器）在圓上分配～個點這樣就能抑制分布不均勻最大限度地減小服務器增減時的緩存重新分布用戶數據映射在虛擬節點上就表示用戶數據真正存儲位置是在該虛擬節點代表的實際物理服務器上
了解了原理下面看一下具體實現
JAVA實現代碼取自Spy Memcached client中的類原文的作者也盡可能的對代碼進行注釋說明所以讓我剩了不少時間
下面是相應的NET實現（注釋參考JAVA版本）:
public class KetamaNodeLocator
{
//原文中的JAVA類TreeMap實現了Comparator方法這裡我圖省事直接用了net下的SortedList其中Comparer接口方法）
private SortedList<long string> ketamaNodes = new SortedList<long string>();
private HashAlgorithm hashAlg;
private int numReps = ;
//此處參數與JAVA版中有區別因為使用的靜態方法所以不再傳遞HashAlgorithm alg參數
public KetamaNodeLocator(List<string> nodes int nodeCopies)
{
ketamaNodes = new SortedList<long string>();
numReps = nodeCopies;
//對所有節點生成nCopies個虛擬結點
foreach (string node in nodes)
{
//每四個虛擬結點為一組
for (int i = ; i < numReps / ; i++)
{
//getKeyForNode方法為這組虛擬結點得到惟一名稱
byte[] digest = puteMd(node + i);
/** Md是一個字節長度的數組將字節的數組每四個字節一組分別對應一個虛擬結點這就是為什麼上面把虛擬結點四個劃分一組的原因*/
for (int h = ; h < ; h++)
{
long m = HashAlgorithmhash(digest h);
ketamaNodes[m] = node;
}
}
}
}
public string GetPrimary(string k)
{
byte[] digest = puteMd(k);
string rv = GetNodeForKey(HashAlgorithmhash(digest ));
return rv;
}
string GetNodeForKey(long hash)
{
string rv;
long key = hash;
//如果找到這個節點直接取節點返回
if (!ketamaNodesContainsKey(key))
{
//得到大於當前key的那個子Map然後從中取出第一個key就是大於且離它最近的那個key 說明詳見:
var tailMap = from coll in ketamaNodes
where collKey > hash
select new { collKey };
if (tailMap == null || tailMapCount() == )
key = ketamaNodesFirstOrDefault()Key;
else
key = tailMapFirstOrDefault()Key;
}
rv = ketamaNodes[key];
return rv;
}
}
下面的代碼與JAVA中有所不同它使用靜態方法實現
public class HashAlgorithm
{
public static long hash(byte[] digest int nTime)
{
long rv = ((long)(digest[ + nTime * ] & xFF) << )
| ((long)(digest[ + nTime * ] & xFF) << )
| ((long)(digest[ + nTime * ] & xFF) << )
| ((long)digest[ + nTime * ] & xFF);
return rv & xffffffffL; /* Truncate to bits */
}
/**
* Get the md of the given key
*/
public static byte[] computeMd(string k)
{
MD md = new MDCryptoServiceProvider();
byte[] keyBytes = mdComputeHash(EncodingUTFGetBytes(k));
mdClear();
//mdupdate(keyBytes);
//return mddigest();
return keyBytes;
}
}
From:http://tw.wingwit.com/Article/program/net/201311/13174.html
