Dubbo源码学习--ConsistentHashLoadBalance负载均衡（五）

短命女 2022-05-28 00:45 193阅读 0赞

### ConsistentHash LoadBalance ###

*  **一致性 Hash**，相同参数的请求总是发到同一提供者。
 *  当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
 *  算法参见：[http://en.wikipedia.org/wiki/Consistent\_hashing][http_en.wikipedia.org_wiki_Consistent_hashing]
 *  缺省只对第一个参数 Hash，如果要修改，请配置 `<dubbo:parameter key="hash.arguments" value="0,1" />`

*  缺省用 160 份虚拟节点，如果要修改，请配置 `<dubbo:parameter key="hash.nodes" value="320" />`

一致性Hash负载均衡涉及到两个主要的配置参数为**hash.arguments** 与**hash.nodes**。

**hash.arguments** ： 当进行调用时候根据调用方法的哪几个参数生成key，并根据key来通过一致性hash算法来选择调用结点。例如调用方法invoke(String s1,String s2); 若hash.arguments为1(默认值)，则仅取invoke的参数1（s1）来生成hashCode。

**hash.nodes**： 为结点的副本数。

缺省只对第一个参数Hash，如果要修改，请配置
    <dubbo:parameter key="hash.arguments" value="0,1" />
    
    缺省用160份虚拟节点，如果要修改，请配置
    <dubbo:parameter key="hash.nodes" value="320" />

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7

# Dubbo中一致性Hash的实现分析 #

dubbo的[一致性哈希][Link 1]通过ConsistentHashLoadBalance类来实现。

ConsistentHashLoadBalance内部定义ConsistentHashSelector类，最终通过该类进行结点选择。ConsistentHashLoadBalance实现的doSelect方法来利用所创建的ConsistentHashSelector对象选择结点。

doSelect的实现如下。当调用该方法时，如果选择器不存在则去创建。随后通过ConsistentHashSelector的select方法选择结点。

@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();
            // 生成调用列表hashCode
            int identityHashCode = System.identityHashCode(invokers);
            // 以调用方法名为key,获取一致性hash选择器
            ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
            // 若不存在则创建新的选择器
            if (selector == null || selector.getIdentityHashCode() != identityHashCode) {
                // 创建ConsistentHashSelector时会生成所有虚拟结点
                selectors.put(key, new ConsistentHashSelector<T>(invokers, invocation.getMethodName(), identityHashCode));
                // 获取选择器
                selector = (ConsistentHashSelector<T>) selectors.get(key);
            }
            // 选择结点
            return selector.select(invocation);
        }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19

ConsistentHashSelector在构造函数内部会创建replicaNumber个虚拟结点，并将这些虚拟结点存储于TreeMap。随后根据调用方法的参数来生成key，并在TreeMap中选择一个结点进行调用。

private static final class ConsistentHashSelector<T> {
    
            private final TreeMap<Long, Invoker<T>> virtualInvokers; // 虚拟结点
    
            private final int                       replicaNumber;   // 副本数 
    
            private final int                       identityHashCode;// hashCode
    
            private final int[]                     argumentIndex;   // 参数索引数组
    
            public ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
                // 创建TreeMap 来保存结点
                this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
                // 生成调用结点HashCode
                this.identityHashCode = System.identityHashCode(invokers);
                // 获取Url 
                // dubbo://169.254.90.37: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
                this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
                // 获取需要进行hash的参数数组索引，默认对第一个参数进行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生成replicaNumber个虚拟结点，并存放于TreeMap中
                for (Invoker<T> invoker : invokers) {
    
                    for (int i = 0; i < replicaNumber / 4; i++) {
                        // 根据md5算法为每4个结点生成一个消息摘要，摘要长为16字节128位。
                        byte[] digest = md5(invoker.getUrl().toFullString() + i);
                        // 随后将128位分为4部分，0-31,32-63,64-95,95-128，并生成4个32位数，存于long中，long的高32位都为0
                        // 并作为虚拟结点的key。
                        for (int h = 0; h < 4; h++) {
                            long m = hash(digest, h);
                            virtualInvokers.put(m, invoker);
                        }
                    }
                }
            }
    
            public int getIdentityHashCode() {
                return identityHashCode;
            }
    
            // 选择结点
            public Invoker<T> select(Invocation invocation) {
                // 根据调用参数来生成Key
                String key = toKey(invocation.getArguments());
                // 根据这个参数生成消息摘要
                byte[] digest = md5(key);
                //调用hash(digest, 0)，将消息摘要转换为hashCode，这里仅取0-31位来生成HashCode
                //调用sekectForKey方法选择结点。
                Invoker<T> invoker = sekectForKey(hash(digest, 0));
                return invoker;
            }
    
            private String toKey(Object[] args) {
                StringBuilder buf = new StringBuilder();
                // 由于hash.arguments没有进行配置，因为只取方法的第1个参数作为key
                for (int i : argumentIndex) {
                    if (i >= 0 && i < args.length) {
                        buf.append(args[i]);
                    }
                }
                return buf.toString();
            }
    
            //根据hashCode选择结点
            private Invoker<T> sekectForKey(long hash) {
                Invoker<T> invoker;
                Long key = hash;
                // 若HashCode直接与某个虚拟结点的key一样，则直接返回该结点
                if (!virtualInvokers.containsKey(key)) {
                    // 若不一致，找到一个最小上届的key所对应的结点。
                    SortedMap<Long, Invoker<T>> tailMap = virtualInvokers.tailMap(key);
                    // 若存在则返回，例如hashCode落在图中[1]的位置
                    // 若不存在，例如hashCode落在[2]的位置，那么选择treeMap中第一个结点
                    // 使用TreeMap的firstKey方法，来选择最小上界。
                    if (tailMap.isEmpty()) {
                        key = virtualInvokers.firstKey();
                    } else {
    
                        key = tailMap.firstKey();
                    }
                }
                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();
            }
    
        }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24
 *  25
 *  26
 *  27
 *  28
 *  29
 *  30
 *  31
 *  32
 *  33
 *  34
 *  35
 *  36
 *  37
 *  38
 *  39
 *  40
 *  41
 *  42
 *  43
 *  44
 *  45
 *  46
 *  47
 *  48
 *  49
 *  50
 *  51
 *  52
 *  53
 *  54
 *  55
 *  56
 *  57
 *  58
 *  59
 *  60
 *  61
 *  62
 *  63
 *  64
 *  65
 *  66
 *  67
 *  68
 *  69
 *  70
 *  71
 *  72
 *  73
 *  74
 *  75
 *  76
 *  77
 *  78
 *  79
 *  80
 *  81
 *  82
 *  83
 *  84
 *  85
 *  86
 *  87
 *  88
 *  89
 *  90
 *  91
 *  92
 *  93
 *  94
 *  95
 *  96
 *  97
 *  98
 *  99
 *  100
 *  101
 *  102
 *  103
 *  104
 *  105
 *  106
 *  107
 *  108
 *  109
 *  110
 *  111
 *  112
 *  113
 *  114
 *  115
 *  116
 *  117
 *  118
 *  119

上述代码中 hash(byte\[\] digest, int number)方法用来生成hashCode。该函数将生成的结果转换为long类，这是因为生成的结果是一个32位数，若用int保存可能会产生负数。而一致性hash生成的逻辑环其hashCode的范围是在 0 - MAX\_VALUE之间。因此为正整数，所以这里要强制转换为long类型，避免出现负数。

进行结点选择的方法为select,最后通过sekectForKey方法来选择结点。

// 选择结点
            public Invoker<T> select(Invocation invocation) {
                // 根据调用参数来生成Key
                String key = toKey(invocation.getArguments());
                // 根据这个参数生成消息摘要
                byte[] digest = md5(key);
                //调用hash(digest, 0)，将消息摘要转换为hashCode，这里仅取0-31位来生成HashCode
                //调用sekectForKey方法选择结点。
                Invoker<T> invoker = sekectForKey(hash(digest, 0));
                return invoker;
            }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11

sekectForKey方法的实现如下。

private Invoker<T> sekectForKey(long hash) {
                Invoker<T> invoker;
                Long key = hash;
                // 若HashCode直接与某个虚拟结点的key一样，则直接返回该结点
                if (!virtualInvokers.containsKey(key)) {
                    // 若不在，找到一个最小上届的key所对应的结点。
                    SortedMap<Long, Invoker<T>> tailMap = virtualInvokers.tailMap(key);
                    // 若存在则返回，例如hashCode落在图中[1]的位置
                    // 若不存在，例如hashCode落在[2]的位置，那么选择treeMap中第一个结点
                    // 使用TreeMap的firstKey方法，来选择最小上界。
                    if (tailMap.isEmpty()) {
                        key = virtualInvokers.firstKey();
                    } else {
    
                        key = tailMap.firstKey();
                    }
                }
                invoker = virtualInvokers.get(key);
                return invoker;
            }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20

在进行选择时候若HashCode直接与某个虚拟结点的key一样，则直接返回该结点，例如hashCode落在某个结点上(圆圈所表示)。若不在，找到一个最小上届的key所对应的结点。例如进行选择时的key落在图中1所标注的位置。由于利用TreeMap存储，key所落在的位置可能无法找到最小上界，例如图中2所标注的位置。那么需要返回TreeMap中的最小值（构成逻辑环状结构，找不到，则返回最开头的结点）。   
![这里写图片描述][SouthEast]

[http_en.wikipedia.org_wiki_Consistent_hashing]: http://en.wikipedia.org/wiki/Consistent_hashing
[Link 1]: https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=0&rsv_idx=1&tn=baidu&wd=%E4%B8%80%E8%87%B4%E6%80%A7hash%20java%E5%AE%9E%E7%8E%B0&rsv_pq=85112d6c00002723&rsv_t=f8ce1BZNAhUnrUFtKDyyQaCCYI3/xks1OBqkZGhCj%2BDvm2foWitaPcobSNI&rqlang=cn&rsv_enter=1&rsv_sug3=12&rsv_sug1=10&rsv_sug7=100
[SouthEast]: /images/20220528/372e6b4d9ef04c65ace9519250a96193.png