写点什么

架构学习第 5 周作业

用户头像
乐天
关注
发布于: 2020 年 07 月 09 日



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

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

package com.hy;

import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.util.*;
import java.security.MessageDigest;

// key->value server
class Server {
private HashMap<String, String> hmap;
private String serverName;

public Server(String name) {
serverName = name;
hmap = new HashMap<String, String>();
}

public void set(String key, String val) {
hmap.put(key, val);
}

public String get(String key) {
return hmap.get(key);
}

public int size() {
return hmap.size();
}
}

class ConsistentHashService {
// 服务器哈希->服务器
private HashMap<String, Server> serverMap;
// 服务器对应的虚拟节点数量
private int virtualNums = 3;
// 服务器哈希值数组
private ArrayList<String> hashCircle;

private HashSet<Server> servers;

public ConsistentHashService(int replic) {
virtualNums = replic;
hashCircle = new ArrayList<String>();
serverMap = new HashMap<String, Server>();
servers = new HashSet<Server>();
}

private void insertHashCircle(String hash) {
for (int i = 0; i < hashCircle.size(); i++) {
if (hashCircle.get(i).compareTo(hash) > 0 ) {
hashCircle.add(i, hash);
return;
}
}

hashCircle.add(hash);
}

private void removeHashCirCle(String hash) {
int index = hashCircle.indexOf(hash);
if (index >= 0) {
hashCircle.remove(index);
}
}

public void addServer(String serverName) {
Server server = new Server(serverName);
servers.add(server);
for (int i = 0; i < virtualNums; i++) {
String virtualName = serverName + '#' + i;
String hashName = hashKey(virtualName);
insertHashCircle(hashName);
serverMap.put(hashName, server);
}
}

public void removeServer(String serverName) {
String virtualName = serverName + '#' + 1;
String hashName = hashKey(virtualName);
if (serverMap.get(hashName) != null) {
servers.remove(serverMap.get(hashName));
}

for (int i = 0; i < virtualNums; i++) {
virtualName = serverName + '#' + i;
hashName = hashKey(virtualName);
removeHashCirCle(hashName);
serverMap.remove(serverName);
}
}

public void set(String key, String val) {
Server server = getServer(key);
if (server != null) {
server.set(key, val);
}
}

public String get(String key) {
Server server = getServer(key);
if (server != null) {
return server.get(key);
}
return null;
}

private String hashKey(String key) {
byte[] secretBytes = null;
try {
secretBytes = MessageDigest.getInstance("md5").digest(
key.getBytes());
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("没有这个md5算法!");
}
String md5code = new BigInteger(1, secretBytes).toString(16);
for (int i = 0; i < 32 - md5code.length(); i++) {
md5code = "0" + md5code;
}
return md5code;
}

// 根据哈希值查找下一个离的最近的服务器, 采用二分法
private Server getNext(String key) {
if (hashCircle.size() == 0) return null;

String serverhash = hashCircle.get(0);

int low = 0;
int high = hashCircle.size() - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
String midVal = hashCircle.get(mid);
int cmp = midVal.compareTo(key);
if (cmp > 0) {
serverhash = midVal;
high = mid - 1;
} else if (cmp == 0) {
serverhash = midVal;
break;
} else {
low = mid + 1;
}
}

return serverMap.get(serverhash);
}

private Server getServer(String key) {
String hashKey = hashKey(key);
return getNext(hashKey);
}

public Set<Server> getServers() {
return servers;
}

};

public class Main {

private static double variance(long[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dAve = sum / m;// 求平均值
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve)* (x[i] - dAve);
}
return dVar / m;
}

private static double standardDeviation(long[] x) {
double var = variance(x);
return Math.sqrt(var);
}

private static void analyze(Set<Server> servers) {
long[] dataNums = new long[servers.size()];
int i = 0;
for (Server server: servers) {
dataNums[i++] = server.size();
}

double stdVar = standardDeviation(dataNums);
long min = dataNums[0];
long max = 0;
double avg = 0;
long sum = 0;
for (i = 0; i < servers.size(); i++) {
sum += dataNums[i];
if (dataNums[i] < min) min = dataNums[i];
if (dataNums[i] > max) max = dataNums[i];
}
avg = sum / servers.size();


System.out.println(String.format("平均值:%.2f", avg));
System.out.println(String.format("最大值:%d,(%.2f%%)", max, 100.0 * max / avg));
System.out.println(String.format("最小值:%d,(%.2f%%)", min, 100.0 * min / avg));
System.out.println(String.format("标准差:%.2f,(%.2f%%)", stdVar, 100.0 * stdVar));
}

public static void main(String[] args) {
// write your code here
ConsistentHashService service = new ConsistentHashService(150);

for (int i = 1; i <= 10; i++) {
service.addServer("10.0.0." + i);
}

HashMap<String, String> testData = new HashMap<String, String>();
for (int i = 1; i <= 1000000; i++) {
testData.put("key11" + i, "value33" + i);
}

for (Map.Entry<String, String> entry : testData.entrySet()) {
String key = entry.getKey();
String Val = entry.getValue();
service.set(key, Val);
}

for (Map.Entry<String, String> entry : testData.entrySet()) {
String key = entry.getKey();
String Val = entry.getValue();
if (!service.get(key).equals(Val)) {
System.out.printf("key %s valid error\r\n", key);
}
}

analyze(service.getServers());

System.out.println("add one server");
service.addServer("10.0.0.20");
// service.removeServer("10.0.0.1");

int count = 0;
for (Map.Entry<String, String> entry : testData.entrySet()) {
String key = entry.getKey();
String Val = entry.getValue();
String keyVal = service.get(key);
if (keyVal == null) {
count++;
continue;
}

if (!keyVal.equals(Val)) {
System.out.printf("key %s valid error\r\n", key);
}
}
System.out.printf("miss key count %d\r\n", count);
analyze(service.getServers());

System.out.println("all test ok");
}
}




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

乐天

关注

还未添加个人签名 2020.02.02 加入

还未添加个人简介

评论

发布
暂无评论
架构学习第5周作业