【架构师训练营】第五周作业

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



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



package com.houzh.hash;
import com.google.common.collect.Lists;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @Author: houzh
* @Date: 2020/7/8 9:59 上午
*/
public class ConsistentHashVirtualNode {
private static String[] servers = {"192.168.0.1:8080", "192.168.0.2:8080", "192.168.0.3:8080",
"192.168.0.4:8080", "192.168.0.5:8080", "192.168.0.6:8080", "192.168.0.7:8080", "192.168.0.8:8080", "192.168.0.9:8080", "192.168.0.10:8080"};
private static LinkedList<String> realNodes = Lists.newLinkedList();
private static SortedMap<Long, String> virtualNodes = new TreeMap<>();
public static final int VIRTUAL_NODE = 200;
public static String[] keys = new String[1000000];
static {
for (int i = 0; i < 1000000; i++) {
keys[i] = String.valueOf(i);
}
for (int i = 0; i < servers.length; i++) {
realNodes.add(servers[i]);
}
for (String realNode : realNodes) {
for (int i = 0; i < VIRTUAL_NODE; i++) {
String virtualNodeName = realNode + "&NO=" + i;
long hash = getHash(virtualNodeName);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static String getServer(String key) {
long hash = getHash(key);
SortedMap<Long, String> subMap = virtualNodes.tailMap(hash);
String virtualNode;
if (subMap.isEmpty()) {
Long aLong = virtualNodes.firstKey();
virtualNode = virtualNodes.get(aLong);
} else {
Long aLong = subMap.firstKey();
virtualNode = subMap.get(aLong);
}
return virtualNode.substring(0, virtualNode.indexOf("&"));
}
private static long getHash(String value) {
byte[] bytes = md5(value);
return hash(bytes, 0);
}
private static long hash(byte[] digest, int number) {
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[0 + number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
private static byte[] md5(String value) {
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.reset();
byte[] bytes;
try {
bytes = value.getBytes("UTF-8");
} catch (UnsupportedEncodingException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.update(bytes);
return md5.digest();
}
public static void main(String[] args) {
SortedMap<String, AtomicInteger> map = new TreeMap<>();
for (int i = 0; i < keys.length; i++) {
String server = getServer(keys[i]);
map.putIfAbsent(server, new AtomicInteger(0));
map.get(server).incrementAndGet();
}
Iterator<Map.Entry<String, AtomicInteger>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<String, AtomicInteger> entry = entries.next();
System.out.println(entry.getKey() + ":" + entry.getValue());
}
}
}

测试结果



用户头像

Mr.hou

关注

还未添加个人签名 2018.09.22 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
建议按习题要求计算一下标准差,比曲线会更直观一些
2020 年 07 月 13 日 17:57
回复
没有更多了
【架构师训练营】第五周作业