最近在研究"一致性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.
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.
我的理解，这类方法其实有点像大学里的微积分的思想（通过连续函数的取值区间来计算图形面积）。通过把已知的实结点（memcached服务IP端口）列表结成一个圆，然后在两两实结点之间“放置”尽可能多的虚拟节点(上面文中的unsigned ints)， 假设用户数据映射在虚拟节点上（用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上），这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。如下图：
下面是添加结点时：
如这篇文章所说（总结一致性哈希(Consistent Hashing) ）：
Consistent Hashing最大限度地抑制了hash键的重新分布。另外要取得比较好的负载均衡的效果，往往在服务器数量比较少的时候需要增加虚拟节点来保证服务器能均匀的分布在圆环上。因为使用一般的hash方法，服务器的映射地点的分布非常不均匀。使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配100～200个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上，就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。
了解了原理，下面看一下具体实现。
JAVA实现代码取自Spy Memcached client中的类，原文的作者也尽可能的对代码进行注释说明，所以让我剩了不少时间。
本文导航
- 第1页: 首页
- 第2页: 相应的.NET实现
- 第3页: .net版本下的测试结果
