架构师训练营第 5 周作业

用户头像
0x12FD16B
关注
发布于: 2020 年 07 月 08 日
  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

类图

Node 接口

public interface Node {
String getKey();
}

VirtualNode 类

public class VirtualNode<T extends Node> implements Node {
final T physicalNode;
final int vIndex;
public VirtualNode(T physicalNode, int vIndex) {
this.physicalNode = physicalNode;
this.vIndex = vIndex;
}
public boolean isVirtualNodeOf(T physicalNode) {
if (physicalNode == null) return false;
return physicalNode.getKey().equals(this.physicalNode.getKey());
}
@Override
public String getKey() {
return this.physicalNode.getKey() + "_" + vIndex;
}
public T getPhysicalNode() {
return physicalNode;
}
}

Server Node 类

public class ServerNode implements Node {
private final String zoneId;
private final String ip;
private final int port;
public ServerNode(String zoneId, String ip, int port) {
this.zoneId = zoneId;
this.ip = ip;
this.port = port;
}
@Override
public String getKey() {
return zoneId + "_" + ip + ":" + port;
}
}

HashAlgorithm 接口

public interface HashAlgorithm {
long hash(String key);
}

Sha256HashAlgorithm 类

public class Sha256HashAlgorithm implements HashAlgorithm {
private final MessageDigest messageDigest;
public Sha256HashAlgorithm() {
try {
messageDigest = MessageDigest.getInstance("SHA-256");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("初始化 SHA-256 哈希算法失败");
}
}
@Override
public long hash(String key) {
byte[] digest = messageDigest.digest(key.getBytes());
long h = 0;
for (int i = 0; i < 4; i++) {
h <<= 8;
h |= ((int) digest[i]) & 0xFF;
}
return h;
}
}

ConsistentHash 类

public class ConsistentHash<T extends Node> {
private final SortedMap<Long, VirtualNode<T>> hashRing = new TreeMap<>();
private final HashAlgorithm hashAlgorithm;
public ConsistentHash(Collection<T> pNodes, int vNodeCount) {
this(pNodes, vNodeCount, new Sha256HashAlgorithm());
}
public ConsistentHash(Collection<T> pNodes, int vNodeCount, HashAlgorithm hashAlgorithm) {
this.hashAlgorithm = hashAlgorithm;
if (pNodes != null) {
for (T pNode : pNodes) {
appendVirtualNode(pNode, vNodeCount);
}
}
}
public void appendVirtualNode(T pNode, int vNodeCount) {
if (vNodeCount < 0) throw new IllegalArgumentException("虚拟节点数量不能小于 0");
int existingVNodeCount = this.getPhysicalNodeExistingVirtualNodeCount(pNode);
for (int i = 0; i < vNodeCount; i++) {
VirtualNode<T> virtualNode = new VirtualNode<>(pNode, i + existingVNodeCount);
hashRing.put(hashAlgorithm.hash(virtualNode.getKey()), virtualNode);
}
}
public void removePhysicalNode(T pNode) {
if (pNode == null) return;
Iterator<Long> iterator = hashRing.keySet().iterator();
while (iterator.hasNext()) {
Long key = iterator.next();
VirtualNode<T> virtualNode = hashRing.get(key);
if (virtualNode.isVirtualNodeOf(pNode)) {
iterator.remove();
}
}
}
public T routeNode(String key) {
if (hashRing.isEmpty()) {
return null;
}
long hash = hashAlgorithm.hash(key);
SortedMap<Long, VirtualNode<T>> tailMap = hashRing.tailMap(hash);
long nodeHash = !tailMap.isEmpty() ? tailMap.firstKey() : hashRing.firstKey();
return hashRing.get(nodeHash).getPhysicalNode();
}
private int getPhysicalNodeExistingVirtualNodeCount(T physicalNode) {
int count = 0;
for (VirtualNode<T> node : hashRing.values()) {
if (node.isVirtualNodeOf(physicalNode)) {
count++;
}
}
return count;
}
}

测试类

public class Test {
public static void main(String[] args) {
// 虚拟节点数量
for (int i = 1; i < 1000; i++) {
int times = 1000000;
List<ServerNode> servers = Arrays.asList(
new ServerNode("zone1", "192.168.0.1", 6789),
new ServerNode("zone1", "192.168.0.2", 6789),
new ServerNode("zone1", "192.168.0.3", 6789),
new ServerNode("zone1", "192.168.0.4", 6789),
new ServerNode("zone1", "192.168.0.5", 6789),
new ServerNode("zone1", "192.168.0.6", 6789),
new ServerNode("zone1", "192.168.0.7", 6789),
new ServerNode("zone1", "192.168.0.8", 6789),
new ServerNode("zone1", "192.168.0.9", 6789),
new ServerNode("zone1", "192.168.0.10", 6789));
ConsistentHash<ServerNode> consistentHash = new ConsistentHash<>(servers, i);
Map<String, Integer> routedCount = Maps.newLinkedHashMap();
routedCount.put("zone1_192.168.0.1:6789", 0);
routedCount.put("zone1_192.168.0.2:6789", 0);
routedCount.put("zone1_192.168.0.3:6789", 0);
routedCount.put("zone1_192.168.0.4:6789", 0);
routedCount.put("zone1_192.168.0.5:6789", 0);
routedCount.put("zone1_192.168.0.6:6789", 0);
routedCount.put("zone1_192.168.0.7:6789", 0);
routedCount.put("zone1_192.168.0.8:6789", 0);
routedCount.put("zone1_192.168.0.9:6789", 0);
routedCount.put("zone1_192.168.0.10:6789", 0);
for (int j = 0; j < times; j++) {
ServerNode routeNode = consistentHash.routeNode(UUID.randomUUID().toString());
routedCount.put(routeNode.getKey(), routedCount.get(routeNode.getKey()) + 1);
}
System.out.println(i + "\t" + getStandardDeviation(routedCount.values().toArray(new Integer[0])));
}
}
private static double getStandardDeviation(Integer[] array) {
int m = array.length;
double sum = 0;
for (Integer i : array) {
sum += i;
}
double dAve = sum / m;
double dVar = 0;
for (Integer i : array) {
dVar += (i - dAve) * (i - dAve);
}
return Math.sqrt(dVar / m);
}
}

结果



用户头像

0x12FD16B

关注

还未添加个人签名 2018.01.19 加入

还未添加个人简介

评论

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