一致性hash算法.docVIP

一致性Hash算法(KetamaHash)的c#实现 ?????? 最近在研究一致性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:?:11211,?:11211,?: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中的类，原文的作者也尽可能的对代码进行注释说明，所以让我剩了不少时间。