写点什么

架构师训练营 week5

用户头像
devfan
关注
发布于: 2020 年 07 月 08 日

作业一:

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

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

实现

带虚拟节点的具体实现如下

public class ConsistentHash<T> {
//Hash函数
private final HashStrategy hashStrategy;
//虚拟节点倍数
private final int virtualNodeMultiple ;
//有序Map构造Hash环
private final SortedMap<Long, T> circle = new TreeMap<>();
/**
* 有参构造函数
* @param hashStrategy
* @param virtualNodeMultiple
*/
public ConsistentHash(HashStrategy hashStrategy, int virtualNodeMultiple) {
this.hashStrategy = hashStrategy;
this.virtualNodeMultiple = virtualNodeMultiple;
}
/**
* 添加节点
* @param node
*/
public void add(T node) {
for (int i = 0; i < virtualNodeMultiple; i++) {
long key = hashStrategy.getHashCode(node.toString() + "#" + i);
circle.put(key, node);
}
}
/**
* 移除节点
* @param node
*/
public void remove(T node) {
for (int i = 0; i < virtualNodeMultiple; i++) {
long key = hashStrategy.getHashCode(node.toString() + "#" + i);
circle.remove(key);
}
}
/**
* 获取服务器节点
* @param key
* @return
*/
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
long hash = hashStrategy.getHashCode((String) key);
//如果没有对应此hash的服务器节点,获取大于等于此hash后面的服务器节点;
//如果还没有,则获取服务器节点分布圆的第一个节点
if (!circle.containsKey(hash)) {
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
/**
* 求标准差
* @param map
* @return
*/
public static double StandardDiviation(ConcurrentHashMap<String, LongAdder> map) {
int size = map.size();
//求和
long sum = map.values().stream().mapToLong(LongAdder::longValue).sum();
//求平均值
double dAve= sum/size;
double dVar=0;
//求方差
for(Object key:map.keySet()){
long value = map.get(key).longValue();
dVar += (value - dAve) * (value - dAve);
}
return Math.sqrt(dVar/size);
}
/**
* 打印hash环
* @return
*/
public String printCircle() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<Long, T> entry : circle.entrySet()) {
sb.append(entry.getKey()).append("=").append(entry.getValue());
sb.append("&");
}
return sb.toString().substring(0, sb.toString().length() - 1);
}



通过标准差反应一致性Hash的均衡性

采用MD5 hash算法,10台服务器,100个虚拟节点,100w的key来验证一致性Hash算法的均衡性

//使用MD5 hash算法
HashStrategy strategy = new Md5Hash();
//预置10台服务器
String[] nodes = new String[]{"10.21.100.1","10.21.100.2","10.21.100.3","10.21.100.4","10.21.100.5","10.21.100.6","10.21.100.7","10.21.100.8","10.21.100.9","10.21.100.10"};
//预设100个虚拟节点
int virtualNodeMultiple = 100;
ConsistentHash<String> consistentHash = new ConsistentHash<>(strategy, virtualNodeMultiple);
//添加服务到和虚拟节点到Hash环上
for(String node:nodes){
consistentHash.add(node);
}
ConcurrentHashMap<String, LongAdder> map = new ConcurrentHashMap<>();
for (int i=0; i<1000000; i++){
map.computeIfAbsent(consistentHash.get(RandomString.getRandomString()), k -> new LongAdder()).increment();
}
//打印每台服务器分配到的key数量
System.out.println(map.toString());
//打印标准差结果
System.out.println(ConsistentHash.StandardDiviation(map));



输出结果如下:

-----------key分布情况------------
{10.21.100.8=105590, 10.21.100.7=92469, 10.21.100.6=96057, 10.21.100.5=89047, 10.21.100.9=116228, 10.21.100.4=104149, 10.21.100.3=101953, 10.21.100.2=99218, 10.21.100.10=85484, 10.21.100.1=109805}

-----------标准差------------
9029.5056232332



用户头像

devfan

关注

还未添加个人签名 2017.11.12 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 week5