写点什么

架构师训练营第五周作业

用户头像
xs-geek
关注
发布于: 2020 年 10 月 25 日
  1. 用你熟悉的编程语言实现一致性 hash 算法。

  2. 编写测试用例测试这个算法,测试 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 日阅读数: 36
用户头像

xs-geek

关注

还未添加个人签名 2018.04.22 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周作业