架构师训练营第 5 周作业

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

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

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

一、代码实现

package com.study.architect.homework.week05;
import java.util.*;
/**
* @ClassName ConsistentHashing
* @Description 一致性Hash算法
* @Date 2020/7/8 22:45
* @Version 1.0
**/
public class ConsistentHashing {
// 物理节点
private Set<String> physicalNodes = new TreeSet<String>() {
{
add("192.168.1.101");
add("192.168.1.102");
add("192.168.1.103");
add("192.168.1.104");
add("192.168.1.105");
add("192.168.1.106");
add("192.168.1.107");
add("192.168.1.108");
add("192.168.1.109");
add("192.168.1.110");
}
};
//虚拟节点
private final int VIRTUAL_COPIES = 200; // 物理节点至虚拟节点的复制倍数
private TreeMap<Long, String> virtualNodes = new TreeMap<>(); // 哈希值 => 物理节点
// 32位的 Fowler-Noll-Vo 哈希算法
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
private static Long FNVHash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for (int idx = 0, num = key.length(); idx < num; ++idx) {
hash = (hash ^ key.charAt(idx)) * 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 ConsistentHashing() {
for (String nodeIp : physicalNodes) {
addPhysicalNode(nodeIp);
}
}
// 添加物理节点
public void addPhysicalNode(String nodeIp) {
for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
long hash = FNVHash(nodeIp + "#" + idx);
virtualNodes.put(hash, nodeIp);
}
}
// 删除物理节点
public void removePhysicalNode(String nodeIp) {
for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
long hash = FNVHash(nodeIp + "#" + idx);
virtualNodes.remove(hash);
}
}
// 查找对象映射的节点
public String getObjectNode(String object) {
long hash = FNVHash(object);
SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
return virtualNodes.get(key);
}
// 统计对象与节点的映射关系
public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
// 统计
Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
for (int object = objectMin; object <= objectMax; ++object) {
String nodeIp = getObjectNode(Integer.toString(object));
Integer count = objectNodeMap.get(nodeIp);
objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
}
// 打印
double totalCount = objectMax - objectMin + 1;
System.out.println("======== " + label + " ========");
for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
long percent = (int) (100 * entry.getValue() / totalCount);
System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
}
}
public static void main(String[] args) {
ConsistentHashing ch = new ConsistentHashing();
// 节点情况
System.out.println("==================================================");
ch.dumpObjectNodeMap("节点情况", 0, 65536);
// 添加数据
Map<String, Integer> physicalStatisticsMap = new HashMap<>();
for (String physicalNode : ch.physicalNodes) {
physicalStatisticsMap.put(physicalNode, 0);
}
for (int i = 0; i < 1000000; i++) {
String physicalNode = ch.getObjectNode("测试数据key" + i);
int curr = physicalStatisticsMap.get(physicalNode);
physicalStatisticsMap.put(physicalNode, ++curr);
}
// 计算方差
Integer[] array = (Integer[])physicalStatisticsMap.values().toArray(new Integer[physicalStatisticsMap.values().size()]);
int sum = 0;
for(int i = 0; i < array.length; i++){
sum += array[i]; //求出数组的总和
}
double average = sum/array.length; //求出数组的平均数
int total=0;
for(int i=0;i<array.length;i++){
total += (array[i]-average)*(array[i]-average); //求出方差,如果要计算方差的话这一步就可以了
}
double standardDeviation = Math.sqrt(total/array.length); //求出标准差
// 输出统计
System.out.println("==================================================");
System.out.println("物理节点数据统计:" + physicalStatisticsMap);
System.out.println("标准差:" + standardDeviation);
}

二、输出结果

==================================================

IP=192.168.1.101: RATE=9%

IP=192.168.1.102: RATE=11%

IP=192.168.1.103: RATE=13%

IP=192.168.1.104: RATE=10%

IP=192.168.1.105: RATE=8%

IP=192.168.1.106: RATE=7%

IP=192.168.1.107: RATE=9%

IP=192.168.1.108: RATE=7%

IP=192.168.1.109: RATE=10%

IP=192.168.1.110: RATE=12%

==================================================

物理节点数据统计:{192.168.1.107=87958, 192.168.1.108=76926, 192.168.1.109=108705, 192.168.1.103=136984, 192.168.1.104=102958, 192.168.1.105=80258, 192.168.1.106=74592, 192.168.1.110=121497, 192.168.1.101=91829, 192.168.1.102=118293}

标准差:14654.29507004687



用户头像

养乐多

关注

还未添加个人签名 2019.11.12 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第5周作业