概述
比较经典的5种负载均衡算法:随机法、轮询法、最少连接数法、最快响应法、Hash化散列法(包括IP-Hash和参数值Hash一致性算法),另外还可以整合权重(配置权重值和JVM预热启动加权)
- 随机法:实现比较简单,也不需要记住状态位,每次随机选举,实现负载均衡的同时又避免了在选取节点时候的复杂运算
- 轮询法:实现更公平的负载均摊,但是是基于所有访问的服务器处理响应时间差不多的业务场景
- 最少连接数法:实现了更贴合实际场景的负载均摊,真正实现了根据服务器的实际处理能力来分摊请求,避免了慢堆积
- 通过统计每个Server的平均响应时间,然后选取最快的server,可以实现动态的调整负载的均摊。
- Hash化散列法:IP哈希可以解决集群的Session共享问题,Hash一致性解决的是在非常复杂的集群模式下,频繁发生节点的新增和删除的时候,如何实现影响最小的请求均摊。
- 权重值的引入,非常有意义的一个干预参数,因为实际的业务场景,每台服务器的物理环境所导致的服务性能各不相同。可以和随机法、轮训法、最少连接数法结合起来用,在和轮询法结合起来用时,又有平滑的负载均摊和不是很平滑的负载均摊。
总体来看,Dubbo提供的负载均衡的方法最多,但是负载的实现问题也多,性能也有待优化。Nginx次之,但是功能也很丰富、性能都较好。
Dubbo负载均衡算法 2.6.2版本
Dubbo提供了功能丰富(bug也多)的4种负载均衡算法,解决Consumer如何从Provider集群间选择哪个Provider提供服务的问题。
另外Dubbo在负载均衡时引入了自定义权重配置、JVM预热时间加权的规则进来。
四种算法:
-
Random LoadBalance:按照权重随机分配Provider,比如随机且权重Node1:Node2= 2:1,那么运行30次,大约有20次在Node1上,10次在Node2上。
-
RoundRobin LoadBalance:按照权重轮询分配。比如权重Node1:Node2= 20:10,那么运行30次:前20次里面轮询Node1和Node2大家各10次,第20次到30次,全部选择Node1。因为Dubbo默认是不会做公约数的处理,只有完成一个完整的20+10次运算,才能保证负载均衡的权重比例准确,如果Consumer只调用了20次,那么这里配置的权重的结果就是1:1了,该算法很不平滑。
-
LeastActive LoadBalance:节点处理越快分配更多,避免慢节点堆积,每次筛选Provider的时候,都只取Active值最小的节点,如果最小Active值的节点有多个,则按照权重随机选取。Provider每获取到一个任务Active值++,每结束一个任务Active值--
-
ConsistentHash LoadBalance:唯一忽略权重配置和JVM预热的算法。先把所有Provider都分配160个虚拟节点,通过Hash算法,全部分散到Hash圆上。每次Consumer调用时,会根据参数值做Hash换算,最后映射到Hash圆上,找到邻近的虚拟节点,最终获取到提供服务的Provider。但是Dubbo在实现的时候违背了Hash一致性的原则,每次Porvider发生改变的时候(新增或者剔除),都会重新创建一个Hash圆,而不是在之前的Hash圆上新增或者剔除不合格的Porvider
AbstractLoadBalance抽象类
这个类提供了计算权重的方法,该方法里面会根据JVM启动时间做加权,并且直接处理了只有1个Provider或者没有Provider的情况,通过doSelect抽象方法,让4种负载均衡实现类去实现各自的规则。
- 获取服务节点的时候,首先调用的是AbstractLoadBalance的select()方法,该方法对一些只有1个Provider或者没有Provider做了处理,如果可用Porvider不止1个,配置的算法才有意义
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
if (invokers == null || invokers.size() == 0)
return null;
if (invokers.size() == 1)
return invokers.get(0);
return doSelect(invokers, url, invocation);
}
- 因为jvm重启后有一段预热过程,要运行一段时间,它的性能才能达到最佳,所以Dubbo在做负载均衡计算Provider的权重时,引入了warmupTime的加权的算法。
在AbstractLoadBalance里面getWeight方法里面:weight= weight * (启动时间/逾期预热时间),warmup默认10分钟,Provider的权重会随着启动时间的增长,取的权重值增加,到了10分钟后,才是真正的配置的权重值
static int calculateWarmupWeight(int uptime, int warmup, int weight) {
int ww = (int) ( (float) uptime / ( (float) warmup / (float) weight ) );
return ww < 1 ? 1 : (ww > weight ? weight : ww);
}
- 备注:2.5.3版本代码里面有bug,在求当前Provider的运行时间参数的时候,实际上取的是当前Consumer的jvm启动时间,不过后来修复了
正确的取值参数为:REMOTE_TIMESTAMP_KEY。2.5.3版本的参数为 TIMESTAMP_KEY
long timestamp = invoker.getUrl().getParameter(Constants.REMOTE_TIMESTAMP_KEY, 0L);
RandomLoadBalance源码分析:
- 先求总权重,如果权重有不相等的,就根据总权重为上限生成随机值,然后看该随机值落在哪个Node上
- 如果权重未配置或者所有节点权重相同,就按照节点数做随机取值
public class RandomLoadBalance extends AbstractLoadBalance {
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size(); // 总个数
int totalWeight = 0; // 总权重
boolean sameWeight = true; // 权重是否都一样
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
totalWeight += weight; // 累计总权重
if (sameWeight && i > 0 && weight != getWeight(invokers.get(i - 1), invocation)) {
sameWeight = false; // 计算所有权重是否一样
}
}
if (totalWeight > 0 && ! sameWeight) {
int offset = random.nextInt(totalWeight);
for (int i = 0; i < length; i++) {
offset -= getWeight(invokers.get(i), invocation);
if (offset < 0) {
return invokers.get(i);
}
}
}
return invokers.get(random.nextInt(length));
}
}
RoundRobinLoadBalance源码分析
核心思想
核心思想是先均摊,小权重的节点权重使用完后被淘汰,大权重节点之间均摊,逐个淘汰,最后是最大的一个节点独占。
比如Node1、Node2、Node3 :1:5:10的权重,那么16次调用的结果就是
(Node1,Node2,Node3)
(Node2,Node3,Node2,Node3,Node2,Node3,Node2,Node3)
(node3,node3,node3,node3,node3)
缺点1:不够平滑,如果只调用了10次,那么权重类似于1:5:4
缺点2:没有类似公约数的处理,节点1:节点2设置1:10和 100万:1000万权重的耗时相差极大
缺点3:大权重值时循环次数太多,第1000万次的调用的时候,会循环1000*2次才能判断出哪个节点来处理请求,节点数越多,权重值设置越大越严重。
改进方案:
- 引入公约数,或者按照1-100进行折算
- 借鉴Nginx的平滑的权重加权轮询的算法
代码分析
- 通过一个全局的sequences根据key来存储调用的值。每个方法对应一个key,value来标记该方法是第几次被调用。
- 通过预热加权后的权重,计算出所有Provider的最大权重、最小权重、累计权重
- 2层for循环自减,第一层for循环的上线时maxWeight,第二层循环的次数是list<invokers>.size
private final ConcurrentMap<String, AtomicPositiveInteger> sequences = new ConcurrentHashMap<String, AtomicPositiveInteger>();
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
int length = invokers.size(); // Number of invokers
int maxWeight = 0; // The maximum weight
int minWeight = Integer.MAX_VALUE; // The minimum weight
final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
int weightSum = 0;
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
maxWeight = Math.max(maxWeight, weight); // Choose the maximum weight
minWeight = Math.min(minWeight, weight); // Choose the minimum weight
if (weight > 0) {
invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight));
weightSum += weight;
}
}
AtomicPositiveInteger sequence = sequences.get(key);
if (sequence == null) {
sequences.putIfAbsent(key, new AtomicPositiveInteger());
sequence = sequences.get(key);
}
//计算当前方法是第几次发起的调用
int currentSequence = sequence.getAndIncrement();
//如果Providers之间的权重不相同,会按照权重来进行轮询Provider
if (maxWeight > 0 && minWeight < maxWeight) {
//关键的两层循环,调用次数会按照weightSum的余数来循环计算
int mod = currentSequence % weightSum;
//这里的上限是maxWeight,因为 里面会有invokerList.size()次的判断,maxWeight*size >sumWeight
for (int i = 0; i < maxWeight; i++) {
//不管该invoker的权重是否自减完了,仍然要取值判断
for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) {
final Invoker<T> k = each.getKey();
final IntegerWrapper v = each.getValue();
if (mod == 0 && v.getValue() > 0) {
return k;
}
//只有当value<0的时候,该节点已经被淘汰,没有资格自减mod
if (v.getValue() > 0) {
v.decrement();
mod--;
}
}
}
}
// Round robin
return invokers.get(currentSequence % length);
}
LeastActiveLoadBalance
- 配置:需要设置Consumer的filter="activelimit"
<dubbo:reference id="demoService" interface="..." loadbalance="leastactive" filter="activelimit"/>
- 算法逻辑
每个Provider对象里面有active值,抽选节点的时候优先判断Active是否是最小的,再根据权重值最随机抽选节点,这样避免让调用堆积在速度相应慢的节点上面
- 如果最小active值的Provider只有1个,那么就调用这个Provider
- 如果最小active值的Provider有多个,则用一个数组存起来,在这个数组中的Provider按照权重值做随机抽选
- 如果大家的Active值都一样,且权重也都一样,就随机抽选
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
...
//遍历所有节点,获取几个指标
//用int[] leastIndexs 保存所有活跃值都最小且相同的Providers的下标
//totalWeight 只获取该数组的Providers的totalWeight,不是最小的Provider不统计
// boolean sameWeight 判断该数组中的Providers的权重是否都相同
for (int i = 0; i < length; i++) {
...
if (leastActive == -1 || active < leastActive) { // 发现更小的活跃数,重新开始
leastActive = active; // 记录最小活跃数
leastCount = 1; // 重新统计相同最小活跃数的个数
leastIndexs[0] = i; // 重新记录最小活跃数下标
totalWeight = weight; // 重新累计总权重
firstWeight = weight; // 记录第一个权重
sameWeight = true; // 还原权重相同标识
} else if (active == leastActive) { // 累计相同最小的活跃数
leastIndexs[leastCount ++] = i; // 累计相同最小活跃数下标
totalWeight += weight; // 累计总权重
// 判断所有权重是否一样
if (sameWeight && i > 0 && weight != firstWeight) {
sameWeight = false;
}
}
}
...
//如果最小活跃值数组不止一个且大家权重不相同
//然后按照权重做随机选取
if (! sameWeight && totalWeight > 0) {
// 如果权重不相同且权重大于0则按总权重数随机
int offsetWeight = random.nextInt(totalWeight);
// 并确定随机值落在哪个片断上
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
if (offsetWeight <= 0)
return invokers.get(leastIndex);
}
}
// 权重相同或权重为0则均等随机
return invokers.get(leastIndexs[random.nextInt(leastCount)]);
}
- 活跃数统计ActiveLimitFilter
配置了Filter时,在开始调用方法时会beginCount,active++,方法调用结束时会active--
public Result invoke(Invoker<?> invoker, Invocation invocation) throws RpcException {
RpcStatus count = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
int active = count.getActive();
RpcStatus.beginCount(url, methodName);
Result result = invoker.invoke(invocation);
RpcStatus.endCount(url, methodName, System.currentTimeMillis() - begin, true);
return result;
}
private static void beginCount(RpcStatus status) {
status.active.incrementAndGet();
}
ConsistentHashLoadBalance
- 算法分析:
- 根据设置的参数和参数值的拼接,来通过Hash一致性算法,获取在圆上对应的Provider节点,默认配置160个虚拟节点,只取第一个参数的参数值进行散列
- 实现的效果是:类似优化粒度的随机取值,而且随机的好坏和散列的算法关联度很高。目前的API并没有支持动态的扩容和缩容,只是简单的初始化和选取节点。
- 该算法不参考权重值
- 配置
<dubbo:reference id="demoService" interface="com.mor.server.dubbo.service.DemoServer">
<dubbo:method name="sayHello" loadbalance="consistenthash"/>
</dubbo:reference>
- 源码分析
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
return selector.select(invocation);
}
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
...
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
argumentIndex = new int[index.length];
//构建一个160份镜像的散列的invoker
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
for (int i = 0; i < replicaNumber / 4; i++) {
byte[] digest = md5(address + i);
for (int h = 0; h < 4; h++) {
long m = hash(digest, h);
virtualInvokers.put(m, invoker);
}
}
}
哈希一致性算法
假如有2000张图片,图片名/图片路径 组成,有4台机器来存储,会进行图片进行CRUD操作。
- 如果采取随机法存储,那么每次get一张图片,最差需要遍历所有数据才能获取到对应的图片
- 哈希取余法,根据图片名称 散列成一个hashcode值,然后和4取余数,这样就可以大致均摊到4台服务器,而且每次get的时候,都只需要查找1个节点即可
- 哈希取余法的缺点:伸缩性不好,如果新增加一台机器,那么get图片就会出错,需要2000万条数据,全部重新排序,分配到5台节点。如果考虑缩减一个节点,也需要全部重新2000万数据重排列
- 哈希一致性算法:把各个节点按照serverId进行散列,让其尽可能的均匀的散布在一个最大值为 2的32次方的圆上,这样,这个圆上就有4个server节点,存储图片的时候,需要按照相同的算法,然后,分配到比自己值大的最近的一个节点。
- 哈希一致性的优点:新增和缩容的时候,只会影响到下一个节点,而不是全部节点要调整
-
新增一个节点的时候,比如之前节点在圆上的散落顺序是顺序散落,4台server求出来的hash值分别是 1、100、200、300,新增一台机器的E节点hash值是250,那么只需要把落在它的上一个节点,也就是D节点的所有数据(数据的key的区间是201-300)重新进行排列,然后该圆就仍然有效,不会影响到 A、B、C节点的数据。
image - 如果要缩容,去除掉D节点,只需要取出300节点的所有数据,全部分配给A节点即可。
- 哈希一致性算法引入虚拟节点:可以降低分散的不均匀性,但是会提升容量调整时的复杂性。
- 加入虚拟数为2,之前的排列是 A B C D,现在是 A1 B1 A2 C1 C2 D1 B2 D2,如果新增或者删除A节点,那么也只会影响到 *虚拟数的节点,也就是 B1 和C1节点,而不会影响其他 B2 C2 D1 D2节点
- 虚拟数越大,容量变化时需要调整的数据就越多,但是虚拟数越大,数据分布的就越均匀
Nginx的负载均衡算法
结合第三方插件,可以实现高可用,剔除掉出问题的节点
Nginx目前有5种负载均衡配置:
-
round_robin,加权轮询,是默认的HTTP负载均衡算法,适用于知道机器的性能,且默认所有的请求对于服务器而言,处理的时间相差不大。比如我Server1 比Server2的配置要高一倍,我设置为2:1的权重,可以实现比较科学的负载。算法实现上,简单的轮询很简单,给每个Server依次编号,然后只要记录一个调用index,既可以实现轮询。
-
ip_hash,IP哈希,可保持会话
-
least_conn; 避免了慢堆积,会取连接数最小的server提供服务,可以避免有些请求耗时长,有些耗时端的情况。根据实际的连接数选择服务器。
-
fair,需要插件扩展该功能,根据后端服务器的响应时间来分配请求,响应时间短的优先分配,避免慢堆积。
-
权重配置:而且采用的是平滑的负载均衡算法,比如node1:node2:node3=1:2:5 --> node3,node3,node2,node3,node1,node3,node2,node3
平滑的轮询负载均衡算法(Smooth Weighted Round Robin)
例如server-a:server-b:server-c=4:2:1。选取7次的话,选取的结果 server-a,server-b,server-a,server-c,server-a,server-b,server-a。
每次都筛选当前权重值最大的节点,然后对该节点权重值-totalWeight,然后所有的节点都grow一下,都用当前权重+init权重
初始化的时候大家的权重(4,2,1),Server-a的权重最大,选他干活,干完之后,a节点的权重-最大权重,a的当前权重为-3,然后所有节点的权重,都按照自己的初始权重自增一次(-3+4,2+2,1+1),也就是(1,4,2),开始第二轮选取
image
java代码实现
class Server{
int initWeigth;
int printCount=0;
int weigth;
String name;
}
public List<Server> init(){
Server server1=new Server(4,4,"server-a");
totalWeight+=4;
Server server2=new Server(2,2,"server-b");
totalWeight+=2;
Server server3=new Server(1,1,"server-c");
totalWeight+=1;
List<Server> list=new ArrayList();
list.add(server1);
list.add(server2);
list.add(server3);
return list;
}
public Server chooseServer(List<Server> list){
Server choosenServer=list.get(0);
for(int i=1;i<list.size();i++){
Server server=list.get(i);
if(choosenServer.getWeigth()<server.getWeigth()){
choosenServer=server;
}
}
choosenServer.setWeigth(choosenServer.getWeigth()-totalWeight);
return choosenServer;
}
public void grow(List<Server> list){
for(int i=0;i<list.size();i++){
Server server=list.get(i);
server.setWeigth(server.getWeigth()+server.getInitWeigth());
}
}
public static void main(String[] args) {
Test smooth=new Test();
List<Server> list=smooth.init();
for(int i=0;i<7;i++){
Server server= smooth.chooseServer(list);
System.out.println("server-"+server.getName()+" is working");
server.setPrintCount(server.getPrintCount()+1);
smooth.grow(list);
}
System.out.println("--------------------");
for(int i=0;i<list.size();i++){
Server server=list.get(i);
System.out.println(server.getName()+" initWeight-"+server.getInitWeigth()+" totalPrint-"+server.getPrintCount()+"times");
}
}
参考资料
https://blog.csdn.net/revivedsun/article/category/6435629
github中文官网
https://dubbo.gitbooks.io/dubbo-user-book/content/preface/background.html
哈希一致性算法
https://www.cnblogs.com/lpfuture/p/5796398.html
https://blog.csdn.net/bntX2jSQfEHy7/article/details/79549368
网友评论