架构师训练营第五周作业
发布于: 2020 年 10 月 25 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
外部依赖(Maven)
<dependencies> <!-- https://mvnrepository.com/artifact/com.google.guava/guava --> <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>28.1-jre</version> </dependency> <!-- https://mvnrepository.com/artifact/org.projectlombok/lombok --> <dependency> <groupId>org.projectlombok</groupId> <artifactId>lombok</artifactId> <version>1.18.12</version> <scope>provided</scope> </dependency> </dependencies>
Node节点 -- 物理机
import lombok.AllArgsConstructor;import lombok.Data;import lombok.NoArgsConstructor;import lombok.ToString;@Data@NoArgsConstructor@AllArgsConstructor@ToStringclass Node { String ip; String name;}
一致性hash
import com.google.common.base.Charsets;import lombok.Data;import lombok.NoArgsConstructor;import java.util.SortedMap;import java.util.TreeMap;import static com.google.common.hash.Hashing.murmur3_32;@Data@NoArgsConstructorpublic class ConsistentHash { private int virtualNum; private final TreeMap<Integer, Node> virtualNodes = new TreeMap<>(); private int getHashCode(Node node, int number) { return getHashCode(node.toString() + "-" + number); } private int getHashCode(String key) { return murmur3_32().hashString(key, Charsets.UTF_8).asInt(); } public void add(Node node) { for (int i = 0; i < virtualNum; i++) { virtualNodes.put(getHashCode(node, i), node); } } public void remove(Node node) { for (int i = 0; i < virtualNum; i++) { virtualNodes.remove(getHashCode(node, i)); } } public Node get(String key) { if (virtualNodes.isEmpty()) { return null; } int hashcode = getHashCode(key); int nodeHashcode; if (virtualNodes.containsKey(hashcode)) { nodeHashcode = hashcode; } else { SortedMap<Integer, Node> tailMap = virtualNodes.tailMap(hashcode); nodeHashcode = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey(); } return virtualNodes.get(nodeHashcode); }}
测试
package com.example;import java.util.*;import java.util.stream.Collectors;import java.util.stream.IntStream;public class Main { public static List<Node> initNodes(int nodeNumber) { String ipPrefix = "172.10.0."; List<Node> nodes = IntStream.range(0, nodeNumber).mapToObj(i -> { String ip = ipPrefix + i; String name = "node-" + i; return new Node(ip, name); }).collect(Collectors.toList()); // 节点// nodes.forEach(System.out::println); // print return nodes; } public static ConsistentHash initConsistentHash(List<Node> nodes, int virtualNumber) { ConsistentHash consistentHash = new ConsistentHash(); consistentHash.setVirtualNum(virtualNumber); nodes.forEach(consistentHash::add); return consistentHash; } public static double standardDeviation(Collection<Integer> list) { Double avg = list.stream().mapToDouble(Integer::doubleValue).average().orElse(0D); // 平均 int total = list.stream().mapToInt(num -> (int) ((num - avg) * (num - avg))).sum(); // 方差 return Math.sqrt(total); } public static void testVirtual(int totalNode, int perVirtualNode) { List<Node> nodes = initNodes(totalNode); //10节点 Map<String, Integer> counts = new HashMap<>(); nodes.forEach(node -> { String ip = node.getIp(); counts.put(ip, 0); }); // 初始化计数 ConsistentHash consistentHash = initConsistentHash(nodes, perVirtualNode); // 初始化虚拟节点 for (int i = 0; i < 1000000; i++) { String randomKey = UUID.randomUUID().toString(); Node node = consistentHash.get(randomKey); counts.put(node.getIp(), counts.get(node.getIp()) + 1); }// counts.forEach((k, v) -> {// System.out.println(k + " -> " + v);// }); System.out.println(perVirtualNode + " virtualNode: " + standardDeviation(counts.values())); } public static void main(String[] args) { testVirtual(10, 50); testVirtual(10, 100); testVirtual(10, 150); testVirtual(10, 200); testVirtual(10, 250); }}
划线
评论
复制
发布于: 2020 年 10 月 25 日阅读数: 26
版权声明: 本文为 InfoQ 作者【xs-geek】的原创文章。
原文链接:【http://xie.infoq.cn/article/61cae592964c9022406542462】。未经作者许可,禁止转载。
xs-geek
关注
还未添加个人签名 2018.04.22 加入
还未添加个人简介
评论