Java实现常见的负载均衡算法

z 2022-08-08 随笔

# 什么是负载均衡

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

# 常见的负载均衡算法

# 1.轮询（Round Robin）

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

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

请求1 -> s1

请求2-> s2

请求3 -> s3

请求4 -> s1

请求5 -> s2

请求6 -> s3

…

优点：

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

实现绝对公平

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

java实现轮询算法：

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

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

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

        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

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

思路：

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

已知：

服务器	权重
s1	1
s2	2
s3	3

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

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

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

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

实现思路

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

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

1
2
3

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

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

3-6 =-3

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

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

1
2
3

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

# 3.随机（Random）

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 4.加权随机（Weight Random）

思路：

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

已知：

服务器	权重
s1	1
s2	2
s3	3

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

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

        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# 5.IPHash

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

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

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

/**
 * 最小连接数法是根据服务器当前的连接情况进行负载均衡的，当请求到来时，会选取当前连接数最少的一台服务器来处理请求。
 */
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();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 参考

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

在 GitHub 上编辑此页！ (opens new window)

上次更新: 2024/10/22, 09:33:35

zの自留地

zの自留地

Choose mode