dubbo技术内幕八 一致性hash负载均衡Consistent

关于一致性hash的讲解网上很多，我们不说，具体看下dubbo里面是如何的实现一致性hash算法的。
我们先看下ConsistentHashLoadBalance里面的doSelect方法

 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 methodName = RpcUtils.getMethodName(invocation);
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
        int identityHashCode = System.identityHashCode(invokers);
        //等于说selectors里面缓存了 key（服务名+方法）对应的ConsistentHashSelector
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
       //当selector为空，说明这个key对应的服务方法还没有调用过
       //如果selector.identityHashCode != identityHashCode说明invokers发生了动态变化
       //都需要重构ConsistentHashSelector
        if (selector == null || selector.identityHashCode != identityHashCode) {
            selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        //使用选择器针对invocation进行选择，我们可以看到这个selectors的这个缓存是很大的，如果有一万个服务，每个服务一万个方法，那么这个缓存的大小相当的恐怖了，
但是底层使用了currentmap，会自动的进行优化

        return selector.select(invocation);
    }

那接下来我们看下ConsistentHashSelector具体是怎么实现的，如下

 private static final class ConsistentHashSelector<T> {
        //虚拟节点 Long 为其对应的hash环上的值  Invoker为实际对应的invoker
        private final TreeMap<Long, Invoker<T>> virtualInvokers;
       //hash环上的复制节点数
        private final int replicaNumber;
        //此ConsistentHashSelector对应的hash值，用于判断此ConsistentHashSelector是否有过期（如果invokers发生了变化，这个值会失效）
        private final int identityHashCode;
        //根据哪些argumentIndex来计算virtualInvokers里面的Long值
        private final int[] argumentIndex;
}

我们看看其构造函数

ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
            this.identityHashCode = identityHashCode;
            URL url = invokers.get(0).getUrl();
            //缺省160个 
            this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);   
            //缺省使用第一个参数计算hash值
            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]);
            }
           //默认将每个invoker复制160份，分散到hash环
            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);
                    }
                }
            }
        }

我们再看下最核心的一个方法

//直接根据hash值在红黑树上面找到小于hash值的第一个Invoker
//如果没有找到，那么返回第一个（要形成环）
private Invoker<T> selectForKey(long hash) {
            Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
            if (entry == null) {
                entry = virtualInvokers.firstEntry();
            }
            return entry.getValue();
        }

如上，根据treeMap就巧妙的实现了一个一致性hash环。