加权轮询

加权轮询在Nginx和Dubbo及其他负载均衡器里都是比较常见的。

简单加权轮询

可以在内存中初始化一个数组，数组内容是根据权重值生成相等数量的节点，如，a、b、c三个节点权重值分别是1、2、4，则生成一个数组：{a, b, b, c, c, c, c}，维护一个总请求数 totalCount，每次使用总请求数对数组长度取模mod，mod就是要选中的节点在数组中的下标。
缺点：请求被分配到三个节点上机会不够平滑。前3次请求都不会打在c节点上。

平滑加权轮询

Nginx实现了一种叫做平滑加权轮询的算法，可以将请求均匀的分布到各个节点上。
网上很多博客对这块儿的介绍都不够浅显易懂，今天话不多说，手撸一个最基本的加权负载均衡算法，供大家参考。

代码实现

定义ServerNode实体类：

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

/**
 * @author xueliang
 * @since 2020-03-26 16:50
 */
@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
public class ServerNode {

    private String hostname;

    /** 设置的weight */
    private int weight;

    /** 当前weight */
    private int currentWeight;

    public void selected(int total) {
        currentWeight -= total;
    }

    public void increaseCurrentWeight() {
        currentWeight += weight;
    }
}

轮询算法：

import org.xueliang.algorithm.loadbalance.LoadBalance;
import org.xueliang.algorithm.loadbalance.ServerNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 负载均衡 - 加权轮询算法
 * @author xueliang
 * @since 2020-03-26 16:52
 */
public class WeightRoundRobinLoadBalance implements LoadBalance {

    @Override
    public ServerNode select(List<ServerNode> serverNodes) {
        ServerNode serverNodeSelected = null;
        int maxWeight = Integer.MIN_VALUE;
        int totalWeight = 0;
        for (ServerNode serverNode : serverNodes) {
            // 增加各自的 currentWeight
            serverNode.increaseCurrentWeight();
            if (serverNode.getCurrentWeight() > maxWeight) {
                maxWeight = serverNode.getCurrentWeight();
                serverNodeSelected = serverNode;
            }
            totalWeight += serverNode.getWeight();
        }
        if (serverNodeSelected != null) {
            // 被选中的节点，currentWeight 需要减去所有 weight 之和
            serverNodeSelected.selected(totalWeight);
            return serverNodeSelected;
        }
        // should not happen here
        return serverNodes.get(0);
    }

    // 测试
    public static void main(String[] args) {
        WeightRoundRobinLoadBalance lb = new WeightRoundRobinLoadBalance();
        List<ServerNode> servers = new ArrayList<>();
        // 初始化3个节点：a、b、c，权重分别是：1、2、4
        servers.add(new ServerNode("a", 1, 0));
        servers.add(new ServerNode("b", 2, 0));
        servers.add(new ServerNode("c", 4, 0));
        for (int i = 0; i < 15; i++) {
            if (i % 7 == 0) {
                System.out.println(String.format("\n第 %s 轮请求======:", (i / 7) + 1));
            }
            ServerNode selected = lb.select(servers);
            System.out.println(String.format("第 %s 次请求，选中机器：%s", i + 1, selected.getHostname()));

        }
    }
}

Output：

第 1 轮请求======:
第 1 次请求，选中机器：c
第 2 次请求，选中机器：b
第 3 次请求，选中机器：c
第 4 次请求，选中机器：a
第 5 次请求，选中机器：c
第 6 次请求，选中机器：b
第 7 次请求，选中机器：c

第 2 轮请求======:
第 8 次请求，选中机器：c
第 9 次请求，选中机器：b
第 10 次请求，选中机器：c
第 11 次请求，选中机器：a
第 12 次请求，选中机器：c
第 13 次请求，选中机器：b
第 14 次请求，选中机器：c

第 3 轮请求======:
第 15 次请求，选中机器：c
第 13 次请求，选中机器：b
第 14 次请求，选中机器：c

第 3 轮请求======:
第 15 次请求，选中机器：c

可以看出前两轮共14次请求中命中了2次a，4次b，8次c，a、b、c请求接收之比为2 : 4 : 8，即1 : 2 : 4，与其权重之比相等，符合预期。

参考链接

Nginx 加权负载均衡算法源码：https://trac.nginx.org/nginx/browser/nginx/src/http/ngx_http_upstream_round_robin.c#L508

Dubbo 加权负载均衡算法源码：https://github.com/apache/dubbo/blob/master/dubbo-cluster/src/main/java/org/apache/dubbo/rpc/cluster/loadbalance/RoundRobinLoadBalance.java

加权轮询

简单加权轮询

平滑加权轮询

代码实现

参考链接

相关阅读