架构师训练营 - 第五周 - 命题作业

发布于: 2020 年 07 月 08 日
架构师训练营-第五周-命题作业

作业

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

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

import com.google.common.base.Charsets;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
public class ConsistentHashDemo {
private static final int size = 1024;
/**
* 每个物理节点分配的虚拟节点个数
*/
private int virtualFactor = 50;
/**
* 用于存储物理节点
*/
List<String> nodes;
/**
* 虚拟节点信息
*/
List<String> virtualNodes;
HashFunction murmur3_32 = Hashing.murmur3_32();
/**
* 记录每台物理服务器请求数量
*/
Map<String, AtomicInteger> requestMap = new ConcurrentHashMap<>();
public ConsistentHashDemo(List<String> nodes, int virtualFactor) {
virtualNodes = Arrays.asList(new String[size]);
this.nodes = new ArrayList<>(10);
//this.nodes = new ArrayList<>(nodes);
for (String node : nodes) {
this.addNode(node);
}
this.virtualFactor = virtualFactor;
}
/**
* 添加物理节点到虚拟环上
*
* @param server 物理节点信息
*/
public void addNode(String server) {
boolean isNew = false;
// 判断物理节点是否是新添加的
if (!nodes.contains(server)) {
isNew = true;
nodes.add(server);
}
if (isNew) {
// 添加虚拟节点
for (int i = 0; i < virtualFactor; i++) {
virtualNodes.set(hash(server + "_" + i), server);
}
}
}
public void removeNode(String server) {
boolean isExists = false;
if (nodes.contains(server)) {
isExists = true;
}
if (isExists) {
// 删除虚拟节点
for (int i = 0; i < virtualFactor; i++) {
virtualNodes.set(hash(server + "_" + i), null);
}
}
}
public String requestHandler(String request) {
String ret;
int index = hash(request);
int i = index + 1;
i = i < size ? i : 0;
for (; i < size; i++) {
if (virtualNodes.get(i) != null || i == index) {
break;
}
if (i == size - 1) {
i = 0;
}
}
ret = virtualNodes.get(i);
AtomicInteger count = requestMap.get(ret);
if (count == null) {
count = new AtomicInteger(0);
requestMap.put(ret, count);
}
count.getAndIncrement();
return ret;
}
public int hash(String str) {
return murmur3_32.newHasher().putString(str, Charsets.UTF_8).hash().asInt() & Integer.MAX_VALUE % size;
}
public int getVirtualFactor() {
return virtualFactor;
}
public double computeStd() {
requestMap.keySet();
Collection<AtomicInteger> values = requestMap.values();
double avg = values.
stream().
mapToInt(AtomicInteger::intValue).
average().
orElse(0d);
double avgStd = values.
stream().
map(count -> Math.pow(count.intValue() - avg, 2)).
mapToDouble(Double::doubleValue).
average().
orElse(0d);
double std = Math.sqrt(avgStd);
return std;
}
public static void main(String[] args) {
List<String> nodes = Arrays.asList("192.168.80.1:9091",
"192.168.80.2:9091",
"192.168.80.3:9091",
"192.168.80.4:9091",
"192.168.80.5:9091");
for (int i = 0; i < 1000; i++) {
ConsistentHashDemo demo = new ConsistentHashDemo(nodes, i);
int count = 1000000;
long startTime = System.currentTimeMillis();
demo.addNode("192.168.80.6:9091");
demo.addNode("192.168.80.7:9091");
demo.addNode("192.168.80.8:9091");
demo.addNode("192.168.80.9:9091");
demo.addNode("192.168.80.10:9091");
for (int j = 0; j < count; j++) {
demo.requestHandler(UUID.randomUUID().toString());
}
System.out.println(demo.getVirtualFactor() + "\t" +
(System.currentTimeMillis() - startTime) + "\t" +
demo.computeStd()
);
}
}
}

使用 Murmur Hash算法,当环的空间为1024时,随着每个节点分配的虚拟节点个数越多,均方差在10w左右波动

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

sljoai

关注

还未添加个人签名 2017.11.09 加入

还未添加个人简介

评论

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