架构师训练营 - 第五周 - 作业
发布于: 2020 年 07 月 06 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
public class Case4Application { SortedMap<Integer, String> sortedCircle = new TreeMap<>(); int virtualNums = 200; /** * 初始化虚拟节点 */ private void init(List<String> nodes) { //服务器节点对应放大虚拟节点 Map<String, String> virtualNodes = new HashMap<>(); for (String node : nodes) { for (int i = 0; i < virtualNums; i++) { virtualNodes.put(node + "_" + i, node); } } for (String key : virtualNodes.keySet()) { sortedCircle.put(hash(key), virtualNodes.get(key)); } } /** * 增加节点 * @param node */ private void addNode(String node) { //服务器节点对应放大虚拟节点 Map<String, String> virtualNodes = new HashMap<>(); for (int i = 0; i < virtualNums; i++) { virtualNodes.put(node + "_" + i, node); } for (String key : virtualNodes.keySet()) { sortedCircle.put(hash(key), virtualNodes.get(key)); } } /** * 找到离该key的hash值最新的一个节点 * 找不到取第一个节点 * * @param key * @return */ private String findNodeByHash(String key) { int hash = hash(key); SortedMap<Integer, String> subMap = sortedCircle.tailMap(hash); return subMap.isEmpty() ? sortedCircle.get(sortedCircle.firstKey()) : subMap.get(subMap.firstKey()); } /** * hash值计算 * 32位FNV算法1 * * @param data * @return */ private static int hash(String data) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < data.length(); i++) hash = (hash ^ data.charAt(i)) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } /** * 计算缓存key在节点上的分布和标准差 * * @param keyValus */ private void compute(Map<String, Object> keyValus) { //每个节点分配的缓存key个数 Map<String, Integer> result = new HashMap<>(); for (String key : keyValus.keySet()) { String nodeName = findNodeByHash(key); if (result.get(nodeName) == null) { result.put(nodeName, 1); } else { Integer value = result.get(nodeName); result.put(nodeName, value + 1); } } System.out.println(result); System.out.println("标准差:" + stdDev(result, keyValus.size())); } /** * 标准差计算 * * @param map * @param totalNums * @return */ private double stdDev(Map<String, Integer> map, long totalNums) { int n = map.size(); long avgNums = totalNums / map.size(); double sum = 0; for (String key : map.keySet()) { int value = map.get(key); sum += (value - avgNums) * (value - avgNums); } return Math.sqrt(sum / n); } public static void main(String[] args) { //服务器节点 List<String> nodes = Arrays.asList("node1", "node2", "node3" , "node4", "node5", "node6", "node7", "node8", "node9", "node10"); Case4Application case4Application = new Case4Application(); //初始化,默认虚拟节点为200 case4Application.init(nodes); //需要环节的1000000个key Map<String, Object> keyValus = new HashMap<>(); for (int i = 1; i <= 1000000; i++) { keyValus.put("key" + i, "value" + i); } //输出缓存key在节点上的分布及标准差 case4Application.compute(keyValus); //添加一个新节点 case4Application.addNode("node11"); case4Application.compute(keyValus); }}
输出结果
{node4=98661, node10=92694, node5=103651, node2=88519, node3=112497, node8=90940, node9=89461, node6=94505, node7=109283, node1=119789}标准差:10284.048249595098{node4=89700, node5=92328, node10=83027, node11=92332, node2=78758, node3=105872, node8=85593, node9=82934, node6=90864, node7=101427, node1=97165}标准差:7867.034967623964
划线
评论
复制
发布于: 2020 年 07 月 06 日 阅读数: 57
韩挺
关注
还未添加个人签名 2019.01.25 加入
还未添加个人简介
评论