week05 作业

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

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

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



一致性hash通常用于解决负载均衡问题,在分布式cache场景下,使用一致性hash还可以很好的实现单调性。



一致性hash目标命中的标准差与实际应用场景及hash算法/数据特征有较强相关性,可定制性优化。在此暂不做分布测试。

public class Hash {
private static final int MAX_HASH = Integer.MAX_VALUE;
private static final int VIRTUAL_SIZE = 100;
private static final long VIRTUAL_NODE_DISTANCE = MAX_HASH / VIRTUAL_SIZE;
private SortedMap<Integer, Node> map = new TreeMap<>();
public void addNode(Node node) {
int code = node.hashCode();
for (int i = 0; i < VIRTUAL_SIZE; i++) {
map.put((int)(code + i * VIRTUAL_NODE_DISTANCE) % MAX_HASH, node);
}
}
public Node get(String key) {
Integer code = key.hashCode();
SortedMap<Integer, Node> tailMap = map.tailMap(code);
if (tailMap.isEmpty()) {
return map.get(map.firstKey());
}
return map.get(tailMap.firstKey());
}
static class Node {
private String name;
public Node(String name) {
this.name = name;
}
}
public static void main(String[] args) {
Hash hash = new Hash();
for (int i = 0; i < 10; i++) {
Node node = new Node(String.valueOf(i));
hash.addNode(node);
}
}
}



用户头像

Safufu

关注

还未添加个人签名 2018.11.16 加入

还未添加个人简介

评论

发布
暂无评论
week05 作业