第五周作业 1
发布于: 2020 年 11 月 22 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
package arch.study;import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;import java.util.HashMap;import java.util.ArrayList;import java.util.UUID;public class ConsistentHash { //待添加入Hash环的服务器列表 private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111", "192.168.0.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111"}; private static List<String> realNodes = new LinkedList<>(); private static SortedMap<Integer, String> virtualNodes = new TreeMap<>(); private static final int VIRTUAL_NODES = 100; static{ for(int i = 0; i < servers.length; i++) realNodes.add(servers[i]); for (String str : realNodes){ for(int i = 0; i < VIRTUAL_NODES; i++){ String virtualNodeName = str + "&&VN" + String.valueOf(i); int hash = getHash(virtualNodeName); System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash); virtualNodes.put(hash, virtualNodeName); } } System.out.println(); } //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 private 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; } private static String getServer(String key){ int hash = getHash(key); SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash); String virtualNode; if(subMap.isEmpty()){ Integer i = virtualNodes.firstKey(); virtualNode = virtualNodes.get(i); }else{ Integer i = subMap.firstKey(); virtualNode = subMap.get(i); } return virtualNode.substring(0, virtualNode.indexOf("&&")); } public static void main(String[] args){ List<String> invocations = new ArrayList<>(); for (int i = 0; i < 1000000; i++) { invocations.add(UUID.randomUUID().toString()); } HashMap<String, Long> atomicLongMap = new HashMap(); for (String server : realNodes) { atomicLongMap.put(server, 0L); } for (String invocation : invocations) { String selectedServer = getServer(invocation); atomicLongMap.put(selectedServer, atomicLongMap.get(selectedServer) + 1); } System.out.println(StatisticsUtil.standardDeviation(atomicLongMap.values().toArray(new Long[]{}))); }}
package arch.study;public class StatisticsUtil { // 方差 s^2=[(x1-x)^2 +...(xn-x)^2]/n public static double variance(Long[] x) { int m = x.length; double sum = 0; for (int i = 0; i < m; i++) {// 求和 sum += x[i]; } double dAve = sum / m;// 求平均值 double dVar = 0; for (int i = 0; i < m; i++) {// 求方差 dVar += (x[i] - dAve)* (x[i] - dAve); } return dVar / m; } // 标准差σ=sqrt(s^2) public static double standardDeviation(Long[] x) { double variance_value = variance(x); return Math.sqrt(variance_value); }}
划线
评论
复制
发布于: 2020 年 11 月 22 日阅读数: 19
版权声明: 本文为 InfoQ 作者【jingx】的原创文章。
原文链接:【http://xie.infoq.cn/article/6c3684fc24fe55a85f2aaa5e5】。未经作者许可,禁止转载。
jingx
关注
还未添加个人签名 2018.09.07 加入
还未添加个人简介
评论