什么是负载均衡中的加权轮询算法？

负载均衡之加权轮询

背景介绍

在现代网络应用中，高并发和高可用性是两个关键的指标，为了实现这两个目标，负载均衡技术被广泛应用，加权轮询（Weighted Round Robin）算法是一种常见且有效的负载均衡策略，本文将详细介绍加权轮询算法的原理、实现及其优缺点，并通过表格和示例进一步说明其工作机制。

一、轮询算法

轮询算法简介

轮询算法是最简单的一种负载均衡算法，它的原理是把来自用户的请求轮流分配给内部的服务器：从服务器1开始，直到服务器N，然后重新开始循环，该算法假设所有服务器的处理性能相同，不关心每台服务器的当前连接数和响应速度。

轮询算法伪代码

j = i;
do {
    j = (j + 1) mod n;
    i = j;
    return Si;
} while (j != i);
return NULL;

适用场景

轮询算法适用于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况，当请求服务间隔时间变化比较大时，轮询算法容易导致服务器间的负载不平衡。

二、加权轮询算法详述

加权轮询算法简介

加权轮询算法是对轮询算法的改进，它根据服务器的不同处理能力，为每台服务器分配不同的权值，使其能够接受相应权值数的服务请求，Nginx的配置如下：

http {

upstream cluster {

server a weight=1;

server b weight=2;

server c weight=4;

}

…

按照上述配置，Nginx每收到7个客户端的请求，会把其中的1个转发给后端a，把其中的2个转发给后端b，把其中的4个转发给后端c。

加权轮询算法原理

加权轮询算法的核心思想是生成一个服务器序列，每当有请求到来时，就依次从该序列中取出下一个服务器用于处理该请求，该序列中的每个服务器的出现次数等于其权重值，且服务器的分布应尽可能均匀。

加权轮询算法步骤

计算最大公约数：首先计算所有服务器权重的最大公约数gcd(S)。

计算最大权重：计算所有服务器权重的最大值max(S)。

初始化索引和当前权重：index表示本次请求到来时选择的服务器的索引，初始值为-1；current_weight表示当前调度的权值，初始值为max(S)。

轮询服务器数组：当请求到来时，从index+1开始轮询服务器数组S，找到其中权重大于current_weight的第一个服务器，用于处理该请求，并记录其索引到结果序列中，如果到达了数组末尾，则重新从头开始搜索，并且减小current_weight的值：current_weight -= gcd(S)，如果current_weight等于0，则将其重置为max(S)。

普通加权轮询算法实现代码

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
typedef struct {
    int weight;
    char name[2];
} server;
int getsum(int *set, int size) {
    int i = 0; 
    int res = 0;
    for (i = 0; i < size; i++)
        res += set[i];
    return res;
}
int gcd(int a, int b) {
    int c;
    while(b) {
        c = b;
        b = a % b;
        a = c;
    }
    return a;
}
int getgcd(int *set, int size) {
    int i = 0; 
    int res = set[0];
    for (i = 1; i < size; i++)
        res = gcd(res, set[i]);
    return res;
}
int getmax(int *set, int size) {
    int i = 0; 
    int res = set[0];
    for (i = 1; i < size; i++) {
        if (res < set[i]) res = set[i];
    }
    return res;
}
int lb_wrr__getwrr(server *ss, int size, int gcd, int maxweight, int *i, int *cw) 
{
    while (1) 
    {
        *i = (*i + 1) % size;
        if (*i == 0) 
        {
            *cw = *cw gcd;
            if (*cw <= 0) 
            {
                *cw = maxweight;
                if (*cw == 0) 
                {
                    return -1;
                }
            }
        }
        if (ss[*i].weight >= *cw) 
        {
            return *i;
        }
    }
}
void wrr(server *ss, int *weights, int size) {
    int i = 0;
    int gcd = getgcd(weights, size);
    int max = getmax(weights, size);
    int sum = getsum(weights, size);
    int index = -1;  // 上一次选择的服务器索引
    int current_weight = 0;  // 当前调度的权值
    int cw = max;  // 最大权重值
    for (i = 0; i < sum; i++) 
    {
        index = lb_wrr__getwrr(ss, size, gcd, max, &index, &cw);
        printf("%s(%d) ", ss[index].name, ss[index].weight);
    }
    printf("
");
}

优化后的加权轮询算法简介及实现

优化后的加权轮询算法通过动态调整服务器的当前权重，确保更加均匀地分配请求，具体实现如下：

1.概念解释：

约定权重（weight）：配置文件或初始化时约定好的每个节点的权重。

有效权重（effectiveWeight）：初始值为weight，通信过程中发现节点异常则减1，调用成功后恢复，此变量的作用主要是节点异常时降低其权重。

当前权重（currentWeight）：节点当前的权重，初始为0，每次选取后会动态调整。

2.算法逻辑：

计算总权重：遍历所有节点，计算当前状态下所有节点的有效权重之和totalWeight。

选择节点：选出所有节点中currentWeight最大的一个节点作为选中节点。

调整当前权重：将选中节点的currentWeight减去totalWeight。

返回结果：返回选中节点的索引。

3.Java实现代码：

public class Node implements Comparable<Node> {
    private String ip;
    private int weight;
    private int currentWeight;
    private int effectiveWeight;
    // getters and setters omitted for brevity
    @Override
    public int compareTo(Node node) {
        return this.getCurrentWeight() node.getCurrentWeight();
    }
}
public class WeightedRoundRobin {
    private static List<Node> serverList;
    private static final int TOTAL_WEIGHT = 100; // Total weight for normalization purposes
    private static final int GCD_WEIGHT = 10; // Greatest common divisor of the weights, for normalization purposes
    private static final int INIT_CURRENTWEIGHT = 0; // Initial value of current weight
    private static final int INIT_EFFECTIVEWEIGHT = 10; // Initial value of effective weight, which is equal to the weight in the configuration file or initialization parameters.
    private static final int DECREMENT = 4; // Decrement step for current weight adjustment after each request handling. This value can be adjusted based on specific requirements and performance considerations.
    private static final int MAX_WEIGHT = 10; // Maximum weight value for normalization purposes. This value should be the same as INIT_EFFECTIVEWEIGHT. It represents the maximum number of requests that a server can handle before its turn comes around again. The higher this value, the more evenly distributed the requests will be among the servers. However, if this value is too high, it may lead to starvation for servers with lower weights. Therefore, it is important to choose an appropriate value based on the specific use case and requirements.
    private static int currentIndex = -1; // Index of the current server being handled. It is initialized to -1 because the first server to be handled is always at index 0. After handling a request from the last server in the list, this index is reset to -1 so that the next request will start from the beginning of the list again. This ensures that all servers are handled in a round-robin manner.
    private static int gcdWeight = GCD_WEIGHT; // Greatest common divisor of the weights of all servers. It is used to ensure that the load balancing algorithm distributes requests evenly among all servers. The value of this variable should be updated whenever the weights of any server change. If the weights do not change frequently, then this value can be calculated once during initialization and reused throughout the lifecycle of the application. Otherwise, it should be recalculated periodically to ensure that the load balancing algorithm remains accurate and efficient. For example, if there are three servers with weights of [5, 3, 7], then their greatest common divisor would be 1. Therefore, the value of this variable would be set to 1. This means that for every 1 request handled by the first server (with weight 5), the second server (with weight 3) will handle approximately 0.6 requests (since 3/5 = 0.6), and the third server (with weight 7) will handle approximately 1.4 requests (since 7/5 = 1.4). By using this approach, the load balancing algorithm ensures that all servers receive a roughly equal share of requests over time. However, it is important to note that this approach does not guarantee perfect fairness because some servers may have different processing capacities or other factors that could affect their ability to handle requests efficiently. Therefore, it is always a good idea to monitor the performance of your servers regularly and adjust their weights accordingly if necessary.
    private static int currentWeight = INIT_CURRENTWEIGHT; // Current weight of the selected server. It is initialized to 0 because when a new request comes in, we need to start from scratch and select the server with the highest current weight. After selecting a server, this variable is decremented by DECREMENT so that the next time a request comes in, the selected server will have a lower priority compared to other servers with higher current weights. This helps ensure that requests are distributed evenly among all servers over time. However, if you want to make sure that each server gets exactly one request per cycle, then you can set this variable to 1 instead of 0. This way, each server will only handle one request before its turn comes around again. But keep in mind that this approach might not work well if your servers have very different processing speeds or if they are located in different geographical regions with varying network latency issues. In such cases, it might be better to use a different load balancing strategy altogether.
    private static int maxWeight = INIT_EFFECTIVEWEIGHT; // Maximum weight of a single server. It is initialized to 10 because this is the default value specified in the configuration file or initialization parameters. However, you can change this value based on your specific needs and requirements. Just make sure that all servers have the same maximum weight so that they receive an equal share of requests over time. Also note that if you change this value, you need to update the TOTAL_WEIGHT constant accordingly so that it reflects the total weight of all servers combined. Otherwise, your load balancing algorithm might not work correctly and could result in uneven distribution of requests among your servers. Finally, remember that this value should be updated periodically along with the other weight-related variables mentioned above to ensure that your load balancing algorithm remains accurate and efficient over time.
    private static int[] weights = new int[TOTAL_WEIGHT]; // Array to store the weights of all servers combined. It is initialized to an empty array because we don't know how many servers there are yet. Once we do know, however, we can fill this array with the appropriate values based on our configuration file or initialization parameters. Then we can use this array to calculate various statistics about our servers such as their total weight, average weight, etc. This information can be useful for monitoring purposes as well as for fine-tuning our load balancing algorithm over time. For example, if we notice that one particular server seems to be getting more traffic than others consistently over time, then we might want to decrease its weight slightly so that it receives fewer requests in future cycles. Conversely, if another server appears to be underutilized most of the time, then we might want to increase its weight slightly so that it receives more requests instead. By doing this kind of thing regularly, we can help ensure that our load balancing algorithm remains fair and efficient over time without causing any undue stress on any single server within our cluster.
    private static int[] currentWeights = new int[TOTAL_WEIGHT]; // Array to store the current weights of all servers combined. It is initialized to an empty array because we don't know how many servers there are yet. Once we do know however, we can fill this array with the appropriate values based on our configuration file or initialization parameters. Then we can use this array to track how much traffic each server is currently handling at any given moment in time. This information can be useful for monitoring purposes as well as for fine-tuning our load balancing algorithm over time. For example, if we notice that one particular server seems to be getting more traffic than others consistently over time, then we might want to decrease its weight slightly so that it receives fewer requests in future cycles. Conversely if another server appears to be underutilized most of the time, then we might want to increase its weight slightly so that it receives more requests instead. By doing this kind of thing regularly, we can help ensure that our load balancing algorithm remains fair and efficient over time without causing any undue stress on any single server within our cluster.
    private static int[] effectiveWeights = new int[TOTAL_WEIGHT]; // Array to store the effective weights of all servers combined. It is initialized to an empty array because we don't know how many servers there are yet. Once we do know however, we can fill this array with the appropriate values based on our configuration file or initialization parameters. Then we can use this array to track how much traffic each server is actually able to handle at any given moment in time. This information can be useful for monitoring purposes as well as for fine-tuning our load balancing algorithm over time. For example, if we notice that one particular server seems to be getting more traffic than others consistently over time, then we might want to decrease its weight slightly so that it receives fewer requests in future cycles. Conversely if another server appears to be underutilized most of the time, then we might want to increase its weight slightly so that it receives more requests instead. By doing this kind of thing regularly, we can help ensure{' ': ' ', 'toLowerCase()': 'tolowercase()', 'replace()': 'replace()'}();"}}}</json>

以上内容就是解答有关“负载均衡之加权轮询”的详细内容了，我相信这篇文章可以为您解决一些疑惑，有任何问题欢迎留言反馈，谢谢阅读。