前几天参加某公司面试，被问到Dubbo的负载均衡算法实现，由于电话面试无法画图详解，不才小生简单口头描述后，换来面试官一句“没这么复杂吧”（…）。于是写下此篇文章，详细介绍下Dubbo框架中负载均衡的加权轮训算法实现。后续如果有闲情的话，再完善其余的算法实现（大概）
简单介绍
负载均衡（LoadBalance）的详细定义请参考维基百科以及Dubbo官方文档，简单来说就是针对服务集群，按照特定的规则对请求进行分发，使集群下的资源被平衡访问的一种技术。
加权轮训算法
负载均衡的一种算法实现，效果是按服务的权重设置轮询比率，循环请求资源服务。Dubbo 借鉴 Nginx 的平滑加权轮询算法，并对此做了优化。
源码分析
Dubbo的负载均衡算法实现，放在org.apache.dubbo.rpc.cluster包下，以org.apache.dubbo.rpc.cluster.LoadBalance定义，通过SPI功能动态加载，默认实现为org.apache.dubbo.rpc.cluster.loadbalance.RandomLoadBalance（加权随机），本文着重介绍Dubbo框架下的另一种负载均衡实现-加权轮训，源码位置org.apache.dubbo.rpc.cluster.loadbalance.RoundRobinLoadBalance#doSelect
源码实现
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
| protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.computeIfAbsent(key, k -> new ConcurrentHashMap<>());
int totalWeight = 0;
long maxCurrent = Long.MIN_VALUE;
long now = System.currentTimeMillis();
Invoker<T> selectedInvoker = null;
WeightedRoundRobin selectedWRR = null;
for (Invoker<T> invoker : invokers) {
String identifyString = invoker.getUrl().toIdentityString();
int weight = getWeight(invoker, invocation);
WeightedRoundRobin weightedRoundRobin = map.computeIfAbsent(identifyString, k -> {
WeightedRoundRobin wrr = new WeightedRoundRobin();
wrr.setWeight(weight);
return wrr;
});
if (weight != weightedRoundRobin.getWeight()) {
weightedRoundRobin.setWeight(weight);
}
long cur = weightedRoundRobin.increaseCurrent();
weightedRoundRobin.setLastUpdate(now);
if (cur > maxCurrent) {
maxCurrent = cur;
selectedInvoker = invoker;
selectedWRR = weightedRoundRobin;
}
totalWeight += weight;
}
if (invokers.size() != map.size()) {
map.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
}
if (selectedInvoker != null) {
selectedWRR.sel(totalWeight);
return selectedInvoker;
}
return invokers.get(0);
}
|
源码分析
首先算法会轮训所调用服务的所有实例，计算所有服务的静态权重之和（totalWeight），并对各服务的权重使用内部类WeightedRoundRobin进行的二次包装，源码如下
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
| protected static class WeightedRoundRobin {
private int weight;
private AtomicLong current = new AtomicLong(0);
private long lastUpdate;
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
current.set(0);
}
public long increaseCurrent() {
return current.addAndGet(weight);
}
public void sel(int total) {
current.addAndGet(-1 * total);
}
public long getLastUpdate() {
return lastUpdate;
}
public void setLastUpdate(long lastUpdate) {
this.lastUpdate = lastUpdate;
}
}
|
可以发现在WeightedRoundRobin中为所有服务定义了一个动态的权重值，该值后续会在每次服务调用后改变。可以看到Dubbo在第一次调用服务时，除了服务本身配置的静态权重外，还会给所有服务初始化一个值为0的动态权重。在每次选举之前，将所有服务的动态权重加上自身的静态权重后，选举出动态权重最大的服务进行调用，选举完成后再将选中服务的动态权重减去所有服务的静态权重之和（totalWeight），然后以此为循环，实现服务的加权轮询选举。
实例演示
假设目前我们有ABC三台服务，其配置的权重分别为A=2 B=1 C=1（这里为了方便演示，实际情况下权重值的配置往往为百位数，来提高精细度），那么在进入选举时，会分别为这三台服务初始化值为0的动态权重，后续流程看下表。
| 轮训次数 |
选举前动态权重（自增静态权重） |
选举结果 |
选举后动态权重（减去静态权重之和） |
| 1 |
A(2) B(1) C(1) |
A |
A(-2) B(1) C(1) |
| 2 |
A(0) B(2) C(2) |
B |
A(0) B(-2) C(2) |
| 3 |
A(2) B(-1) C(3) |
C |
A(2) B(-1) C(-1) |
| 4 |
A(4) B(0) C(0) |
A |
A(0) B(0) C(0) |
| 5 |
A(2) B(1) C(1) |
A |
A(-2) B(1) C(1) |
| 6 |
A(0) B(2) C(2) |
B |
A(0) B(-2) C(2) |
| 7 |
A(2) B(-1) C(3) |
C |
A(2) B(-1) C(-1) |
| 8 |
A(4) B(0) C(0) |
A |
A(0) B(0) C(0) |
| 9 |
A(2) B(1) C(1) |
A |
A(-2) B(1) C(1) |
可以看到，选举结果以A、B、C、A为一组进行循环，符合以A=2 B=1 C=1为权重配置的期望。