架构师训练营 week05 作业 -- 一致性 Hash 算法

发布于: 2020 年 07 月 08 日
架构师训练营 week05 作业 -- 一致性 Hash 算法

作业

1、用你熟悉的编程语言实现一致性hash算法。

2、编写测试用例测试这个算法,测试100万KV数据,10个服务器节点的情况下,计算这些KV数据在服务器尚分布数量的标准差,以评估算法的存储负载不均衡性。

实现

public class ConsistentHash {
// 每个虚拟节点个数
private final int virtualNodeNumberOfReplicas;
//哈希环 存储虚拟节点的hash值到真实节点的映射
private final SortedMap<Integer, String> circle = new TreeMap<>();
//保存真实服务器和请求次数
private final TreeMap<String, Integer> servers = new TreeMap<>();
public ConsistentHash(Collection<String> nodes, int virtualNodeNumberOfReplicas) {
this.virtualNodeNumberOfReplicas = virtualNodeNumberOfReplicas;
System.out.println("节点个数:" + nodes.size());
System.out.println("每个节点虚拟节点个数:" + virtualNodeNumberOfReplicas);
for (String node:nodes) {
add(node);
}
}
public String getKey(String nodeKey){
if(circle.size() == 0){
return null;
}
int hashCode = getHashCode(nodeKey);
if(!circle.containsKey(hashCode)){
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> tailMap = circle.tailMap(hashCode);
// 第一个Key就是顺时针过去离node最近的那个节点
hashCode = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
String server = circle.get(hashCode);
server = server.substring(0, server.indexOf("#"));
servers.put(server,servers.get(server) + 1);
return server;
}
private int getHashCode(String key) {
final int p = 16777619;
int hashCode = (int)2166136261L;
for (int i = 0; i < key.length(); i++) {
hashCode = (hashCode ^ key.charAt(i)) * p;
hashCode += hashCode << 13;
hashCode ^= hashCode >> 7;
hashCode += hashCode << 3;
hashCode ^= hashCode >> 17;
hashCode += hashCode << 5;
}
if (hashCode < 0) {
hashCode = Math.abs(hashCode);
}
return hashCode;
}
public void add(String nodeServer){
if(!servers.containsKey(nodeServer)){
servers.put(nodeServer,0);
}
//添加虚拟节点
for (int j = 0; j < virtualNodeNumberOfReplicas; j++) {
String nodeKey = (String) (nodeServer + "#" + j);
Integer hashCode = getHashCode(nodeKey);
circle.put(hashCode,nodeKey);
}
}
public void remove(String nodeServer){
//删除虚拟节点
for (int j = 0; j < virtualNodeNumberOfReplicas; j++) {
circle.remove(getHashCode((String) (nodeServer + "#" + j)));
}
}
public double calcStandardDeviation(){
Integer[] visitData = new Integer[servers.size()];
servers.values().toArray(visitData);
// 计算平均值
double avg = Arrays.stream(visitData).mapToInt(value -> value).average().orElse(0);
double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d);
double std = Math.sqrt(avgStd);
return std;
}
public static void main(String[] args) {
//服务器节点
String[] serverNode = {"192.168.0.1","192.168.0.2","192.168.0.3","192.168.0.4","192.168.0.5","192.168.0.6"
,"192.168.0.7","192.168.0.8","192.168.0.9","192.168.0.10"};
ConsistentHash consistentHash = new ConsistentHash(Arrays.asList(serverNode),100);
long time = System.currentTimeMillis();
int countKey = 1000000;
for (int i = 0; i < countKey; i++) {
consistentHash.getKey(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println("存入时间差:"+time + " ms \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
consistentHash = new ConsistentHash(Arrays.asList(serverNode),1000);
time = System.currentTimeMillis();
for (int i = 0; i < countKey; i++) {
consistentHash.getKey(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println("存入时间差:"+time + " ms \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
consistentHash = new ConsistentHash(Arrays.asList(serverNode),2000);
time = System.currentTimeMillis();
for (int i = 0; i < countKey; i++) {
consistentHash.getKey(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println("存入时间差:"+time + " ms \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
consistentHash = new ConsistentHash(Arrays.asList(serverNode),3000);
time = System.currentTimeMillis();
for (int i = 0; i < countKey; i++) {
consistentHash.getKey(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println("存入时间差:"+time + " ms \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
consistentHash = new ConsistentHash(Arrays.asList(serverNode),5000);
time = System.currentTimeMillis();
for (int i = 0; i < countKey; i++) {
consistentHash.getKey(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println("存入时间差:"+time + " ms \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
consistentHash = new ConsistentHash(Arrays.asList(serverNode),6000);
time = System.currentTimeMillis();
for (int i = 0; i < countKey; i++) {
consistentHash.getKey(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println("存入时间差:"+time + " ms \t ,标准差:" + (int) consistentHash.calcStandardDeviation());
}
}

result

/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/bin/java -Dfile.encoding=UTF-8 -classpath /Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/lib/tools.jar:/Users/chenlei/private/designpattern/out/production/designpattern com.chenlei.demo.consistenthash.ConsistentHash
节点个数:10
每个节点虚拟节点个数:100
存入时间差:2947 ms ,标准差:6993
节点个数:10
每个节点虚拟节点个数:1000
存入时间差:1778 ms ,标准差:2731
节点个数:10
每个节点虚拟节点个数:2000
存入时间差:1867 ms ,标准差:1433
节点个数:10
每个节点虚拟节点个数:3000
存入时间差:1819 ms ,标准差:1510
节点个数:10
每个节点虚拟节点个数:5000
存入时间差:1939 ms ,标准差:1281
节点个数:10
每个节点虚拟节点个数:6000
存入时间差:2013 ms ,标准差:917
Process finished with exit code 0

用户头像

尔东雨田

关注

预备用枪! 2017.12.12 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 week05 作业 -- 一致性 Hash 算法