本文基于 Dubbo 2.6.1 版本，望知悉。
1. 概述
本文接 《精尽 Dubbo 源码解析 —— 集群容错（三）之 Directory 实现》 一文，分享 dubbo-cluster 模块， loadbalance 包，各种 LoadBalance 实现类。
LoadBalance 子类如下图：
LoadBalance 子类
我们可以看到，目前一共有四个子类，意味着内置了四种负载均衡的选择算法。
老艿艿：本文对应 《Dubbo 用户指南 —— 负载均衡》 文档。
2. LoadBalance
com.alibaba.dubbo.rpc.cluster.LoadBalance ， LoadBalance 接口。代码如下：
(RandomLoadBalance.NAME) |
@SPI(RandomLoadBalance.NAME)注解，Dubbo SPI 拓展点，默认为"random"，即随机。@Adaptive注解，基于 Dubbo SPI Adaptive 机制，加载对应的 Cluster 实现，使用URL.loadbalance属性。#selectList<Invoker<T>>, URL, Invocation)接口方法，从 Invoker 集合中，选择一个。
3. AbstractLoadBalance
com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance ，实现 LoadBalance 接口，LoadBalance 抽象类，提供了权重计算的功能。
3.1 select
#select(List<Invoker<T>>, URL, Invocation) 实现方法，默认只有一个 Invoker 时，直接选择返回。代码如下：
|
子类实现
#doSelect(List<Invoker<T>>, URL, Invocation)抽象方法，提供自定义的负载均衡策略。protected abstract <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation);
3.2 getWeight
protected int getWeight(Invoker<?> invoker, Invocation invocation) { |
考虑到 JVM 自身会有预热的过程，所以服务提供者一启动就直接承担 100% 的流量，可能会出现很吃力的情况。因此权重的计算，默认自带了预热的过程。
#calculateWarmupWeight(uptime, warmup, weight)静态方法，代码如下：static int calculateWarmupWeight(int uptime, int warmup, int weight) {
// 计算权重
int ww = (int) ((float) uptime / ((float) warmup / (float) weight));
// 权重范围为 [0, weight] 之间
return ww < 1 ? 1 : (ww > weight ? weight : ww);
}- 计算权重的代码这么写看起来比较“绕”，我们来修改成
(uptime / warmup) * weight，是否就好理解多了，相当于进度百分比 * 权重。 如下是我飞哥举的一个例子，感觉非常赞。
根据calculateWarmupWeight()方法实现可知，随着provider的启动时间越来越长，慢慢提升权重直到weight，且权重最小值为1，所以：
- 如果 provider 运行了 1 分钟，那么 weight 为 10，即只有最终需要承担的 10% 流量；
- 如果 provider 运行了 2 分钟，那么 weight 为 20，即只有最终需要承担的 20% 流量；
- 如果 provider 运行了 5 分钟，那么 weight 为 50，即只有最终需要承担的 50% 流量；
… … - 如果 provider 运行了 10 分钟，那么 weight 为 100，即只有最终需要承担的 100% 流量；
- 计算权重的代码这么写看起来比较“绕”，我们来修改成
"weight"配置项，默认为 100 。"warmup"配置项，默认为 10*60*1000 = 10 分钟。
4. RandomLoadBalance
com.alibaba.dubbo.rpc.cluster.loadbalance.RandomLoadBalance ，实现 AbstractLoadBalance 抽象类，随机，按权重设置随机概率。
在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。
1: public class RandomLoadBalance extends AbstractLoadBalance { |
- 第 12 至 19 行：计算总权重，并判断所有 Invoker 是否相同权重。
- 第 20 至 33 行：权重不相等，随机权重后，判断在哪个 Invoker 的权重区间中。
- 第 36 行：权重相等，直接随机选择 Invoker 即可。相等于对【第 20 至 33 行】的优化。
算法说明
FROM 飞哥的 《dubbo源码-负载均衡》
假定有3台dubbo provider:
- 10.0.0.1:20884, weight=2
- 10.0.0.1:20886, weight=3
- 10.0.0.1:20888, weight=4
随机算法的实现：
totalWeight=9;
- 假设offset=1（即random.nextInt(9)=1）
1-2=-1<0？是，所以选中 10.0.0.1:20884, weight=2- 假设offset=4（即random.nextInt(9)=4）
4-2=2<0？否，这时候offset=2， 2-3<0？是，所以选中 10.0.0.1:20886, weight=3- 假设offset=7（即random.nextInt(9)=7）
7-2=5<0？否，这时候offset=5， 5-3=2<0？否，这时候offset=2， 2-4<0？是，所以选中 10.0.0.1:20888, weight=4
5. RoundRobinLoadBalance
com.alibaba.dubbo.rpc.cluster.loadbalance.RoundRobinLoadBalance ，实现 AbstractLoadBalance 抽象类，轮循，按公约后的权重设置轮循比率。
存在慢的提供者累积请求的问题，比如：第二台机器很慢，但没挂，当请求调到第二台时就卡在那，久而久之，所有请求都卡在调到第二台上。
1: public class RoundRobinLoadBalance extends AbstractLoadBalance { |
第 18 行：
invokerToWeightMap变量，Invoker 与其权重的映射。其中，IntegerWrapper 为 RoundRobinLoadBalance 的内部类。代码如下：private static final class IntegerWrapper {
// 权重值
private int value;
// ... 省略 构造 / getting / setting 方法
// 扣除一
public void decrement() {
this.value--;
}
}第 20 至 29 行：计算最小、最大权重，总的权重和，并初始化
invokerToWeightMap。- 其中，最小权重用来判断，所有 Invoker 的权重是否都相等。
- 第 30 至 35 行：获得对应的 AtomicPositiveInteger 对象，作为顺序计数器。
- 第 37 行：获得当前顺序号，并递增 + 1 。注意，递增要放后面，不然就不是从头开始了。
- 第 38 至 56 行：权重不相等，顺序根据权重分配。因为顺序分配的过程需要考虑权重，所以看起来比较“绕”。我们可以理解成：
- 顺序发
mod次牌 - 每向一个 Invoker 发一次牌，它的剩余
weight减一。当且仅当向有剩余weight的 Invoker 发牌。 - 当没有可发的
mod牌时，选择该 Invoker 。
- 顺序发
- 第 59 行：权重相等，直接平均顺序分配。相等于对【第 38 至 56 行】的优化。
FROM 飞哥的 《dubbo源码-负载均衡》
假定有3台权重都一样的dubbo provider:
- 10.0.0.1:20884, weight=100
- 10.0.0.1:20886, weight=100
- 10.0.0.1:20888, weight=100
轮询算法的实现：
其调用方法某个方法(key)的 sequence 从 0 开始：
- sequence=0时，选择invokers.get(0%3)=10.0.0.1:20884
- sequence=1时，选择invokers.get(1%3)=10.0.0.1:20886
- sequence=2时，选择invokers.get(2%3)=10.0.0.1:20888
- sequence=3时，选择invokers.get(3%3)=10.0.0.1:20884
- sequence=4时，选择invokers.get(4%3)=10.0.0.1:20886
- sequence=5时，选择invokers.get(5%3)=10.0.0.1:20888
如果有3台权重不一样的dubbo provider：
- 10.0.0.1:20884, weight=50
- 10.0.0.1:20886, weight=100
- 10.0.0.1:20888, weight=150
调试过很多次，这种情况下有问题；留一个TODO；
6. LeastActiveLoadBalance
com.alibaba.dubbo.rpc.cluster.loadbalance.LeastActiveLoadBalance ，实现 AbstractLoadBalance 抽象类，最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差。
使慢的提供者收到更少请求，因为越慢的提供者的调用前后计数差会越大。
相比来说，LeastActiveLoadBalance 是 RandomLoadBalance 的加强版，基于最少活跃调用数。
1: public class LeastActiveLoadBalance extends AbstractLoadBalance { |
- 第 16 至 36 行：计算获得相同最小活跃数的数组(
leastIndexes)和个数(leastCount)。注意，leastIndexes是重用的，所以需要leastCount作为下标。- 每个 Invoker 的活跃数计算，通过 RpcStatus ，在 《精尽 Dubbo 源码分析 —— 过滤器（四）之 ActiveLimitFilter && ExecuteLimitFilter》 已经有详细解析。
- 第 38 行：如果只有一个最小则直接返回。
- ========== 如下部分，和 RandomLoadBalance 类似 ==========
- 第 42 至 53 行：权重不相等，随机权重后，判断在哪个 Invoker 的权重区间中。
- 第 55 行：权重相等，直接随机选择 Invoker 即可。相等于对【第 42 至 53 行】的优化。
算法说明
FROM 飞哥的 《dubbo源码-负载均衡》
最小活跃数算法实现：
假定有3台dubbo provider:
- 10.0.0.1:20884, weight=2，active=2
- 10.0.0.1:20886, weight=3，active=4
- 10.0.0.1:20888, weight=4，active=3
active=2最小，且只有一个2，所以选择10.0.0.1:20884
假定有3台dubbo provider:
- 10.0.0.1:20884, weight=2，active=2
- 10.0.0.1:20886, weight=3，active=2
- 10.0.0.1:20888, weight=4，active=3
active=2最小，且有2个，所以从[10.0.0.1:20884,10.0.0.1:20886 ]中选择；接下来的算法与随机算法类似：
- 假设offset=1（即random.nextInt(5)=1）
1-2=-1<0？是，所以选中 10.0.0.1:20884, weight=2- 假设offset=4（即random.nextInt(5)=4）
4-2=2<0？否，这时候offset=2， 2-3<0？是，所以选中 10.0.0.1:20886, weight=3
7. ConsistentHashLoadBalance
com.alibaba.dubbo.rpc.cluster.loadbalance.ConsistentHashLoadBalance ，实现 AbstractLoadBalance 抽象类，一致性 Hash，相同参数的请求总是发到同一提供者。
当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
1: public class ConsistentHashLoadBalance extends AbstractLoadBalance { |
- 第 15 行：调用
System#identityHashCode(Object)方法，基于invokers集合，根据对象内存地址来计算定义哈希值。 - 第 16 至 21 行：获得 ConsistentHashSelector 对象。若为空，或者定义哈希值变更（说明
invokers集合发生变化），进行创建新的 ConsistentHashSelector 对象。 - 第 22 行：调用
ConsistentHashSelector#select(invocation)方法，选择一个 Invoker 对象。
7.1 ConsistentHashSelector
ConsistentHashSelector ，是 ConsistentHashLoadBalance 的内部类，一致性哈希选择器，基于 Ketama 算法。
老艿艿：下文参考 《Ketama一致性Hash算法(含Java代码)》 文章。从该文章中，我们可以看到，Spy Memcached Client 也采用这种算法。
7.1.1 构造方法
/** |
identityHashCode字段，定义哈希值。replicaNumber字段，每个 Invoker 对应的虚拟节点数，默认为 160 。- 可通过
<dubbo:parameter key="hash.nodes" value="320" />自定义，对应【第 7 行】代码。
- 可通过
argumentIndex字段，选择 Invoker 时，计算 Hash 值的参数位置数组，默认为第一个参数。- 可通过
<dubbo:parameter key="hash.arguments" value="0,1" />自定义， 对应【第 8 至 13 行】代码。
- 可通过
virtualInvokers字段，虚拟节点与 Invoker 的映射关系。对应【第 14 至 28 行】进行初始化。- 第 15 行：循环每个 Invoker 对象。
- 第 18 行：循环
replicaNumber / 4次，每四个虚拟节点为一组，为什么这样呢？详细见【第 20 行】。 第 20 行：拼接
address + i作为虚拟节点名的唯一名称。调用#md5(value)方法，计算 MD5 。代码如下：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();
}- MD5 是一个 16 字节长度的数组，将 16 字节的数组每四个字节一组，分别对应一个虚拟结点，这就是为什么上面把虚拟结点四个划分一组的原因
第 22 行：顺序循环每四个字节。
第 24 行：调用
#hash(byte[] digest, int number)方法，对于每四个字节，组成一个 Long 值数值，做为这个虚拟节点的在环中的惟一 KEY 。代码如下：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;
}- x
- 第 25 行：添加 Invoker 到
virtualInvokers中。
7.1.2 select
public Invoker<T> select(Invocation invocation) { |
调用
#toKey(Object[] args)方法，基于方法参数，获得 KEY 。代码如下：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();
}调用
#md5(key)方法，计算 MD5 值。- 调用
#hash(digest, hash)方法，计算 KEY 值。 调用
#selectForKey(hash)方法，选一个 Invoker 对象。代码如下：private Invoker<T> selectForKey(long hash) {
// 得到大于当前 key 的那个子 Map ，然后从中取出第一个 key ，就是大于且离它最近的那个 key
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
// 不存在，则取 virtualInvokers 第一个
if (entry == null) {
entry = virtualInvokers.firstEntry();
}
// 存在，则返回
return entry.getValue();
}
# 666. 彩蛋
小文一篇，美滋滋！