第一次调用
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都处于空闲状态:
转化为表格如下:
从表格的最终结果一栏也可以直观的看出,七次请求对应的服务器端口为:
分布确实不够均匀。
再推翻,再重建,平滑加权。
从issue中可以看到,再次重构的加权算法的灵感来源是Nginx的平滑加权轮询负载均衡:
看代码之前,先介绍其计算过程。
假设每个服务器有两个权重,一个是配置的weight,不会变化,一个是currentWeight会动态调整,初始值为0。当有新的请求进来时,遍历服务器列表,让它的currentWeight加上自身权重。遍历完成后,找到最大的currentWeight,并将其减去权重总和,然后返回相应的服务器即可。
如果你还是不知道上面的表格是如何算出来的,我再给你详细的分析一下第1、2个请求的计算过程
第一个请求计算过程如下:
第二个请求计算过程如下:
后面的请求你就可以自己分析了。
从表格的最终结果一栏也可以直观的看出,七次请求对应的服务器端口为:
可以看到,权重之比同样是5:1:1,但是最终的请求分发的就比较的"平滑"。对比一下:
对于平滑加权算法,我想多说一句。我觉得这个算法非常的神奇,我是彻底的明白了它每一步的计算过程,知道它最终会形成一个闭环,但是我想了很久,我还是不知道背后的数学原理是什么,不明白为什么会形成一个闭环,非常的神奇。
很正常,我不纠结的,程序猿的工作不就是这样吗?我也不知道为什么,它能工作。别问,问就是玄学,如果一定要说出点什么的话,我想,我愿称之为:绝活吧。
但是我们只要能够理解我前面所表达的平滑加权轮询算法的计算过程,知道其最终会形成闭环,就能理解下面的代码。配合代码中的注释食用,效果更佳。
以下代码以及注释来源官网:
http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html
总结
好了,到这里关于Dubbo的五种负载均衡策略就讲完了。简单总结一下:(加权随机算法在讲最小活跃数算法的时候提到过,因为原理十分简单,这里就不专门拿出章节来描述了。)
最短响应时间负载均衡:在所有服务提供者中选出平均响应时间最短的一个,如果能选出来,则使用选出来的一个。如果不能选出来多个,再根据权重选,如果权重也一样,则随机选择。
一致性哈希负载均衡:在一致性哈希算法中,不管是增加节点,还是宕机节点,受影响的区间仅仅是增加或者宕机服务器在哈希环空间中,逆时针方向遇到的第一台服务器之间的区间,其它区间不会受到影响。为了解决数据倾斜的问题,引入了虚拟节点的概念。一致性哈希算法是 Dubbo 中唯一一个与权重没有任何关系的负载均衡算法,可以保证相同参数的请求打到同一台机器上。
最小活跃数负载均衡:需要配合 activeFilter 使用,活跃数在方法调用前后进行维护,响应越快的服务器堆积的请求越少,对应的活跃数也少。Dubbo 在选择的时候遵循下面的规则,有最小活跃数用最小活跃数,没有最小活跃数根据权重选择,权重一样则随机返回的负载均衡算法。
加权随机算法:随机,顾名思义,就是从多个服务提供者中随机选择一个出来。加权,就是指需要按照权重设置随机概率。常见场景就是对于性能好的机器可以把对应的权重设置的大一点,而性能相对较差的,权重设置的小一点。哎,像极了这个社会上的某些现象,对外宣传是随机摇号,背后指不定有一群权重高的人呢。
加权轮询负载均衡:轮询就是雨露均沾的意思,所有的服务提供者都需要调用。而当轮询遇到加权则可以让请求(不论多少)严格按照我们的权重之比进行分配。比如有A、B、C三台服务器,权重之比为5:3:2,一共处理10个请求。那么采用负载均衡采用轮询加权算法时,A、B、C服务一定是分别承担5、3、2个请求。同时需要注意的是加权轮询算法的两次升级过程,以及最终的“平滑”的解决方案。
再说一件事
本文主要聊的是负载均衡嘛,让我想起了 2019 年阿里巴巴第五届中间件挑战赛的初赛赛题也是实现一个负载均衡策略。
具体的赛题可以看这里:
https://tianchi.aliyun.com/competition/entrance/231714/information
这种比赛还是很有意思的,你报名之后仅仅是读懂赛题,然后自己多想想怎么实现,哪怕是不提交代码,在比赛完成后看前几名的赛题分析,再去把他们的代码拉下来看看,你就会发现,其实最终的思路都大同小异,差别会体现在参数调优和代码优化程度上。
当然最大的差别还是会体现在语言的层面。如果不限制参数语言的话,Java 系的选手一定是被 C 系选手吊打的。
但是,被吊打不重要,重要的是真的能学到很多的东西,而这些东西,在绝大部分工作中是很难学到的。
最近,阿里巴巴第六届中间件挑战赛也开始了,可以看一下这个链接:
这次是分为三个赛道,选择性更多了。
作为这个比赛的长期关注者(持续关注三年了吧),这次作为一个自来水免费宣传一波。
朋友,我真心建议你去看一下,报个名,玩一玩,收获真的很大的。
当然,如果能在报名的时候邀请人那一栏填【why技术】,我真心感谢你。