写点什么

架构师训练营第五周作业

用户头像
Shunyi
关注
发布于: 2020 年 10 月 25 日

作业一(2 选 1):

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

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

import java.util.TreeMap;
import java.util.Map;
import java.util.Random;
import java.lang.Math;
public class ConsistentHash {
private int virtual_node_count = 150;
private TreeMap<Integer, String> hash_ring = new TreeMap<Integer, String>();
private TreeMap<String, Integer> server_hit_map = new TreeMap<String, Integer>();
public ConsistentHash() {
}
public ConsistentHash(int virtualNodCount) {
if (virtualNodCount > 0) {
virtual_node_count = virtualNodCount;
}
}
public void addServerNode(String server_node_ip) {
//invalid
if (server_node_ip == null || server_node_ip.isEmpty()){
return;
}
//already in the map
if (server_hit_map.containsKey(server_node_ip)) {
return;
}
Random rom = new Random(1);
int nCurrentSize = hash_ring.size();
int nNewSize = nCurrentSize + virtual_node_count;
while (hash_ring.size() < nNewSize) {
int value = rom.nextInt();
if (!hash_ring.containsKey(value)) {
hash_ring.put(value, server_node_ip);
}
}
}
public String queryServerNodeByKey(String key) {
if (key == null || hash_ring.isEmpty()) {
return null;
}
Map.Entry<Integer, String> entry = hash_ring.ceilingEntry(key.hashCode());
if (entry == null) {
entry = hash_ring.firstEntry();
}
String server = entry.getValue();
if (server_hit_map.containsKey(server)) {
Integer value = server_hit_map.get(server);
server_hit_map.put(server, value+1);
}
else {
server_hit_map.put(server, 1);
}
return server;
}
public void outPutStatistics() {
int totalQuery = 0;
double standardDeviation = 0.0;
double variance = 0;
for (Map.Entry<String, Integer> entry : server_hit_map.entrySet() ) {
totalQuery += entry.getValue();
}
double average = 1.0/(double)server_hit_map.size();
System.out.println("Total " + totalQuery + " queries.");
for (Map.Entry<String, Integer> entry : server_hit_map.entrySet() ) {
System.out.println("Server " + entry.getKey() + " hit: " + entry.getValue() + "; percentage: " + 100 * entry.getValue()/(double)totalQuery + "%");
double dif = entry.getValue()/(double)totalQuery - average;
variance += dif * dif;
}
variance = variance / server_hit_map.size();
standardDeviation = Math.sqrt(variance);
System.out.println("Standard deviation of probability distribution is: " + standardDeviation);
}
public static void main(String[] args) {
ConsistentHash ch = new ConsistentHash(200);
//add 10 sever node.
ch.addServerNode("192.168.1.1");
ch.addServerNode("192.168.1.12");
ch.addServerNode("192.168.1.23");
ch.addServerNode("192.168.1.44");
ch.addServerNode("192.168.1.25");
ch.addServerNode("192.168.1.76");
ch.addServerNode("192.168.1.27");
ch.addServerNode("192.168.1.98");
ch.addServerNode("192.168.1.49");
ch.addServerNode("192.168.1.20");
int caseSize = 1000000;
Random rom = new Random(1);
for(int i = 0; i < caseSize; ++i) {
String c = new String("case_value_" + rom.nextInt());
ch.queryServerNodeByKey(c);
}
ch.outPutStatistics();
}
}
OutPut:
Total 1000000 queries.
Server 192.168.1.1 hit: 103978; percentage: 10.3978%
Server 192.168.1.12 hit: 112146; percentage: 11.2146%
Server 192.168.1.20 hit: 106206; percentage: 10.6206%
Server 192.168.1.23 hit: 101144; percentage: 10.1144%
Server 192.168.1.25 hit: 100779; percentage: 10.0779%
Server 192.168.1.27 hit: 89479; percentage: 8.9479%
Server 192.168.1.44 hit: 96215; percentage: 9.6215%
Server 192.168.1.49 hit: 101727; percentage: 10.1727%
Server 192.168.1.76 hit: 85643; percentage: 8.5643%
Server 192.168.1.98 hit: 102683; percentage: 10.2683%
Standard deviation of probability distribution is: 0.0073831019632672



作业二:根据当周学习情况,完成一篇学习总结



用户头像

Shunyi

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论

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