架构师训练营 -Week 05 命题作业

用户头像
华乐彬
关注
发布于: 2020 年 07 月 08 日



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

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



类图:

HashFunction接口类:

public interface HashFunction {
Integer hash(Object key);
}

ConsistentHash接口类:

public interface ConsistentHash<T> {
public void addNode(T node);
public Boolean removeNode(T node);
public T getDistribution(Object key);
}

ConsistentHashImpl类

public class ConsistentHashImpl<T> implements ConsistentHash<T> {
private NavigableMap<Integer, T> circle = new TreeMap<>();
private Integer numberOfReplicas;
private HashFunction hashFunction;
public ConsistentHashImpl(Integer numberOfReplicas) {
this(null, numberOfReplicas, null);
}
public ConsistentHashImpl(Collection<T> nodes, Integer numberOfReplicas) {
this(nodes, numberOfReplicas, null);
}
public ConsistentHashImpl(Collection<T> nodes, int numberOfReplicas, HashFunction hashFunction) {
this.numberOfReplicas = numberOfReplicas > 1 ? numberOfReplicas : 1;
if (nodes != null) {
for (T node: nodes) {
addNode(node);
}
}
if (hashFunction == null) {
this.hashFunction = new HashFunction() {
@Override
public Integer hash(Object key) {
return HashUtil.fnvHash(key.toString());
}
};
}
}
@Override
public void addNode(T node) {
if (node == null) {
return;
}
for (int i = 1; i <= numberOfReplicas; i++) {
this.circle.put(hashFunction.hash(node.toString() + i), node);
}
}
@Override
public Boolean removeNode(T node) {
if (node != null) {
for (int i = 1; i <= numberOfReplicas; i++) {
this.circle.remove(hashFunction.hash(node.toString() + i));
}
}
return true;
}
@Override
public T getDistribution(Object key) {
if (key == null) {
throw new NullPointerException("key can not be null.");
}
if (this.circle.isEmpty()) {
return null;
}
Integer hash = hashFunction.hash(key);
SortedMap<Integer, T> tailMap = this.circle.tailMap(hash);
Integer matchNodeHash = tailMap.isEmpty() ? this.circle.firstKey() : tailMap.firstKey();
return this.circle.get(matchNodeHash);
}
public NavigableMap<Integer, T> getCircle() {
return this.circle;
}
}

ServerNode类:

public class ServerNode {
private String ip;
private int port;
private Map<String, Object> cacheData = new HashMap<>();
public ServerNode(String ip, int port) {
this.ip = ip;
this.port = port;
}
@Override
public String toString() {
return new StringBuilder().append(ip).append(":").append(port).toString();
}
public void put(String key, Object value) {
this.cacheData.put(key, value);
}
public Object remove(String key) {
return cacheData.remove(key);
}
public Integer getDataCount() {
return cacheData.size();
}
}



测试:

public class ConsistentHashImplTest {
public static final String[] ips = new String[]{
"192.168.0.10", "192.168.0.11", "192.168.0.12", "192.168.0.13", "192.168.0.14",
"192.168.0.15", "192.168.0.16", "192.168.0.17", "192.168.0.18", "192.168.0.19"
};
public static final int port = 8000;
@Test
public void testFnvHashBalance() {
// 每个服务器节点对应10个虚拟节点
ConsistentHash<ServerNode> consistentHash = new ConsistentHashImpl<>(10);
test(consistentHash);
}
private void test(ConsistentHash<ServerNode> consistentHash) {
List<ServerNode> nodeList = new ArrayList<>(ips.length);
for (String ip : ips) {
ServerNode serverNode = new ServerNode(ip, port);
consistentHash.addNode(serverNode);
nodeList.add(serverNode);
}
// 打印虚拟节点分布
NavigableMap<Integer, ServerNode> circle = ((ConsistentHashImpl<ServerNode>) consistentHash).getCircle();
Iterator<Integer> it = circle.keySet().iterator();
int num = 1;
while(it.hasNext()) {
Integer i = it.next();
System.out.printf("第%s个虚拟节点, 服务器【%s】\n", num++, circle.get(i).toString());
}
// 准备一百万条数据,用一致性分布算法分布在服务器上
for (int i = 0; i < 1000000; i++) {
String key = String.valueOf(i);
String value = RandomUtil.randomString(6);
consistentHash.getDistribution(key).put(key, value);
}
// 打印分布
for (ServerNode serverNode : nodeList) {
System.out.printf("服务器【%s】节点存储(%s)条数据\n", serverNode.toString(), serverNode.getDataCount());
}
// 标准差计算
int total = nodeList.stream().mapToInt(ServerNode::getDataCount).sum();
double avg = total * 1.0 / nodeList.size();
double sum = nodeList.stream().mapToDouble(node -> Math.pow((node.getDataCount() * 1.0) - avg, 2)).sum();
double standardDeviation = Math.sqrt(sum / nodeList.size());
System.out.printf("标准差:%s", String.valueOf(standardDeviation));
}
/*
结果:
哈希算法:FnvHash
虚拟节点数:100
每个服务器节点对应10个虚拟节点
服务器【192.168.0.10:8000】节点存储(79204)条数据
服务器【192.168.0.11:8000】节点存储(77773)条数据
服务器【192.168.0.12:8000】节点存储(151707)条数据
服务器【192.168.0.13:8000】节点存储(128070)条数据
服务器【192.168.0.14:8000】节点存储(73088)条数据
服务器【192.168.0.15:8000】节点存储(99577)条数据
服务器【192.168.0.16:8000】节点存储(120744)条数据
服务器【192.168.0.17:8000】节点存储(94620)条数据
服务器【192.168.0.18:8000】节点存储(86496)条数据
服务器【192.168.0.19:8000】节点存储(88721)条数据
标准差:24251.429566110117
*/



用户头像

华乐彬

关注

还未添加个人签名 2019.03.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 -Week 05 命题作业