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代码及测试代码

评论

34 楼 jasonGe 2016-07-20  

Normal case : nodes count : 50
Added case : nodes count : 58
Reduced case : nodes count : 40
81582   ---   75086
Same percent in added case : 81.582%
Same percent in reduced case : 75.086%

楼主你好，这是我运行的结果，平衡性差异挺大啊。第二个58，第三个40 。
能帮忙解释下么？

33 楼 guliangliang 2016-07-13  

tdttyl.cwm 写道

runjia1987 写道

我想知道，如果key的哈希冲突了，乍办？

如何理解key的哈希冲突？
1、不同的key经过hash运算之后得到同一个hash值？
2、应用中某一个或某几个key非常热？

对于第一种情况输入hash算法问题，hash算法有一个特性是均衡性。均衡性很难保证的hash算法是不合格的。
对于第二种情况，可以在原有hash基础上再次做一次hash，通过二次hash来重建均衡性。ConcurrentHashMap中选择segment就采用了二次hash。

以上是个人理解。

楼主，“均衡性很难保证的hash算法是不合格的。” 这句话怎么理解....

32 楼 tdttyl.cwm 2016-02-28  

runjia1987 写道

我想知道，如果key的哈希冲突了，乍办？

如何理解key的哈希冲突？
1、不同的key经过hash运算之后得到同一个hash值？
2、应用中某一个或某几个key非常热？

对于第一种情况输入hash算法问题，hash算法有一个特性是均衡性。均衡性很难保证的hash算法是不合格的。
对于第二种情况，可以在原有hash基础上再次做一次hash，通过二次hash来重建均衡性。ConcurrentHashMap中选择segment就采用了二次hash。

以上是个人理解。

31 楼 chenchunji 2015-03-17  

哥们，冒昧的问一下。这个代码你们在JAVA项目中应用了吗？

30 楼 runjia1987 2014-09-03  

我想知道，如果key的哈希冲突了，乍办？

29 楼 langyu 2012-11-26  

kevins.xf 写道

请问为什么要四个虚拟结点为一组呢，没看出来有什么好处

在代码的注释中我解释过，只是为了适应MD5的16字节

28 楼 kevins.xf 2012-11-23  

请问为什么要四个虚拟结点为一组呢，没看出来有什么好处

27 楼 grzrt 2012-05-17  

langyu 写道

grzrt 写道

正常情况下不应该，但是如果出现这种情况，怎么解决呢？

你也看到了，hash函数及虚拟节点的引入都是为了解决尽量让负载在节点间平衡。如果出现不平衡的问题，一定得先查出是什么原因导致。可以从数据的特点来分析，是不是某些数据与其它数据不一样，让hash函数不是那么平均？

如果真的出现这种问题，我们需要更平均地分摊负载。可能的作法有：加节点；增加虚拟节点数量；使用更平均的hash函数。我能想到的就是这几点。你的看法呢？

嗯。我暂时没有好的想法，只是有这么个疑虑

26 楼 langyu 2012-05-17  

grzrt 写道

正常情况下不应该，但是如果出现这种情况，怎么解决呢？

你也看到了，hash函数及虚拟节点的引入都是为了解决尽量让负载在节点间平衡。如果出现不平衡的问题，一定得先查出是什么原因导致。可以从数据的特点来分析，是不是某些数据与其它数据不一样，让hash函数不是那么平均？

如果真的出现这种问题，我们需要更平均地分摊负载。可能的作法有：加节点；增加虚拟节点数量；使用更平均的hash函数。我能想到的就是这几点。你的看法呢？

25 楼 grzrt 2012-05-17  

langyu 写道

grzrt 写道

请问增么控制新增加的节点的位置？如果发现原来的其中一台的压力比较大，要减压扩容怎么做呢？

一台压力比较大的原因是什么？正常情况下不应该的

正常情况下不应该，但是如果出现这种情况，怎么解决呢？

24 楼 langyu 2012-05-17  

grzrt 写道

请问增么控制新增加的节点的位置？如果发现原来的其中一台的压力比较大，要减压扩容怎么做呢？

一台压力比较大的原因是什么？正常情况下不应该的

23 楼 grzrt 2012-05-17  

请问增么控制新增加的节点的位置？如果发现原来的其中一台的压力比较大，要减压扩容怎么做呢？

22 楼 grzrt 2012-05-17  

楼主 给力

21 楼 manecocomph 2011-07-19  

学习了, 写的真不错

20 楼 langyu 2011-04-20  

veenter 写道

我有一个问题： 虚拟节点的多少应该如何设置呢！或者说和物理节点的多少有什么倍数关系吗

引入虚拟节点的概念是解决物理节点分布不均的问题。所以理论上说，虚拟节点设置的越多，往集群中放数据时选择节点的概率越平等，分布在每台节点的数据也就越均匀。所以这个值的设置由你把握。

19 楼 veenter 2011-04-20  

我有一个问题： 虚拟节点的多少应该如何设置呢！或者说和物理节点的多少有什么倍数关系吗

18 楼 langyu 2011-04-20  

wanrue 写道

楼主，为什么测试用的key不用ketama hash算法处理呢？

Ketama 算法是产生众多虚拟节点的过程，以便key在选择时可以更随机。而key的目的单纯，只是为了选择某个虚拟节点，除了hash就不需要更多的处理。不知道这样解释可能解决你的疑惑？

17 楼 wanrue 2011-04-19  

楼主，为什么测试用的key不用ketama hash算法处理呢？

16 楼 wanrue 2011-04-19  

楼主 给力
可以参考下了 真需要

15 楼 gigi_112 2010-12-22  

前提是我用在了数据库中，有个问题想问下，如果由于机房拆迁，你的node更换了IP地址，此时所有隐射都会改变，除了在隐射一次新地址和老地址之外，还有别的方法么