架构师训练营第五章作业

发布于: 2020 年 07 月 07 日

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

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

基于虚拟节点的一致性Hash算法

  • 服务器字符串的hash值放到环上,节点变成虚拟节点;

  • 一个服务分成多个虚拟节点均匀的分布在环上面;

  • 根据算出来的hash值顺时针查找获取最近的虚拟节点;

  • 影响范围是基本所有虚拟节点都会受到影响,但是影响的数据量相对较少;

Hash代码实现

一致性Hash实现

public class HashNodeHandler {
private List<String> nodes;
private TreeMap<Integer, String> virtualNodes = new TreeMap<>();
private TreeMap<String, Integer> serverVisit = new TreeMap<>();
private int nodeNum;
public HashNodeHandler(List<String> nodes,Integer nodeNum){
this.nodes = nodes;
this.nodeNum = nodeNum;
}
public void calculation(){
nodes.forEach(s -> {
serverVisit.put(s, 0);
for (int i = 0; i < nodeNum; i++) {
virtualNodes.put(hash(s + "NODE=" + i), s);
}
});
}
public void put(Object object){
int hash = hash(object);
SortedMap<Integer, String> integerStringSortedMap = virtualNodes.tailMap(hash);
String server = "";
if (integerStringSortedMap.isEmpty()) {
// 如果没有比reqHash大的值,则返回第一个虚拟服务器节点
server = virtualNodes.get(virtualNodes.firstKey());
} else {
// greaterMap第一个值就是顺时针下离reqHash最近的虚拟服务器节点
server = integerStringSortedMap.get(integerStringSortedMap.firstKey());
}
serverVisit.put(server, serverVisit.get(server) + 1);
}
private int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public double calculationStandard() {
Integer[] visitData = new Integer[serverVisit.size()];
serverVisit.values().toArray(visitData);
double avg = Arrays.stream(visitData).mapToInt(Integer::intValue).average().orElse(0d);
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 TreeMap<String, Integer> getServerVisit() {
return serverVisit;
}
}

测试类

public class HashTest {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("192.168.0.1");
list.add("192.168.0.2");
list.add("192.168.0.3");
list.add("192.168.0.4");
list.add("192.168.0.5");
list.add("192.168.0.6");
list.add("192.168.0.7");
list.add("192.168.0.8");
list.add("192.168.0.9");
list.add("192.168.0.10");
int num = 2000;
HashNodeHandler hashNodeHandler = new HashNodeHandler(list, num);
hashNodeHandler.calculation();
test1000000(hashNodeHandler);
}
private static void test1000000(HashNodeHandler hashNodeHandler) {
int num = 1000000;
loop(hashNodeHandler,num);
}
private static void loop(HashNodeHandler hashNodeHandler,int num) {
for (int i = 0; i < num; i++) {
hashNodeHandler.put(i+"nodeDa");
}
System.out.println(hashNodeHandler.getServerVisit());
System.out.println(hashNodeHandler.calculationStandard());
}
}

验证结果

服务器数量:10
虚拟节点数量:2000
测试数据量:1000000
服务器分配情况:{192.168.0.1=185375, 192.168.0.10=88721, 192.168.0.2=136291, 192.168.0.3=67317, 192.168.0.4=141577, 192.168.0.5=84482, 192.168.0.6=75216, 192.168.0.7=83256, 192.168.0.8=69623, 192.168.0.9=68142}
标准差:38213.9756816796
服务器数量:11
虚拟节点数量:2200
测试数据量:1000000
服务器分配情况:{192.168.0.1=185375, 192.168.0.10=88721, 192.168.0.11=30946, 192.168.0.2=136291, 192.168.0.3=66028, 192.168.0.4=141577, 192.168.0.5=81289, 192.168.0.6=75216, 192.168.0.7=56792, 192.168.0.8=69623, 192.168.0.9=68142}
标准差:42899.69760532234
服务器数量:8
虚拟节点数量:1600
测试数据量:1000000
服务器分配情况:{192.168.0.1=185375, 192.168.0.2=197838, 192.168.0.3=123376, 192.168.0.4=141577, 192.168.0.5=84482, 192.168.0.6=108407, 192.168.0.7=83256, 192.168.0.8=75689}
标准差:43759.45812621541

发布于: 2020 年 07 月 07 日 阅读数: 8
用户头像

叮叮董董

关注

还未添加个人签名 2020.04.08 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五章作业