Load balancing -- consistent Hash algorithm

Before talking about consistency hash, you need to hash the hash. For hash, you only need the time complexity of O(1), and then you can calculate the result. For example, in our HashMap, the hash algorithm is used to calculate the subscript of the key, but it is similar to hashing the hash value after calculating the hashcode. For the same key, the result of each calculation is the same, This is consistency, but what is more about consistency hash than hash

Ordinary hash: suppose we have three servers. We can use the hash of the key to calculate the subscript like adding elements in the HashMap. Because the hash calculated by the same key is the same every time, our same request can be routed to the same server. In this way, we can effectively use caching and other mechanisms to reduce the overhead caused by repeated requests. It is simple and easy to use, But there are defects. When we need to add machines or reduce machines, what will happen?
First, add the machine. The direct result of our hash and subscript leads to the mismatch between the server and the request, which is routed to another machine. Isn't it a mess?
Therefore, consistency Hash is proposed

Consistency hash: the main feature is the hash ring. Our requests can be constructed into a hash ring to record hash and requests clockwise
When our service hangs up A, we only need to hand over A's request to B behind A for processing
When we need to add server C, we just need to draw a range on the Hash ring and give it to C
In this way, dynamic capacity expansion and reduction can be realized.
Consistent hash is used to solve the problem of node selection in distributed cache system and the disappearance and redistribution of data cache caused by node reduction after adding and deleting servers

public class ConsistentHash {

    //Hash ring
    private static TreeMap<Integer,String> virtual=new TreeMap<>();
    //Initialize hash ring
    static {
        for (String ip: IPs.LIST){

            for (int i=0;i<VIRTUAL_NODES;i++){
                //Generate hash for ip
                int hash=getHash(ip);
                virtual.put(hash,ip);
            }
        }
    }

	//Feel free to add or not
    private static int getHash(String str){
        final int p=16777619;
        int hash=(int) 2166136261L;
        for (int i=0;i<str.length();i++){
            hash=(hash^str.charAt(i))*p;
        }
        hash+=hash<<13;
        hash^=hash>>7;
        hash+=hash<<3;
        hash^=hash>>17;
        hash+=hash<<5;
        if (hash<0){
            hash=Math.abs(hash);
        }
        return hash;
    }

    public static String getServer(String client){
		//Get Hash
        int hash=getHash(client);
       
        //Find the firstKey that is greater than the number of words in hash and virtual
        SortedMap<Integer, String> subMap = virtual.tailMap(hash);
        Integer firstKey = null;
        if (subMap==null){
        	//
            firstKey =  virtual.firstKey();
        }else {
            firstKey=subMap.firstKey();
        }
        return virtual.get(firstKey);
    }

    public static void main(String[] args) {
        System.out.println(getServer("client"));
    }
}

However, have you ever considered a problem, that is, the inclination of our server nodes, that is, the Hash range managed by the server is uneven, resulting in a large number of requests hitting only one server, but the pressure of other servers is very small, just like this (the picture is painted by yourself, which is ugly)

Now that the above problems have arisen, how can we solve them?

Consistency Hash with virtual nodes: add N virtual nodes, calculate multiple hashes of real nodes to form multiple virtual nodes and place them on the Hash ring. The positioning algorithm remains unchanged, but there is an additional step in the process of mapping virtual nodes to real nodes. Then, when the server hangs up, other servers can share their virtual nodes

Like this

Here, we must also mention the hash slots in redis. Hash slots are used for data fragmentation in redis cluster to store and read data. By default, there are 16384 slots. The algorithm used to calculate the slot area is CRC16(key) mod 16384. Each server node will be assigned a specified number of hash slots. When our node hangs up, Other server nodes will bear the data, resulting in the re allocation of the slot area. Note that the hash slot is not a closed loop like the consistency hash. It is a slot, and the rules for locating the server node are also different. Our consistency hash needs to be calculated and then searched clockwise, while the slot only needs to calculate the slot area

Finally, let's take a look at how Dubbo implements the consistent Hash algorithm

//Implementation of consistent Hash load balancing in Dubbo
public class ConsistentHashLoadBalance extends AbstractLoadBalance {

    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<String, ConsistentHashSelector<?>>();

    @SuppressWarnings("unchecked")
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        int identityHashCode = System.identityHashCode(invokers);
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        if (selector == null || selector.getIdentityHashCode() != identityHashCode) {
            selectors.put(key, new ConsistentHashSelector<T>(invokers, invocation.getMethodName(), identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        return selector.select(invocation);
    }

    private static final class ConsistentHashSelector<T> {

        //Hash ring
        private final TreeMap<Long, Invoker<T>> virtualInvokers;
        //Virtual node tree
        private final int replicaNumber;
        //HashCode
        private final int identityHashCode;
        //Parameter index array
        private final int[] argumentIndex;

        public ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            //Use treeMap to save our nodes
            this.virtualInvokers = new TreeMap<Long, Invoker<T>>();

            this.identityHashCode = System.identityHashCode(invokers);
            //Get our Url
            //dubbo://127.0.0.1:20880/service.DemoService?anyhost=true&application=srcAnalysisClient&check=false&dubbo=2.8.4&generic=false&interface=service.DemoService&loadbalance=consistenthash&methods=sayHello,retMap&pid=14648&sayHello.timeout=20000&side=consumer&timestamp=1493522325563
            URL url = invokers.get(0).getUrl();
            //160 virtual nodes by default
            this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
            String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
            argumentIndex = new int[index.length];
            for (int i = 0; i < index.length; i++) {
                argumentIndex[i] = Integer.parseInt(index[i]);
            }
            //Traverse our Invoker and add it to our ring
            for (Invoker<T> invoker : invokers) {
                for (int i = 0; i < replicaNumber / 4; i++) {
                    byte[] digest = md5(invoker.getUrl().toFullString() + i);
                    for (int h = 0; h < 4; h++) {
                        //Calculate Hash
                        long m = hash(digest, h);
                        //Put it into our Hash ring
                        virtualInvokers.put(m, invoker);
                    }
                }
            }
        }

        public int getIdentityHashCode() {
            return identityHashCode;
        }

        //Select node
        public Invoker<T> select(Invocation invocation) {
            //Generate Key based on parameters
            String key = toKey(invocation.getArguments());
            //MD5 post hash
            byte[] digest = md5(key);
            //Select node
            Invoker<T> invoker = sekectForKey(hash(digest, 0));
            return invoker;
        }

        private String toKey(Object[] args) {
            StringBuilder buf = new StringBuilder();
            for (int i : argumentIndex) {
                if (i >= 0 && i < args.length) {
                    buf.append(args[i]);
                }
            }
            return buf.toString();
        }

        private Invoker<T> sekectForKey(long hash) {
            Invoker<T> invoker;
            Long key = hash;
            //Without this Key
            if (!virtualInvokers.containsKey(key)) {
                //If not, find the nearest key node larger than this key
                SortedMap<Long, Invoker<T>> tailMap = virtualInvokers.tailMap(key);
                //If the map is empty, we need to take the first node directly
                if (tailMap.isEmpty()) {
                    key = virtualInvokers.firstKey();
                } else {
                    //
                    key = tailMap.firstKey();
                }
            }
            //Get the node directly, and then return
            invoker = virtualInvokers.get(key);
            return invoker;
        }

        private long hash(byte[] digest, int number) {
            return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                    | (digest[0 + number * 4] & 0xFF))
                    & 0xFFFFFFFFL;
        }

        private byte[] md5(String value) {
            MessageDigest md5;
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.reset();
            byte[] bytes = null;
            try {
                bytes = value.getBytes("UTF-8");
            } catch (UnsupportedEncodingException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.update(bytes);
            return md5.digest();
        }

    }

}