写点什么

【架构师训练营第 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 日阅读数: 33
用户头像

Bear

关注

还未添加个人签名 2019.02.16 加入

还未添加个人简介

评论

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