有限分布算法

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

算法简介

该算法使用时首先需要限定集群中节点的最大数量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. 出于性能角度的考虑,随机序列中的随机数并不需要一次性全部获取。

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

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

一致性哈希

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

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

一致性哈希实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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);
}

}

算法执行时间

631-639毫秒

单节点宕机后移动数据量

55324(=该节点原分布数据量)

数据分布图(10.10.1.0宕机前、10.10.1.0宕机后)

Alt text

有限分布算法

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

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

有限分布算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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;
}

}

算法执行时间

401-405毫秒

单节点宕机后移动数据量

49917(=该节点原分布数据量)

数据分布图(10.10.1.0宕机前、10.10.1.0宕机后)

Alt text

总结

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

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