Ketama一致性Hash算法(含Java代码)

一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。Memcached client也选择这种算法，解决将key-value均匀分配到众多Memcached server上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真正存储的server，命中率会急剧下降)，详细的介绍在这篇帖子中http://www.iteye.com/topic/611976(后文指代这篇文章的地方均称为引文)。

［下面以Memcached的分布式问题为讨论点，但将Memcached server抽象为节点(Node)］
引文中描述的一致性Hash算法有个潜在的问题是:
     将节点hash后会不均匀地分布在环上，这样大量key在寻找节点时，会存在key命中各个节点的概率差别较大，无法实现有效的负载均衡。
     如有三个节点Node1,Node2,Node3，分布在环上时三个节点挨的很近，落在环上的key寻找节点时，大量key顺时针总是分配给Node2，而其它两个节点被找到的概率都会很小。

这种问题的解决方案可以有:
     改善Hash算法，均匀分配各节点到环上；［引文］使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配100～200个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上，就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。

在查看Spy Memcached client时，发现它采用一种称为Ketama的Hash算法，以虚拟节点的思想，解决Memcached的分布式问题。

对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.

下面以Spy Memcached中的代码为例来说明这种算法的使用

该client采用TreeMap存储所有节点，模拟一个环形的逻辑关系。在这个环中，节点之前是存在顺序关系的，所以TreeMap的key必须实现Comparator接口。
那节点是怎样放入这个环中的呢？

   
//对所有节点，生成nCopies个虚拟结点
		for(Node node : nodes) {
			//每四个虚拟结点为一组，为什么这样？下面会说到
			for(int i=0; i<nCopies / 4; i++) {
				//getKeyForNode方法为这组虚拟结点得到惟一名称
				byte[] digest=HashAlgorithm.computeMd5(getKeyForNode(node, i));
			/** Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，
                        分别对应一个虚拟结点，这就是为什么上面把虚拟结点四个划分一组的原因*/
				for(int h=0;h<4;h++) {
                  //对于每四个字节，组成一个long值数值，做为这个虚拟节点的在环中的惟一key
					Long k = ((long)(digest[3+h*4]&0xFF) << 24)
						| ((long)(digest[2+h*4]&0xFF) << 16)
						| ((long)(digest[1+h*4]&0xFF) << 8)
						| (digest[h*4]&0xFF);
					
					allNodes.put(k, node);
				}
			}
		}

上面的流程大概可以这样归纳:四个虚拟结点为一组，以getKeyForNode方法得到这组虚拟节点的name，Md5编码后，每个虚拟结点对应Md5码16个字节中的4个，组成一个long型数值，做为这个虚拟结点在环中的惟一key。第12行k为什么是Long型的呢？呵呵，就是因为Long型实现了Comparator接口。

处理完正式结点在环上的分布后，可以开始key在环上寻找节点的游戏了。
对于每个key还是得完成上面的步骤:计算出Md5，根据Md5的字节数组，通过Kemata Hash算法得到key在这个环中的位置。

        final Node rv;
		byte[] digest = hashAlg.computeMd5(keyValue);
		Long key = hashAlg.hash(digest, 0);
        //如果找到这个节点，直接取节点，返回
		if(!ketamaNodes.containsKey(key)) {
        //得到大于当前key的那个子Map，然后从中取出第一个key，就是大于且离它最近的那个key
			SortedMap<Long, Node> tailMap=ketamaNodes.tailMap(key);
			if(tailMap.isEmpty()) {
				key=ketamaNodes.firstKey();
			} else {
				key=tailMap.firstKey();
			}
            //在JDK1.6中，ceilingKey方法可以返回大于且离它最近的那个key
			//For JDK1.6 version
//			key = ketamaNodes.ceilingKey(key);
//			if (key == null) {
//				key = ketamaNodes.firstKey();
//			}
		}
		
		
		rv=allNodes.get(key);

引文中已详细描述过这种取节点逻辑:在环上顺时针查找，如果找到某个节点，就返回那个节点;如果没有找到，则取整个环的第一个节点。

测试结果
测试代码是自己整理的，主体方法没有变

分布平均性测试:测试随机生成的众多key是否会平均分布到各个结点上
测试结果如下:

Nodes count : 5, Keys count : 100000, Normal percent : 20.0%
-------------------- boundary  ----------------------
Node name :node1 - Times : 20821 - Percent : 20.821001%
Node name :node3 - Times : 19018 - Percent : 19.018%
Node name :node5 - Times : 19726 - Percent : 19.726%
Node name :node2 - Times : 19919 - Percent : 19.919%
Node name :node4 - Times : 20516 - Percent : 20.516%

最上面一行是参数说明，节点数目，总共有多少key，每个节点应该分配key的比例是多少。下面是每个结点分配到key的数目和比例。
多次测试后发现，这个Hash算法的节点分布还是不错的，都在标准比例左右徘徊，是个合适的负载均衡算法。


节点增删测试:在环上插入N个结点，每个节点nCopies个虚拟结点。随机生成众多key，在增删节点时，测试同一个key选择相同节点的概率
测试如果如下:

Normal case : nodes count : 50
Added case : nodes count : 51
Reduced case : nodes count : 49
------------ boundary -------------
Same percent in added case : 93.765%
Same percent in reduced case : 93.845%

上面三行分别是正常情况，节点增加，节点删除情况下的节点数目。下面两行表示在节点增加和删除情况下，同一个key分配在相同节点上的比例(命中率)。
多次测试后发现，命中率与结点数目和增减的节点数量有关。同样增删结点数目情况下，结点多时命中率高。同样节点数目，增删结点越少，命中率越高。这些都与实际情况相符。


附件为Ketama算法的Java代码及测试代码

评论

14 楼 langyu 2010-12-17  

capaccino 写道

langyu：
   代码中Node类是在哪里呢？

不好意思哈，主要是让大家看算法实现呢，就把Node类忽略了。它大致如此：

public class Node {

	private String nodeName;
	
	Node(String name) {
		this.nodeName = name;
	}
	
	public String getName() {
		return this.nodeName;
	}
	
	public String toString() {
		return this.nodeName;
	}
	
	public boolean equals(Object obj) {
		if (obj instanceof Node) {
			return ((Node) obj).nodeName.equals(this.nodeName);
		}
		
		return false;
	}
	
	public int hashCode() {
		return this.nodeName.hashCode();
	}
}

13 楼 capaccino 2010-12-16  

langyu：
   代码中Node类是在哪里呢？

12 楼 langyu 2010-12-08  

flynofry 写道

用long不用integer是为了避免出现负数值。

最高字节是这样生成的:

bKey[3] & 0xFF) << 24

，&后它的最高符号位是0，不会出现负数

11 楼 flynofry 2010-12-08  

langyu 写道

pandonix 写道

呵呵，就是因为Long型实现了Comparator接口。
-------
难道Integer就没有实现Comparator接口了么？

呀，被挑出来了，厉害。上面说过，这个模型是由TreeMap搭起来的，TreeMap需要它的key必须实现Comparator接口。
从算法实现上看，它的确应当选择Integer，而不是Long。
每个md5是16个字节，四个一组划分，这样每组四个字节。将一组四个字节从高字节到低字节依次移位，这四个字节就重新组成Integer，但是算法将它提升到了long型，这里的Long型只有低四字节有值，高四字节全是0。附件代码中有个方法HashAlgorithm.hash()，也是选择了md5的低四位组成一个Integer，又把它提升到Long了，用于从TreeMap中选择合适的虚拟节点。
你的疑问很对的。
我查看了Spy-Memcached client，由一个key去选择合适虚拟节点时它有这样的代码：

case KETAMA_HASH:
	byte[] bKey=computeMd5(k);
	rv = ((long) (bKey[3] & 0xFF) << 24)
		| ((long) (bKey[2] & 0xFF) << 16)
		| ((long) (bKey[1] & 0xFF) << 8)
		| (bKey[0] & 0xFF);
break;

这里可以看出，只是将Integer提升到Long了。至于是否有其它考量，暂时还看不出来。

用long不用integer是为了避免出现负数值。

10 楼 langyu 2010-10-29  

pandonix 写道

呵呵，就是因为Long型实现了Comparator接口。
-------
难道Integer就没有实现Comparator接口了么？

呀，被挑出来了，厉害。上面说过，这个模型是由TreeMap搭起来的，TreeMap需要它的key必须实现Comparator接口。
从算法实现上看，它的确应当选择Integer，而不是Long。
每个md5是16个字节，四个一组划分，这样每组四个字节。将一组四个字节从高字节到低字节依次移位，这四个字节就重新组成Integer，但是算法将它提升到了long型，这里的Long型只有低四字节有值，高四字节全是0。附件代码中有个方法HashAlgorithm.hash()，也是选择了md5的低四位组成一个Integer，又把它提升到Long了，用于从TreeMap中选择合适的虚拟节点。
你的疑问很对的。
我查看了Spy-Memcached client，由一个key去选择合适虚拟节点时它有这样的代码：

case KETAMA_HASH:
	byte[] bKey=computeMd5(k);
	rv = ((long) (bKey[3] & 0xFF) << 24)
		| ((long) (bKey[2] & 0xFF) << 16)
		| ((long) (bKey[1] & 0xFF) << 8)
		| (bKey[0] & 0xFF);
break;

这里可以看出，只是将Integer提升到Long了。至于是否有其它考量，暂时还看不出来。

9 楼 pandonix 2010-10-29  

呵呵，就是因为Long型实现了Comparator接口。
-------
难道Integer就没有实现Comparator接口了么？

8 楼 谢继雷 2010-07-05  

比如取模，若增加k个结点，
若 hash(key) ≡ i   (mod N*(N+k)) 且 0 ≤ i < N，
则有
  hash(key) ≡ i    (mod N)
以及
  hash(key) ≡ i    (mod N+k)
这样的 i 共有 0..N 个，占 N/(N+k) = 1/(N+k)。


设 g=gcd(N, N+k)，若 hash(key) ≡ i   (mod N(N+k)/g²)， 0 ≤ i < N/g，
则有
  hash(key) ≡ i    (mod N/g)
以及
  hash(key) ≡ i    (mod (N+k)/g)

在区间 0..N(N+k)/g² 中这样的 i 共有 0..N/g 个，占 (N/g) / (N(N+k)/g²) = g/(N+k)。

（前面 T=g²/(N+k) 写错了）
一致性hash 我只是简单的算了下，只是经验值，请懂概率的朋友细推一下，
n 大于100、k 大于n/10时 是我假设的情况。

7 楼 langyu 2010-07-02  

谢继雷 写道

考虑几种算法的性能度量，我算了一下

1，取模，hash值域足够长时，n+k结点时的命中率T为：
   
    若 (n, n+k) 互质，T = 1/(n+k)
    否则取 g = gcd(n, n+k)，T = g2/(n+k)
   
    当k=1时几乎总是有 T=1/(n+1)

2，平均分配，hash值域平均分割为n等分，则 n+k结点的命中率为：
   
    当k=1时有 T(1) = 1/2
    当k=j时有 T(j) = T(j-1)/2
    因此 T = 2^(-k)
   
    可见当k=1时平均分配比取模的效率更好。

3，一致性hash，当n足够大时，可以假设是均衡的，则n+k结点命中率为
   
    当k比较小时有 T = 1-k/2n
    当k较大时，T 大于 1-k/2n

这位兄弟看来精于此道，能说说具体的计算过程么？算法的理论依据是什么呢
比如对于一致性Hash，k与n怎么判断足够小与足够大呢？

6 楼 谢继雷 2010-07-02  

考虑几种算法的性能度量，我算了一下

1，取模，hash值域足够长时，n+k结点时的命中率T为：
   
    若 (n, n+k) 互质，T = 1/(n+k)
    否则取 g = gcd(n, n+k)，T = g2/(n+k)
   
    当k=1时几乎总是有 T=1/(n+1)

2，平均分配，hash值域平均分割为n等分，则 n+k结点的命中率为：
   
    当k=1时有 T(1) = 1/2
    当k=j时有 T(j) = T(j-1)/2
    因此 T = 2^(-k)
   
    可见当k=1时平均分配比取模的效率更好。

3，一致性hash，当n足够大时，可以假设是均衡的，则n+k结点命中率为
   
    当k比较小时有 T = 1-k/2n
    当k较大时，T 大于 1-k/2n

5 楼 langyu 2010-06-18  

waterdh 写道

和memcached java client的一致性hash算法大同小异， memcached client是将（servername + 循环的后缀）产生md5 byte[]，并分割成4个整形分布到环上。同样的，3个节点会产生几百个虚拟的server节点

呵呵，你看上面了么，就是这样的原理

4 楼 waterdh 2010-06-18  

和memcached java client的一致性hash算法大同小异， memcached client是将（servername + 循环的后缀）产生md5 byte[]，并分割成4个整形分布到环上。同样的，3个节点会产生几百个虚拟的server节点

3 楼 D-tune 2010-06-18  

正所谓高山流水，阳春白雪，高处不胜寒阿
lz，高手是需要耐得住寂寞的，code学习中

2 楼 liudun 2010-06-18  

实在是一篇好文章，不评论感觉对不起作者。哈哈

1 楼 langyu 2010-06-18  

发出文章这么久了，都没有人来评论下，哎