Java负载均衡算法实现之轮询和加权轮询
作者:持行非就 发布时间:2023-07-16 15:27:17
1.普通轮询算法
轮询(Round Robin,RR)是依次将用户的访问请求,按循环顺序分配到web服务节点上,从1开始到最后一台服务器节点结束,然后再开始新一轮的循环。这种算法简单,但是没有考虑到每台节点服务器的具体性能,请求分发往往不均衡。
代码实现:
/**
* 普通轮询算法
*/public class RoundRobin {
private static Integer index = 0;
private static List<String> nodes = new ArrayList<>();
// 准备模拟数据
static {
nodes.add("192.168.1.101");
nodes.add("192.168.1.103");
nodes.add("192.168.1.102");
System.out.println("普通轮询算法的所有节点:"+nodes);//打印所有节点
}
// 关键代码
public String selectNode(){
String ip = null;
synchronized (index){
// 下标复位
if(index>=nodes.size()) index = 0;
ip = nodes.get(index);
index++;
}
return ip;
}
// 并发测试:两个线程循环获取节点
public static void main(String[] args) {
new Thread(() -> {
RoundRobin roundRobin1 = new RoundRobin();
for (int i=1;i<=5;i++){
String serverIp = roundRobin1.selectNode();
System.out.println(Thread.currentThread().getName()+"==第"+i+"次获取节点:"+serverIp);
}
}).start();
RoundRobin roundRobin2 = new RoundRobin();
for (int i=1;i<=nodes.size();i++){
String serverIp = roundRobin2.selectNode();
System.out.println(Thread.currentThread().getName()+"==第"+i+"次获取节点:"+serverIp);
}
}
}
执行结果:不同线程访问,结果依旧是按顺序循环分配节点
普通轮询算法的所有节点:[192.168.1.101, 192.168.1.103, 192.168.1.102]
main==第1次获取节点:192.168.1.101
Thread-0==第1次获取节点:192.168.1.103
Thread-0==第2次获取节点:192.168.1.102
Thread-0==第3次获取节点:192.168.1.101
Thread-0==第4次获取节点:192.168.1.103
Thread-0==第5次获取节点:192.168.1.102
main==第2次获取节点:192.168.1.101
main==第3次获取节点:192.168.1.103
2.加权轮询算法
加权轮询(Weighted Round Robin,WRR)是根据设定的权重值来分配访问请求,权重值越大的,被分到的请求数也就越多。一般根据每台节点服务器的具体性能来分配权重。
2.1.实现方式一
将需要轮询的所有节点按权重数循环生成一个List 集合,然后就跟普通轮询算法一样,来一个、分配一个、进1位。
例如:
所有节点信息:{{“192.168.1.100“,5},{“192.168.1.101“,1},{“192.168.1.102“,3}}
那么生成的List 集合为:
{“192.168.1.100“,
“192.168.1.100“,
“192.168.1.100“,
“192.168.1.100“,
“192.168.1.100“,
“192.168.1.101“,
“192.168.1.102“,
“192.168.1.102“,
“192.168.1.102“}
后面就是普通轮询算法的逻辑
代码实现:
类似于二维数组 降维成 一维数组,然后使用普通轮询
/**
* 简单版的加权轮询
*/public class WeightedRoundRobinSimple {
private static Integer index = 0;
private static Map<String,Integer> mapNodes = new HashMap<>();
// 准备模拟数据
static {
mapNodes.put("192.168.1.101",1);
mapNodes.put("192.168.1.102",3);
mapNodes.put("192.168.1.103",2);
/* -- 以下代码只为了方便查看所有节点,删除不影响 -- S */
List<String> nodes = new ArrayList<>();
Iterator<Map.Entry<String, Integer>> iterator = mapNodes.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<String, Integer> entry = iterator.next();
String key = entry.getKey();
for (int i=0;i<entry.getValue();i++){
nodes.add(key);
}
}
System.out.println("简单版的加权轮询:"+nodes);//打印所有节点
/* -- 以上代码只为了方便查看所有节点,删除不影响-- E */
}
// 关键代码:类似于二维数组 降维成 一维数组,然后使用普通轮询
public String selectNode(){
List<String> nodes = new ArrayList<>();
Iterator<Map.Entry<String, Integer>> iterator = mapNodes.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<String, Integer> entry = iterator.next();
String key = entry.getKey();
for (int i=0;i<entry.getValue();i++){
nodes.add(key);
}
}
String ip = null;
synchronized (index){
// 下标复位
if(index>=nodes.size()) index = 0;
ip = nodes.get(index);
index++;
}
return ip;
}
// 并发测试:两个线程循环获取节点
public static void main(String[] args) {
new Thread(() -> {
WeightedRoundRobinSimple roundRobin1 = new WeightedRoundRobinSimple();
for (int i=1;i<=6;i++){
String serverIp = roundRobin1.selectNode();
System.out.println(Thread.currentThread().getName()+"==第"+i+"次获取节点:"+serverIp);
}
}).start();
WeightedRoundRobinSimple roundRobin2 = new WeightedRoundRobinSimple();
for (int i=1;i<=6;i++){
String serverIp = roundRobin2.selectNode();
System.out.println(Thread.currentThread().getName()+"==第"+i+"次获取节点:"+serverIp);
}
}
}
执行结果:两个线程循环测试,输出结果会出现交替分配到不同的IP,但最终的效果都是一个个按顺序分配,类似于普通轮询算法。
简单版的加权轮询:[192.168.1.103, 192.168.1.103, 192.168.1.101, 192.168.1.102, 192.168.1.102, 192.168.1.102]
main==第1次获取节点:192.168.1.103
main==第2次获取节点:192.168.1.103
main==第3次获取节点:192.168.1.101
main==第4次获取节点:192.168.1.102
main==第5次获取节点:192.168.1.102
Thread-0==第1次获取节点:192.168.1.102
Thread-0==第2次获取节点:192.168.1.103
main==第6次获取节点:192.168.1.103
Thread-0==第3次获取节点:192.168.1.101
Thread-0==第4次获取节点:192.168.1.102
Thread-0==第5次获取节点:192.168.1.102
Thread-0==第6次获取节点:192.168.1.102
2.2.实现方式二(重点难点)
本文的重点难点。
在实现方式一的算法中可以很明显的看到,同权重的IP会被连续分配,也就是说同一个IP在短时间内收到不同的请求,过了这个连续点,就要等到下一轮才会被分配到,并没有做到均匀分配节点。
实现方式二将尽可能地均匀分配每个节点,节点分配不再是连续的,但最终的权重比和上一个方式一样,这种加权轮询又被称为平滑加权轮询。
理解关键的几个参数和算法逻辑,方便理解代码的实现。
2.2.1.概述
关键参数
ip:负载IP
weight:权重,保存配置的权重
effectiveWeight:有效权重,轮询的过程权重可能变化
currentWeight:当前权重,比对该值大小获取节点
注意几个点:
weight 权重,在整个过程不会对它做修改,只用来保存配置时的权重参数值。如果直接拿weight 运算而不保存配置的最原始权重参数,那么将会丢失最关键的用户配置的权重参数。
effectiveWeight 有效权重,在整个过程可能会变化,初始值等于weight,主要用于当节点出现分配失败时降低权重值,成功时提高权重值(但不能大于weight值),本案例为了简化算法,并未加入这功能,因此本案例中effectiveWeight始终等于weight。
currentWeight 当前权重,通过循环所有节点比对该值大小来分配权重最大的节点,初始值等于weight。
三个权重参数的变化情况
仅仅针对本案例,因为本案例为了简化算法,并未加入[节点出现分配失败时降低权重值,成功时提高权重值(但不能大于weight值)的功能],所以有效权重effectiveWeight 不会发生变化。
第一次加权轮询时:currentWeight = weight = effectiveWeight;
后面每次加权轮询时:currentWeight 的值都会不断变化,weight 和effectiveWeight 的值不变;
被分配的节点的currentWeight = currentWeight - 权重之和
所有节点的currentWeight = currentWeight + effectiveWeight
2.2.2.举个例子理解算法
你面前有三个瓶子A、B、C,分别装有1L、3L、2L水。
第一轮分配情况:B多,所以把B瓶子的3L水,分1L给A,分2L给C(按权重分),分完之后:A、B、C分别为:2L、0L、4L
第二轮分配情况:C多,所以把C瓶子的4L水,分1L给A,分3L给B(按权重分),分完之后:A、B、C分别为:3L、3L、0L
第三轮分配情况:A和B一样多,那么拿谁去分呢?拿谁其实都一样(算法中写了A大于B才选A,现在等于,所以不选A),所以把B瓶子的3L水,分1L给A,分2L给C(按权重分),分完之后:A、B、C分别为:4L、0L、2L
然后不断的进行下去……
简化成数学逻辑(代码实现)的关键两步
被分配的节点的currentWeight = currentWeight - 权重之和
所有节点的currentWeight = currentWeight + effectiveWeight
下面通过阅读代码来理解
2.2.3.代码实现
节点对象
/**
* String ip:负载IP
* final Integer weight:权重,保存配置的权重
* Integer effectiveWeight:有效权重,轮询的过程权重可能变化
* Integer currentWeight:当前权重,比对该值大小获取节点
* 第一次加权轮询时:currentWeight = weight = effectiveWeight
* 后面每次加权轮询时:currentWeight 的值都会不断变化,其他权重不变
*/public class Node implements Comparable<Node>{
private String ip;
private final Integer weight;
private Integer effectiveWeight;
private Integer currentWeight;
public Node(String ip,Integer weight){
this.ip = ip;
this.weight = weight;
this.effectiveWeight = weight;
this.currentWeight = weight;
}
public Node(String ip, Integer weight, Integer effectiveWeight, Integer currentWeight) {
this.ip = ip;
this.weight = weight;
this.effectiveWeight = effectiveWeight;
this.currentWeight = currentWeight;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public Integer getWeight() {
return weight;
}
public Integer getEffectiveWeight() {
return effectiveWeight;
}
public void setEffectiveWeight(Integer effectiveWeight) {
this.effectiveWeight = effectiveWeight;
}
public Integer getCurrentWeight() {
return currentWeight;
}
public void setCurrentWeight(Integer currentWeight) {
this.currentWeight = currentWeight;
}
@Override
public int compareTo(Node node) {
return currentWeight > node.currentWeight ? 1 : (currentWeight.equals(node.currentWeight) ? 0 : -1);
}
@Override
public String toString() {
return "{ip='" + ip + "', weight=" + weight + ", effectiveWeight=" + effectiveWeight + ", currentWeight=" + currentWeight + "}";
}
}
加权轮询算法
/**
* 加权轮询算法
*/public class WeightedRoundRobin {
private static List<Node> nodes = new ArrayList<>();
// 权重之和
private static Integer totalWeight = 0;
// 准备模拟数据
static {
nodes.add(new Node("192.168.1.101",1));
nodes.add(new Node("192.168.1.102",3));
nodes.add(new Node("192.168.1.103",2));
nodes.forEach(node -> totalWeight += node.getEffectiveWeight());
}
/**
* 按照当前权重(currentWeight)最大值获取IP
* @return Node
*/
public Node selectNode(){
if (nodes ==null || nodes.size()<=0) return null;
if (nodes.size() == 1) return nodes.get(0);
Node nodeOfMaxWeight = null; // 保存轮询选中的节点信息
synchronized (nodes){
// 打印信息对象:避免并发时打印出来的信息太乱,不利于观看结果
StringBuffer sb = new StringBuffer();
sb.append(Thread.currentThread().getName()+"==加权轮询--[当前权重]值的变化:"+printCurrentWeight(nodes));
// 选出当前权重最大的节点
Node tempNodeOfMaxWeight = null;
for (Node node : nodes) {
if (tempNodeOfMaxWeight == null)
tempNodeOfMaxWeight = node;
else
tempNodeOfMaxWeight = tempNodeOfMaxWeight.compareTo(node) > 0 ? tempNodeOfMaxWeight : node;
}
// 必须new个新的节点实例来保存信息,否则引用指向同一个堆实例,后面的set操作将会修改节点信息
nodeOfMaxWeight = new Node(tempNodeOfMaxWeight.getIp(),tempNodeOfMaxWeight.getWeight(),tempNodeOfMaxWeight.getEffectiveWeight(),tempNodeOfMaxWeight.getCurrentWeight());
// 调整当前权重比:按权重(effectiveWeight)的比例进行调整,确保请求分发合理。
tempNodeOfMaxWeight.setCurrentWeight(tempNodeOfMaxWeight.getCurrentWeight() - totalWeight);
sb.append(" -> "+printCurrentWeight(nodes));
nodes.forEach(node -> node.setCurrentWeight(node.getCurrentWeight()+node.getEffectiveWeight()));
sb.append(" -> "+printCurrentWeight(nodes));
System.out.println(sb); //打印权重变化过程
}
return nodeOfMaxWeight;
}
// 格式化打印信息
private String printCurrentWeight(List<Node> nodes){
StringBuffer stringBuffer = new StringBuffer("[");
nodes.forEach(node -> stringBuffer.append(node.getCurrentWeight()+",") );
return stringBuffer.substring(0, stringBuffer.length() - 1) + "]";
}
// 并发测试:两个线程循环获取节点
public static void main(String[] args){
Thread thread = new Thread(() -> {
WeightedRoundRobin weightedRoundRobin1 = new WeightedRoundRobin();
for(int i=1;i<=totalWeight;i++){
Node node = weightedRoundRobin1.selectNode();
System.out.println(Thread.currentThread().getName()+"==第"+i+"次轮询选中[当前权重最大]的节点:" + node + "\n");
}
});
thread.start();
//
WeightedRoundRobin weightedRoundRobin2 = new WeightedRoundRobin();
for(int i=1;i<=totalWeight;i++){
Node node = weightedRoundRobin2.selectNode();
System.out.println(Thread.currentThread().getName()+"==第"+i+"次轮询选中[当前权重最大]的节点:" + node + "\n");
}
}
}
执行结果:
main==加权轮询--[当前权重]值的变化:[1,3,2] -> [1,-3,2] -> [2,0,4] main==第1次轮询选中[当前权重最大]的节点:{ip='192.168.1.102', weight=3, effectiveWeight=3, currentWeight=3}
Thread-0==加权轮询--[当前权重]值的变化:[2,0,4] -> [2,0,-2] -> [3,3,0] Thread-0==第1次轮询选中[当前权重最大]的节点:{ip='192.168.1.103', weight=2, effectiveWeight=2, currentWeight=4}
main==加权轮询--[当前权重]值的变化:[3,3,0] -> [3,-3,0] -> [4,0,2] main==第2次轮询选中[当前权重最大]的节点:{ip='192.168.1.102', weight=3, effectiveWeight=3, currentWeight=3}
main==加权轮询--[当前权重]值的变化:[4,0,2] -> [-2,0,2] -> [-1,3,4] main==第3次轮询选中[当前权重最大]的节点:{ip='192.168.1.101', weight=1, effectiveWeight=1, currentWeight=4}
Thread-0==加权轮询--[当前权重]值的变化:[-1,3,4] -> [-1,3,-2] -> [0,6,0] Thread-0==第2次轮询选中[当前权重最大]的节点:{ip='192.168.1.103', weight=2, effectiveWeight=2, currentWeight=4}
main==加权轮询--[当前权重]值的变化:[0,6,0] -> [0,0,0] -> [1,3,2] main==第4次轮询选中[当前权重最大]的节点:{ip='192.168.1.102', weight=3, effectiveWeight=3, currentWeight=6}
Thread-0==加权轮询--[当前权重]值的变化:[1,3,2] -> [1,-3,2] -> [2,0,4] Thread-0==第3次轮询选中[当前权重最大]的节点:{ip='192.168.1.102', weight=3, effectiveWeight=3, currentWeight=3}
main==加权轮询--[当前权重]值的变化:[2,0,4] -> [2,0,-2] -> [3,3,0] main==第5次轮询选中[当前权重最大]的节点:{ip='192.168.1.103', weight=2, effectiveWeight=2, currentWeight=4}
Thread-0==加权轮询--[当前权重]值的变化:[3,3,0] -> [3,-3,0] -> [4,0,2] Thread-0==第4次轮询选中[当前权重最大]的节点:{ip='192.168.1.102', weight=3, effectiveWeight=3, currentWeight=3}
main==加权轮询--[当前权重]值的变化:[4,0,2] -> [-2,0,2] -> [-1,3,4] main==第6次轮询选中[当前权重最大]的节点:{ip='192.168.1.101', weight=1, effectiveWeight=1, currentWeight=4}
Thread-0==加权轮询--[当前权重]值的变化:[-1,3,4] -> [-1,3,-2] -> [0,6,0] Thread-0==第5次轮询选中[当前权重最大]的节点:{ip='192.168.1.103', weight=2, effectiveWeight=2, currentWeight=4}
Thread-0==加权轮询--[当前权重]值的变化:[0,6,0] -> [0,0,0] -> [1,3,2] Thread-0==第6次轮询选中[当前权重最大]的节点:{ip='192.168.1.102', weight=3, effectiveWeight=3, currentWeight=6}
为了方便分析,简化两线程执行后的结果
[当前权重]值的变化:[1,3,2] -> [1,-3,2] -> [2,0,4]
[当前权重]值的变化:[2,0,4] -> [2,0,-2] -> [3,3,0]
[当前权重]值的变化:[3,3,0] -> [3,-3,0] -> [4,0,2]
[当前权重]值的变化:[4,0,2] -> [-2,0,2] -> [-1,3,4]
[当前权重]值的变化:[-1,3,4] -> [-1,3,-2] -> [0,6,0]
[当前权重]值的变化:[0,6,0] -> [0,0,0] -> [1,3,2]
[当前权重]值的变化:[1,3,2] -> [1,-3,2] -> [2,0,4]
[当前权重]值的变化:[2,0,4] -> [2,0,-2] -> [3,3,0]
[当前权重]值的变化:[3,3,0] -> [3,-3,0] -> [4,0,2]
[当前权重]值的变化:[4,0,2] -> [-2,0,2] -> [-1,3,4]
[当前权重]值的变化:[-1,3,4] -> [-1,3,-2] -> [0,6,0]
[当前权重]值的变化:[0,6,0] -> [0,0,0] -> [1,3,2]
因为整个过程只有当前权重发生变化,所以分析清楚它就明白了整个过程。
结论:
分配完成后当前权重发生变化,但权限之和还是等于最初值;
每6轮(1+3+2权重)就出现权重全部为0,所以会出现重新循环,6正好等于权重之和,权重比等于1/6 : 3/6 : 2/6;
a=权重1,b=权重3,c=权重2,那么权重变化的6(a+b+c)次中,分配情况为:b c b a c b,很明显,每个节点均匀按权重分配,节点分配不再是连续的。这也是最重要的结论,正是实现方式二在文初提到的要实现的关键点。
该算法在权重比相差很大时,比如:A=1,B=5,那这个算法的结果就跟方式一没啥区别了,分配结果就变成了:{A,B,B,B,B,B},既然没区别,那根据算法复杂情况,那肯定方式一更好了,所以方式一和方式二可以互补,可以根据权重比选择不同的算法。
留下悬念
第一点:节点出现分配失败时降低有效权重值,成功时提高有效权重值(但不能大于weight值)的功能。理解了方式二,后面再加这块功能进去就很好理解了;
第二点:该算法实现的背后数学证明,用的是什么数学理论?
来源:https://www.cnblogs.com/dennyLee2025/p/16128477.html
猜你喜欢
- 前言最近项目中需要与andorid端进行交互,采用了MQTT消息进行通信,生产环境中偶尔会出现Too many publishesin pr
- 描述说明:public class TryCatchStu { /*try catch:自己处理异常 *t
- 在工作过程中,需要将一个文件夹生成压缩文件,然后提供给用户下载。所以自己写了一个压缩文件的工具类。该工具类支持单个文件和文件夹压缩。放代码:
- 属性问题引入前面我们已经在父工程中的dependencyManagement标签中对项目中所使用的jar包版本进行了统一的管理,但是如果在标
- 一:算术运算符1.算术运算符有哪些①基本四则运算符:+ - * / %②增量赋值运算符:+= -= *= /= %=③自增/自减运算符++
- 1.以ApplocationContext上下文单例模式装配bean为例,深入探讨bean的生命周期:(1).生命周期图:(2).具体事例:
- 访问修饰符都知道是什么,但是在这之前没有深入的去研究和探索,每天都接触的东西应该清楚才可以。最基础的三个访问修饰符:public 、priv
- 前言工作中你可能会遇到很多这样的场景,一个接口,要从其他几个service调用查询方法,分别获取到需要的值之后再封装数据返回。还可能在微服务
- 示例1:public static String hello() { String s = "商务&qu
- 本文实例为大家分享了Winform实现导入导出Excel文件的具体代码,供大家参考,具体内容如下/// <summary> &n
- 1,实现方法一:通过给当前界面布局文件的父layout设置点击事件(相当于给整个Activity设置点击事件),在事件里进行键盘隐藏<
- 需求是在我按下按钮时,该变按钮颜色,使用户感觉到自己按了按钮,当松开的时候,变回原来的颜色。正常时:按下时:有人说,直接监听按钮的按下事件不
- pom.xml增加依赖包 <dependency> <groupId>io.springf
- 目录Spring事件驱动源码实战在项目实际开发过程中,我们有很多这样的业务场景:一个事务中处理完一个业务逻辑后需要跟着处理另外一个业务逻辑,
- 本文实例讲述了Android DatePicker和DatePickerDialog基本用法。分享给大家供大家参考,具体如下:DatePic
- 本文实例讲述了Android编程实现ActionBar的home图标动画切换效果。分享给大家供大家参考,具体如下:Material Desi
- 在作应用系统开发时,管理配置是必不可少的。例如数据库服务器的配置、安装和更新配置等等。由于Xml的兴起,现在的配置文件大都是以xml文档来存
- using System;using System.Collections.Generic;using System.IO;using Sy
- 本篇文章介绍自定义View配合属性动画来实现如下的效果实现思路挺简单:画一个半透明的圆实现两种动画效果,点击时扩散和不点击时扩散回收使用线程
- 本文实例讲述了java继承中的构造方法。分享给大家供大家参考。具体如下:继承中的构造方法: 1、子类的构造过程中必须调用其基类的构造方法。2