架构师训练营第 05 周—— 练习

用户头像
李伟
关注
发布于: 2020 年 07 月 08 日
架构师训练营第 05周—— 练习

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

import java.util.Arrays;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
/**
* 保存哈希环上的虚拟节点
*/
private final TreeMap<Integer, String> virtualNodes = new TreeMap<>();
/**
* 物理服务器访问量统计
*/
private final TreeMap<String, Integer> visitedServer = new TreeMap<>();
/**
* 每台物理服务器对应的虚拟节点个数
*/
private final int virtualFactor;
/**
* 初始化缓存服务器集群参数
*
* @param virtualFactor
*/
public ConsistentHash(int virtualFactor) {
if (virtualFactor < 1) {
throw new IllegalArgumentException("请输入合法的虚拟节点数量");
}
this.virtualFactor = virtualFactor;
}
/**
* 用于增加服务器
*
* @param serverList:服务器名称
*/
public void addVirtualServerNodes(List<String> serverList) {
for (String server : serverList) {
// 输出参数校验
if (visitedServer.containsKey(server)) {
continue;
}
// 记录物理节点的访问次数
visitedServer.put(server, 0);
//将服务器对应的虚拟节点平均分布在环上
for (int i = 0; i < virtualFactor; i++) {
int finalCode = getFVNHashCode(server + "#" + i);
virtualNodes.put(finalCode, server + "#" + i);
}
}
}
/**
* 模拟请求访问
*
* @param key
* @return
*/
public String request(String key) {
int hashCode = getFVNHashCode(key);
String server = "";
// 查找最近一个大于等于hashCode的虚拟节点
SortedMap<Integer, String> result = virtualNodes.tailMap(hashCode);
if (result == null || (result.isEmpty())) {
server = virtualNodes.get(virtualNodes.firstKey());
} else {
server = result.get(result.firstKey());
}
//将虚拟节点转换为物理节点
server = server.substring(0, server.indexOf("#"));
// 记录访问次数
visitedServer.put(server, visitedServer.get(server) + 1);
return server;
}
/**
* 计算请求分布的标准差
*
* @return
*/
public double calcStd() {
Integer[] visitData = new Integer[visitedServer.size()];
visitedServer.values().toArray(visitData);
// 计算平均值
double avg = Arrays.stream(visitData).mapToInt(value -> value).average().orElse(0);
double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d);
double std = Math.sqrt(avgStd);
return std;
}
/**
* 使用FVN哈希算法计算字符串的哈希值
*
* @param data
* @return
*/
private int getFVNHashCode(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 < 0 ? Math.abs(hash) : hash;
}
}



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



使用多线程测试:

package com.lw;
import java.util.List;
import java.util.UUID;
public class Mission implements Runnable {
private int start;
private int end;
private List<String> servers;
public Mission(int start, int end, List<String> servers) {
this.start = start;
this.end = end;
this.servers = servers;
}
@Override
public void run() {
for (int i = start; i < end; i += 5) {
ConsistentHash consistentHash = new ConsistentHash(i);
consistentHash.addVirtualServerNodes(servers);
long time = System.currentTimeMillis();
for (int j = 0; j < 1000000; j++) {
consistentHash.request(UUID.randomUUID().toString());
}
time = System.currentTimeMillis() - time;
System.out.println(i + "\t" + time + "\t" + (int) consistentHash.calcStd());
}
}
}



public class Test {
public static void main(String[] args) {
// 模拟10台服务器
List<String> servers = List.of("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");
Thread thread1 = new Thread(new Mission(1, 1000, servers));
Thread thread2 = new Thread(new Mission(1001, 2000, servers));
Thread thread3 = new Thread(new Mission(2001, 3000, servers));
Thread thread4 = new Thread(new Mission(3001, 4000, servers));
thread1.start();
thread2.start();
thread3.start();
thread4.start();
}
}



测试结果:



按标准差从小到大,前三名结果如下:

虚拟节点个数 存入时间 标注差

2776 12467 1327

2736 12613 1332

2726 12430 1343



用户头像

李伟

关注

还未添加个人签名 2018.05.07 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 05周—— 练习