写点什么

第五周 技术选型 作业一

用户头像
应鹏
关注
发布于: 2020 年 10 月 25 日
第五周 技术选型 作业一



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

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



主要算法实现:

import java.util.SortedMap;
import java.util.TreeMap;
/**
* 基于虚拟节点的一致性hash
*
* @author yingp
*/
public class ConsistentHash {
/**
* 真实节点
*/
private final String[] nodes;
/**
* 一个真实节点对应150个虚拟节点
*/
private final static int VIRTUAL_NODE_SIZE = 150;
/**
* 虚拟节点到真实节点的映射,key表示虚拟节点的hash值,value表示真实节点的索引位置
*/
private SortedMap<Integer, Integer> virtualNodeMap;
public ConsistentHash(String[] nodes) {
this.nodes = nodes;
this.virtualNodeMap = new TreeMap<>();
int i = 0;
for (String node : nodes) {
for (int j = 0; j < VIRTUAL_NODE_SIZE; j++) {
String virtualNodeName = String.format("%s->%s", node, j);
virtualNodeMap.put(hashCode(virtualNodeName), i);
}
i++;
}
}
/**
* FNV1_32_HASH算法
*
* @param str
* @return
*/
private static int hashCode(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
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;
}
/**
* 根据key值拿到节点
*
* @param key
* @return
*/
public String getNode(String key) {
// 得到大于该hash值的所有Map
SortedMap<Integer, Integer> subMap = virtualNodeMap.tailMap(hashCode(key));
Integer nodeIndex = 0;
if (!subMap.isEmpty()) {
// 顺时针选择最近的虚拟结点
nodeIndex = subMap.get(subMap.firstKey());
}
return nodes[nodeIndex];
}
}



测试:

import java.util.HashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
// 测试10个服务器节点
final String[] nodes = new String[]{"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"};
final ConsistentHash hash = new ConsistentHash(nodes);
// 计数器,统计每个节点的命中次数
HashMap<String, AtomicInteger> counter = new HashMap<>(nodes.length);
for (String node : nodes) {
counter.put(node, new AtomicInteger());
}
// 100万次测试
IntStream.range(0, 1000000).mapToObj(String::valueOf).parallel().forEach(i -> {
// 以i为key值,返回命中的节点
String node = hash.getNode(i);
counter.get(node).incrementAndGet();
});
counter.forEach((node, count) -> {
System.out.println(node + "次数:" + count);
});
// 计算标准差
Integer[] counterArr = counter.values().stream().map(AtomicInteger::get).collect(Collectors.toList())
.toArray(new Integer[counter.size()]);
System.out.println("标准差:" + getStandardDeviation(counterArr));
}
/**
* 计算标准差
*
* @param arr
*/
private static double getStandardDeviation(Integer[] arr) {
int len = arr.length;
double sum = 0;
for (int i = 0; i < len; i++) {
sum += arr[i];
}
double avg = sum / len;
double var = 0;
for (int i = 0; i < len; i++) {
var += (arr[i] - avg) * (arr[i] - avg);
}
return Math.sqrt(var / len);
}
}



测试结果:

192.168.0.2次数:99704
192.168.0.1次数:99212
192.168.0.4次数:112385
192.168.0.3次数:108530
192.168.0.10次数:95650
192.168.0.9次数:93799
192.168.0.6次数:106480
192.168.0.5次数:101454
192.168.0.8次数:94226
192.168.0.7次数:88560
标准差:7018.189068413589



发布于: 2020 年 10 月 25 日阅读数: 77
用户头像

应鹏

关注

还未添加个人签名 2020.08.25 加入

还未添加个人简介

评论

发布
暂无评论
第五周 技术选型 作业一