Week05 作业

发布于: 2020 年 07 月 07 日

作业一:

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

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

带虚节点的一致性Hash算法的实现(Java):

@Data
public class Node {
/**
* 服务器节点IP
*/
private String ip;
/**
* 服务器节点名称
*/
private String name;
}
public class ConsistentHashWithVirtualNode {
private final static Integer P = 16777619;
private SortedMap<Integer, Node> circleMap;
private Integer num;
public ConsistentHashWithVirtualNode(int num, List<Node> nodes) {
this.circleMap = new TreeMap<>();
this.num = num;
for (Node node : nodes) {
add(node);
}
}
/**
* add 服务器节点
*
* @param node
*/
public void add(Node node) {
for (int i = 0; i < this.num; i++) {
circleMap.put(this.getHash(node.getIp() + i), node);
}
}
/**
* del 服务器节点
*
* @param node
*/
public void remove(Node node) {
for (int i = 0; i < this.num; i++) {
circleMap.remove(this.getHash(node.getIp() + i));
}
}
/**
* get 服务器节点
*
* @param key
* @return
*/
public Node get(String key) {
if (!circleMap.isEmpty()) {
Integer hash = getHash(key);
if (!circleMap.containsKey(hash)) {
SortedMap<Integer, Node> tailMap = circleMap.tailMap(hash);
hash = tailMap.isEmpty() ? circleMap.firstKey() : tailMap.firstKey();
}
return circleMap.get(hash);
}
return null;
}
/**
* 获取hash值
* @param str
* @return
*/
public Integer getHash(String str) {
Integer hash = P;
for (int i = 0; i < str.length(); i++) {
hash = (hash ^ str.charAt(i)) * P;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
}
public class ConsistentHashWithVirtualNodeTest {
private final static String IP_PRE_FIX = "192.168.1.";
private final static int SERVER_COUNT = 10;
private final static int COUNT = 1000000;
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
List<Node> realNodes = new ArrayList<>();
for (int i = 1; i <= SERVER_COUNT; i++) {
map.put(IP_PRE_FIX + String.valueOf(i), 0);
Node node = new Node(IP_PRE_FIX + String.valueOf(i), "node" + i);
realNodes.add(node);
}
ConsistentHashWithVirtualNode consistentHash = new ConsistentHashWithVirtualNode(100, realNodes);
List<Integer> list = new ArrayList<>();
for (int i = 0; i < COUNT; i++) {
String data = UUID.randomUUID().toString() + i;
Node node = consistentHash.get(data);
map.put(node.getIp(), map.get(node.getIp()) + 1);
list.add(map.get(node.getIp()));
}
for (int i = 1; i <= COUNT; i++) {
System.out.println(String.format("%s 节点记录条数:%s", IP_PRE_FIX + String.valueOf(i), map.get(IP_PRE_FIX + i)));
}
System.out.println(String.format("方差:%d", calcStdDeviation(list.toArray(new Integer[list.size()]))));
}
public static double calcStdDeviation(Integer[] list) {
double sum = 0;
int count = list.length;
for (int i = 0; i < count; i++) {
sum += list[i];
}
double avg = sum / count;
double variance = 0;
for (int i = 0; i < count; i++) {
variance += (list[i] - avg) * (list[i] - avg);
}
return Math.sqrt(variance / count);
}
}

用户头像

关注

还未添加个人签名 2018.04.17 加入

还未添加个人简介

评论

发布
暂无评论
Week05 作业