写点什么

第五周作业

用户头像
赵龙
关注
发布于: 2020 年 07 月 05 日



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

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



public class ConsistentHash {
// 服务器列表
private List<String> servers = null;
// 服务器虚拟节点
private TreeMap<Integer, String> virtualNodes = new TreeMap<>();
// 服务器访问统计
private TreeMap<String, Integer> serverVisit = new TreeMap<>();
// 虚拟节点个数
private int virtualFactor = 180;
public ConsistentHash(List<String> servers, int virtualFactor) {
this.servers = servers;
this.virtualFactor = virtualFactor;
this.servers.forEach(server -> this.addServer(server));
}
/**
* 获取字符串的hash值
*
* @param str
* @return
*/
public int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
/**
* 添加server节点
*
* @param server
*/
public void addServer(String server) {
if (!serverVisit.containsKey(server)) {
serverVisit.put(server, 0);
for (int i = 0; i < virtualFactor; i++) {
virtualNodes.put(getHash(server + "?VNODE=" + i), server);
}
}
}
/**
* 移除server节点
*
* @param server
*/
public void removeServer(String server) {
if (serverVisit.containsKey(server)) {
serverVisit.remove(server);
for (int i = 0; i < virtualFactor; i++) {
Object o = virtualNodes.remove(getHash(server + "?VNODE=" + i));
}
}
}
/**
* 模拟请求获取服务地址
*
* @param reqKey
* @return
*/
public String request(String reqKey) {
String server = null;
int reqHash = getHash(reqKey);
SortedMap<Integer, String> greaterMap = virtualNodes.tailMap(reqHash, true);
if (greaterMap.isEmpty()) {
// 如果没有比reqHash大的值,则返回第一个虚拟服务器节点
server = virtualNodes.get(virtualNodes.firstKey());
} else {
// greaterMap第一个值就是顺时针下离reqHash最近的虚拟服务器节点
server = greaterMap.get(greaterMap.firstKey());
}
// 记录访问次数
serverVisit.put(server, serverVisit.get(server) + 1);
return server;
}
/**
* 计算请求分布的标准差
*
* @return
*/
public double calcStd() {
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 static void main(String[] args) {
// 模拟请求次数
for (int j = 1; j < 1000; j++) {
int times = 1000000;
List<String> servers = Arrays.asList("192.168.1.1:8080", "192.168.1.2:8080", "192.168.1.3:8080");
ConsistentHash consistentHash = new ConsistentHash(servers, j);
long s = System.currentTimeMillis();
/*for (int i = 0; i < times; i++) {
consistentHash.request(UUID.randomUUID().toString());
}
System.out.println("耗时:" + (System.currentTimeMillis() - s) + " 标准差:"+consistentHash.calcStd());
// 打印模拟请求分布情况
consistentHash.serverVisit.forEach((k, v) -> {
System.out.println(k + " - [ " + v + " - " + times / consistentHash.serverVisit.size() + " = " + (v - times / consistentHash.serverVisit.size()) + " ]");
});
System.out.println("=======================================================");
// 清除模拟请求分布数据
consistentHash.serverVisit.forEach((k, v) -> {
consistentHash.serverVisit.put(k, 0);
});
// 模拟移除一台服务器
consistentHash.removeServer("192.168.1.1:8080");
s = System.currentTimeMillis();
for (int i = 0; i < times; i++) {
consistentHash.request(UUID.randomUUID().toString());
}
System.out.println("耗时:" + (System.currentTimeMillis() - s) + " 标准差:"+consistentHash.calcStd());
consistentHash.serverVisit.forEach((k, v) -> {
System.out.println(k + " - [ " + v + " - " + times / consistentHash.serverVisit.size() + " = " + (v - times / consistentHash.serverVisit.size()) + " ]");
});
System.out.println("=======================================================");
// 清除模拟请求分布数据
consistentHash.serverVisit.forEach((k, v) -> {
consistentHash.serverVisit.put(k, 0);
});
// 模拟添加几台服务器
consistentHash.addServer("192.168.1.1:8080");*/
consistentHash.addServer("192.168.1.4:8080");
consistentHash.addServer("192.168.1.5:8080");
consistentHash.addServer("192.168.1.6:8080");
consistentHash.addServer("192.168.1.7:8080");
consistentHash.addServer("192.168.1.8:8080");
consistentHash.addServer("192.168.1.9:8080");
consistentHash.addServer("192.168.1.10:8080");
s = System.currentTimeMillis();
for (int i = 0; i < times; i++) {
consistentHash.request(UUID.randomUUID().toString());
}
System.out.println(consistentHash.virtualFactor + "\t" + (System.currentTimeMillis() - s) + "\t" + consistentHash.calcStd());
}
}



用户头像

赵龙

关注

还未添加个人签名 2017.12.10 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
可以把结果打印出来,改变虚拟节点的数目看看变化
2020 年 07 月 13 日 21:58
回复
没有更多了
第五周作业