《有限分布算法》来了！ 抛弃一致性哈希吧

声明

《有限分布算法》由本文作者原创，知识产权为本文作者所有。该算法可以用于个人研究，以及其他非商业性或非盈利性用途，但同时您应该遵守著作权法以及其他相关法律的规定，不得侵犯本文作者的合法权益。

 

算法简介

该算法使用时首先需要限定集群中节点的最大数量MAX，接下来我用一个简单的例子来描述这个算法的原理。假设集群中最多有10个节点，集群中现在有一个文件test.log，那么test.log就在集群中按如下规则分布：

 

1. 根据文件名字符串获取哈希码：hash(test.log)=-1147914264
2. 使用哈希码作为SEED获取0-10(MAX)之间的随机序列：[9, 5, 7, 8, 3, 1, 0, 6, 2, 4]。
3. test.log沿着这个随机序列寻找它自己的分布位置——若9离线，则分布于5，若9和5离线，则分布于7。
4. 当9再次上线后，test.log副本可以根据需要从5或7移动回节点9中。
5. 出于性能角度的考虑，随机序列中的随机数并不需要一次性全部获取。

 

《有限分布算法》相对于“一致性哈希”而言，它显然可以在数据的均衡分布上表现的更好。由于所有数据都基于不同的随机数种子随机分布在集群中，因此它可以在理论上实现系统负载的完全均衡，而集群状态发生改变时，它也仅需要处理受到影响的那一部分数据副本。

 

《有限分布算法》的性能表现也优于“一致性哈希”，其中原理不再赘述，下文中的测试数据可以证明有限分布算法的性能优势。

 

测试数据

参与测试的“一致性哈希”实现代码如下所示：

package com.limited;
import java.util.Collection;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 一致性哈希
 * @author sulin
 * @date 2013-7-30
 * @version 0.1
 */
public class ConsistentHash{

	private final int numberOfReplicas;
	private final SortedMap<Integer, String> circle = new TreeMap<Integer, String>();

	public ConsistentHash(int numberOfReplicas, Collection<String> nodes) {
		this.numberOfReplicas = numberOfReplicas;
		for (String node : nodes) {
			add(node);
		}
	}

	public void add(String node) {
		Random r = new Random(node.hashCode());
		for (int i = 0; i < numberOfReplicas; i++) {
			/**
			 * 我最初使用的是：	(node+"#"+i).hashCode();
			 * 这种方式但它的效果很差。
			 */
			/**
			 * 第二种选择是：整数区块平均切分：
			 * hashcode + (Integer.MAX_VALUE/numberOfReplicas) * 2
			 * 这种方式的效果也很差。
			 */
			int key = r.nextInt();
			circle.put(key, node);
		}
	}

	public void remove(String node) {
		Random r = new Random(node.hashCode());
		for (int i = 0; i < numberOfReplicas; i++) {
			int key = r.nextInt();
			circle.remove(key);
		}
	}

	public String get(Object key) {
		if (circle.isEmpty()) {
			return null;
		}
		int hash = key.hashCode();
		if (!circle.containsKey(hash)) {
			SortedMap<Integer, String> tailMap = circle.tailMap(hash);
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}

}

 

测试数据分别为：数据分布图、节点宕机后数据流动量、计算分布时间。

测试条件为：1000000个随机文件、20个节点（每个物理节点映射为分散的20个虚拟节点）。

 

《一致性哈希》数据分布图（10.10.1.0宕机前、10.10.1.0宕机后）

 

算法执行时间：631-639毫秒

 

10.10.1.0宕机后数据移动量：55324（=该节点原分布数据量）

 

---------------------------------------分割线---------------------------------

参与测试的“有限分布算法”实现如下：

package com.limited;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 有限分布算法
 * @author sulin
 * @date 2013-7-30
 * @version 0.1
 */
public class LimitedDistribute {

	/**
	 * 节点名:是否在线
	 */
	private final Map<String, Boolean> nodes;
	
	private final String[] nodeArray;
	
	public LimitedDistribute(Collection<String> nodes) {
		this.nodes = new HashMap<String, Boolean>();
		for(String node : nodes)
			this.nodes.put(node, true);
		
		nodeArray = nodes.toArray(new String[]{});
	}
	
	public void online(String node){
		if(nodes.containsKey(node))
			nodes.put(node, true);
	}
	
	public void outline(String node){
		if(nodes.containsKey(node))
			nodes.put(node, false);
	}
	
	public String get(Object key) {
		if (nodes.isEmpty()) {
			return null;
		}
		Random r = new Random(key.hashCode());
		String result = null;
		while(result == null){
			int i = r.nextInt(nodes.size());
			if(nodes.get(nodeArray[i]))
				result = nodeArray[i];
		}
		
		return result;
	}
	
}

 

测试数据分别为：数据分布图、节点宕机后数据流动量、计算分布时间。

 

测试条件为：1000000个随机文件、20个节点（每个物理节点映射为分散的20个虚拟节点）。

 

《有限分布算法》数据分布图（10.10.1.0宕机前、10.10.1.0宕机后）

 

算法执行时间：401-405毫秒

 

10.10.1.0宕机后数据移动量：49917（=该节点原分布数据量）

 

总结

根据测试数据我们可以很清晰的看到，一致性哈希的数据分布是非常不规则的，而有限分布算法的数据分布极其平均的。同时“一致性哈希”的计算性能与《有限分布算法》相比，降低了几乎50%，当然这也可能是笔者的算法实现不够完善所导致的。笔者会将全部源码以附件形式给出，如果你感兴趣的话可以下载源码自己尝试一下。

 

如果我们把《一致性哈希》所使用的“虚拟节点数量”增到至200、2000，这种分布的不规则性会在一定程度的得到抑制，但它永远也无法达到《有限分布算法》这样近乎完全平均分布的状态，并且“虚拟节点数量”的增加会进一步拉开《有限分布算法》与它之间的性能差距。总而言之一致性哈希的不规则分布是由该算法本身缺陷所导致的，即便技术非常精湛的工程师也无法弥补这个缺陷。如果你正在使用一致性哈希，现在你是否考虑抛弃它呢？

 

本文的讲解比较粗糙，这是因为《有限分布算法》只是笔者研究“分布式文件系统”时的副产品，具体详情会在下一篇博文中介绍。需要提前告知的是，笔者下一篇博文的挑战目标是现在名声大噪的HDFS，敬请期待。

 

作者：苏林

邮箱：[e-mail]

 

转载请注明出处：http://sulin.iteye.com/blog/1915431

评论

3 楼 s929498110 2014-06-20  

lliiqiang 写道

既然是算法一定是有限功能，不可能完成无限局限，你都挑出它不能做的事情.只是你本身也限制了.当然算法自身就是能够实现功能的

哈，产权什么的只是一个声明，防君子不防小人。

这个算法有一定的局限性，因此我才命名它为“有限分布算法”，或许将来有一天我能想出来一种“无限分布算法”。

路漫漫其修远兮，吾将上下而求索。

2 楼 lliiqiang 2014-06-19  

其实不存在什么知识产权的事情，因为都是人可以做的.只是说甚至对于外星人做法判断，简单却有效.

1 楼 lliiqiang 2014-06-19  

既然是算法一定是有限功能，不可能完成无限局限，你都挑出它不能做的事情.只是你本身也限制了.当然算法自身就是能够实现功能的