负载均衡算法--平滑加权轮询法（Smooth Weight Round Robin）_平滑加权轮询伪代码

接上一篇博文：负载均衡算法–加权轮询法（Weight Round Robin），接下来介绍平滑加权轮询法。

在加权轮询算法中我们讲到“从宏观的角度讲，权重高的服务器被访问的次数高一些，近似均衡；微观的角度讲，权重高的服务器会被连续访问到，看起来没有那么均衡。”，为了更好的解决均衡的问题，nginx 的作者提出了均衡加权轮询算法。

算法描述

假设有 N 台服务器 S = {S0, S1, S2, …, Sn}，默认权重为 W = {W0, W1, W2, …, Wn}，当前权重为 CW = {CW0, CW1, CW2, …, CWn}。在该算法中有两个权重，默认权重表示服务器的原始权重，当前权重表示每次访问后重新计算的权重，当前权重的出初始值为默认权重值，当前权重值最大的服务器为 maxWeightServer，所有默认权重之和为 weightSum，服务器列表为 serverList，算法可以描述为：
1、找出当前权重值最大的服务器 maxWeightServer；
2、计算 {W0, W1, W2, …, Wn} 之和 weightSum；
3、将 maxWeightServer.CW = maxWeightServer.CW - weightSum；
4、重新计算 {S0, S1, S2, …, Sn} 的当前权重 CW，计算公式为 Sn.CW = Sn.CW + Sn.Wn
5、返回 maxWeightServer

假定我们现在有如下四台服务器：

代码实现

1、服务器权重bean

package org.learn.loadbalance;

import java.io.Serializable;

public class SmoothWeightServer implements Serializable {
    private static final long serialVersionUID = 7246747589293111189L;

    private String server;
    private Integer originalWeight;
    private Integer currentWeight;

    public SmoothWeightServer(String server, Integer originalWeight, Integer currentWeight){
        this.server = server;
        this.originalWeight = originalWeight;
        this.currentWeight = currentWeight;
    }
    public Integer getOriginalWeight() {
        return originalWeight;
    }

    public void setOriginalWeight(Integer originalWeight) {
        this.originalWeight = originalWeight;
    }

    public Integer getCurrentWeight() {
        return currentWeight;
    }

    public void setCurrentWeight(Integer currentWeight) {
        this.currentWeight = currentWeight;
    }

    public String getServer() {
        return server;
    }

    public void setServer(String server) {
        this.server = server;
    }
}

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

2、服务器管理类

package org.learn.loadbalance;

import java.util.Map;
import java.util.TreeMap;

/**
 * @author zhibo
 * @date 2019/5/16 16:25
 */
public class SmoothServerManager {
    public volatile static Map<String, SmoothWeightServer> serverMap = new TreeMap<>();

    static {
        serverMap.put("192.168.1.1", new SmoothWeightServer("192.168.1.1",1,1));
        serverMap.put("192.168.1.2", new SmoothWeightServer("192.168.1.2",2,2));
        serverMap.put("192.168.1.3", new SmoothWeightServer("192.168.1.3",3,3));
        serverMap.put("192.168.1.4", new SmoothWeightServer("192.168.1.4",4,4));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、平滑加权轮询类

package org.learn.loadbalance;

import java.util.*;

/**
 * @author zhibo
 * @date 2019/5/16 16:28
 */
public class SmoothWeightRoundRobin {

    public static String getServer() {
        Map<String, SmoothWeightServer> serverMap = new TreeMap<>(SmoothServerManager.serverMap);

        /// 原始权重之和
        Integer weightSum = 0;
        /// 最大当前权重对象
        SmoothWeightServer maxWeightServer = null;

        /// 计算最大当前权重对象，同时求原始权重之和
        Iterator<String> iterator = serverMap.keySet().iterator();
        while (iterator.hasNext()){
            SmoothWeightServer smoothWeightServer = serverMap.get(iterator.next());
            if(smoothWeightServer != null){
                weightSum += smoothWeightServer.getOriginalWeight();
                if(maxWeightServer == null){
                    maxWeightServer = smoothWeightServer;
                }
                if(smoothWeightServer.getCurrentWeight() > maxWeightServer.getCurrentWeight()){
                    maxWeightServer = smoothWeightServer;
                }
            }
        }

        /**
         * 重新调整 currentWeight 权重：
         * maxWeightServer.currentWeight -= weightSum
         * 每个 smoothWeightServer.currentWeight += smoothWeightServer.originalWeight
         */
        if(maxWeightServer == null){
            return "";
        }
        maxWeightServer.setCurrentWeight(maxWeightServer.getCurrentWeight() - weightSum);

        iterator = serverMap.keySet().iterator();
        while (iterator.hasNext()){
            SmoothWeightServer smoothWeightServer = serverMap.get(iterator.next());
            if(smoothWeightServer != null){
                smoothWeightServer.setCurrentWeight(smoothWeightServer.getCurrentWeight() + smoothWeightServer.getOriginalWeight());
            }
        }

        return maxWeightServer.getServer();
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            String server = getServer();
            System.out.println(server);
        }
    }
}

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

执行 main 方法输出结果如下：

文章内容仅代表个人观点，如有不正之处，欢迎批评指正，谢谢大家。