Dubbo负载均衡算法Word格式.docx
《Dubbo负载均衡算法Word格式.docx》由会员分享，可在线阅读，更多相关《Dubbo负载均衡算法Word格式.docx（19页珍藏版）》请在冰点文库上搜索。
if（i==0）{
cw=cw-gcd（S）;
if（cw<
=0）{
cw=max（S）;
if（cw==0）
returnNULL;
}
if（W（Si）>
=cw）
returnSi;
这种算法的逻辑实现如图2所示，图中我们假定四台服务器的处理能力为3:
1:
1。
图1权重轮询调度实现逻辑图示
由于权重轮询调度算法考虑到了不同服务器的处理能力，所以这种均衡算法能确保高性能的服务器得到更多的使用率，避免低性能的服务器负载过重。
所以，在实际应用中比较常见。
2、ConsistentHashLoadBalance
一致性Hash，相同参数的请求总是发到同一个提供者。
一：
一致性Hash算法可以解决服务提供者的增加、移除及挂掉时的情况，能尽可能小的改变已存在key映射关系，尽可能的满足单调性的要求。
二：
一致性Hash通过构建虚拟节点，能尽可能避免分配失衡，具有很好的平衡性。
一致性Hash下面就来按照5个步骤简单讲讲consistenthash算法的基本原理。
因为以下资料来自于互联网，现说明几点：
一、下面例子中的对象就相当于Client发的请求，cache相当于服务提供者。
环形hash空间
考虑通常的hash算法都是将value映射到一个32为的key值，也即是0~2^32-1次方的数值空间；
我们可以将这个空间想象成一个首（0）尾（2^32-1）相接的圆环，如下面图2所示的那样。
图2环形hash空间
把对象映射到hash空间
接下来考虑4个对象object1~object4，通过hash函数计算出的hash值key在环上的分布如图3所示。
hash（object1）=key1;
……
hash（object4）=key4;
图34个对象的key值分布
把cache映射到hash空间
Consistenthashing的基本思想就是将对象和cache都映射到同一个hash数值空间中，并且使用相同的hash算法。
假设当前有A,B和C共3台cache，那么其映射结果将如图4所示，他们在hash空间中，以对应的hash值排列。
hash（cacheA）=keyA;
hash（cacheC）=keyC;
图4cache和对象的key值分布
说到这里，顺便提一下cache的hash计算，一般的方法可以使用cache机器的IP地址或者机器名作为hash输入。
把对象映射到cache
现在cache和对象都已经通过同一个hash算法映射到hash数值空间中了，接下来要考虑的就是如何将对象映射到cache上面了。
在这个环形空间中，如果沿着顺时针方向从对象的key值出发，直到遇见一个cache，那么就将该对象存储在这个cache上，因为对象和cache的hash值是固定的，因此这个cache必然是唯一和确定的。
这样不就找到了对象和cache的映射方法了吗！
依然继续上面的例子（参见图4），那么根据上面的方法，对象object1将被存储到cacheA上；
object2和object3对应到cacheC；
object4对应到cacheB；
考察cache的变动
前面讲过，一致性Hash算法可以解决服务提供者的增加、移除及挂掉时的情况，能尽可能小的改变已存在key映射关系，尽可能的满足单调性的要求。
移除cache
考虑假设cacheB挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿cacheB逆时针遍历直到下一个cache（cacheC）之间的对象，也即是本来映射到cacheB上的那些对象。
因此这里仅需要变动对象object4，将其重新映射到cacheC上即可；
参见图5。
图5CacheB被移除后的cache映射
添加cache
再考虑添加一台新的cacheD的情况，假设在这个环形hash空间中，cacheD被映射在对象object2和object3之间。
这时受影响的将仅是那些沿cacheD逆时针遍历直到下一个cache（cacheB）之间的对象（它们是也本来映射到cacheC上对象的一部分），将这些对象重新映射到cacheD上即可。
因此这里仅需要变动对象object2，将其重新映射到cacheD上；
参见图6。
图6添加cacheD后的映射关系
虚拟节点
考虑Hash算法的另一个指标是平衡性（Balance），定义如下：
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
hash算法并不是保证绝对的平衡，如果cache较少的话，对象并不能被均匀的映射到cache上，比如在上面的例子中，仅部署cacheA和cacheC的情况下，在4个对象中，cacheA仅存储了object1，而cacheC则存储了object2、object3和object4；
分布是很不均衡的。
为了解决这种情况，consistenthashing引入了“虚拟节点”的概念，它可以如下定义：
“虚拟节点”（virtualnode）是实际节点在hash空间的复制品（replica），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在hash空间中以hash值排列。
仍以仅部署cacheA和cacheC的情况为例，在图5中我们已经看到，cache分布并不均匀。
现在我们引入虚拟节点，并设置“复制个数”为2，这就意味着一共会存在4个“虚拟节点”，cacheA1,cacheA2代表了cacheA；
cacheC1,cacheC2代表了cacheC；
假设一种比较理想的情况，参见图7。
图7引入“虚拟节点”后的映射关系
此时，对象到“虚拟节点”的映射关系为：
objec1->
cacheA2；
objec2->
cacheA1；
objec3->
cacheC1；
objec4->
cacheC2；
因此对象object1和object2都被映射到了cacheA上，而object3和object4映射到了cacheC上；
平衡性有了很大提高。
引入“虚拟节点”后，映射关系就从{对象->
节点}转换到了{对象->
虚拟节点}。
查询物体所在cache时的映射关系如图8所示。
图8查询对象所在cache
“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。
例如假设cacheA的IP地址为202.168.14.241。
引入“虚拟节点”前，计算cacheA的hash值：
Hash（“202.168.14.241”）;
引入“虚拟节点”后，计算“虚拟节”点cacheA1和cacheA2的hash值：
Hash（“202.168.14.241#1”）;
//cacheA1
Hash（“202.168.14.241#2”）;
//cacheA2
3、RandomLoadBalance与LeastActionLoadBalance
RandomLoadBalance与LeastActionLoadBalance算法比较简单，可以参照Dubbo文档中的给的描述及后面代码附录。
Dubbo文档截图如下图9所示：
图9负载均衡算法
4、附录
1、RandomLoadBalance算法
publicclassRandomLoadBalanceextendsAbstractLoadBalance{
publicstaticfinalStringNAME="
random"
;
privatefinalRandomrandom=newRandom（）;
protected<
T>
Invoker<
doSelect（List<
Invoker<
>
invokers,URLurl,Invocationinvocation）{
intlength=invokers.size（）;
//总个数
inttotalWeight=0;
//总权重
booleansameWeight=true;
//权重是否都一样
for（inti=0;
i<
length;
i++）{
intweight=getWeight（invokers.get（i）,invocation）;
totalWeight+=weight;
//累计总权重
if（sameWeight&
&
i>
0
&
weight!
=getWeight（invokers.get（i-1）,invocation））{
sameWeight=false;
//计算所有权重是否一样
}
if（totalWeight>
0&
!
sameWeight）{
//如果权重不相同且权重大于0则按总权重数随机
intoffset=random.nextInt（totalWeight）;
//并确定随机值落在哪个片断上
offset-=getWeight（invokers.get（i）,invocation）;
if（offset<
0）{
returninvokers.get（i）;
//如果权重相同或权重为0则均等随机
returninvokers.get（random.nextInt（length））;
2、RoundRobinLoadBalance算法
publicclassRoundRobinLoadBalanceextendsAbstractLoadBalance{
roundrobin"
privatefinalConcurrentMap<
String,AtomicPositiveInteger>
sequences=newConcurrentHashMap<
（）;
weightSequences=newConcurrentHashMap<
Stringkey=invokers.get（0）.getUrl（）.getServiceKey（）+"
."
+invocation.getMethodName（）;
intmaxWeight=0;
//最大权重
intminWeight=Integer.MAX_VALUE;
//最小权重
maxWeight=Math.max（maxWeight,weight）;
//累计最大权重
minWeight=Math.min（minWeight,weight）;
//累计最小权重
if（maxWeight>
minWeight<
maxWeight）{//权重不一样
AtomicPositiveIntegerweightSequence=weightSequences.get（key）;
if（weightSequence==null）{
weightSequences.putIfAbsent（key,newAtomicPositiveInteger（））;
weightSequence=weightSequences.get（key）;
intcurrentWeight=weightSequence.getAndIncrement（）%maxWeight;
List<
weightInvokers=newArrayList<
for（Invoker<
invoker:
invokers）{//筛选权重大于当前权重基数的Invoker
if（getWeight（invoker,invocation）>
currentWeight）{
weightInvokers.add（invoker）;
intweightLength=weightInvokers.size（）;
if（weightLength==1）{
returnweightInvokers.get（0）;
}elseif（weightLength>
1）{
invokers=weightInvokers;
length=invokers.size（）;
AtomicPositiveIntegersequence=sequences.get（key）;
if（sequence==null）{
sequences.putIfAbsent（key,newAtomicPositiveInteger（））;
sequence=sequences.get（key）;
//取模轮循
returninvokers.get（sequence.getAndIncrement（）%length）;
3、LeastActionLoadBalance算法
publicclassLeastActiveLoadBalanceextendsAbstractLoadBalance{
leastactive"
intleastActive=-1;
//最小的活跃数
intleastCount=0;
//相同最小活跃数的个数
int[]leastIndexs=newint[length];
//相同最小活跃数的下标
intfirstWeight=0;
//第一个权重，用于于计算是否相同
//是否所有权重相同
Invoker<
invoker=invokers.get（i）;
intactive=RpcStatus.getStatus（invoker.getUrl（）,invocation.getMethodName（））.getActive（）;
//活跃数
intweight=invoker.getUrl（）.getMethodParameter（invocation.getMethodName（）,Constants.WEIGHT_KEY,Constants.DEFAULT_WEIGHT）;
//权重
if（leastActive==-1||active<
leastActive）{//发现更小的活跃数，重新开始
leastActive=active;
//记录最小活跃数
leastCount=1;
//重新统计相同最小活跃数的个数
leastIndexs[0]=i;
//重新记录最小活跃数下标
totalWeight=weight;
//重新累计总权重
firstWeight=weight;
//记录第一个权重
sameWeight=true;
//还原权重相同标识
}elseif（active==leastActive）{//累计相同最小的活跃数
leastIndexs[leastCount++]=i;
//累计相同最小活跃数下标
//判断所有权重是否一样
0
=firstWeight）{
//assert（leastCount>
0）
if（leastCount==1）{
//如果只有一个最小则直接返回
returninvokers.get（leastIndexs[0]）;
if（!
sameWeight&
totalWeight>
intoffsetWeight=random.nextInt（totalWeight）;
leastCount;
intleastIndex=leastIndexs[i];
offsetWeight-=getWeight（invokers.get（leastIndex）,invocation）;
if（offsetWeight<
=0）
returninvokers.get（leastIndex）;
returninvokers.get（leastIndexs[random.nextInt（leastCount）]）;
4、ConsistentHashLoadBalance算法
publicclassConsistentHashLoadBalanceextendsAbstractLoadBalance{
String,ConsistentHashSelector<
?
selectors=newConcurrentHashMap<
@SuppressWarnings（"
unchecked"
）
@Override
intidentityHashCode=System.identityHashCode（invokers）;
ConsistentHashSelector<
selector=（ConsistentHashSelector<
）selectors.get（key）;
if（selector==null||selector.getIdentityHashCode（）!
=identityHashCode）{
selectors.put（key,newCon
升级会员 