Dubbo加权轮询负载均衡的源码和Bug，了解一下？

本文是对于Dubbo负载均衡策略之一的加权随机算法的详细分析。从2.6.4版本聊起，该版本在某些情况下存在着比较严重的性能问题。由问题入手，层层深入，了解该算法在Dubbo中的演变过程，读懂它的前世今生。

之前也写了Dubbo的负载均衡策略：

《一文讲透Dubbo负载均衡之最小活跃数算法》

《Dubbo一致性哈希负载均衡的源码和Bug，了解一下？》

本文目录

第一节：什么是轮询？

本小节主要是介绍轮询算法和其对应的优缺点。引出加权轮询算法。

第二节：什么是加权轮询？

本小节主要是介绍加权轮询的概率，并和加权随机算法做对比。区分两者之间的关系。

第三节：Dubbo 2.6.4版本的实现

本小节主要分析了Dubbo 2.6.4版本的源码，以及对调用过程进行了详细的分析。并引出该版本的性能问题。

第四节：推翻，重建

针对Dubbo 2.6.4版本的性能问题，在对应的issue中进行了激烈的讨论。并提出了第一版优化意见，时间复杂度优化到了常量级。但不久之后，又有人发现了该版本的其他问题，计算过程不够平滑。

第五节：再推翻，再重建，平滑加权。

针对改进后的算法还是不够平滑的问题，最终借助Nginx的思想，融入了平滑加权的过程，形成最终版。

什么是轮询？

在描述加权轮询之前，先解释一下什么是轮询算法，如下图所示：

假设我们有A、B、C三台服务器，共计处理6个请求，服务处理请求的情况如下:

第一个请求发送给了A服务器

第二个请求发送给了B服务器

第三个请求发送给了C服务器

第四个请求发送给了A服务器

第五个请求发送给了B服务器

第六个请求发送给了C服务器

……

上面这个例子演示的过程就叫做轮询。可以看出，所谓轮询就是将请求轮流分配给每台服务器。

轮询的优点是无需记录当前所有服务器的链接状态，所以它一种无状态负载均衡算法，实现简单，适用于每台服务器性能相近的场景下。

轮询的缺点也是显而易见的，它的应用场景要求所有服务器的性能都相同，非常的局限。

大多数实际情况下，服务器性能是各有差异，针对性能好的服务器，我们需要让它承担更多的请求，即需要给它配上更高的权重。

所以加权轮询，应运而生。

什么是加权轮询？

为了解决轮询算法应用场景的局限性。当遇到每台服务器的性能不一致的情况，我们需要对轮询过程进行加权，以调控每台服务器的负载。

经过加权后，每台服务器能够得到的请求数比例，接近或等于他们的权重比。比如服务器 A、B、C 权重比为 5:3:2。那么在10次请求中，服务器 A 将收到其中的5次请求，服务器 B 会收到其中的3次请求，服务器 C 则收到其中的2次请求。

这里要和加权随机算法做区分哦。加权随机我在《一文讲透Dubbo负载均衡之最小活跃数算法》中介绍过，直接把画的图拿过来：

上面这图是按照比例画的，可以直观的看到，对于某一个请求，区间(权重)越大的服务器，就越可能会承担这个请求。所以，当请求足够多的时候，各个服务器承担的请求数，应该就是区间，即权重的比值。

假设有A、B、C三台服务器，权重之比为5:3:2，一共处理10个请求。

那么负载均衡采用加权随机算法时，很有可能A、B服务就处理完了这10个请求，因为它是随机调用。

采用负载均衡采用轮询加权算法时，A、B、C服务一定是分别承担5、3、2个请求。

Dubbo2.6.4版本的实现

对于Dubbo2.6.4版本的实现分析，可以看下图，我加了很多注释，其中的输出语句都是我加的：

示例代码还是沿用之前文章中的Demo，不了解的可以查看《一文讲透Dubbo负载均衡之最小活跃数算法》，本文分别在20881、20882、20883端口启动三个服务，各自的权重分别为1,2,3。

客户端调用8次：

输出结果如下：

可以看到第七次调用后mod=0，回到了第一次调用的状态。形成了一个闭环。

再看看判断的条件是什么：

其中mod在代码中扮演了极其重要的角色，mod根据一个方法的调用次数不同而不同，取值范围是[0，weightSum)。

因为weightSum=6，所以列举mod不同值时，最终的选择结果和权重变化：

可以看到20881,20882,20883承担的请求数量比值为1:2:3。同时我们可以看出，当 mod >= 1 后，20881端口的服务就不会被选中了，因为它的权重被减为0了。当 mod >= 4 后，20882端口的服务就不会被选中了，因为它的权重被减为0了。

结合判断条件和输出结果，我们详细分析一下(下面内容稍微有点绕，如果看不懂，多结合上面的图片看几次):

第一次调用

mod=0，第一次循环就满足代码块①的条件，直接返回当前循环的invoker，即20881端口的服务。此时各端口的权重情况如下：

第二次调用

mod=1，需要进入代码块②，对mod进行一次递减。

第一次循环对20881端口的服务权重减一，mod-1=0。

第二次循环，mod=0，循环对象是20882端口的服务，权重为2，满足代码块①，返回当前循环的20882端口的服务，此时各端口的权重情况如下：

第三次调用

mod=2，需要进入代码块②，对mod进行两次递减。

第一次循环对20881端口的服务权重减一，mod-1=1；

第二次循环对20882端口的服务权重减一，mod-1=0；

第三次循环时，mod已经为0，当前循环的是20883端口的服务，权重为3，满足代码块①，返回当前循环的20883端口的服务，此时各端口的权重情况如下：

第四次调用

mod=3，需要进入代码块②，对mod进行三次递减。

第一次循环对20881端口的服务权重减一，从1变为0，mod-1=2；

第二次循环对20882端口的服务权重减一，从2变为1，mod-1=1；

第三次循环对20883端口的服务权重减一，从3变为2，mod-1=0；

第四次循环的是20881端口的服务，此时mod已经为0，但是20881端口的服务的权重已经变为0了，不满足代码块①和代码块②，进入第五次循环。

第五次循环的是20882端口的服务，当前权重为1，mod=0，满足代码块①，返回20882端口的服务，此时各端口的权重情况如下：

第五次调用

mod=4，需要进入代码块②，对mod进行四次递减。

第一次循环对20881端口的服务权重减一，从1变为0，mod-1=3；

第二次循环对20882端口的服务权重减一，从2变为1，mod-1=2；

第三次循环对20883端口的服务权重减一，从3变为2，mod-1=1；

第四次循环的是20881端口的服务，此时mod为1，但是20881端口的服务的权重已经变为0了，不满足代码块②，mod不变，进入第五次循环。

第五次循环时，mod为1，循环对象是20882端口的服务，权重为1，满足代码块②，权重从1变为0，mod从1变为0，进入第六次循环。

第六次循环时，mod为0，循环对象是20883端口的服务，权重为2，满足条件①，返回当前20883端口的服务，此时各端口的权重情况如下：

第六次调用

第六次调用，mod=5，会循环九次，最终选择20883端口的服务，读者可以自行分析一波，分析出来了，就了解的透透的了。

第七次调用

第七次调用，又回到mod=0的状态：

2.6.4版本的加权轮询就分析完了，但是事情并没有这么简单。这个版本的加权轮询是有性能问题的。

该问题对应的issue地址如下:

https://github.com/apache/dubbo/issues/2578

问题出现在invoker返回的时机上：

截取issue里面的一个回答：

10分钟才选出一个invoker，还怎么玩？

有时间可以读一读这个issue，里面各路大神针对该问题进行了激烈的讨论，第一种改造方案被接受后，很快就被推翻，被第二种方案代替，可以说优化思路十分值得学习，很精彩，接下来的行文路线就是按照该issue展开的。

推翻，重建。

上面的代码时间复杂度是O(mod)，而第一次修复之后时间复杂度降低到了常量级别。可以说是一次非常优秀的优化，值得我们学习，看一下优化之后的代码：

其关键优化的点是这段代码，我加入输出语句，便于分析。

输出日志如下：

把上面的输出转化到表格中去，7次请求的选择过程如下：

该算法的原理是：

把服务端都放到集合中(invokerToWeightList)，然后获取服务端个数(length)，并计算出服务端权重最大的值(maxWeight)。

index表示本次请求到来时，处理该请求的服务端下标，初始值为0，取值范围是[0,length)。

currentWeight表示当前调度的权重，初始值为0，取值范围是[0,maxWeight)。

当请求到来时，从index(就是0)开始轮询服务端集合(invokerToWeightList)，如果是一轮循环的开始(index=0)时，则对currentWeight进行加一操作（不会超过maxWeight），在循环中找出第一个权重大于currentWeight的服务并返回。

这里说的一轮循环是指index再次变为0所经历过的循环，这里可以把index=0看做是一轮循环的开始。每一轮循环的次数与Invoker的数量有关，Invoker数量通常不会太多，所以我们可以认为上面代码的时间复杂度为常数级。

从issue上看出，这个算法最终被merged了。

但是很快又被推翻了：

这个算法不够平滑。什么意思呢？

翻译一下上面的内容就是：服务器[A, B, C]对应权重[5, 1, 1]。进行7次负载均衡后，选择出来的序列为[A, A, A, A, A, B, C]。前5个请求全部都落在了服务器A上，这将会使服务器A短时间内接收大量的请求，压力陡增。而B和C此时无请求，处于空闲状态。而我们期望的结果是这样的[A, A, B, A, C, A, A]，不同服务器可以穿插获取请求。

我们设置20881端口的权重为5，20882、20883端口的权重均为1。

进行实验，发现确实如此：可以看到一共进行7次请求，第1次到5次请求都分发给了权重为5的20881端口的服务，前五次请求，20881和20882都处于空闲状态：