Java实现平滑加权轮询算法之降权和提权详解

什么是平滑加权轮询算法？

平滑加权轮询算法(Smooth Weighted Round-Robin, SWRR)是一种负载均衡算法，它可以按权重分配请求到不同的服务器上。与传统的轮询算法不同的是，SWRR可以在考虑到服务器权重的情况下，按照权重比例为每台服务器分配请求。

为什么需要降权和提权？

在实际应用中，服务器的性能不是一成不变的，可能出现负载过高或过低等情况。当某台服务器节点本身负载已经过高时，再按照原来的权重进行分配，可能导致该节点更加过载；反之，若某台节点空闲，这时再按照原来的权重进行分配，可能导致其他服务器的资源浪费。因此，当节点的实际负载发生变化时，需要对节点的权重进行更新，调整节点分配的比例，避免出现负载不均。

平滑加权轮询算法的实现

实现平滑加权轮询算法，需要以下三个变量：

• weight：节点的权重值，表示该节点能处理多少请求；
• currentWeight：节点当前的权重值，当前权重值的初始值为0，每当调度到该节点时，当前权重值就会增加weight，之后，如果出现更新权重的情况，currentWeight也需要做相应的更新；
• greatestCommonDivisor：节点权重的最大公约数，这里涉及到算法的时间复杂度，使得选择的节点更加均匀，避免出现过度分布的情况。

其核心算法如下：

public static String getServer() {
    int totalWeight = 0;
    String selectedServer = null;
    for (Map.Entry<String, Integer> entry : serverMap.entrySet()) {
        String server = entry.getKey();
        int weight = entry.getValue();
        currentWeights.put(server, currentWeights.get(server) + weight);
        totalWeight += weight;
        if (selectedServer == null || currentWeights.get(selectedServer) < currentWeights.get(server)) {
            selectedServer = server;
        }
    }
    currentWeights.put(selectedServer, currentWeights.get(selectedServer) - totalWeight);
    return selectedServer;
}

其中，serverMap为节点和权重的映射关系，currentWeights为节点当前权重值的映射关系。代码执行流程如下：

• 第一个for循环，对serverMap中的每个节点进行循环，计算出所有节点的权重值之和totalWeight，并保存其中currentWeight的最大节点，即selectedServer；
• 在获取到最大currentWeight的节点之后，从currentWeight中删掉它的权重值，并返回selectedServer。

降权和提权的实现

实现降权和提权，需要加入以下两个变量：

• downMap：下线的节点（需要降权），表示该节点处于故障状态；
• upMap：上线的节点（需要提权），表示该节点已经恢复正常运转。

代码实现如下：

public static void updateWeightMap(String server, int weight) {
    // 更新serverMap
    if (serverMap.containsKey(server)) {
        int oldWeight = serverMap.get(server);
        serverMap.put(server, weight);
        int change = weight - oldWeight;
        if (change > 0) {  //提权
            currentWeights.put(server, currentWeights.get(server) + change);
        } else if (change < 0) { //降权
            downMap.put(server, -change);
        }
    } else {
        serverMap.put(server, weight);
        currentWeights.put(server, 0);
    }
}

public static void judgeServers() {
    for (Map.Entry<String, Integer> entry : downMap.entrySet()) {
        String server = entry.getKey();
        int downTime = entry.getValue();
        downTime--;
        if (downTime == 0) { // 节点降权已经处理完成
            downMap.remove(server);
            currentWeights.put(server, 0);
        } else {
            downMap.put(server, downTime);
        }
    }

    for (Map.Entry<String, Integer> entry : upMap.entrySet()) {
        String server = entry.getKey();
        int upTime = entry.getValue();
        upTime--;
        if (upTime == 0) { // 节点提权已经完成
            upMap.remove(server);
            currentWeights.put(server, serverMap.get(server));
        } else {
            upMap.put(server, upTime);
        }
    }
}

其中updateWeightMap()方法用于进行节点权重的更新、降权、提权等操作；judgeServers()方法用于判断节点当前状态是否需要进行降权或提权操作。两个方法的详细说明请参见注释。

示例说明

示例一：对三个节点随机请求分发20次

假设节点权重分别为 {A:5, B:3, C:2}，请求分发次数为20。

public static void main(String[] args) {
    for (int i = 0; i < 20; i++) {
        String server = getServer();
        System.out.println("第" + (i + 1) + "次请求，访问的服务器：" + server);
    }
}

执行过程和输出结果如下：

第1次请求，访问的服务器：A
第2次请求，访问的服务器：B
第3次请求，访问的服务器：A
第4次请求，访问的服务器：C
第5次请求，访问的服务器：A
第6次请求，访问的服务器：B
第7次请求，访问的服务器：A
第8次请求，访问的服务器：A
第9次请求，访问的服务器：C
第10次请求，访问的服务器：A
第11次请求，访问的服务器：B
第12次请求，访问的服务器：A
第13次请求，访问的服务器：A
第14次请求，访问的服务器：C
第15次请求，访问的服务器：A
第16次请求，访问的服务器：B
第17次请求，访问的服务器：A
第18次请求，访问的服务器：A
第19次请求，访问的服务器：C
第20次请求，访问的服务器：A

根据输出结果可以发现，请求被分配到A节点的概率更大，但其他节点仍然会有请求被分配到。

示例二：节点负载不均衡情况下的降权/提权操作

我们将节点B的权重值从3调整为1，然后进行20次请求分发：

public static void main(String[] args) {
    updateWeightMap("B", 1); // 节点B降权
    for (int i = 0; i < 20; i++) {
        String server = getServer();
        System.out.println("第" + (i + 1) + "次请求，访问的服务器：" + server);
        if (i == 3) {
            updateWeightMap("B", 3); // 节点B提权
        }
        if (i == 8) {
            updateWeightMap("B", 1); // 节点B降权
        }
    }
    judgeServers(); // 判断节点状态是否需要降权或提权
}

执行过程和输出结果如下：

第1次请求，访问的服务器：A
第2次请求，访问的服务器：C
第3次请求，访问的服务器：B
第4次请求，访问的服务器：A
第5次请求，访问的服务器：A
第6次请求，访问的服务器：C
第7次请求，访问的服务器：A
第8次请求，访问的服务器：B
第9次请求，访问的服务器：A
第10次请求，访问的服务器：A
第11次请求，访问的服务器：C
第12次请求，访问的服务器：A
第13次请求，访问的服务器：A
第14次请求，访问的服务器：A
第15次请求，访问的服务器：C
第16次请求，访问的服务器：A
第17次请求，访问的服务器：A
第18次请求，访问的服务器：A
第19次请求，访问的服务器：C
第20次请求，访问的服务器：A
{B=0.75, C=0.25, A=1.0}

通过输出结果可以发现，请求在后期明显更多地分配到了节点A上，这也导致了A节点占用的权重比例逐渐上升，而B和C节点的比例逐渐下降。当操作执行完成后，节点A的权重占比达到了1，最终结果是，在20次请求分发过程中，节点A处理了16次请求，而B和C仅处理了2次和2次。