架构师训练营第五周 - 作业
发布于: 2020 年 07 月 08 日
1.用你熟悉的编程语言实现一致性 hash 算法。
2.编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
import java.util.LinkedList;import java.util.ArrayList;import java.util.HashMap;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.SortedMap;import java.util.TreeMap;import org.apache.commons.lang.StringUtils;public class test { private static String[] servers = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"}; private static List<String> realNodes = new LinkedList<String>(); private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>(); private static final int VIRTUAL_NODES = 200; 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(); } 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); } if(StringUtils.isNotBlank(virtualNode)){ return virtualNode.substring(0, virtualNode.indexOf("&&")); } return null; } public static double Variance(List<Integer> x) { int m = x.size(); double sum = 0; for (int i = 0; i < m; i++) { sum += x.get(i); } double dAve = sum / m; double dVar = 0; for (int i = 0; i < m; i++) { dVar += (x.get(i) - dAve) * (x.get(i) - dAve); } return dVar / m; } public static void main(String[] args){ Map<String, Integer> countMap = new HashMap<>(); for (int i = 0; i < servers.length; i++) { realNodes.add(servers[i]); countMap.put(servers[i], 0); } for(int i=0; i<1000000; i++) { System.out.println("[" + "测试"+i + "]的hash值为" + getHash("测试"+i) + ", 被路由到结点[" + getServer("测试"+i) + "]"); countMap.put(getServer("测试"+i), countMap.get(getServer("测试"+i)) + 1); } System.out.println(countMap); List<Integer> x = new ArrayList<>(); for (String key : countMap.keySet()) { x.add(countMap.get(key)); } System.out.println("标准差=:" + Math.sqrt(Variance(x))); } }
输出:
{A=105457, B=108688, C=102894, D=92895, E=100458, F=94681, G=92709, H=109539, I=95614, J=97065}
标准差=:6038.380594165956
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 48
版权声明: 本文为 InfoQ 作者【人世间】的原创文章。
原文链接:【http://xie.infoq.cn/article/7f34a21be076ab13e4f59977e】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
人世间
关注
还未添加个人签名 2018.08.21 加入
还未添加个人简介
评论