前言
终于到了集群容错中的最后一个关键词,也就是LoadBalance(负载均衡),负载均衡必然会涉及一些算法.但是也不用太担心,算法这个词虽然高大上,但是算法也有简单和复杂之分.既然是源码解析类的文章,那么就有义务让看不懂代码的看文章总结都能明白原理的义务.所以本篇尽量用一些简单的数学式子和流程图和大家一起梳理一下这些集群容错算法.
插播面试题
为了能够带着面试题去看文章,我把这个插播面试题的环节放在了前面比较显眼的位置
●谈谈dubbo中的负载均衡算法及特点
●最小活跃数算法中是如何统计这个活跃数的
●简单谈谈你对一致性哈希算法的认识
直入主题
我们还是按照惯例来看看接口的继承图
SPI
LoadBalance
ABstractLoadBalance
ROundRobiNLoaDBalance
LeastActiveLoadBalance
ConsistentHashLoadBalance
RandomLoadBalance
下面就对这四种负载均衡策略依次解析
RandomLoadBalance(随机)
引用文档介绍
●随机，按权重设置随机概率。
●在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。
这个随机的策略是默认的策略,但是这个随机和我们理解上的随机还是不一样的,因为他还有个概念叫weight(权重),这个"权重"的概念Android的同学一定不会陌生,因为在LinearLayout布局中就有这个概念,在前端的CSS框架Bootstrap的栅格和也有类似概念.说白了,这里说的权重就是用来控制这个随机的概率的,我们来看代码实现.
Inyokersi)doselect(istinyokrsk
protected
invokers.size);//总个数
length
int
//总权重
inttotaiweighto;
true;权重是否都一样
booleansameweight
for(intio;ilength;1++)
Intweightgetweight(invokers.ge()cation;
totaiweight+aweight;/累计总权重
if(sameweight&&1>0
8&weightlgetweight(invokers.get(catin
sameweightfalse;/计算所有权重是否一样
if
(totalweighto&&sameweight)
/如果权重不相同且权重大于:则按总权重数随机
toffsetrandom.nextInt(totaiweight);
intof
并确定随机值落在哪个片断上
(inti
ti-0;i<length;i++)f
for
ofFseTgeTWeIght(IOkers.ge()ocatin;
if(offset<0)f
returninvokers.get(i);
如果权重相同或权重为则均等随机
returninvokers.get(random.nextInt(1ength);
如果暂时没明白没关系,可以看看下面的流程图和数学分析
流程图
start
获取invokers
的个数,并遍
历累加权重
芸不为第0个则将当前权重与上一个
均等随机调用
行比较.只要有一个不等,则认为不等,即
stop
sameWeightfalse
总权重>0且sameWeightfalse
按权重获取随机
数根据随机数和
权重相减确定调用
的节点
数学分析
假设有四个集群节点A,B,C,D,对应的权重分别是1,2,3,4,那么请求到A节点的概率就为1/(1+2+3+4) = 10%.B,C,D节点依次类推为20%,30%,40%.
敲黑板划重点
虽然这个随机算法理解起来是比较容易的,面试一般不会问这个,但是假如我们要实现类似的功能,他这个代码实现的思路还是很优雅的,非常具有借鉴意义.他这个实现思路从纯数学角度是很好理解的,我们还是按照上面数学分析中的前提条件.我们知道总权重为10(1+2+3+4),那么怎么做到按权重随机呢?根据10随机出一个整数,假如为随机出来的是2.然后依次和权重相减,比如2(随机数)-1(A的权重) = 1,然后1(上一步计算的结果)-2(B的权重) = -1,此时-1 < 0,那么则调用B,其他的以此类推
RoundRobinLoadBalance(轮询)
引用文档介绍
●轮循，按公约后的权重设置轮循比率。
●存在慢的提供者累积请求的问题，比如：第二台机器很慢，但没挂，当请求调到第二台时就卡在那，久而久之，所有请求都卡在调到第二台上。
nvokersT>>invokersuuatinincatin)
InvokerTdoselect(list
protected
StringkeyLndkers.et.guog
tlengtheinvokers.size);//总个
总个数
int:
intma
tmaxweight0;l/最大权重
intminweightInteger.MAX_VALUE;//最小权重
fnILinKedHbshlapsnyker,n
intweightSum0;
for(inti-e;i<length;i++)f
intweightgetweight(invokers.get()iocation;
maxweightMath.max(maxweight,weght);累计最大权重
Math.min(minweight,weight);累计最小权重
minweightMat
if(weight>0)f
INVOkeroweIghtMapput(Inoke()rwe)
weightsum+aweight;
AtomicPositiveIntegersequencesequencesge(key);
(sequenceEnu11)
sequenceS.putIfAbsent(key,wtomioivetee
sequencesequencesget(Key);
currentsequencesequence.geTAndIncremen;
一
(maxweight88minweightmaxweight)权重不一样
intmod
currentsequence%weightsum;
(inti0;imaxweight;i++)
for
Map.EntryjInvokers,Integewrappersech:ivokeoeightMp.entryset)
for
finalI
InvokersTk-each.getKeyO;
Integerwrappervaeach.getvalue();
fina1I
hod0&8vgetvalue)
0)f
if(mod
return
if
vgetvalue)>0)f
decrement);
mod
取模轮循
invokers.get(currentsequence%1ength);
这个可以先网上搜索一下权重轮询调度算法,因为Nginx的负载均衡默认就是轮询,所以我打算后面专门写一篇详细讲一下这个算法.
LeastActiveLoadBalance(最少活跃数)
引用文档介绍
●最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差。
●使慢的提供者收到更少请求，因为越慢的提供者的调用前后计数差会越大。
看完文档可能还是不明白究竟是什么意思,那我举个例子.每个服务有一个活跃计数器,那么我们假如有A,B两个提供者.计数均为0.当A提供者开始处理请求,该计数+1,此时A还没处理完,当处理完后则计数-1.而B请求接收到请求处理得很快.B处理完后A还没处理完,所以此时A,B的计数为1,0.那么当有新的请求来的时候,就会选择B提供者(B的活跃计数比A小).这就是文档说的,使慢的提供者收到更少请求
那么我们来看代码实现
InvOkersTdoselect(ListInvokerT>invoke
Invocationinvocation)
invokers
protecte
intlengtheinvokers.size;//总个数
intleastactive-1;1/最小的活跃数
1ntleastCount0;1相同最小活跃数的个数
intleastindexsnewintlengthj;/相同最小活跃数的下标
inttotaiweight;l/总权重
intfirstheight;/第一个权重,用于于计算是否相同
booLeansameweIghttrue;是否所有权重相同
for(Intao;1ulength;1++)
Invokertinvokerinvokers.get(1)
城atwe.Ppstusgestatuskeu
晒址
IF(Leastactive
active<leastactive)发现更小的活跃数,重新开始
active记录最小活跃数
Ieastactive-
1eastcount1;1/重新统计相同最小活跃数的个数
1eastIndexs[e]1;/重新记录最小活跃数下标
totaiheightHeight;重新累计总权重
firstHeightHeight;记录第一个权重
sameweight-true;/还原权重相同标识
elseif(activeleastactive)累计相同最小的活跃数
leastIndexs[leastcount+];小活下标
totaiweight+aweight;/累计总权重
判断所有权重是否一样
(SameHleight&&1>0
&&weightfirstweight)
sameweightfalse
'
assert(leastCount>0)
(leastCount1)f
如果只有一个最小则直接返回
returninvokers.get(leastIndexs[o]);
1f(!sameweight&&totaweight>O)
/如果权重不相同且权重大于则按总权重数随机
intoffsetweightrandom.nextIn(e
并确定随机值落在哪个片断上
for(Int1
;Iuleastcount;1++)
INtLEastIndexleastIndexs[];
OFFSETWEIhTTNk
if(offsetweightso)
returninvokers.get(leastIndex);
如果权重相同或权重为则均等随机
returninvokers.get(leastindexs[randonnextInt(eastcount));
看不懂代码没关系,我讲一下他的思路,这部分代码概括起来就两部分,一部分是活跃数和权重的统计,另一部分是选择invoker.也就是他把最小活跃数的invoker统计到leastIndexs数组中,如果权重一致(这个一致的规则参考上面的随机算法)或者总权重为0,则均等随机调用,如果不同,则从leastIndexs数组中按照权重比例调用(还是和随机算法中的那个依次相减的思路一样).还不明白没关系,看下面的流程图和数学分析
流程图
start
获取invoker的总个数初始化最小活跃数相
同最小活跃数相同最小活跃数数组
追历invokers,获取invoker的权重,活跃数找
出最小活跃的invoker
有一个以上最小获
直接调用
取的invoker?
有多个invoker
将多个invoker放入数组
stop
重不等且总权重大
均等随机调用
于0
按照权重比例调用
数学分析
假设A,B,C,D节点的最小活跃数分别是1,1,2,3,权重为1,2,3,4.则leastIndexs(该数组是最小活跃数组,因为A,B的活跃数是1,均为最小)数组内容为[A,B].A,B的权重是1和2,所以调用A的概率为 1/(1+2) = 1/3,B的概率为 2/(1+2) = 2/3
敲黑板划重点
活跃数的变化是在com.alibaba.dubbo.rpc.filter.ActiveLimitFilter中,如果没有配置dubbo:reference的actives属性,默认是调用前活跃数+1,调用结束-1,鉴于很多人可能没用过这个属性,所以我把文档截图贴出来
另外如果使用该种负载均衡算法,则dubbo:service中还需要配置filter="activelimit"
ConsistentHashLoadBalance(一致性哈希)
引用文档介绍
●一致性 Hash，相同参数的请求总是发到同一提供者。
●当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
●算法参见：http://en.wikipedia.org/wiki/Consistent_hashing
●缺省只对第一个参数 Hash，如果要修改，请配置
●缺省用 160 份虚拟节点，如果要修改，请配置
该算法的代码实现拿出来讲的话篇幅较大,这个一致性哈希算法在缓存例如redis的面试题中也经常喜欢问到,网上也有很多相关的文章,我这里主要是想用大白话来讲一下,主要讲三个关键词,原理,down机影响,虚拟节点
原理
简单讲就是,假设我们有个时钟,各服务器节点映射放在钟表的时刻上,把key也映射到钟表的某个时刻上,然后key顺时针走,碰到的第一个节点则为我们需要找的服务器节点
还是假如我们有a,b,c,d四个节点(感觉整篇文章都在做这个假如....),把他们通过某种规则转成整数,分别为0,3,6,9.所以按照时钟分布如下图
假设这个key通过某种规则转化成1,那么他顺时针碰到的第一个节点就是b,也就是b是我们要找的节点
那么我们可能就有疑问了,这个某种规则究竟是什么规则?
这个规则你可以自己设计,但是要注意的是,不同的节点名,转换为相同的整数的概率就是衡量这个规则的好坏,如果你能做到不同的节点名唯一对应一个整数,那就是棒棒哒.当然java里面的CRC32这个类你可以了解一下.
说到这里可能又会有另个疑问,时钟点数有限,万一装不下怎么办
其实这个时钟只是方便大家理解做的比喻而已,在实际中,我们可以在圆环上分布[0,2^32-1]的数字,这量级全世界的服务器都可以装得下.
down机影响
通过上图我们可以看出,当b节点挂了之后,根据顺时针的规则,那么目标节点就是c,也就是说,只影响了一个节点,其他节点不受影响.
如果是轮询的取模算法,假设从N台服务器变成了N-1台,那么命中率就变成1/(N-1),因此服务器越多,影响也就越大.
虚拟节点
为什么要有虚拟节点的概念呢?我们还是回到第一个假设,我们还是有a,b,c,d四个节点,他们通过某个规则转化成0,3,6,9这种自然是均匀的.但是万一是0,1,2,3这样,那就是非常不均匀了.事实上, 一般的Hash函数对于节点在圆环上的映射,并不均匀.所以我们需要引入虚拟节点,那么什么是虚拟节点呢?
假如有N个真实节点,把每个真实节点映射成M个虚拟节点,再把 M*N 个虚拟节点, 散列在圆环上. 各真实节点对应的虚拟节点相互交错分布这样,某真实节点down后,则把其影响平均分担到其他所有节点上.
也就是a,b,c,d的虚拟节点a0,a1,a2,b0,b1,b2,c0,c1,c2,d0,d1,d2散落在圆环上,假设C号节点down,则c0,c1,c2的压力分别传给d0,a1,b1,如下图
若有收获，就点个赞吧
