一致性哈希算法 Java 实现

// Represent a node which should be mapped to a hash ringpublic interface Node {    // return the key which will used for hash mapping    String getKey();}

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

// Hash String to long valuepublic interface HashFunction {    long hash(String key);}

import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;import java.util.Arrays;import java.util.Collection;import java.util.Iterator;import java.util.SortedMap;import java.util.TreeMap;
// To hash Node objects to a hash ring with a certain amount of// virtual node.// Method routeNode will return a Node instance which the object// key should be allocated to according to consistent hash algorithmpublic class ConsistentHashRouter<T extends Node> {    private final SortedMap<Long, VirtualNode<T>> ring = new TreeMap<>();    private final HashFunction hashFunction;
    /**     *     * @param pNodes collections of physical nodes     * @param vNodeCount amounts of virtual nodes     * @param hashFunction hash Function to hash Node instances     */    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 ConsistentHashRouter(Collection<T> pNodes, int vNodeCount) {//            this(pNodes, vNodeCount, new MD5Hash());//        }
    /**     * add physical node to the hash ring with some virtual nodes     * @param pNode physical node needs added to hash ring     * @param vNodeCount the number of virtual node of the physical     *                   node. Value should be greater than or equals 0     *     */    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);        }    }
    /**     * remove the physical node from the hash ring     * @param pNode physical node     */    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();            }        }    }
    /**     * with a specified key, route the nearest Node instance in the     * current hash ring     * @param objectKey the object key to find a nearest Node     * @return     */    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();    }
    public int getExistingReplicas(T pNode) {        int replicas = 0;        for (VirtualNode<T> vNode : ring.values()) {            if (vNode.isVirtualNodeOf(pNode)) {               replicas++;            }        }        return replicas;    }
    private 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;        }    }}

import java.util.Arrays;
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();    }
    private static void goRoute(ConsistentHashRouter<MyServiceNode> consistentHashRouter, String... requestIps) {        for (String requestIp : requestIps) {            System.out.println(requestIp + " is route to " + consistentHashRouter.routeNode(requestIp));        }    }
    public static void main(String[] args) {        MyServiceNode node1 = new MyServiceNode("IDC1", "127.0.0.1", 8080);        MyServiceNode node2 = new MyServiceNode("IDC1", "127.0.0.1", 8081);        MyServiceNode node3 = new MyServiceNode("IDC1", "127.0.0.1", 8082);        MyServiceNode node4 = new MyServiceNode("IDC1", "127.0.0.1", 8083);
        ConsistentHashRouter<MyServiceNode> consistentHashRouter =                new ConsistentHashRouter<>(Arrays.asList(node1, node2, node3, node4), 10);
        String requestIP1 = "192.168.0.1";        String requestIP2 = "192.168.0.2";        String requestIP3 = "192.168.0.3";        String requestIP4 = "192.168.0.4";        String requestIP5 = "192.168.0.5";
        goRoute(consistentHashRouter, requestIP1, requestIP2, requestIP3, requestIP4, requestIP5);
        // new node online        MyServiceNode node5 = new MyServiceNode("IDC2", "127.0.0.1", 8080);        System.out.println("------puting new node online" + node5.getKey() + "------");        consistentHashRouter.addNode(node5, 10);
        goRoute(consistentHashRouter, requestIP1, requestIP2, requestIP3, requestIP4, requestIP5);
        System.out.println("------remove node online" + node3.getKey() + "------");        consistentHashRouter.removeNode(node3);
        goRoute(consistentHashRouter, requestIP1, requestIP2, requestIP3, requestIP4, requestIP5);    }}