Java 常用负载均衡算法解析

灰太狼 2022-09-07 05:59 246阅读 0赞

## 前言 ##

负载均衡在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();
        }
    
    }

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]

**轮询算法优缺点小结**

*  实现简单，机器列表可自由加减，节点寻找时间复杂度为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");
    
        }
    
    }

运行代码观察结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]  
**随机算法小结**

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

## 加权随机算法 ##

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

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

/**
     * 加权随机
     */
    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();
            }
        }
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 2]  
我们不妨将10.1的权重值再调的大点，比如调为3，再次运行一下，这个效果就更明显了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 3]

**加权随机算法小结**

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

## 加权轮询算法 ##

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 6]

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

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

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

从打印输出结果来看，也是符合预期效果的，具有更大权重的机器，在轮询中被请求到的可能性更大  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 7]

## 源地址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，下面运行下这段程序，观察输出结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 8]

**源地址hash算法小结**

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

## 最小请求数算法 ##

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 9]

如图所示，所有机器列表按照类二叉树的结构进行组装，组装的依据按照不同节点的访问次数，某次请求过来时，选择堆顶的元素（待响应的机器）返回，然后堆顶机器的请求数量加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 方法，该方法是实现每次请求之后，将堆顶元素进行移动的关键实现，运行这段代码，结合输出结果进行理解

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 10]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 11]

**最小连接数算法小结**

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

**负载均衡的各种算法在Nginx的配置中都有着实际的用途，生产环境中可以结合实际的业务进行配置，了解了其底层的算法对于我们在后续的配置中更加得心应手，本篇到此结束，最后感谢观看！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: /images/20220829/67d7f8f527714b4594fb01dfa11ae3df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]: /images/20220829/da06deb3e2ea402cb60f281c1e441074.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 2]: /images/20220829/7c2486a8cc2f4f42b6e2d7f8f3115707.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 3]: /images/20220829/7f7ea7c333c241578f402549c033567d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 4]: /images/20220829/97fb01dbfafe4643b4d44ba3b98ca152.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 5]: /images/20220829/0d1116484c3f47a9847caeb9fff44bf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 6]: /images/20220829/e2a278ecb45d48f79b77b45ba79aaff0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 7]: /images/20220829/19ec7e19bac346d2ac294070daf8443b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 8]: /images/20220829/23886af383104e0487a1db4e3c403260.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 9]: /images/20220829/31d3bcb79c2f413f9c0aacb258b6a0d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 10]: /images/20220829/57a39a7c419c41268edc2ae7732f607d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 11]: /images/20220829/335eb17cb0d44acfa9a0b107c6624a25.png