Dubbo负载均衡算法实现

负载均衡策略

Dubbo目前主要提供下列四种负载均衡算法：

1.RandomLoadBalance：

随机负载均衡算法，Dubbo默认的负载均衡策略。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // 总个数
        int totalWeight = 0; // 总权重
        boolean sameWeight = true; // 权重是否都一样
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            totalWeight += weight; // 累计总权重
            if (sameWeight && i > 0
                    && weight != getWeight(invokers.get(i - 1), invocation)) {
                sameWeight = false; // 计算所有权重是否一样
            }
        }
        if (totalWeight > 0 && ! sameWeight) {
            // 如果权重不相同且权重大于0则按总权重数随机
            int offset = random.nextInt(totalWeight);
            // 并确定随机值落在哪个片断上
            for (int i = 0; i < length; i++) {
                offset -= getWeight(invokers.get(i), invocation);
                if (offset < 0) {
                    return invokers.get(i);
                }
            }
        }
        // 如果权重相同或权重为0则均等随机
        return invokers.get(random.nextInt(length));
    }

我们现在假设集群有四个节点分别对应的权重为{A:1,B:2,C:3,D:4｝，分别将权重套入到代码中进行分析，该随机算法按总权重进行加权随机，A节点负载请求的概率为1/(1+2+3+4)，依次类推，B，C，D负载的请求概率分别是20%，30%，40%。在这种方式下，用户可以根据机器的实际性能动态调整权重比率，如果发现机器D负载过大，请求堆积过多，通过调整权重可以缓解机器D处理请求的压力。

2.RoundRobinLoadBalance：

轮询负载均衡算法，按公约后的权重设置轮循比率。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        int length = invokers.size(); // 总个数
        int maxWeight = 0; // 最大权重
        int minWeight = Integer.MAX_VALUE; // 最小权重
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            maxWeight = Math.max(maxWeight, weight); // 累计最大权重
            minWeight = Math.min(minWeight, weight); // 累计最小权重
        }
        if (maxWeight > 0 && minWeight < maxWeight) { // 权重不一样
            AtomicPositiveInteger weightSequence = weightSequences.get(key);
            if (weightSequence == null) {
                weightSequences.putIfAbsent(key, new AtomicPositiveInteger());
                weightSequence = weightSequences.get(key);
            }
            int currentWeight = weightSequence.getAndIncrement() % maxWeight;
            List<Invoker<T>> weightInvokers = new ArrayList<Invoker<T>>();
            for (Invoker<T> invoker : invokers) { // 筛选权重大于当前权重基数的Invoker
                if (getWeight(invoker, invocation) > currentWeight) {
                    weightInvokers.add(invoker);
                }
            }
            int weightLength = weightInvokers.size();
            if (weightLength == 1) {
                return weightInvokers.get(0);
            } else if (weightLength > 1) {
                invokers = weightInvokers;
                length = invokers.size();
            }
        }
        AtomicPositiveInteger sequence = sequences.get(key);
        if (sequence == null) {
            sequences.putIfAbsent(key, new AtomicPositiveInteger());
            sequence = sequences.get(key);
        }
        // 取模轮循
        return invokers.get(sequence.getAndIncrement() % length);
    }

分析算法我们能够发现，新的请求默认均负载到一个节点上。后续分析主要是针对同一个服务的同一个方法。我们现在假设集群有四个节点分别对应的权重为{A:1,B:3,C:5,D:7｝，分别将权重套入到代码中进行分析，此时存在一个基础权重集合，每次请求的时候将大于当前权重基数的提供者放入到基础权重集合中，然后从基础权重集合中按照轮询比率负载到实际的服务提供者上:

对于第一个请求， 此时基础集合中有{A，B，C，D｝四个节点，此时按照实际的轮询比率，获取第invokers.get(0%4)个节点，即获取节点A负载请求。

对于第二个请求，此时基础集合中只包含{B，C，D｝三个节点，将获取第invokers.get(1%3)个节点，即获取节点C负载请求。

对于第三个请求，此时基础集合中只包含{B，C，D｝三个节点，将获取第invokers.get(2%3)个节点，即获取节点D负载请求。

......

依次类推，能够发现，这种模式下，在权重设置不合理的情况下，会导致某些节点无法负载请求，另外，如果有些机器性能比较低，会存在请求阻塞的情况。

3.LeastActiveLoadBalance：

最少活跃数负载均衡算法，对于同一个服务的同一个方法，会将请求负载到该请求活跃数最少的节点上，如果节点上活跃数相同，则随机负载。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // 总个数
        int leastActive = -1; // 最小的活跃数
        int leastCount = 0; // 相同最小活跃数的个数
        int[] leastIndexs = new int[length]; // 相同最小活跃数的下标
        int totalWeight = 0; // 总权重
        int firstWeight = 0; // 第一个权重，用于于计算是否相同
        boolean sameWeight = true; // 是否所有权重相同
        for (int i = 0; i < length; i++) {
            Invoker<T> invoker = invokers.get(i);
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); // 活跃数
            int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT); // 权重
            if (leastActive == -1 || active < leastActive) { // 发现更小的活跃数，重新开始
                leastActive = active; // 记录最小活跃数
                leastCount = 1; // 重新统计相同最小活跃数的个数
                leastIndexs[0] = i; // 重新记录最小活跃数下标
                totalWeight = weight; // 重新累计总权重
                firstWeight = weight; // 记录第一个权重
                sameWeight = true; // 还原权重相同标识
            } else if (active == leastActive) { // 累计相同最小的活跃数
                leastIndexs[leastCount ++] = i; // 累计相同最小活跃数下标
                totalWeight += weight; // 累计总权重
                // 判断所有权重是否一样
                if (sameWeight && i > 0 
                        && weight != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // assert(leastCount > 0)
        if (leastCount == 1) {
            // 如果只有一个最小则直接返回
            return invokers.get(leastIndexs[0]);
        }
        if (! sameWeight && totalWeight > 0) {
            // 如果权重不相同且权重大于0则按总权重数随机
            int offsetWeight = random.nextInt(totalWeight);
            // 并确定随机值落在哪个片断上
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexs[i];
                offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
                if (offsetWeight <= 0)
                    return invokers.get(leastIndex);
            }
        }
        // 如果权重相同或权重为0则均等随机
        return invokers.get(leastIndexs[random.nextInt(leastCount)]);
    }

思路主要是，获取最小的活跃数，把活跃数等于最小活跃数的调用者维护成一个数组

如果权重一致随机取出，如果不同则跟随机负载均衡一致，累加权重，然后随机取出。

即一共维护了两个数组，假设最小活跃数数组为{A:2，B:2，C:3，D:4｝，权重数组为{A:2，B:3，C:4，D:5｝，那么最终将A节点负载的概率为40%，B节点负载的概率为60%

4.ConsistentHashLoadBalance:

一致性Hash，相同参数的请求总是发到同一提供者。

当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。

public class ConsistentHashLoadBalance extends AbstractLoadBalance {
    private static final class ConsistentHashSelector<T> {
        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);
                    }
                }
            }
        }
        public Invoker<T> select(Invocation invocation) {
            String key = toKey(invocation.getArguments());
            byte[] digest = md5(key);
            Invoker<T> invoker = sekectForKey(hash(digest, 0));
            return invoker;
        }
    }
}

构造函数中，每个实际的提供者均有160个(默认值，可调整)虚拟节点，每个提供者对应的虚拟节点将平均散列到哈希环上，当有请求时，先计算该请求参数对应的哈希值，然后顺时针寻找最近的虚拟节点，得到实际的提供者节点。

以上就是动力节点小编介绍的"Dubbo负载均衡算法实现"，希望对大家有帮助，想了解更多可查看Dubbo教程。动力节点在线学习教程，针对没有任何Java基础的读者学习,让你从入门到精通,主要介绍了一些Java基础的核心知识，让同学们更好更方便的学习和了解Java编程，感兴趣的同学可以关注一下。