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, 虚拟节点数: 10000
IDC1-127.0.0.1:8081 命中次数 100603
IDC1-127.0.0.1:8088 命中次数 98452
IDC1-127.0.0.1:8089 命中次数 99852
IDC1-127.0.0.1:8082 命中次数 99039
IDC1-127.0.0.1:8085 命中次数 100860
IDC1-127.0.0.1:8080 命中次数 99956
IDC1-127.0.0.1:8083 命中次数 101813
IDC1-127.0.0.1:8084 命中次数 99300
IDC1-127.0.0.1:8086 命中次数 99662
IDC1-127.0.0.1:8087 命中次数 100463
标准差: 924.7948961796881

用户头像

雪涛公子

关注

还未添加个人签名 2017.11.20 加入

还未添加个人简介

评论

发布
暂无评论
week5 作业