写点什么

第五周 - 作业

用户头像
leo
关注
发布于: 2020 年 11 月 21 日
第五周 - 作业



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

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



package com.leo.homework;
import cn.hutool.core.util.HashUtil;
import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class ConsistentHashingWithoutVirtualNode {
private static final String[] servers = {
"192.168.0.0",
"192.168.0.1",
"192.168.0.2",
"192.168.0.3",
"192.168.0.4",
"192.168.0.5",
"192.168.0.6",
"192.168.0.7",
"192.168.0.8",
"192.168.0.9",
"192.168.0.10"
};
private static final List<String> realNodes = new LinkedList<>();
private static final Map<String, Integer> numOfNodes = new HashMap<>(servers.length);
private static final SortedMap<Integer, String> virtualNodes = new TreeMap<>();
private static final int VIRTUAL_NODES = 5;
static {
Collections.addAll(realNodes, servers);
for (String str : realNodes) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
String virtualNodeName = str + "&&VN" + i;
int hash = HashUtil.fnvHash(virtualNodeName);
virtualNodes.put(hash, virtualNodeName);
}
}
}
public static void main(String[] args) {
List<String> testKey = getTestKey(1000000);
for (String key : testKey) {
String server = getServer(HashUtil.fnvHash(key));
numOfNodes.put(server, numOfNodes.getOrDefault(server, 0) + 1);
}
Collection<Integer> values = numOfNodes.values();
if (CollectionUtils.isEmpty(values)) return;
double avg = values.stream().mapToInt(Integer::intValue).average().orElse(0);
int total = values.stream().mapToInt(value -> (int) ((value - avg) * (value - avg))).sum();
System.out.println("数据在服务器上分布数量的标准差: " + Math.sqrt(total * 1.0 / values.size()));
}
private static String getServer(int hashKey) {
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hashKey);
String virtualNode =
subMap.isEmpty()
? virtualNodes.get(virtualNodes.firstKey())
: subMap.get(subMap.firstKey());
return StringUtils.hasText(virtualNode)
? virtualNode.substring(0, virtualNode.indexOf("&&"))
: null;
}
private static List<String> getTestKey(int num) {
return IntStream.range(0, num)
.mapToObj(i -> UUID.randomUUID().toString())
.collect(Collectors.toList());
}
}

10个服务器,100万个数据,数据在服务器上分布的数据标准差范围大致8800-9000

发布于: 2020 年 11 月 21 日阅读数: 18
用户头像

leo

关注

还未添加个人签名 2018.03.23 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
不同的虚拟节点数影响很大,可以做一做尝试
2020 年 11 月 29 日 11:39
回复
没有更多了
第五周 - 作业