文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java负载均衡算法实现之轮询和加权轮询

2024-04-02 19:55

关注

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);
        
        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);//打印所有节点
        
    }

    // 关键代码:类似于二维数组 降维成 一维数组,然后使用普通轮询
    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.概述

关键参数

注意几个点:

weight 权重,在整个过程不会对它做修改,只用来保存配置时的权重参数值。如果直接拿weight 运算而不保存配置的最原始权重参数,那么将会丢失最关键的用户配置的权重参数。

effectiveWeight 有效权重,在整个过程可能会变化,初始值等于weight,主要用于当节点出现分配失败时降低权重值,成功时提高权重值(但不能大于weight值),本案例为了简化算法,并未加入这功能,因此本案例中effectiveWeight始终等于weight。

currentWeight 当前权重,通过循环所有节点比对该值大小来分配权重最大的节点,初始值等于weight。

三个权重参数的变化情况

仅仅针对本案例,因为本案例为了简化算法,并未加入[节点出现分配失败时降低权重值,成功时提高权重值(但不能大于weight值)的功能],所以有效权重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

然后不断的进行下去……

简化成数学逻辑(代码实现)的关键两步

下面通过阅读代码来理解

2.2.3.代码实现

节点对象

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());
    }

    
    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值)的功能。理解了方式二,后面再加这块功能进去就很好理解了;

第二点:该算法实现的背后数学证明,用的是什么数学理论?

总结

到此这篇关于Java负载均衡算法实现之轮询和加权轮询的文章就介绍到这了,更多相关Java轮询和加权轮询算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯