week5 作业

public interface Node {
    String getKey();}

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;    }}

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

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;        }    }}

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);    }}

节点数: 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