一致性 Hash 实现

发布于: 21 小时前

本文主要讨论一致性Hash的Java实现,使用了Java的TreeMap来实现,采用了CRC32和FNV1_32两种散列算法来算Hash值,也加入了虚拟节点的避免数据倾斜。

public interface HashAlgorithm {
public long hash(String originString);
}
public class CRC32HashAlgorithm implements HashAlgorithm {
public long hash(String originString) {
CRC32 crc = new CRC32();
crc.update(originString.getBytes());
return crc.getValue();
}
}
public class FNV132HashAlgorithm implements HashAlgorithm {
public long hash(String originString) {
final int p = 16777619;
long hash = 2166136261L;
for (int i = 0; i < originString.length(); i++)
hash = (hash ^ originString.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
// 如果算出来的值为负数则取其绝对值
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
}
public class Node {
private String value;
public Node(String value) {
this.value = value;
}
public String getValue() {
return value;
}
}
public class ConsistencyHash {
private SortedMap<Long, Node> virtualNodeMap = new TreeMap<Long, Node>();
private int virtualNodeNum;
private HashAlgorithm hashAlgorithm;
public ConsistencyHash(int virtualNodeNum, HashAlgorithm hashAlgorithm) {
this.virtualNodeNum = virtualNodeNum;
this.hashAlgorithm = hashAlgorithm;
}
/**
* 将服务器节点加入一致性Hash环
* @param node
*/
public void addNode(Node node) {
for (int i = 0; i < virtualNodeNum; i++) {
long hashValue = hashAlgorithm.hash(node.getValue() + "-" + i);
virtualNodeMap.put(hashValue, node);
}
}
/**
* 计算key对应的服务器节点
* @param key
* @return
*/
public Node getNode(String key) {
long hashValue = hashAlgorithm.hash(key);
SortedMap<Long, Node> map = virtualNodeMap.tailMap(hashValue);
Long resultKey = 0L;
//如果找不到,则说明在最后一个节点和第一个节点之间,则分配到第一个节点
if (map.size() == 0) {
resultKey = virtualNodeMap.firstKey();
} else {
resultKey = map.firstKey();
}
return virtualNodeMap.get(resultKey);
}
}

以上是一致性Hash的实现,下面我们来验证一下均衡性,10个服务器节点

public class Client {
public static void main(String[] args) {
String[] servers = new String[]{
"192.168.0.1:8080",
"192.168.0.2:8080",
"192.168.0.3:8080",
"192.168.0.4:8080",
"192.168.0.5:8080",
"192.168.0.6:8080",
"192.168.0.7:8080",
"192.168.0.8:8080",
"192.168.0.9:8080",
"192.168.0.10:8080"
};
//--------FNV132HashAlgorithm------------//
ConsistencyHash consistencyHashWith80VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(80, new FNV132HashAlgorithm());
System.out.println("FNV132HashAlgorithm with 80 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith80VirtualNodeAndFNV132HashAlgorithm)));
ConsistencyHash consistencyHashWith160VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(160, new FNV132HashAlgorithm());
System.out.println("FNV132HashAlgorithm with 160 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith160VirtualNodeAndFNV132HashAlgorithm)));
ConsistencyHash consistencyHashWith200VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(200, new FNV132HashAlgorithm());
System.out.println("FNV132HashAlgorithm with 200 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith200VirtualNodeAndFNV132HashAlgorithm)));
ConsistencyHash consistencyHashWith320VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(320, new FNV132HashAlgorithm());
System.out.println("FNV132HashAlgorithm with 320 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith320VirtualNodeAndFNV132HashAlgorithm)));
//--------CRC32HashAlgorithm------------//
ConsistencyHash consistencyHashWith80VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(80, new CRC32HashAlgorithm());
System.out.println("CRC32HashAlgorithm with 80 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith80VirtualNodeAndCRC32HashAlgorithm)));
ConsistencyHash consistencyHashWith160VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(160, new CRC32HashAlgorithm());
System.out.println("CRC32HashAlgorithm with 160 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith160VirtualNodeAndCRC32HashAlgorithm)));
ConsistencyHash consistencyHashWith200VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(200, new CRC32HashAlgorithm());
System.out.println("CRC32HashAlgorithm with 200 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith200VirtualNodeAndCRC32HashAlgorithm)));
ConsistencyHash consistencyHashWith320VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(320, new CRC32HashAlgorithm());
System.out.println("CRC32HashAlgorithm with 320 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith320VirtualNodeAndCRC32HashAlgorithm)));
}
private static List<Long> computeNodeAllocation(String[] servers, ConsistencyHash consistencyHash) {
for (int i = 0; i < servers.length; i++) {
consistencyHash.addNode(new Node(servers[i]));
}
Map<String, Long> result = new HashMap<String, Long>();
for (int i = 0; i < 1000000; i++) {
Random random = new Random();
String key = "test" + random.nextInt(10000);
Node node = consistencyHash.getNode(key);
if (result.get(node.getValue()) == null) {
result.put(node.getValue(), 1L);
} else {
result.put(node.getValue(), result.get(node.getValue()) + 1L);
}
}
List<Long> resultNum = new ArrayList<Long>();
for (Map.Entry<String, Long> entry : result.entrySet()) {
resultNum.add(entry.getValue());
}
return resultNum;
}
private static Double computeStandardDeviation(List<Long> resultNum) {
long sum = 0;
int length = resultNum.size();
for(int i = 0; i < resultNum.size(); i++){
sum += resultNum.get(i); //求出数组的总和
}
double average = sum / length; //求出数组的平均数
long total = 0;
for (int i = 0; i < length; i++) {
total += (resultNum.get(i) - average) * (resultNum.get(i) - average); //求出方差,如果要计算方差的话这一步就可以了
}
double standardDeviation = Math.sqrt(total / length); //求出标准差
return standardDeviation;
}
}

测试结果如下,根据测试结果其实能看出,虚拟节点也并不是越多越好,100-200之间就好,而且和hash算法也有很大的关系。

FNV132HashAlgorithm with 80 virtual node, standard deviation is 45717.53488542443
FNV132HashAlgorithm with 160 virtual node, standard deviation is 23627.90045687513
FNV132HashAlgorithm with 200 virtual node, standard deviation is 19698.36820652919
FNV132HashAlgorithm with 320 virtual node, standard deviation is 21673.15865304363
CRC32HashAlgorithm with 80 virtual node, standard deviation is 27903.421080577198
CRC32HashAlgorithm with 160 virtual node, standard deviation is 13226.479879393459
CRC32HashAlgorithm with 200 virtual node, standard deviation is 13922.735435251221
CRC32HashAlgorithm with 320 virtual node, standard deviation is 18066.353644274765

发布于: 21 小时前 阅读数: 5
用户头像

olderwei

关注

还未添加个人签名 2018.04.26 加入

还未添加个人简介

评论

发布
暂无评论
一致性Hash实现