Java 负载均衡算法作用详细解析

目录
  • 前言
  • 轮询算法
  • 随机算法
  • 加权随机算法
  • 加权轮询算法
  • 源地址hash算法
  • 最小请求数算法

前言

负载均衡在Java领域中有着广泛深入的应用,不管是大名鼎鼎的nginx,还是微服务治理组件如dubbo,feign等,负载均衡的算法在其中都有着实际的使用

负载均衡的核心思想在于其底层的算法思想,比如大家熟知的算法有 轮询,随机,最小连接,加权轮询等,在现实中不管怎么配置,都离不开其算法的核心原理,下面将结合实际代码对常用的负载均衡算法做一些全面的总结。

轮询算法

轮询即排好队,一个接一个的轮着来。从数据结构上,有一个环状的节点,节点上面布满了服务器,服务器之间首尾相连,带有顺序性。当请求过来的时候,从某个节点的服务器开始响应,那么下一次请求再来,就依次由后面的服务器响应,由此继续

按照这个描述,我们很容易联想到,可以使用一个双向(双端)链表的数据结构来模拟实现这个算法

1、定义一个server类,用于标识服务器中的链表节点

class Server {
    Server prev;
    Server next;
    String name;

    public Server(String name) {
        this.name = name;
    }
}

2、核心代码

/**
 * 轮询
 */
public class RData {
    private static Logger logger = LoggerFactory.getLogger(RData.class);
    //标识当前服务节点,每次请求过来时,返回的是current节点
    private Server current;

    public RData(String serverName) {
        logger.info("init servers : " + serverName);
        String[] names = serverName.split(",");
        for (int i = 0; i < names.length; i++) {
            Server server = new Server(names[i]);
            //当前为空,说明首次创建
            if (current == null) {
                //current就指向新创建server
                this.current = server;
                //同时,server的前后均指向自己
                current.prev = current;
                current.next = current;
            } else {
                //说明已经存在机器了,则按照双向链表的功能,进行节点添加
                addServer(names[i]);
            }
        }
    }

    //添加机器节点
    private void addServer(String serverName) {
        logger.info("add new server : " + serverName);
        Server server = new Server(serverName);
        Server next = this.current.next;
        //在当前节点后插入新节点
        this.current.next = server;
        server.prev = this.current;
        //由于是双向链表,修改下一节点的prev指针
        server.next = next;
        next.prev = server;
    }
    //机器节点移除,修改节点的指向即可
    private void removeServer() {
        logger.info("remove current = " + current.name);
        this.current.prev.next = this.current.next;
        this.current.next.prev = this.current.prev;
        this.current = current.next;
    }

    //请求。由当前节点处理
    private void request() {
        logger.info("handle server is : " + this.current.name);
        this.current = current.next;
    }

    public static void main(String[] args) throws Exception {
        //初始化两台机器
        RData rr = new RData("192.168.10.0,192.168.10.1");
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    rr.request();
                }
            }
        }).start();
        //3s后,3号机器加入清单
        Thread.currentThread().sleep(2000);
        rr.addServer("192.168.10.3");

        //3s后,当前服务节点被移除
        Thread.currentThread().sleep(3000);
        rr.removeServer();
    }
}

结合注释对代码进行理解,这段代码解释开来就是考察对双端链表的底层能力,操作链表结构时,最重要的就是要搞清在节点的添加和移除时,理清节点的前后指向,然后再理解这段代码时就没有难度了,下面运行下程序

轮询算法优缺点小结

  • 实现简单,机器列表可自由加减,节点寻找时间复杂度为o(1)
  • 无法针对节点做偏向性定制处理,节点处理能力强弱无法做区分对待,比如某些处理能力强配置高的服务器更希望承担更多的请求这个就做不到

随机算法

从可提供的服务器列表中随机取一个提供响应。

既然是随机存取的场景,很容易想到使用数组可以更高效的通过下标完成随机读取,这个算法的模拟比较简单,下面直接上代码

/**
 * 随机
 */
public class RandomMath {
    private static List<String> ips;
    public RandomMath(String nodeNames) {
        System.out.println("init servers : " + nodeNames);
        String[] nodes = nodeNames.split(",");
        //初始化服务器列表,长度取机器数
        ips = new ArrayList<>(nodes.length);
        for (String node : nodes) {
            ips.add(node);
        }
    }
    //请求处理
    public void request() {
        Random ra = new Random();
        int i = ra.nextInt(ips.size());
        System.out.println("the handle server is :" + ips.get(i));
    }
    //添加节点,注意,添加节点可能会造成内部数组扩容
    void addnode(String nodeName) {
        System.out.println("add new node : " + nodeName);
        ips.add(nodeName);
    }

    //移除
    void remove(String nodeName) {
        System.out.println("remove node is: " + nodeName);
        ips.remove(nodeName);
    }

    public static void main(String[] args) throws Exception {
        RandomMath rd = new RandomMath("192.168.10.1,192.168.10.2,192.168.10.3");
        //使用一个线程,模拟不间断的请求
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    rd.request();
                }
            }
        }).start();
        //间隔3秒之后,添加一台新的机器
        Thread.currentThread().sleep(3000);
        rd.addnode("192.168.10.4");

        //3s后,当前服务节点被移除
        Thread.currentThread().sleep(3000);
        rd.remove("192.168.10.2");

    }
}

运行代码观察结果:

随机算法小结

  • 随机算法简单高效
  • 适合一个服务器集群中,各个机器配置差不多的情况,和轮询一样,无法根据各个服务器本身的配置做一些定向的区分对待

加权随机算法

在随机选择的基础上,机器仍然是被随机被筛选,但是做一组加权值,根据权值不同,机器列表中的各个机器被选中的概率不同,从这个角度理解,可认为随机是一种等权值的特殊情况

设计思路依然相同,只是每个机器需要根据权值大小,生成不同数量的节点,节点排队后,随机获取。这里的数据结构主要涉及到随 机的读取,所以优选为数组

/**
 * 加权随机
 */
public class WeightRandom {
    ArrayList<String> list;

    public WeightRandom(String nodes) {
        String[] ns = nodes.split(",");
        list = new ArrayList<>();
        for (String n : ns) {
            String[] n1 = n.split(":");
            int weight = Integer.valueOf(n1[1]);
            for (int i = 0; i < weight; i++) {
                list.add(n1[0]);
            }
        }
    }

    public void request() {
        //下标,随机数,注意因子
        int i = new Random().nextInt(list.size());
        System.out.println("the handle server is : " + list.get(i));
    }
    public static void main(String[] args) throws Exception{
        WeightRandom wr = new WeightRandom("192.168.10.1:2,192.168.10.2:1");
        for (int i = 0; i < 9; i++) {
            Thread.sleep(2000);
            wr.request();
        }
    }
}

我们不妨将10.1的权重值再调的大点,比如调为3,再次运行一下,这个效果就更明显了

加权随机算法小结

  • 为随机算法的升级和优化
  • 一定程度上解决了服务器节点偏向问题,可以通过指定权重来提升某个机器的偏向

加权轮询算法

在前面的轮询算法中我们看到,轮询只是机械的旋转不断在双向链表中进行移动,而加权轮询则弥补了所有机器被一视同仁的缺点。在轮询的基础上,服务器初始化 时,各个机器携带一个权重值

加权轮询的算法思想不是很好理解,下面我以一个图进行说明:

加权轮询算法的初衷是希望通过这样一套算法保证整体的请求平滑性,从上图中也可以发现,经过几轮的循环之后,由可以回到最初的结果,而且在某一个轮询中,不同机器根据权重值的不同,请求被读取的概率也会不同

实现思路和轮询差不多,整体仍然是链表结构,不同的是,每个具体的节点需加上权重值属性

1、节点属性类

class NodeServer {

    int weight;
    int currentWeight;
    String ip;
    public NodeServer(String ip, int weight) {
        this.ip = ip;
        this.weight = weight;
        this.currentWeight = 0;
    }

    @Override
    public String toString() {
        return String.valueOf(currentWeight);
    }
}

2、核心代码

/**
 * 加权轮询
 */
public class WeightRDD {
    //所有机器节点列表
    ArrayList<NodeServer> list;

    //总权重
    int total;

    //机器节点初始化 , 格式:a#4,b#2,c#1,实际操作时可根据自己业务定制
    public WeightRDD(String nodes) {
        String[] ns = nodes.split(",");
        list = new ArrayList<>(ns.length);
        for (String n : ns) {
            String[] n1 = n.split("#");
            int weight = Integer.valueOf(n1[1]);
            list.add(new NodeServer(n1[0], weight));
            total += weight;
        }
    }
    public NodeServer getCurrent() {
        for (NodeServer node : list) {
            node.currentWeight += node.weight;
        }
        NodeServer current = list.get(0);
        int i = 0;
        //从列表中获取当前的currentWeight最大的那个作为待响应的节点
        for (NodeServer node : list) {
            if (node.currentWeight > i) {
                i = node.currentWeight;
                current = node;
            }
        }
        return current;
    }

    //请求,每次得到请求的节点之后,需要对当前的节点的currentWeight值减去 sumWeight
    public void request() {
        NodeServer node = this.getCurrent();
        System.out.print(list.toString() + "‐‐‐");
        System.out.print(node.ip + "‐‐‐");
        node.currentWeight -= total;
        System.out.println(list);
    }

    public static void main(String[] args) throws Exception {
        WeightRDD wrr = new WeightRDD("192.168.10.1#4,192.168.10.2#2,192.168.10.3#1");
        //7次执行请求,观察结果
        for (int i = 0; i < 7; i++) {
            Thread.currentThread().sleep(2000);
            wrr.request();
        }
    }
}

从打印输出结果来看,也是符合预期效果的,具有更大权重的机器,在轮询中被请求到的可能性更大

源地址hash算法

即对当前访问的ip地址做一个hash值,相同的key将会被路由到同一台机器去。常见于分布式集群环境下,用户登录 时的请求路由和会话保持

源地址hash算法可以有效解决在跨地域机器部署情况下请求响应的问题,这一特点使得源地址hash算法具有某些特殊的应用场景

该算法的核心逻辑是需要自定义一个能结合实际业务场景的hash算法,从而确保请求能够尽可能达到源IP机器进行处理

源地址hash算法的实现比较简单,下面直接上代码

/**
 * 源地址请求hash
 */
public class SourceHash {
    private static List<String> ips;
    //节点初始化
    public SourceHash(String nodeNames) {
        System.out.println("init list : " + nodeNames);
        String[] nodes = nodeNames.split(",");
        ips = new ArrayList<>(nodes.length);
        for (String node : nodes) {
            ips.add(node);
        }
    }
    //添加节点
    void addnode(String nodeName) {
        System.out.println("add new node : " + nodeName);
        ips.add(nodeName);
    }
    //移除节点
    void remove(String nodeName) {
        System.out.println("remove one node : " + nodeName);
        ips.remove(nodeName);
    }
    //ip进行hash
    private int hash(String ip) {
        int last = Integer.valueOf(ip.substring(ip.lastIndexOf(".") + 1, ip.length()));
        return last % ips.size();
    }
    //请求模拟
    void request(String ip) {
        int i = hash(ip);
        System.out.println("req ip : " + ip + "‐‐>" + ips.get(i));
    }

    public static void main(String[] args) throws Exception {
        SourceHash hash = new SourceHash("192.168.10.1,192.168.10.2");
        for (int i = 1; i < 10; i++) {
            String ip = "192.168.1." + i;
            hash.request(ip);
        }

        Thread.sleep(3000);
        System.out.println();

        hash.addnode("192.168.10.3");
        for (int i = 1; i < 10; i++) {
            String ip = "192.168.1." + i;
            hash.request(ip);
        }
        Thread.sleep(3000);
        System.out.println();
        hash.remove("192.168.10.1");
        for (int i = 1; i < 10; i++) {
            String ip = "192.168.1." + i;
            hash.request(ip);
        }
    }
}

请关注核心的方法 hash(),我们模拟9个随机请求的IP,下面运行下这段程序,观察输出结果

源地址hash算法小结

  • 可以有效匹配同一个源IP从而定向到特定的机器处理
  • 如果hash算法不够合理,可能造成集群中某些机器压力非常大
  • 未能很好的解决新节点加入之后打破原来的请求平衡(一致性hash可解决)

最小请求数算法

即通过统计当前机器的请求连接数,选择当前连接数最少的机器去响应新请求。前面的各种算法是基于请求的维度,而最小 连接数则是站在机器的连接数量维度

从描述来看,实现这种算法需要定义一个链接表记录机器的节点IP,和机器连接数量的计数器

而为了比较并选择出最小的连接数的机器,内部采用最小堆做排序处理,请求响应时取堆顶节点即是 最小连接数(可以参考最小顶堆算法)

如图所示,所有机器列表按照类二叉树的结构进行组装,组装的依据按照不同节点的访问次数,某次请求过来时,选择堆顶的元素(待响应的机器)返回,然后堆顶机器的请求数量加1,然后通过算法将这个堆顶的元素下沉,把请求数量最小的元素上升为堆顶,以便下次响应最新的请求

1、机器节点

该类记录了节点的IP以及连接数

class Node {
    String name;
    AtomicInteger count = new AtomicInteger(0);
    public Node(String name) {
        this.name = name;
    }
    public void inc() {
        count.getAndIncrement();
    }
    public int get() {
        return count.get();
    }
    @Override
    public String toString() {
        return name + "=" + count;
    }
}

2、核心代码

/**
 * 最小连接数算法
 */
public class LeastRequest {
    Node[] nodes;
    //节点初始化
    public LeastRequest(String ns) {
        String[] ns1 = ns.split(",");
        nodes = new Node[ns1.length + 1];
        for (int i = 0; i < ns1.length; i++) {
            nodes[i + 1] = new Node(ns1[i]);
        }
    }

    ///节点下沉,与左右子节点比对,选里面最小的交换
    //目的是始终保持最小堆的顶点元素值最小【结合图理解】
    //ipNum:要下沉的顶点序号
    public void down(int ipNum) {
        //顶点序号遍历,只要到1半即可,时间复杂度为O(log2n)
        while (ipNum << 1 < nodes.length) {
            int left = ipNum << 1;
            //右子,左+1即可
            int right = left + 1;
            int flag = ipNum;
            //标记,指向 本节点,左、右子节点里最小的,一开始取自己
            if (nodes[left].get() < nodes[ipNum].get()) {
                flag = left;
            }
            //判断右子
            if (right < nodes.length && nodes[flag].get() > nodes[right].get()) {
                flag = right;
            }
            //两者中最小的与本节点不相等,则交换
            if (flag != ipNum) {
                Node temp = nodes[ipNum];
                nodes[ipNum] = nodes[flag];
                nodes[flag] = temp;
                ipNum = flag;
            } else {
                //否则相等,堆排序完成,退出循环即可
                break;
            }
        }
    }
    //请求,直接取最小堆的堆顶元素就是连接数最少的机器
    public void request() {
        System.out.println("‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐");
        //取堆顶元素响应请求
        Node node = nodes[1];
        System.out.println(node.name + " accept");
        //连接数加1
        node.inc();
        //排序前的堆
        System.out.println("ip list before:" + Arrays.toString(nodes));
        //堆顶下沉,通过算法将堆顶下层到合适的位置
        down(1);
        //排序后的堆
        System.out.println("ip list after:" + Arrays.toString(nodes));
    }

    public static void main(String[] args) {
        //假设有7台机器
        LeastRequest lc = new LeastRequest("10.1,10.2,10.3,10.4,10.5,10.6,10.7");
        //模拟10个请求连接
        for (int i = 0; i < 10; i++) {
            lc.request();
        }
    }
}

请关注 down 方法,该方法是实现每次请求之后,将堆顶元素进行移动的关键实现,运行这段代码,结合输出结果进行理解

最小连接数算法小结

  • 实现相比其他的算法稍微复杂一些
  • 从最小连接数的维度考量,能充分考虑到环境的影响,看似更合理

负载均衡的各种算法在Nginx的配置中都有着实际的用途,生产环境中可以结合实际的业务进行配置,了解了其底层的算法对于我们在后续的配置中更加得心应手,

到此这篇关于Java 负载均衡算法作用详细解析的文章就介绍到这了,更多相关Java 负载均衡内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java实现5种负载均衡算法(小结)

    目录 概念 轮询算法 加权轮询法 加权随机法 随机法 IP_Hash算法 概念 负载均衡是将客户端请求访问,通过提前约定好的规则转发给各个server.其中有好几个种经典的算法,下面我们用Java实现这几种算法. 轮询算法 轮询算法按顺序把每个新的连接请求分配给下一个服务器,最终把所有请求平分给所有的服务器. 优点:绝对公平 缺点:无法根据服务器性能去分配,无法合理利用服务器资源. package com.monkeyjava.learn.basic.robin; import com.goog

  • 详解Java实现负载均衡的几种算法代码

    本篇文章主要介绍Java实现负载均衡的几种算法,具体如下: 轮询: package class2.zookeeper.loadbalance; import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Set; /** * 負載均衡算法,輪詢法 * @author guoy * */ public class TestRoundRobin { static Map<St

  • Java 负载均衡的 5 种算法实现原理

    目录 一.负载均衡算法简介 1.轮询法 2.随机法 3.源地址哈希法 4.加权轮询法 5.加权随机法 二.代码实现负载均衡五种算法 1.轮询法 2.加权轮询法 3.随机法 4.加权随机 5.源地址哈希法 前言: 什么是负载均衡: 指由多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的辅助.通过某种 负载分担技术,将外部发送来的请求均匀分配到对称结构中的某一台服务器上,而接收到请求的服务器独立地回应客户的请求.负载均衡能够平均分配客户请求

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

    目录 1.普通轮询算法 2.加权轮询算法 2.1.实现方式一 2.2.实现方式二(重点难点) 2.2.1.概述 2.2.2.举个例子理解算法 2.2.3.代码实现 总结 1.普通轮询算法 轮询(Round Robin,RR)是依次将用户的访问请求,按循环顺序分配到web服务节点上,从1开始到最后一台服务器节点结束,然后再开始新一轮的循环.这种算法简单,但是没有考虑到每台节点服务器的具体性能,请求分发往往不均衡. 代码实现: /** * 普通轮询算法 */public class RoundRob

  • 使用Java实现5种负载均衡算法实例

    目录 前言 概念 几种负载均衡算法图例 轮询算法 加权轮询法 加权随机法 随机法 IP_Hash算法 总结 前言 负载均衡是为了解决并发情况下,多个请求访问,把请求通过提前约定好的规则转发给各个server.其中有好几个种经典的算法.在用java代码编写这几种算法之前,先来了解一下负载均衡这个概念. 概念 负载均衡是将客户端请求访问,通过提前约定好的规则转发给各个server.其中有好几个种经典的算法,下面我们用Java实现这几种算法. 几种负载均衡算法图例 主要的负载均衡算法是图中这些,在代码

  • Java 负载均衡算法作用详细解析

    目录 前言 轮询算法 随机算法 加权随机算法 加权轮询算法 源地址hash算法 最小请求数算法 前言 负载均衡在Java领域中有着广泛深入的应用,不管是大名鼎鼎的nginx,还是微服务治理组件如dubbo,feign等,负载均衡的算法在其中都有着实际的使用 负载均衡的核心思想在于其底层的算法思想,比如大家熟知的算法有 轮询,随机,最小连接,加权轮询等,在现实中不管怎么配置,都离不开其算法的核心原理,下面将结合实际代码对常用的负载均衡算法做一些全面的总结. 轮询算法 轮询即排好队,一个接一个的轮着

  • Nginx 负载均衡算法及故障转移解析

    概述 Nginx负载均衡提供上游服务器(真实业务逻辑访问的服务器),负载均衡.故障转移.失败重试.容错.健康检查等. 当上游服务器(真实业务逻辑访问的服务器)发生故障时,可以转移到其他上游服务器(真实业务逻辑访问的服务器). 配置 upstream backServer{ server 127.0.0.1:8080; server 127.0.0.1:8081; } server { listen 80; server_name www.itmayiedu.com; location / { #

  • Spring Cloud负载均衡组件Ribbon原理解析

    目录 前言 一个问题引发的思考 Ribbon的简单使用 Ribbon 原理分析 LoadBalancerAutoConfiguration 自动装配 RestTemplateCustomizer LoadBalancerInterceptor RibbonLoadBalancerClient#execute ZoneAwareLoadBalancer 负载均衡器 如何获取所有服务 如何判断服务是否可用 Ribbon 的负载均衡算法 总结 微服务体系下的 Spring Cloud Netflix

  • vue.js diff算法原理详细解析

    目录 diff算法的概念 虚拟Dom h函数 diff对比规则 patch patchVnode updateChildren 总结 diff算法的概念 diff算法可以看作是一种对比算法,对比的对象是新旧虚拟Dom.顾名思义,diff算法可以找到新旧虚拟Dom之间的差异,但diff算法中其实并不是只有对比虚拟Dom,还有根据对比后的结果更新真实Dom. 虚拟Dom 上面的概念我们提到了虚拟Dom,相信大家对这个名词并不陌生,下面为大家解释一下虚拟Dom的概念,以及diff算法中为什么要对比虚拟

  • Springcloud ribbon负载均衡算法实现

    一 前言 经过几篇的cloud系列文章,我想大家都有一个坚实的基础,后续的学习就会轻松很多,如果是刚刚来看的读者需要有eureka基础知识,或者查阅知识追寻者的cloud系列专栏:这篇文章主要讲解如何使用ribbon实现web service客户端调用,ribbon默认算法实现负载均衡等! 二 ribbon简介 ribbon是一个客户端负载均衡器,其能够整合不同的协议工具进行web service API 调用: 主要特色如下: 提供可插拔式的负载均衡整合服务发现故障弹性恢复cloud支持客户端

  • 关于java中@Async异步调用详细解析附代码

    目录 前言 1. @Async讲解 2. 用法 2.1 同步调用 2.2 异步调用 3. 自定义线程池 前言 异步调用与同步调用 同步调用:顺序执行,通过调用返回结果再次执行下一个调用 异步调用:通过调用,无需等待返回结果,执行下一个调用 1. @Async讲解 其@Async的注解代码如下: @Target({ElementType.TYPE, ElementType.METHOD}) @Retention(RetentionPolicy.RUNTIME) @Documented public

随机推荐