写点什么

【架构师训练营第 1 期 05 周】 作业

用户头像
Bear在挨踢
关注
发布于: 2020 年 10 月 25 日

【架构师训练营第 1 期 05 周】 作业



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

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



根据老师讲解的思路进行开发



服务器


import java.util.concurrent.atomic.AtomicInteger;

public class Node {
private String serverName;
private String ip;
private AtomicInteger count = new AtomicInteger(0);

public Node(String serverName, String ip) {
this.serverName = serverName;
this.ip = ip;
}

public void increase() {
count.incrementAndGet();
}

public String getServerAndIncrease() {
increase();
return getServerName();
}

public String getServerName() {
return serverName;
}

public Integer getCount() {
return count.get();
}

public String getIp() {
return ip;
}

public void setIp(String ip) {
this.ip = ip;
}

@Override
public String toString() {
return "serverName:" + serverName +
", \t ip:" + ip +
", \t count:" + count.get();
}
}



虚拟节点


public class VirtualNode {

private Node realServer;
private String virtualServer;
private int hash;

public VirtualNode(Node realServer, String virtualServer, int hash) {
this.realServer = realServer;
this.virtualServer = virtualServer;
this.hash = hash;
}

public Node getRealServer() {
return realServer;
}

public String getVirtualServer() {
return virtualServer;
}

public int getHash() {
return hash;
}
}



一致性hash


import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashingHelper {

private List<Node> relaServers;

private SortedMap<Integer, VirtualNode> map = new TreeMap<>();

private int virtualNodeNum;

// 没有虚拟节点
public ConsistentHashingHelper(List<Node> relaServers) {
this.relaServers = relaServers;
init();
}
// 有虚拟节点
public ConsistentHashingHelper(List<Node> relaServers, int virtualNodeNum) {
this.relaServers = relaServers;
this.virtualNodeNum = virtualNodeNum;
init();
}

// 初始化
private void init() {
if (relaServers == null || relaServers.isEmpty()) {
throw new IllegalArgumentException();
}

for (Node relaServer : relaServers) {
// 给每个真实节点创建虚拟节点
for (int i = 0; i < virtualNodeNum; i++) {
// 将服务名、服务ip、虚拟节点序号拼接,计算hash值。
String virtualServer = relaServer.getServerName() + relaServer.getIp() + i;
int hash = getHash(virtualServer);
// 创建虚拟节点
VirtualNode virtualNode = new VirtualNode(relaServer, virtualServer, hash);
map.put(hash, virtualNode);
}
}
}

// 获取顺时针最近的服务
public String getNode(String key) {
int hash = getHash(key);
// 获取键值大于hsah值的map
SortedMap<Integer, VirtualNode> resultMap = map.tailMap(hash);
// 如果获取的map为空,即顺时针最近的键值在哈希环最前端,直接取原map
if (resultMap == null || resultMap.isEmpty()) {
resultMap = map;
}
// 取排序后的第一个键值对应的虚拟节点
VirtualNode virtualNode = resultMap.get(resultMap.firstKey());
// 获取虚拟节点对应的真实节点
return virtualNode.getRealServer().getServerAndIncrease();
}

// 获取范围是0到2^32-1区间内的hash值,这个是参考得来的。
public static int getHash(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;
}

}



测试


import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class Test {

public static void main(String[] args) {


// 真实节点数量
int realServerNum = 10;
// 每个真实节点对应的虚拟节点数
int virtualNum = 100;
// 访问次数
int execTimes = 1000000;

List<Node> servers = new ArrayList<>();

for (int i = 0; i < realServerNum; i++) {
Node node = new Node("Test-API-"+String.format("%02d", i+1),"127.0.0." + (i+1));
servers.add(node);
}

// 初始化虚拟节点
ConsistentHashingHelper consistentHashingHelper = new ConsistentHashingHelper(servers, virtualNum);

long startTime = System.currentTimeMillis();
for (int n = 0; n < execTimes; n++) {
// 生成随机数
String key = UUID.randomUUID().toString().replace("-", "");
// 获取节点,并计算次数
consistentHashingHelper.getNode(key);
}
long endTime = System.currentTimeMillis();

double total = 0;
double standardDeviation = 0;
// 每个服务器平均请求量
double avg = execTimes / realServerNum;
// 计算方差
for (int i = 0; i < realServerNum; i++) {
Node node = servers.get(i);
total += Math.abs((double) node.getCount() -avg) * Math.abs((double) node.getCount() - avg);
}

standardDeviation = Math.sqrt(total / realServerNum);

System.out.println("一致性hash测试,共" + realServerNum + "台服务器,各虚拟出" + virtualNum + "个节点,进行"
+ execTimes + "次查找节点,标准差:" + standardDeviation + ",总耗时:" + (endTime - startTime) + "ms,各服务器情况如下。");

for (Node realServer : servers) {
System.out.println(realServer);
}

}
}



结果



总结:

听课的时候觉得方案没问题,但是写代码的时候会想到如果遇到hash冲突的时候,新的虚拟节点会不会把原有的虚拟节点更新掉,导致hash环中虚拟节点总数量变少。还有就是现在是用服务名字和、ip和序号生成虚拟节点hash值,但是拼接后的值其实都很类似,会导致hash不够均匀,后期可以考虑下md5之后再hash。心目中觉得可以根据前一天的热点请求数据,调整hash算法,这样可以让压力分摊的比较平均。

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

Bear在挨踢

关注

还未添加个人签名 2019.02.16 加入

还未添加个人简介

评论

发布
暂无评论
【架构师训练营第 1 期 05 周】 作业