博客

写在开头

本文是接上篇文章之后的第二篇，主要是一致性hash算法的实现，下面会通过详细注解来描述流程。有不清楚的可以评论留言。

开始正文

首先我们来看下ConsistentHashLoadBalance的核心结构，先有个总体的概念，然后顺着方法调用流程逐步往下讲。

public class ConsistentHashLoadBalance extends AbstractLoadBalance {
    public static final String NAME = "consistenthash";  

    //一个方法对应一个一致性hash选择器
    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) {
        // 精确到方法，最为缓存一致性hash选择器的key
        String methodName = RpcUtils.getMethodName(invocation);
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
        int identityHashCode = System.identityHashCode(invokers);  //基于invoker集合，根据对象内存地址来定义hash值
        //获得ConsistentHashSelector，为空则创建再缓存（要么第一次，要么invokers集合发生了变化，都需要重新创建ConsistentHashSelector）
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        if (selector == null || selector.identityHashCode != identityHashCode) {
            //初始化并缓存一致性hash选择器
            selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        return selector.select(invocation);  //选择一个invoker
    }
    //接下来要讲下一致性hash选择器了
    private static final class ConsistentHashSelector<T> {
        //.....
    }   
}复制代码

上面的doSelect方法主要的作用就是创建和初始化了一致性hash选择器。下面我们看下这个选择器是如何实现负载均衡的。

private static final class ConsistentHashSelector<T> {
    //treemap底层是棵红黑树。
    //红黑树不了解的，可以看下我的博客 https://juejin.im/post/5bef5de46fb9a049c15ecbd9
    private final TreeMap<Long, Invoker<T>> virtualInvokers;

    private final int replicaNumber;  //每个invoker对应的虚拟节点数

    private final int identityHashCode;  //定义hash值

    private final int[] argumentIndex;  //参数位置数组（缺省是第一个参数）

    ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap<Long, Invoker<T>>();  // 虚拟节点与 Invoker 的映射关系
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        //缺省用 160 份虚拟节点，如果要修改，请配置 <dubbo:parameter key="hash.nodes" value="320" />
        this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
        //缺省只对第一个参数 Hash，如果要修改，请配置 <dubbo:parameter key="hash.arguments" value="0,1" />
        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]);
        }
        //初始化virtualInvokers,这样可以最终每个invoker都有replicaNumber个虚拟节点
        for (Invoker<T> invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            //每4个虚拟节点为一组，4个节点一共32位。之所以是32位是因为一致性哈希环取值范围为0～2^32
            for (int i = 0; i < replicaNumber / 4; i++) {
                // 地址加上后缀数字，计算md5值
                byte[] digest = md5(address + i);
                // Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，分别对应一个虚拟结点
                for (int h = 0; h < 4; h++) {
                    //计算hash值，作为key,存储节点
                    long m = hash(digest, h);
                    virtualInvokers.put(m, invoker);
                }
            }
        }
    }

    public Invoker<T> select(Invocation invocation) {
        String key = toKey(invocation.getArguments());  //参数转换为string类型
        byte[] digest = md5(key);  // key md5计算，返回16个字节的byte数组
        // 1、hash(digest, 0)，取前四个字节，计算hash值
        // 2、查找临近节点，获取invoker
        return selectForKey(hash(digest, 0));
    }

    //这个方法太简单
    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> selectForKey(long hash) {
        //返回大于或等于给定键，如果不存在这样的键的键 - 值映射，则返回null相关联(treemap底层是棵红黑树，红黑树不了解的，可以看下我的博客 https://juejin.im/post/5bef5de46fb9a049c15ecbd9 )
        Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
        if (entry == null) {
            //如果不存在，那么可能这个hash值比虚拟节点的最大值还大，那么取第一个。这样就形成了一个环
            entry = virtualInvokers.firstEntry();
        }
        return entry.getValue();
    }

    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[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;
        try {
            bytes = value.getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new IllegalStateException(e.getMessage(), e);
        }
        md5.update(bytes);
        return md5.digest();
    }
}复制代码

小结

其实ConsistentHashLoadBalance就是实现了一致性hash算法，之前了解这种算法的同学可能很轻松就能看懂。dubbo的实现其实也很简单，步骤总结如下：

1、生成虚拟节点：

每个invoker生成replicaNumber个hash值，即产生replicaNumber个虚拟节点。

2、请求者生成hash值

：请求方法进来，会按配置的值，取指定的参数，拼接字符串，生成md5值，再取数组的前4个值生成hash值。

3、取临近节点：

根据步骤2生成的hash值，取treemap中获取大于等于该hash值的节点。如果节点不存在，则取第一个节点（形成环）。

4、返回invoker