【架构师训练营 - 作业 -5】一致性 HASH 算法实现
发布于: 2020 年 07 月 06 日
作业一：
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
背景
关于一致性 hash 算法，资源有些多，这边随便留了一篇方便后查
https://blog.csdn.net/lihao21/article/details/54193868?
实现：
模拟服务器的类：需要传入一个缓存管理器，用于注册服务
public class Server {
/** * 缓存管理器 */ private CacheManager cacheManager; /** * 缓存数量 */ private int cacheNum;
public Server(CacheManager cacheManager) { this.cacheManager = cacheManager; cacheNum = 0; }
public void start() throws Exception { // 向缓存管理器注册 if (!cacheManager.register(this)) { throw new Exception("注册缓存失败"); } } public void addCache() { // 只为模拟，省掉了相关信息 cacheNum++; } public int cacheNum() { return cacheNum; }}
复制代码
缓存管理器类：需要一个负载均衡器来负责实现负载均衡
public class CacheManager { /** * 服务列表 */ private Map<String, Server> servers; /** * 负载均衡器 */ private LoadBalance loadBalance;
public CacheManager(LoadBalance loadBalance) { this.loadBalance = loadBalance; servers = new HashMap<>(); }
/** * 服务注册 * @param server 服务 */ public boolean register(Server server) {
while (true) { // 这个重复概率太低,暂不做防止死循环逻辑 String serverId = uniqueServerId(); if (servers.containsKey(serverId)) { continue; }
// 添加到负载均衡器 if (loadBalance.addNode(serverId)) { // 添加成功 servers.put(serverId, server); return true; } return false; } }
/** * 添加缓存 * @param key 缓存key */ public void addCache(String key) { String serverId = loadBalance.chooseNode(key); // 暂不考虑服务器下线的情况 servers.get(serverId).addCache(); }
/** * @return 生成一个唯一的服务器ID */ private String uniqueServerId() { return UUID.randomUUID().toString().replace("-", ""); }
}
复制代码
负责均衡器及其配置类：
@Datapublic class LoadBalanceConfig { private int virtualNodeNum = 1;}public class LoadBalance { public static final long MAX_HASH_CODE = ((long)1 << 32) - 1; /** * 负载均衡配置 */ private LoadBalanceConfig loadBalanceConfig; /** * 虚拟节点集合:服务器ID-->桶里的位置集合 */ private Map<String, long[]> virtualManager; /** * 装虚拟节点的桶:位置-->服务器ID */ private TreeMap<Long, String> barrel;
public LoadBalance(LoadBalanceConfig loadBalanceConfig) { this.loadBalanceConfig = loadBalanceConfig; this.virtualManager = new HashMap<>(); this.barrel = new TreeMap<>(); }
/** * 增加节点，不考虑重复添加等情况 * @param nodeId 节点名 */ public boolean addNode(String nodeId) { // 生成并放置虚拟节点 long[] virtualNodes = new long[loadBalanceConfig.getVirtualNodeNum()]; String virtualNodeId = null; for (int i = 0; i < loadBalanceConfig.getVirtualNodeNum(); i++) { // 设置循环次数上限,防止死循环 int createVirtualNodeCycleTimes = 0; while (true) { // 生成虚拟节点的hashcode long virtualNodeHashCode = getHashCode(createVirtualNodeId()); // 剔除生成的重复节点 if (barrel.containsKey(virtualNodeHashCode)) { createVirtualNodeCycleTimes++; if (createVirtualNodeCycleTimes > 10) { return false; } continue; } // 放置节点 virtualNodes[i] = virtualNodeHashCode; barrel.put(virtualNodeHashCode, nodeId); break; } } return true; }
/** * 选择一个节点 * @param key * @return */ public String chooseNode(String key) { // 计算Hashcode long hashCode = getHashCode(key); // 找到节点 SortedMap<Long, String> tailMap = barrel.tailMap(hashCode); if (tailMap.isEmpty()) { return barrel.firstEntry().getValue(); } return barrel.get(tailMap.firstKey()); }
/** * @return 生成一个虚拟节点ID */ private String createVirtualNodeId() { return UUID.randomUUID().toString().replace("-", ""); }
/** * * @param key * @return 照搬现有hash算法，只是取结果时留32位 */ public static long getHashCode(String key) { final int p = 16777619; long ret = 2166136261L; for (int i = 0; i < key.length(); i++) { ret = (ret ^ key.charAt(i)) * p; } ret += ret << 13; ret ^= ret >> 7; ret += ret << 3; ret ^= ret >> 17; ret += ret << 5; // 视乎可以直接int型不做绝对值本身就是32位的 return ret & MAX_HASH_CODE; }}
复制代码
模拟测试类：
public class TestCache { /** * 运行测试 * @param virtualNodeNum 虚拟节点数量 */ public double runTest(int virtualNodeNum) throws Exception { // 创建负载均衡器 LoadBalanceConfig loadBalanceConfig = new LoadBalanceConfig(); loadBalanceConfig.setVirtualNodeNum(virtualNodeNum); LoadBalance loadBalance = new LoadBalance(loadBalanceConfig); // 创建缓存管理器 CacheManager cacheManager = new CacheManager(loadBalance); // 创建十个服务器 int serverNum = 10; Server[] servers = new Server[serverNum]; for (int i = 0; i < serverNum; i++) { servers[i] = new Server(cacheManager); servers[i].start(); } // 添加缓存 int cacheKeyNum = 1000000; for (int i = 0; i < cacheKeyNum; i++) { cacheManager.addCache(createCacheKey()); } // 获取缓存情况 long[] cacheNums = new long[serverNum]; int cacheNumsIndex = 0;
System.out.println("服务器数量：" + serverNum + ",虚拟节点：" + virtualNodeNum); for (Server server : servers) { cacheNums[cacheNumsIndex++] = server.cacheNum(); System.out.println(server + ":" + server.cacheNum()); } double standardDeviation = calStandardDeviation(cacheNums); System.out.println("标准差：" + standardDeviation); return standardDeviation; }
/** * @return 返回一个虚拟的缓存key */ private static String createCacheKey() { return UUID.randomUUID().toString(); }
/** * 计算标准差 * @param nums * @return */ private double calStandardDeviation(long[] nums) { // 求平均数 -- 不考虑溢出 -- 其实这里都可以直接写死十万= = long sum = 0; for (long each : nums) { sum += each; } double avg = (double) sum / nums.length; double sumOfSquare = 0; for (long num : nums) { sumOfSquare += Math.pow(num - avg, 2); } return Math.sqrt(sumOfSquare / nums.length); }
}
复制代码
main 方法：
public static void main(String[] args) throws Exception { // 模拟测试几种假象情况 int[] waitTestVirtualNodeNum = new int[]{ 10, 30, 50, 100, 120, 150, 200, 250, 300, 500, 700, 1000 }; TestCache testCache = new TestCache(); for (int eachWaitTestVirtualNodeNum : waitTestVirtualNodeNum) { testCache.runTest(eachWaitTestVirtualNodeNum); }
// 模拟测试一个范围的情况，以绘制出趋势图 int begin = 100; int step = 100; int end = 10000; Map<Integer, Double> standardDeviationMap = new HashMap<>(); for (int i = begin; i <= end; i += step) { standardDeviationMap.put(i, testCache.runTest(i)); } for (Map.Entry<Integer, Double> eachData : standardDeviationMap .entrySet()) { System.out.println(eachData.getKey() + "\t" + eachData.getValue());
} }
复制代码
结果：
服务器数量：10,虚拟节点：10标准差：29968.040453122725服务器数量：10,虚拟节点：30标准差：19794.222535881523服务器数量：10,虚拟节点：50标准差：10724.992540789946服务器数量：10,虚拟节点：100标准差：9438.958936238678服务器数量：10,虚拟节点：120标准差：6513.624920119365服务器数量：10,虚拟节点：150标准差：11384.184801732621服务器数量：10,虚拟节点：200标准差：9485.752337057931服务器数量：10,虚拟节点：250标准差：7416.998166374318服务器数量：10,虚拟节点：300标准差：4974.671687659397服务器数量：10,虚拟节点：500标准差：2806.885213185605服务器数量：10,虚拟节点：700标准差：5288.122294349857服务器数量：10,虚拟节点：1000标准差：2389.1400544965963复制代码
负载均衡有各种各样的算法，如轮询、如随机数、如 hash。
hash 的使用非常之广，将各种各样的对象，转换成一串数字来作为索引搜索，极大的降低的搜索的复杂度。
但随之而来的是 hash 碰撞。如何才能将计算结果均衡的分布在一个范围内，产生了各种各样的算法。
而一致性 hash 算法另辟蹊径，不强求分布均衡。所谓的均衡是相对于放置数据的桶而言，那如果我的桶也不均衡呢，也是通过 hash 算法计算出来的，根据算法来分布，是否就可以做到结果均衡了。
算法确实让人眼前一亮，处理问题时换个角度思考可能会带来更大的收获
划线
评论
复制
发布于: 2020 年 07 月 06 日阅读数: 71
版权声明: 本文为 InfoQ 作者【小动物】的原创文章。
原文链接:【http://xie.infoq.cn/article/4ac9884a287c111e9311df8de】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
小动物
关注
还未添加个人签名 2017.12.12 加入
还未添加个人简介
评论