2.2 LeastActiveLoadBalance

LeastActiveLoadBalance 翻译过来是最小活跃数负载均衡。活跃调用数越小，表明该服务提供者效率越高，单位时间内可处理更多的请求。此时应优先将请求分配给该服务提供者。在具体实现中，每个服务提供者对应一个活跃数 active。初始情况下，所有服务提供者活跃数均为0。每收到一个请求，活跃数加1，完成请求后则将活跃数减1。在服务运行一段时间后，性能好的服务提供者处理请求的速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求、这就是最小活跃数负载均衡算法的基本思想。除了最小活跃数，LeastActiveLoadBalance 在实现上还引入了权重值。所以准确的来说，LeastActiveLoadBalance 是基于加权最小活跃数算法实现的。举个例子说明一下，在一个服务提供者集群中，有两个性能优异的服务提供者。某一时刻它们的活跃数相同，此时 Dubbo 会根据它们的权重去分配请求，权重越大，获取到新请求的概率就越大。如果两个服务提供者权重相同，此时随机选择一个即可。关于 LeastActiveLoadBalance 的背景知识就先介绍到这里，下面开始分析源码。

  1. public class LeastActiveLoadBalance extends AbstractLoadBalance {
  3.     public static final String NAME = "leastactive";
  5.     private final Random random = new Random();
  7.     @Override
  8.     protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
  9.         int length = invokers.size();
  10.         // 最小的活跃数
  11.         int leastActive = -1;
  12.         // 具有相同“最小活跃数”的服务者提供者（以下用 Invoker 代称）数量
  13.         int leastCount = 0; 
  14.         // leastIndexs 用于记录具有相同“最小活跃数”的 Invoker 在 invokers 列表中的下标信息
  15.         int[] leastIndexs = new int[length];
  16.         int totalWeight = 0;
  17.         // 第一个最小活跃数的 Invoker 权重值，用于与其他具有相同最小活跃数的 Invoker 的权重进行对比，
  18.         // 以检测是否“所有具有相同最小活跃数的 Invoker 的权重”均相等
  19.         int firstWeight = 0;
  20.         boolean sameWeight = true;
  22.         // 遍历 invokers 列表
  23.         for (int i = 0; i < length; i++) {
  24.             Invoker<T> invoker = invokers.get(i);
  25.             // 获取 Invoker 对应的活跃数
  26.             int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
  27.             // 获取权重 - ⭐️
  28.             int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);
  29.             // 发现更小的活跃数，重新开始
  30.             if (leastActive == -1 || active < leastActive) {
  31.                 // 使用当前活跃数 active 更新最小活跃数 leastActive
  32.                 leastActive = active;
  33.                 // 更新 leastCount 为 1
  34.                 leastCount = 1;
  35.                 // 记录当前下标值到 leastIndexs 中
  36.                 leastIndexs[0] = i;
  37.                 totalWeight = weight;
  38.                 firstWeight = weight;
  39.                 sameWeight = true;
  41.             // 当前 Invoker 的活跃数 active 与最小活跃数 leastActive 相同 
  42.             } else if (active == leastActive) {
  43.                 // 在 leastIndexs 中记录下当前 Invoker 在 invokers 集合中的下标
  44.                 leastIndexs[leastCount++] = i;
  45.                 // 累加权重
  46.                 totalWeight += weight;
  47.                 // 检测当前 Invoker 的权重与 firstWeight 是否相等，
  48.                 // 不相等则将 sameWeight 置为 false
  49.                 if (sameWeight && i > 0
  50.                     && weight != firstWeight) {
  51.                     sameWeight = false;
  52.                 }
  53.             }
  54.         }
  56.         // 当只有一个 Invoker 具有最小活跃数，此时直接返回该 Invoker 即可
  57.         if (leastCount == 1) {
  58.             return invokers.get(leastIndexs[0]);
  59.         }
  61.         // 有多个 Invoker 具有相同的最小活跃数，但它们之间的权重不同
  62.         if (!sameWeight && totalWeight > 0) {
  63.             // 随机生成一个 [0, totalWeight) 之间的数字
  64.             int offsetWeight = random.nextInt(totalWeight);
  65.             // 循环让随机数减去具有最小活跃数的 Invoker 的权重值，
  66.             // 当 offset 小于等于0时，返回相应的 Invoker
  67.             for (int i = 0; i < leastCount; i++) {
  68.                 int leastIndex = leastIndexs[i];
  69.                 // 获取权重值，并让随机数减去权重值 - ⭐️
  70.                 offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
  71.                 if (offsetWeight <= 0)
  72.                     return invokers.get(leastIndex);
  73.             }
  74.         }
  75.         // 如果权重相同或权重为0时，随机返回一个 Invoker
  76.         return invokers.get(leastIndexs[random.nextInt(leastCount)]);
  77.     }
  78. }

上面代码的逻辑比较多，我们在代码中写了大量的注释，有帮助大家理解代码逻辑。下面简单总结一下以上代码所做的事情，如下：

  1. 遍历 invokers 列表，寻找活跃数最小的 Invoker
  2. 如果有多个 Invoker 具有相同的最小活跃数，此时记录下这些 Invoker 在 invokers 集合中的下标，并累加它们的权重，比较它们的权重值是否相等
  3. 如果只有一个 Invoker 具有最小的活跃数，此时直接返回该 Invoker 即可
  4. 如果有多个 Invoker 具有最小活跃数，且它们的权重不相等，此时处理方式和 RandomLoadBalance 一致
  5. 如果有多个 Invoker 具有最小活跃数，但它们的权重相等，此时随机返回一个即可

以上就是 LeastActiveLoadBalance 大致的实现逻辑，大家在阅读的源码的过程中要注意区分活跃数与权重这两个概念，不要混为一谈。

以上分析是基于 Dubbo 2.6.4 版本进行的，由于近期 Dubbo 2.6.5 发布了，并对 LeastActiveLoadBalance 进行了一些修改，下面简单来介绍一下修改内容。回到上面的源码中，我们在上面的代码中标注了两个黄色的五角星⭐️。两处标记对应的代码分别如下：

  1. int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);
  1. offsetWeight -= getWeight(invokers.get(leastIndex), invocation);

问题出在服务预热阶段，第一行代码直接从 url 中取权重值，未被降权过。第二行代码获取到的是经过降权后的权重。第一行代码获取到的权重值最终会被累加到权重总和 totalWeight 中，这个时候会导致一个问题。offsetWeight 是一个在 [0, totalWeight) 范围内的随机数，而它所减去的是经过降权的权重。很有可能在经过 leastCount 次运算后，offsetWeight 仍然是大于0的，导致无法选中 Invoker。这个问题对应的 issue 为 #904，并在 pull request #2172 中被修复。具体的修复逻辑是将标注一处的代码修改为：

  1. // afterWarmup 等价于上面的 weight 变量，这样命名是为了强调该变量经过了 warmup 降权处理
  2. int afterWarmup = getWeight(invoker, invocation);

另外，2.6.4 版本中的 LeastActiveLoadBalance 还有一个缺陷，即当一组 Invoker 具有相同的最小活跃数，且其中一个 Invoker 的权重值为1，此时这个 Invoker 无法被选中。缺陷代码如下：

  1. int offsetWeight = random.nextInt(totalWeight);
  2. for (int i = 0; i < leastCount; i++) {
  3.     int leastIndex = leastIndexs[i];
  4.     offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
  5.     if (offsetWeight <= 0)    // ❌
  6.         return invokers.get(leastIndex);
  7. }

问题出在了offsetWeight <= 0上，举例说明，假设有一组 Invoker 的权重为 5、2、1，offsetWeight 最大值为 7。假设 offsetWeight = 7，你会发现，当 for 循环进行第二次遍历后 offsetWeight = 7 - 5 - 2 = 0，提前返回了。此时，此时权重为1的 Invoker 就没有机会被选中了。该问题在 Dubbo 2.6.5 中被修复了，修改后的代码如下：

  1. int offsetWeight = random.nextInt(totalWeight) + 1;

以上就是 Dubbo 2.6.5 对 LeastActiveLoadBalance 的更新，内容不是很多，先分析到这。接下来分析基于一致性 hash 思想的 ConsistentHashLoadBalance。