常见的负载均衡算法列举与实现。

随机

随机从集群中选择一个服务器

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
/**
 * <b> 负载均衡 - 随机算法   </b>
 * <p> 随机获得服务器
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/8/5 17:13
 */
public class RandomSlb {
    private static final List<Server> servers = new ArrayList<>(); // 所有服务器列表
    private static final ThreadLocal<Server> currentServer = new ThreadLocal<>();   // 当前服务器

    // 获得下一个服务器
    public static Server getNextServer() throws NoSuchAlgorithmException {
        int nextIndex = SecureRandom.getInstanceStrong().nextInt(servers.size());
        Server server = servers.get(nextIndex);
        currentServer.set(server);

        return server;
    }

    public static void main(String[] args) throws NoSuchAlgorithmException {
        servers.add(new Server("127.0.0.1", "111", 1));
        servers.add(new Server("127.0.0.2", "222", 2));
        servers.add(new Server("127.0.0.3", "333", 3));
        servers.add(new Server("127.0.0.4", "444", 4));

        System.out.println(getNextServer());
        System.out.println(getNextServer());
    }
}

随机加权

根据权重值，随机获取集群服务器。权值越大获取的概率越大

TreeMap排序

通过树结构实现：找到大于该权重值中的最小权重的服务。如： random = 4, 则找出的第一个为

结果近似于方法一，key为最大权重值，取最接近的一个

image-20240710113822720

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
68
69
70
71
72
73
74
75
/**
 * <b>   负载均衡 - 加权随机算法   </b>
 * <p> 按权重设置随机概率，示例：
 * 如有4个元素A、B、C、D，权重分别为1、2、3、4，随机结果中A:B:C:D的比例要为1:2:3:4。
 * 总体思路：累加每个元素的权重A(1)-B(3)-C(6)-D(10)，则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。
 * 然后随机出一个[0,10)之间的随机数。落在哪个区间，则该区间之后的元素即为按权重命中的元素。
 * <p>
 * 实现方法：
 * 利用TreeMap，则构造出的一个树为:  利用treemap.tailMap().firstKey()即可找到目标元素。
 * 　　   　　B(3)
 * 　　   　 /      \
 *         /         \
 *      A(1)     D(10)
 *      /
 *     /
 *   C(6)
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/8/5 17:35
 */
public class WeightRandom {
    private final TreeMap<Double, Server> weightMap = new TreeMap<>();

    public WeightRandom(final List<Server> list) {
        for (Server server : list) {
            double lastWeight = this.weightMap.size() == 0 ? 0 : this.weightMap.lastKey(); // 获取最后一个服务累加的权重值

            this.weightMap.put(server.getWeight() + lastWeight, server);    //累加当前权重
        }
    }

    // 随机获取下一个服务
    public Server randomServer() {
        double randomWeight = this.weightMap.lastKey() * Math.random();     // 获取随机数
        // 查找 key 大于  randomWeight 的所有
        SortedMap<Double, Server> tailMap = this.weightMap.tailMap(randomWeight, false);

        return this.weightMap.get(tailMap.firstKey());
    }

    public static void main(String[] args) {
        List<Server> servers = new ArrayList<>();
        servers.add(new Server("127.0.0.1", "111", 1));
        servers.add(new Server("127.0.0.2", "222", 22));
        servers.add(new Server("127.0.0.3", "333", 3));
        servers.add(new Server("127.0.0.4", "444", 4));

        WeightRandom weightRandom = new WeightRandom(servers);
        int s1 = 0, s2 = 0, s3 = 0, s4 = 0;

        float maxCount = 10000;
        for (int i = 0; i < maxCount; i++) {
            Server server = weightRandom.randomServer();
            switch (server.getPort()) {
                case "111":
                    s1++;
                    break;
                case "222":
                    s2++;
                    break;
                case "333":
                    s3++;
                    break;
                case "444":
                    s4++;
                    break;
            }
        }
        System.out.printf("s1 = %d 出现概率 %.2f \n", s1, (s1 / maxCount) * 100);
        System.out.printf("s2 = %d 出现概率 %.2f \n", s2, (s2 / maxCount) * 100);
        System.out.printf("s3 = %d 出现概率 %.2f \n", s3, (s3 / maxCount) * 100);
        System.out.printf("s4 = %d 出现概率 %.2f \n", s4, (s4 / maxCount) * 100);
    }
}

区间法

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * <b>   负载均衡 - 加权随机算法   </b>
 * <p> 按权重设置随机概率，示例：
 * 如有4个元素A、B、C、D，权重分别为1、2、3、4，随机结果中A:B:C:D的比例要为1:2:3:4。
 * 总体思路：累加每个元素的权重A(1)-B(3)-C(6)-D(10)，则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。
 *      然后随机出一个[0,10)之间的随机数。落在哪个区间，则该区间之后的元素即为按权重命中的元素。
 *
 * 实现方法：
 *      根据权值，获得区间范围列表，并加入到对应的服务中，Map<Server, Set<Integer>>  key为服务， value为区间列表值
 *
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/8/5 17:35
 */
public class WeightSlb {
    private static final List<Server> servers = new ArrayList<>(); // 所有服务器列表
    private static volatile int totalWeights;    // 权重总和
    private static final Map<Server, Set<Integer>> maps = new HashMap<>(); // 每个服务器的权重区间值
    private static final ThreadLocal<Server> currentServer = new ThreadLocal<>();   // 当前服务器

    // 设置权重区间值
    private static void weightExtent() {
        totalWeights = servers.stream().mapToInt(Server::getWeight).sum();   //计算权重总和

        int startSum = 0;  // 截至上一个对象的累计权值总和
        for (Server s : servers) {

            Set<Integer> list = maps.computeIfAbsent(s, n -> new HashSet<>());
            for (int i = startSum; i < startSum + s.getWeight(); i++) {
                list.add(i);
            }

            startSum += s.getWeight(); // 累加本服务的权值
        }
    }

    // 获得下一个服务器
    public static Server getNextServer() throws NoSuchAlgorithmException {
//        int nextInt = new Random().nextInt(totalWeights);
//        currentServer.remove();
        int nextInt = SecureRandom.getInstanceStrong().nextInt(totalWeights);
        for (Server server : maps.keySet()) {
            if (maps.get(server).contains(nextInt)) {
                currentServer.set(server);
                break;
            }
        }

        return currentServer.get();
    }

    public static void main(String[] args) throws NoSuchAlgorithmException {
        servers.add(new Server("127.0.0.1", "111", 1));
        servers.add(new Server("127.0.0.2", "222", 12));
        servers.add(new Server("127.0.0.3", "333", 3));
        servers.add(new Server("127.0.0.4", "444", 4));

        weightExtent();
        int s1 = 0, s2 = 0, s3 = 0, s4 = 0;

        float maxCount = 10000;
        for (int i = 0; i < maxCount; i++) {
            Server server = getNextServer();
            switch (server.getPort()) {
                case "111":
                    s1++;
                    break;
                case "222":
                    s2++;
                    break;
                case "333":
                    s3++;
                    break;
                case "444":
                    s4++;
                    break;
            }
        }
        System.out.printf("s1 = %d 出现概率 %.2f \n", s1, (s1 / maxCount) * 100);
        System.out.printf("s2 = %d 出现概率 %.2f \n", s2, (s2 / maxCount) * 100);
        System.out.printf("s3 = %d 出现概率 %.2f \n", s3, (s3 / maxCount) * 100);
        System.out.printf("s4 = %d 出现概率 %.2f \n", s4, (s4 / maxCount) * 100);
//        System.out.println(getNextServer());
    }
}

B+树结构

利用B+树的原理。叶子结点存放元素，非叶子结点用于索引。非叶子结点有两个属性，分别保存左右子树的累加权重。如下图：

img

更改一个元素，只须修改该元素到根结点那半部分的权值即可

轮询

把来自用户的请求轮流分配给集群中的服务器

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
/**
 * <b>   负载均衡 - 轮询算法   </b>
 * <p> 请求轮流分配给内部的服务器
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/8/5 17:02
 */
public class PollingSlb {

    private static final List<Server> servers = new ArrayList<>(); // 所有服务器列表
    private static final ThreadLocal<Server> currentServer = new ThreadLocal<>();   // 当前服务器
    private static volatile int currentServerIndex = 0;    // 当前服务器下标

    // 获得下一个服务器
    public static Server getNextServer() {
        Server server = currentServer.get();
        if (server != null)
            currentServerIndex = (currentServerIndex + 1) % servers.size();

        server = servers.get(currentServerIndex);
        currentServer.set(server);

        return server;
    }
// 测试
    public static void main(String[] args) {
        servers.add(new Server("127.0.0.1", "111", 1));
        servers.add(new Server("127.0.0.2", "222", 1));
        servers.add(new Server("127.0.0.3", "333", 1));

        System.out.println(PollingSlb.getNextServer());
        System.out.println(PollingSlb.getNextServer());
        System.out.println(PollingSlb.getNextServer());
        System.out.println(PollingSlb.getNextServer());
        System.out.println(PollingSlb.getNextServer());
    }
}