Consistent Hash Algorithm and Its Application in Dubbo Load Balancing

The article introduces consistent hashing, describing its basic principle and the data‑skew problem that occurs when a small number of nodes handle most requests, then presents virtual nodes as a solution to distribute load more evenly.

It explains load balancing concepts, quoting Dubbo’s definition of LoadBalance and listing four built‑in algorithms (RandomLoadBalance, LeastActiveLoadBalance, ConsistentHashLoadBalance, RoundRobinLoadBalance), and discusses the drawbacks of simple hash‑based partitioning, especially the heavy data migration caused by scaling up or down.

Virtual nodes are introduced: each physical server can be represented by multiple virtual nodes (e.g., IP+port+index), which spreads requests across servers and reduces data skew. Diagrams illustrate how adding virtual nodes balances request distribution.

The article then focuses on the practical application of consistent hashing in Dubbo. It provides a step‑by‑step source‑code analysis of ConsistentHashLoadBalance, starting with the doSelect method that detects changes in the invoker list and creates a new ConsistentHashSelector when needed.

public class ConsistentHashLoadBalance extends AbstractLoadBalance {
    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String methodName = RpcUtils.getMethodName(invocation);
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
        int identityHashCode = System.identityHashCode(invokers);
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        if (selector == null || selector.identityHashCode != identityHashCode) {
            selectors.put(key, new ConsistentHashSelector<>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        return selector.select(invocation);
    }
    private static final class ConsistentHashSelector<T> { ... }
}

The constructor of ConsistentHashSelector builds a TreeMap<Long, Invoker<T>> of virtual nodes, using MD5 to generate multiple hash points per server and storing them for efficient lookup.

private static final class ConsistentHashSelector<T> {
    private final TreeMap<Long, Invoker<T>> virtualInvokers;
    private final int replicaNumber;
    private final int identityHashCode;
    private final int[] argumentIndex;
    ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap<>();
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        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]);
        }
        for (Invoker<T> invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            for (int i = 0; i < replicaNumber / 4; i++) {
                byte[] digest = md5(address + i);
                for (int h = 0; h < 4; h++) {
                    long m = hash(digest, h);
                    virtualInvokers.put(m, invoker);
                }
            }
        }
    }
    // select and other methods omitted for brevity
}

The select method hashes the invocation arguments, finds the appropriate virtual node in the ring via TreeMap.tailMap, and returns the corresponding real invoker, ensuring that identical request parameters are consistently routed to the same provider.

Finally, the article lists various other load‑balancing techniques (DNS, proxy, NAT, reverse proxy, hybrid) and provides references for further reading.