前言
终于到了集群容错中的最后一个关键词,也就是LoadBalance(负载均衡),负载均衡必然会涉及一些算法.但是也不用太担心,算法这个词虽然高大上,但是算法也有简单和复杂之分.既然是源码解析类的文章,那么就有义务让看不懂代码的看文章总结都能明白原理的义务.所以本篇尽量用一些简单的数学式子和流程图和大家一起梳理一下这些集群容错算法.
插播面试题
为了能够带着面试题去看文章,我把这个插播面试题的环节放在了前面比较显眼的位置
● 谈谈dubbo中的负载均衡算法及特点
● 最小活跃数算法中是如何统计这个活跃数的
● 简单谈谈你对一致性哈希算法的认识
直入主题
我们还是按照惯例来看看接口的继承图
下面就对这四种负载均衡策略依次解析
RandomLoadBalance(随机)
引用文档介绍
● 随机，按权重设置随机概率。
● 在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。
这个随机的策略是默认的策略,但是这个随机和我们理解上的随机还是不一样的,因为他还有个概念叫weight(权重),这个"权重"的概念Android的同学一定不会陌生,因为在LinearLayout布局中就有这个概念,在前端的CSS框架Bootstrap的栅格和也有类似概念.说白了,这里说的权重就是用来控制这个随机的概率的,我们来看代码实现.
如果暂时没明白没关系,可以看看下面的流程图和数学分析
流程图
数学分析
假设有四个集群节点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(轮询)
引用文档介绍
● 轮循，按公约后的权重设置轮循比率。
● 存在慢的提供者累积请求的问题，比如：第二台机器很慢，但没挂，当请求调到第二台时就卡在那，久而久之，所有请求都卡在调到第二台上。
这个可以先网上搜索一下权重轮询调度算法,因为Nginx的负载均衡默认就是轮询,所以我打算后面专门写一篇详细讲一下这个算法.
LeastActiveLoadBalance(最少活跃数)
引用文档介绍
● 最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差。
● 使慢的提供者收到更少请求，因为越慢的提供者的调用前后计数差会越大。
看完文档可能还是不明白究竟是什么意思,那我举个例子.每个服务有一个活跃计数器,那么我们假如有A,B两个提供者.计数均为0.当A提供者开始处理请求,该计数+1,此时A还没处理完,当处理完后则计数-1.而B请求接收到请求处理得很快.B处理完后A还没处理完,所以此时A,B的计数为1,0.那么当有新的请求来的时候,就会选择B提供者(B的活跃计数比A小).这就是文档说的,使慢的提供者收到更少请求
那么我们来看代码实现
看不懂代码没关系,我讲一下他的思路,这部分代码概括起来就两部分,一部分是活跃数和权重的统计,另一部分是选择invoker.也就是他把最小活跃数的invoker统计到leastIndexs数组中,如果权重一致(这个一致的规则参考上面的随机算法)或者总权重为0,则均等随机调用,如果不同,则从leastIndexs数组中按照权重比例调用(还是和随机算法中的那个依次相减的思路一样).还不明白没关系,看下面的流程图和数学分析
流程图
数学分析
假设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,如下图
