---
title: Java实现常见的负载均衡算法
date: 2022-08-08
tags:
- 随笔
categories:
- 随笔 Essay
isShowComments: true
---

<Boxx/>

<!-- more -->

## 什么是负载均衡

负载平衡（Load balancing）是一种电子计算机技术，用来在多个计算机（计算机集群）、网络连接、CPU、磁盘驱动器或其他资源中分配负载，以达到优化资源使用、最大化吞吐率、最小化响应时间、同时避免过载的目的。 使用带有负载平衡的多个服务器组件，取代单一的组件，可以通过冗余提高可靠性。负载平衡服务通常是由专用软件和硬件来完成。 主要作用是将大量作业合理地分摊到多个操作单元上进行执行，用于解决互联网架构中的高并发和高可用的问题。

## 常见的负载均衡算法

### 1.轮询（Round Robin）

轮询算法按照顺序将新的请求分配给下一个服务器，最终实现平分请求。

实例：已知服务器： s1 ，s2， s3

请求1 -> s1

请求2-> s2

请求3 -> s3

请求4 -> s1

请求5 -> s2

请求6 -> s3

…

优点：

 实现简单，无需记录各种服务的状态，是一种无状态的负载均衡策略。

 实现绝对公平

缺点：当各个服务器性能不一致的情况，无法根据服务器性能去分配，无法合理利用服务器资源。

java实现轮询算法：

思路：根据上面的介绍，依次的选择下一个服务器，轮询算法具有周期性的特性，这就是典型的周期性概念，我们第一想法应该就是取余了。

这里推荐大家《程序员的数学1》里面介绍了一些数学和编程思维的一些案例，其中就有介绍周期和分组的思想，个人感觉这本书还是不错的，推荐给大家。

```java
public class RoundRobin {

    @Data
    public static class Server {

        private int serverId;

        private String name;

        private int weight;

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

        public Server(int serverId, String name, int weight) {
            this.serverId = serverId;
            this.name = name;
            this.weight = weight;
        }
    }

    private static AtomicInteger NEXT_SERVER_COUNTER = new AtomicInteger(0);

    private static int select(int modulo) {
        for (; ; ) {
            int current = NEXT_SERVER_COUNTER.get();
            int next = (current + 1) % modulo;
            boolean compareAndSet = NEXT_SERVER_COUNTER.compareAndSet(current, next);
            if (compareAndSet) {
                return next;
            }
        }
    }

    public static Server selectServer(List<Server> serverList) {
        return serverList.get(select(serverList.size()));
    }

    public static void main(String[] args) {
        List<Server> serverList = new ArrayList<>();
        serverList.add(new Server(1, "服务器1"));
        serverList.add(new Server(2, "服务器2"));
        serverList.add(new Server(3, "服务器3"));
        for (int i = 0; i < 10; i++) {
            Server selectedServer = selectServer(serverList);
            System.out.format("第%d次请求，选择服务器%s\n", i + 1, selectedServer.toString());

        }
    }
}
```

![](https://img-blog.csdnimg.cn/0d21428eb8394c7990e279730b46e1ec.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Ziz5YWJ5a6F55S3Xw==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)

### 2.加权轮询（WeightedRound-Robin）

由于不同的服务器配置不同，因此它们处理请求的能力也不同，给配置高的机器配置相对较高的权重，让其处理更多的请求，给配置较低的机器配置较低的权重减轻期负载压力。加权轮询可以较好的解决这个问题。

思路：

根据权重的大小让其获得相应被轮询到的机会。

已知：

| 服务器 | 权重 |
| :----: | :--: |
|   s1   |  1   |
|   s2   |  2   |
|   s3   |  3   |

可以根据权重我们在内存中创建一个这样的数组{s1,s2,s2,s3,s3,s3}，然后再按照轮询的方式选择相应的服务器。

缺点：请求被分配到三台服务器上机会不够平滑。前3次请求都不会落在server3上。

Nginx 实现了一种平滑的加权轮询算法，可以将请求平滑（均匀）的分配到各个节点上。

下面我们用Java实现一下这个算法。

实现思路

我们以当前节点权重作为被选中的概率

```java
 public void incrCurrentWeight() {
      this.currentWeight += weight;
 }
```

为了避免权重大的被连续选中，所以再被选中的时候我们应该让其的当前权重变小。我们可以采用

// 当前权重 = 当前权重 - 总权重
1-6 =-5

3-6 =-3

可得权重越大下次当前权重变成最大的可能性也越大

```java
public void selected(int total) {
    this.currentWeight -= total;
}
```

我们选取当前当前权重最大的一个服务器

```java
public class WeightRoundRobin {

    @Data
    public static class Server {

        private int serverId;

        private String name;

        private int weight;

        private int currentWeight;

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

        public Server(int serverId, String name, int weight) {
            this.serverId = serverId;
            this.name = name;
            this.weight = weight;
        }

        public void selected(int total) {
            this.currentWeight -= total;
        }

        public void incrCurrentWeight() {
            this.currentWeight += weight;
        }
    }

    public static Server selectServer(List<Server> serverList) {
        int total = 0;
        Server selectedServer = null;
        int maxWeight = 0;
        for (Server server : serverList) {
            total += server.getWeight();
            server.incrCurrentWeight();
          	//选取当前权重最大的一个服务器
            if (selectedServer == null || maxWeight < server.getCurrentWeight()) {
                selectedServer = server;
                maxWeight = server.getCurrentWeight();
            }
        }
        if (selectedServer == null){
            Random random = new Random();
            int next = random.nextInt(serverList.size());
            return serverList.get(next);
        }
        selectedServer.selected(total);
        return selectedServer;
    }


    public static void main(String[] args) {
        List<Server> serverList = new ArrayList<>();
        serverList.add(new Server(1, "服务器1", 1));
        serverList.add(new Server(2, "服务器2", 3));
        serverList.add(new Server(3, "服务器3", 10));
        for (int i = 0; i < 10; i++) {
            Server server = selectServer(serverList);
            System.out.format("第%d次请求，选择服务器%s\n", i + 1, server.toString());
        }
    }
}
```

![](https://img-blog.csdnimg.cn/d132077488a7471f89bf8e3d3e3cd02f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Ziz5YWJ5a6F55S3Xw==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)

### 3.随机（Random）

思路：利用随机数从所有服务器中随机选取一台，可以用服务器数组下标获取。

```java
public class RandomLoadBalance {

    @Data
    public static class Server {

        private int serverId;

        private String name;

        private int weight;

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

    public static Server selectServer(List<Server> serverList) {
        Random selector = new Random();
        int next = selector.nextInt(serverList.size());
        return serverList.get(next);
    }

    public static void main(String[] args) {
        List<Server> serverList = new ArrayList<>();
        serverList.add(new Server(1, "服务器1"));
        serverList.add(new Server(2, "服务器2"));
        serverList.add(new Server(3, "服务器3"));
        for (int i = 0; i < 10; i++) {
            Server selectedServer = selectServer(serverList);
            System.out.format("第%d次请求，选择服务器%s\n", i + 1, selectedServer.toString());
        }
    }
}
```

![](https://img-blog.csdnimg.cn/e8ea785078094e0c99b931bdc03e9d93.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Ziz5YWJ5a6F55S3Xw==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)

### 4.加权随机（Weight Random）

思路：

这里我们是利用区间的思想，通过一个小于在此区间范围内的一个随机数，选中对应的区间（服务器），区间越大被选中的概率就越大。

已知：

| 服务器 | 权重 |
| :----: | :--: |
|   s1   |  1   |
|   s2   |  2   |
|   s3   |  3   |

s1：[0,1]
s2：(1,3]
s3 （3,6]

```java
public class WeightRandom {

    @Data
    public static class Server {

        private int serverId;

        private String name;

        private int weight;

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

        public Server(int serverId, String name, int weight) {
            this.serverId = serverId;
            this.name = name;
            this.weight = weight;
        }
    }

    private static Server selectServer(List<Server> serverList) {
        int sumWeight = 0;
        for (Server server : serverList) {
            sumWeight += server.getWeight();
        }
        Random serverSelector = new Random();
        int nextServerRange = serverSelector.nextInt(sumWeight);
        int sum = 0;
        Server selectedServer = null;
        for (Server server : serverList) {
            if (nextServerRange >= sum && nextServerRange < server.getWeight() + sum) {
                selectedServer = server;
            }
            sum += server.getWeight();
        }
        return selectedServer;
    }

    public static void main(String[] args) {
        List<Server> serverList = new ArrayList<>();
        serverList.add(new Server(1, "服务器1", 1));
        serverList.add(new Server(2, "服务器2", 5));
        serverList.add(new Server(3, "服务器3", 10));
        for (int i = 0; i < 10; i++) {
            Server selectedServer = selectServer(serverList);
            System.out.format("第%d次请求，选择服务器%s\n", i + 1, selectedServer.toString());

        }

    }
}
```

![](https://img-blog.csdnimg.cn/e9611b25c162407e9c90b5f09141d09f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Ziz5YWJ5a6F55S3Xw==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)

### 5.IPHash

思路：根据每个每个请求ip（也可以是某个标识）ip.hash() % server.size()

```java
public class IpHash {

    @Data
    public static class Server {

        private int serverId;

        private String name;

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

    public static Server selectServer(List<Server> serverList, String ip) {
        int ipHash = ip.hashCode();
        return serverList.get(ipHash % serverList.size());
    }

    public static void main(String[] args) {
        List<Server> serverList = new ArrayList<>();
        serverList.add(new Server(1, "服务器1"));
        serverList.add(new Server(2, "服务器2"));
        serverList.add(new Server(3, "服务器3"));

        List<String> ips = Arrays.asList("192.168.9.5", "192.168.9.2", "192.168.9.3");
        for (int i = 0; i < 10; i++) {
            for (String ip : ips) {
                Server selectedServer = selectServer(serverList, ip);
                System.out.format("请求ip:%s，选择服务器%s\n", ip, selectedServer.toString());
            }
        }
    }
}
```
![](https://img-blog.csdnimg.cn/3040ded38817493c93e1d9c5c65b8ff0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Ziz5YWJ5a6F55S3Xw==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)

可以看到结果：同一ip肯定会命中同一台机器。

### 6.最小连接数算法（ LeastConnection）

前面我们费尽心思来实现服务消费者请求次数分配的均衡，我们知道这样做是没错的，可以为后端的多台服务器平均分配工作量，最大程度地提高服务器的利用率，但是，实际上，请求次数的均衡并不代表负载的均衡。因此我们需要介绍最小连接数法，最小连接数法比较灵活和智能，由于后台服务器的配置不尽相同，对请求的处理有快有慢，它正是根据后端服务器当前的连接情况，动态的选取其中当前积压连接数最少的一台服务器来处理当前请求，尽可能的提高后台服务器利用率，将负载合理的分流到每一台服务器。

```java
/**
 * 最小连接数法是根据服务器当前的连接情况进行负载均衡的，当请求到来时，会选取当前连接数最少的一台服务器来处理请求。
 */
public class LeastConnection {
    /**
     * 定义map
     * key：模拟后台服务的ip
     * value：一个Map，map的key是权重，value是接受请求的次数，
     */
    static Map<String, Integer> ipMap = new HashMap<>();
    //模拟请求的次数
    static ThreadLocalRandom random = ThreadLocalRandom.current();

    static {
        ipMap.put("192.168.13.1", random.nextInt(10));
        ipMap.put("192.168.13.2", random.nextInt(10));
        ipMap.put("192.168.13.3", random.nextInt(10));
    }

    //从list中选取接受请求数最少的服务并返回
    public String leastConnection() {
        Iterator<String> ipListIterator = ipMap.keySet().iterator();
        String serverName = null;
        int times = 0;//访问次数
        while (ipListIterator.hasNext()) {
            String tmpServerName = ipListIterator.next();
            int requestTimes = ipMap.get(tmpServerName);
            //第一次需要赋值
            if (times == 0) {
                serverName = tmpServerName;
                times = requestTimes;
            } else {
                //找到最小次数
                if (times > requestTimes) {
                    serverName = tmpServerName;
                    times = requestTimes;
                }
            }
        }
        ipMap.put(serverName, ++times);//访问后+1
        System.out.println("获取到的地址是：" + serverName + ", 访问次数：" + times);
        return serverName;
    }

    public static void main(String[] args) {
        TestLeastConnection testLeastConnection = new TestLeastConnection();
        for (int i = 0; i < 10; i++) {
            testLeastConnection.leastConnection();
        }
    }
}
```

## 参考

- https://blog.csdn.net/u011047968/article/details/99844116
- https://blog.csdn.net/mountain9527/article/details/119960229