第五周作业

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



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

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



源码

ConsistentHashing.java

哈希环的实现,使用实现红黑树的TreeMap保存虚拟节点

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class ConsistentHashing {
/**
* 服务器信息集合,key:服务器hash值,value:服务信息(简单用字符串代替)
*/
private Map<Integer, String> serverMap = new HashMap<>();
/**
* hash环,存储了环上所有虚拟节点,key:虚拟节点hash值,value:服务器hash值
*/
private TreeMap<Integer, Integer> hashRing = new TreeMap<>();
/**
* 每个服务对应虚拟节点数
*/
private int nodeCount;
public ConsistentHashing(int nodeCount) {
if (nodeCount <= 0) {
//至少有服务本身节点
this.nodeCount = 1;
return;
}
this.nodeCount = nodeCount;
}
/**
* 增加服务
*
* @param serverId 服务标识
*/
public void appendServer(String serverId) {
int serverHash = HashCode.get(serverId);
if (!serverMap.containsKey(serverHash)) {
serverMap.put(serverHash, serverId);
//添加虚拟节点
for (int i = 0; i < nodeCount; i++) {
hashRing.put(HashCode.get(serverId + ":VIR" + i), serverHash);
}
}
}
/**
* 移除服务
*
* @param serverId 服务标识
*/
public void removeServer(String serverId) {
for (int i = 0; i < nodeCount; i++) {
hashRing.remove(HashCode.get(serverId + ":VIR" + i));
}
}
/**
* 获取服务信息
*
* @param requestKey 请求标识
* @return 服务信息
*/
public String getServer(String requestKey) {
if (serverMap.isEmpty()) {
return null;
}
Map.Entry<Integer, Integer> targetNode = hashRing.ceilingEntry(HashCode.get(requestKey));
if (targetNode == null) {
targetNode = hashRing.firstEntry();
}
return serverMap.get(targetNode.getValue());
}
}



HashCode.java

用于获取hash值,采用FNV算法

public class HashCode {
public static int get(String data){
return FNVHash1(data);
}
private static int FNVHash1(String data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(int i=0;i<data.length();i++) {
hash = (hash ^ data.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
}

StandardDeviation.java

标准差计算类

import java.util.Collection;
public class StandardDeviation {
public static double math(Collection<Integer> datas){
//求出数组的总和
double average = datas.stream().mapToInt(Integer::intValue).average().getAsDouble();
//求出方差
double var = datas.stream().map(d->(d-average)*(d-average)).mapToDouble(Double::doubleValue).sum();
//求出标准差
return Math.sqrt(var/datas.size());
}
}

统计结果

可以看到,在虚拟节点在600左右达到最好的效果

用户头像

CP

关注

还未添加个人签名 2018.03.15 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业