dubbo中的一致性hash（ConsistentHashLoadBalance）详解

注意：本文适用于了解dubbo以及一致性hash的读者

众所周知，dubbo中有四种负载均衡策略：

别的负载均衡策略就不细说了，再这里重点说一下dubo中的一致性hash负载均衡：ConsistentHashLoadBalance

前面的流程不多说，我们直接进入ConsistentHashLoadBalance的doSelect()方法中：

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

刚开始生成一个key，其路径示例如下：com.dubbo.common.service.app.AppManageService:2222.selectLastApp

然后根据生成的hashCode匹配对应的Selector（一般Selector的数量为对应的consumer的数量）

生成一致性hash的核心方法在ConsistentHashSelector的构造方法中：

        public ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
            this.identityHashCode = System.identityHashCode(invokers);
            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) {
                for (int i = 0; i < replicaNumber / 4; i++) {
                    byte[] digest = md5(invoker.getUrl().toFullString() + i);
                    for (int h = 0; h < 4; h++) {
                        long m = hash(digest, h);
                        virtualInvokers.put(m, invoker);
                    }
                }
            }
        }

根据对应的Invokers生成对应的hash环虚拟节点，放在一个TreeMap的结构中，key为虚拟节点的hash值。这样就可以在TreeMap中有序排列，这样hash环就生成了，调用选择的方法如下：

        public Invoker<T> select(Invocation invocation) {
            String key = toKey(invocation.getArguments());
            byte[] digest = md5(key);
            Invoker<T> invoker = sekectForKey(hash(digest, 0));
            return invoker;
        }

以参数值通过md5加密的hash为参数，进入selectForKey方法：

        private Invoker<T> sekectForKey(long hash) {
            Invoker<T> invoker;
            Long key = hash;
            if (!virtualInvokers.containsKey(key)) {
                SortedMap<Long, Invoker<T>> tailMap = virtualInvokers.tailMap(key);
                if (tailMap.isEmpty()) {
                    key = virtualInvokers.firstKey();
                } else {
                    key = tailMap.firstKey();
                }
            }
            invoker = virtualInvokers.get(key);
            return invoker;
        }

以入参hash获取tailMap的第一个比较大的虚拟节点的Invoker，如果入参的hashcode最大则用第一个虚拟节点的Invoker。