MENU

负载均衡之加权轮询调度算法

前言

WRR(Weighted Round Robin)基于权重轮询调度算法。
过去只是在nginx上直接使用,由于最近在自行开发一个webserver,涉及到一个负载均衡功能,因此自行实现基于权重轮询调度算法。

分析

假设有三台服务器(IP 端口 权重)分别为如下:

  • 服务器A:10.1.1.92:8081 weight:5
  • 服务器B:10.1.1.93:8081 weight: 1
  • 服务器C:10.1.1.94:8081 weight: 1

当实现加权轮询调度,可能第一想到的方法是先请求5次服务器A,后分别各请求1次服务器B及服务器C。这种方法存在一个弊端,服务器A在某一段时间内被集中调度
像nginx负载均衡实现基于权重轮询调度,会比较均匀的选择服务器,而不是简单的权重分配。Nginx基于权重的轮询算法的实现:Upstream: smooth weighted round-robin balancing,对比它还实现平滑轮询算法。

同样是上面三台服务器,负载均衡选择顺序会变成如下:

A A B A C A A

相当于简单的基于权重的轮询算法,三台服务器之间负载更加均衡。

实现

大致过程如下:

  • 累加计算权重总值
  • 计算当前节点权重,公式:当前节点权重 = 当前节点权重 + 初始权重
  • 选择权重最大的节点作为本次负载节点,并且权重最大的节点减去总权重
A  B  C
0  0  0  (初始化权重)

5  1  1  (服务器A被选中)
-2  1  1 (由于服务器A权重在此次最大,所以减去总权重7)

3  2  2  (服务器A被选中)
-4  2  2 (由于服务器A权重在此次最大,所以减去总权重7)

1  3  3  (服务器B被选中)
1 -4  3  

6 -3  4  (服务器A被选中)
-1 -3  4

4 -2  5  (服务器C被选中)
4 -2 -2

9 -1 -1  (服务器A被选中)
2 -1 -1

7  0  0  (服务器A被选中)
0  0  0  

代码实现

# 创建一个Server类,当然使用struct也可以。
class Server {
private:
    // 负载均衡IP
    std::string ip;
    // 负载均衡端口
    unsigned int port;
    // 权重
    int weight;
    // 当前权重
    int curWeight;

public:
    Server(std::string ip_, unsigned int port_, int weight_)
            : ip(std::move(ip_)),
              port(port_),
              weight(weight_),
              curWeight(0) {

    }

    ~Server() {
        ip = "";
        port = 0;
        weight = 0;
        curWeight = 0;
    }

    std::string getIp() {
        return ip;
    }

    int getPort() const {
        return port;
    }

    void setWeight(int weight_) {
        weight = weight_;
    }

    int getWeight() const {
        return weight;
    }

    void setCurWeight(int weight_) {
        curWeight = weight_;
    }

    int getCurWeight() const {
        return curWeight;
    }
};

# 负载均衡服务器数组(也即对应上述样例子中的A、B、C)
std::vector<Server> serverLists;

# 负载均衡选择方法
int totalWeight = 0; // 总权重
int maxWeight = 0;  // 当前最大权重
int index = -1;     // 最大权重的index
for (int i = 0; i < serverLists.size(); ++i) {
    // 计算总权重
    totalWeight += serverLists[i].getWeight();
    
    // 计算当前权重 公式:当前节点权重 = 当前节点权重 + 初始权重
    serverLists[i].setCurWeight(serverLists[i].getWeight() + serverLists[i].getCurWeight());

    // 选取最大权重的节点
    if (serverLists[i].getCurWeight() > maxWeight) {
        maxWeight = serverLists[i].getCurWeight();
        index = i;
    }
}
// 将被选择的节点权重(权重最大节点) 减 总权重, 用于下一轮选择
serverLists[index].setCurWeight(serverLists[index].getCurWeight() - totalWeight);
// 返回被选择的节点
return serverLists[index];

参考文章:
平滑的基于权重的轮询算法

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码
添加新评论