第 5 周 - 课后作业

发布于: 2020 年 07 月 07 日

作业一

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

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

import java.util.*;
public class Consistenthashing {
SortedMap<Integer, String> sortedCircle = new TreeMap<>();
int virtualNums = 200;
/**
* 初始化虚拟节点
*/
private void init(List<String> nodes) {
//服务器节点对应放大虚拟节点
Map<String, String> virtualNodes = new HashMap<>();
for (String node : nodes) {
for (int i = 0; i < virtualNums; i++) {
virtualNodes.put(node + "_" + i, node);
}
}
for (String key : virtualNodes.keySet()) {
sortedCircle.put(hash(key), virtualNodes.get(key));
}
}
/**
* 增加节点
* @param node
*/
private void addNode(String node) {
//服务器节点对应放大虚拟节点
Map<String, String> virtualNodes = new HashMap<>();
for (int i = 0; i < virtualNums; i++) {
virtualNodes.put(node + "-" + i, node);
}
for (String key : virtualNodes.keySet()) {
sortedCircle.put(hash(key), virtualNodes.get(key));
}
}
/**
* 找到离该key的hash值最新的一个节点
* 找不到取第一个节点
*
* @param key
* @return
*/
private String findNodeByHash(String key) {
int hash = hash(key);
SortedMap<Integer, String> subMap = sortedCircle.tailMap(hash);
return subMap.isEmpty()
? sortedCircle.get(sortedCircle.firstKey())
: subMap.get(subMap.firstKey());
}
/**
* hash值计算
* 32位FNV算法1
*
* @param data
* @return
*/
private static int hash(String data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
/**
* 计算缓存key在节点上的分布和标准差
*
* @param keyValus
*/
private void compute(Map<String, Object> keyValus) {
//每个节点分配的缓存key个数
Map<String, Integer> result = new HashMap<>();
for (String key : keyValus.keySet()) {
String nodeName = findNodeByHash(key);
if (result.get(nodeName) == null) {
result.put(nodeName, 1);
} else {
Integer value = result.get(nodeName);
result.put(nodeName, value + 1);
}
}
System.out.println(result);
System.out.println("标准差:" + stdDev(result, keyValus.size()));
}
/**
* 标准差计算
*
* @param map
* @param totalNums
* @return
*/
private double stdDev(Map<String, Integer> map, long totalNums) {
int n = map.size();
long avgNums = totalNums / map.size();
double sum = 0;
for (String key : map.keySet()) {
int value = map.get(key);
sum += (value - avgNums) * (value - avgNums);
}
return Math.sqrt(sum / n);
}
public static void main(String[] args) {
//服务器节点
List<String> nodes = Arrays.asList("node1", "node2", "node3", "node4", "node5", "node6", "node7", "node8", "node9", "node10",
"node11", "node12", "node13", "node14", "node15", "node16", "node17", "node18", "node19", "node20");
Consistenthashing consistentHashing = new Consistenthashing();
//初始化,默认虚拟节点为200
consistentHashing.init(nodes);
//需要环节的1000000个key
Map<String, Object> keyValues = new HashMap<>();
for (int i = 1; i <= 1000000; i++) {
keyValues.put("key" + i, "value" + i);
}
//输出缓存key在节点上的分布及标准差
consistentHashing.compute(keyValues);
//添加一个新节点
consistentHashing.addNode("node21");
consistentHashing.compute(keyValues);
}
}

程序输出:

{node20=42825, node10=52494, node11=51401, node12=54091, node13=54539, node14=51651, node15=54459, node16=52487, node17=51907, node18=47184, node19=53771, node1=48548, node4=51045, node5=45303, node2=46926, node3=51240, node8=42128, node9=45328, node6=51122, node7=51551}
标准差:3710.070942717942
{node20=41892, node10=49631, node21=45044, node11=47066, node12=52725, node13=53924, node14=49364, node15=52447, node16=49162, node17=49999, node18=45104, node19=51028, node1=45817, node4=48242, node5=41779, node2=45765, node3=49517, node8=40914, node9=43564, node6=49788, node7=47228}
标准差:3605.4976342352784

用户头像

大海

关注

还未添加个人签名 2018.07.14 加入

还未添加个人简介

评论

发布
暂无评论
第 5 周 - 课后作业