写点什么

架构师训练营第五周作业

用户头像
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
@ToString
class 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
@NoArgsConstructor
public 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
用户头像

xs-geek

关注

还未添加个人签名 2018.04.22 加入

还未添加个人简介

评论

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