写点什么

week5 作业

用户头像
雪涛公子
关注
发布于: 2020 年 07 月 08 日

1.Node-节点

public interface Node {
String getKey();}
复制代码


2.VirtualNode-虚拟节点

public class VirtualNode<T extends Node> implements Node {
final T physicalNode; final int replicaIndex;
public VirtualNode(T physicalNode, int replicaIndex) { this.physicalNode = physicalNode; this.replicaIndex = replicaIndex; }
@Override public String getKey() { return physicalNode.getKey() + "-" + replicaIndex; }
public boolean isVirtualNodeOf(T pNode) { return physicalNode.getKey().equals(pNode.getKey()); }
public T getPhysicalNode() { return physicalNode; }}
复制代码


3.HashFunction-哈希函数

public interface HashFunction {
long hash(String key);}
复制代码


4.ConsistentHashRouter-路由规则

private final SortedMap<Long, VirtualNode<T>> ring = new TreeMap<>();    private final HashFunction hashFunction;
public ConsistentHashRouter(Collection<T> pNodes, int vNodeCount) { this(pNodes, vNodeCount, new MD5Hash()); }
public ConsistentHashRouter(Collection<T> pNodes, int vNodeCount, HashFunction hashFunction) { if (hashFunction == null) { throw new NullPointerException("Hash Function is null"); }
this.hashFunction = hashFunction; if (pNodes != null) { for (T pNode : pNodes) { addNode(pNode, vNodeCount); } } }
public void addNode(T pNode, int vNodeCount) { if (vNodeCount < 0) { throw new IllegalArgumentException("illegal virtual node counts: " + vNodeCount); }
int existingReplicas = getExistingReplicas(pNode); for (int i = 0; i < vNodeCount; i++) { VirtualNode<T> vNode = new VirtualNode<>(pNode, i + existingReplicas); ring.put(hashFunction.hash(vNode.getKey()), vNode); } }
public int getExistingReplicas(T pNode) { int replicas = 0; for (VirtualNode<T> vNode : ring.values()) { if (vNode.isVirtualNodeOf(pNode)) { replicas++; } } return replicas; }
public void removeNode(T pNode) { Iterator<Long> it = ring.keySet().iterator(); while (it.hasNext()) { Long key = it.next(); VirtualNode<T> virtualNode = ring.get(key); if (virtualNode.isVirtualNodeOf(pNode)) { it.remove(); } } }
public T routeNode(String objectKey) { if (ring.isEmpty()) { return null; }
Long hashVal = hashFunction.hash(objectKey); SortedMap<Long, VirtualNode<T>> tailMap = ring.tailMap(hashVal); Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey(); return ring.get(nodeHashVal).getPhysicalNode(); }
private static class MD5Hash implements HashFunction {
MessageDigest instance;
public MD5Hash() { try { instance = MessageDigest.getInstance("MD5"); } catch (NoSuchAlgorithmException e) {
} }
@Override public long hash(String key) { instance.reset(); instance.update(key.getBytes()); byte[] digest = instance.digest();
long h = 0; for (int i = 0; i < 4; i++) { h <<= 8; h |= ((int) digest[i]) & 0xFF; } return h; } }}
复制代码


5.MyServiceNode-测试类

public class MyServiceNode implements Node {
private final String idc; private final String ip; private final int port;
public MyServiceNode(String idc, String ip, int port) { this.idc = idc; this.ip = ip; this.port = port; }
@Override public String getKey() { return idc + "-" + ip + ":" + port; }
@Override public String toString() { return getKey(); }
public static void main(String[] args) { int nodeCount = 10; int virtualCount = 10000; List<MyServiceNode> nodeList = new ArrayList<>(); Map<MyServiceNode, Integer> map = new HashMap<>(); for (int i = 0; i < nodeCount; i++) { MyServiceNode node = new MyServiceNode("IDC1", "127.0.0.1", 8080 + i); nodeList.add(node); map.put(node, 0); }
ConsistentHashRouter<MyServiceNode> consistentHashRouter = new ConsistentHashRouter<>(nodeList, virtualCount); for (int i = 0; i < 1000000; i++) { int random = new Random().nextInt(Integer.MAX_VALUE); MyServiceNode routeNode = consistentHashRouter.routeNode(String.valueOf(random)); map.put(routeNode, map.get(routeNode) + 1); }
System.out.println("节点数: " + nodeCount + ", 虚拟节点数: " + virtualCount); for (Map.Entry<MyServiceNode, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + " 命中次数 " + entry.getValue()); }
System.out.println("标准差: " + standardDeviation(new ArrayList<>(map.values()))); }
// 标准差σ=sqrt(s^2) public static double standardDeviation(List<Integer> list) { int size = list.size(); double sum = 0; for (int i = 0; i < size; i++) { // 求和 sum += list.get(i); }
double dAve = sum / size; // 求平均值 double dVar = 0; for (int i = 0; i < size; i++) { // 求方差 dVar += (list.get(i) - dAve) * (list.get(i) - dAve); } return Math.sqrt(dVar / size); }}
复制代码


6.测试结果

节点数: 10,  虚拟节点数: 10000IDC1-127.0.0.1:8081  命中次数  100603IDC1-127.0.0.1:8088  命中次数  98452IDC1-127.0.0.1:8089  命中次数  99852IDC1-127.0.0.1:8082  命中次数  99039IDC1-127.0.0.1:8085  命中次数  100860IDC1-127.0.0.1:8080  命中次数  99956IDC1-127.0.0.1:8083  命中次数  101813IDC1-127.0.0.1:8084  命中次数  99300IDC1-127.0.0.1:8086  命中次数  99662IDC1-127.0.0.1:8087  命中次数  100463标准差: 924.7948961796881
复制代码


用户头像

雪涛公子

关注

还未添加个人签名 2017.11.20 加入

还未添加个人简介

评论

发布
暂无评论
week5 作业