Dubbo路由层之LoadBalance随机与轮询

前言

经过分析了Directory以及Router，接下来是到了负载均衡器LoadBalance了。

简述负载均衡

搞后端web的同学一定不会陌生，负载均衡在各个层级都有相应的应用。由于单机应用的性能局限性，在负载高的情况下，通常都会采用增加服务器的形式来横向扩展，通过集群和负载均衡来提高整个系统处理能力。

负载均衡在反向代理层、站点层、服务层、数据层等层级上都有不同的解决方案。dubbo框架就具备解决服务层负载均衡的功能。

dubbo的负载均衡——LoadBalance

LoadBalance家族继承图：

典型的模板方法模式和策略模式。

提供了四种负载均衡实现：

RandomLoadBalance
RoundRobinLoadBalance
LeastActiveLoadBalance
ConsistentHashLoadBalance

关于LoadBalance的接口定义:

@SPI(RandomLoadBalance.NAME)
public interface LoadBalance {

    /**
     * select one invoker in list.
     *
     * @param invokers   invokers.
     * @param url        refer url
     * @param invocation invocation.
     * @return selected invoker.
     */
    @Adaptive("loadbalance")
    <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException;

}

简单明了：从提供者列表里获取一个提供者。还可以看到，默认的负载均衡器是RandomLoadBalance。

基类 AbstractLoadBalance

AbstractLoadBalance是所有负载均衡器的基类，它提供了通用的模板方法select。

public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    if (invokers == null || invokers.isEmpty())
        return null;
    if (invokers.size() == 1)
        return invokers.get(0);
    return doSelect(invokers, url, invocation);
}

其中doSelect是又具体子类实现的。

并且其提供了一个通用的获取权重的方法。权重是数学中的一种概念，比如初中学过的加权平均数就是一种体现。

RandomLoadBalance

随机负载均衡。根据文档描述：

随机，按权重设置随机概率。
在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。

源码如下:

protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    int length = invokers.size(); // Number of invokers
    int totalWeight = 0; // The sum of weights
    boolean sameWeight = true; // Every invoker has the same weight?
    // 1.判断是否权重都相同
    for (int i = 0; i < length; i++) {
        int weight = getWeight(invokers.get(i), invocation);
        totalWeight += weight; // Sum
        if (sameWeight && i > 0
                && weight != getWeight(invokers.get(i - 1), invocation)) {
            sameWeight = false;
        }
    }
    // 2.权重不是都相等，则根据权重获取随机invoker
    if (totalWeight > 0 && !sameWeight) {
        // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on totalWeight.
        int offset = random.nextInt(totalWeight);
        // Return a invoker based on the random value.
        for (int i = 0; i < length; i++) {
            offset -= getWeight(invokers.get(i), invocation); // 随机数与权重相减获取调用节点
            if (offset < 0) {
                return invokers.get(i);
            }
        }
    }
    // If all invokers have the same weight value or totalWeight=0, return evenly.
    // 3.所有权重都相同的情况或者权重为0，则随机获取invoker
    return invokers.get(random.nextInt(length));
}

代码比较简单：
判断是否权重都相同，相同则随机数获取调用者，否则则根据权重和随机数来获取一个调用者。算法是根据总权重获取一个随机数，然后与各个调用者的权重相减直到随机数的值小与0，则使用此节点。

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(); // Number of invokers
    int maxWeight = 0; // The maximum weight
    int minWeight = Integer.MAX_VALUE; // The minimum weight
    final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
    int weightSum = 0;
    for (int i = 0; i < length; i++) {
        int weight = getWeight(invokers.get(i), invocation);
        maxWeight = Math.max(maxWeight, weight); // Choose the maximum weight 1.获取最大权重
        minWeight = Math.min(minWeight, weight); // Choose the minimum weight 2.获取最小权重
        if (weight > 0) {
            invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight)); // 3.invoker和权重大小的映射
            weightSum += weight; // 4.获取总权重
        }
    }
    AtomicPositiveInteger sequence = sequences.get(key); // 此方法的调用序列号
    if (sequence == null) {
        sequences.putIfAbsent(key, new AtomicPositiveInteger()); // 存储方法调用的序列号
        sequence = sequences.get(key);
    }
    int currentSequence = sequence.getAndIncrement(); // 序列号+1
    if (maxWeight > 0 && minWeight < maxWeight) { // 如果权重不一样
        int mod = currentSequence % weightSum;
        for (int i = 0; i < maxWeight; i++) {
            for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) {
                final Invoker<T> k = each.getKey();
                final IntegerWrapper v = each.getValue();
                if (mod == 0 && v.getValue() > 0) {
                    return k;
                }
                if (v.getValue() > 0) {
                    v.decrement();
                    mod--;
                }
            }
        }
    }
    // Round robin
    // 权重相同，则直接轮询即可
    return invokers.get(currentSequence % length);
}

控制台设置负载均衡算法：

debug界面：

这个加权算法过程(即代码注释权重不同情况)看着有点懵，大致是:

获取最大权重、计算权重和
调用序列号对权重和取余获取到mod值
mod值为0且invoker对象权重大于0满足条件返回
如果mod值大于0且invoker对象权重大于0则mod值递减，权重值递减
重复3，4过程。

还是很懵，举例演示一下过程。假设提供service{a,b,c}三台，权重分别为{1,2,3}，那么情况如下：

最大权重 = 3，总权重和 = 6。

调用序列号	mod值	返回服务名称	各服务权重
1	0	a	a:1, b:2, c:3
2	1,再进行1次递减	b	a:0, b:2, c:3
3	2,再进行2次递减	c	a:0, b:1, c:3
4	3,再进行3次递减	b	a:0, b:1, c:2
5	4,再进行4次递减	c	a:0, b:0, c:2
6	5,再进行5次递减	c	a:0, b:0, c:1
7	0	a	a:1, b:2, c:3
…	…	…	…

运行算法过程如上，细心的你一定会发现这个算法很不合理，不合理的地方在于调用次数很大时，调用序列号达到假如一千万次，那么获取到的mod值则会非常大，那么doSelect方法循环的次数也会这么大，时间复杂度O(N)，再加上最大权重数maxWeight如果也设置很大，那么性能很受影响。

这个问题被dubbo关注者指出了，详见issue#2578，新的版本也修复了这个问题，具体详见新版本的代码。

除此之外，dubbo官方也指出了这个这种负载的缺点，即：存在慢的提供者累积请求的问题。如果选择此种负载均衡，需要把性能差的机器权重设置低一些。