最近在学习 cluster 的时候，了解到它的负载均衡以及 NGINX 的负载均衡都是基于“轮询调度”算法来实现的。它由 Round Robin 提出，所以又称为“rr 算法”。除此之外，负载均衡使用的是基于权重的“wrr 算法”。为了深入理解，我这里都做了实现。

RR 算法

它的实现思路是：每一次把来自用户的请求轮流分配给内部中的服务器，从 1 开始，直到 N(内部服务器个数)，然后再从头开始分配。一直重复以上过程。

毫无疑问，它的优点是实现简单，而且不需要统计服务器状态以及连接状态，是无状态调度，所以消耗极低。在配置基本一致的集群上，使用这种算法即可。

在实现过程中，利用了 es6 提供的生成器，方便调用。请看下面的代码：

javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function* rr(num) {
    let i = 0
    while (1) {
        yield i++ % num
    }
}

/**
 * 测试代码
 */

const NUM = 5
const reqTimes = 20
const cluster = rr(NUM)

for (let i = 0; i < reqTimes; ++i) {
    console.log(cluster.next().value)
}

WRR 算法

在实际环境中，很少有集群上单机算力完全一样的情况。假设每个单机都有一个权重数据，代表它们目前的能力。那么 WRR 算法就可以根据这组数据，来将不同的请求导给不同的单机，以保证流量比等于权重比。

而对于 WRR 算法如何根据权重分配流量，以及为什么在代码中计算所有数据的最大公约数，就需要理解它的原理，你可以称之为“锚点移动”。请看下面的图：

如图所示，最大公约数就是能够切分每个权重的最小单位（都能切成整份，方便处理）。锚点 P从右向左移动，步长就是最大公约数。停下来之后，再从上到下扫描，扫描到的，就是可以分配的流量。然后再从右向左移动，重复上面步骤，直到锚点 P 到达最左侧。

这个过程中，对于单机来说，被选中的次数就是 Weight/div 。div 是一定的，所以选中次数和权重成正比。

代码首先实现求最大公约数：

javascript
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
/**
 * 求x, y的最大公约数
 * @param {Number} x
 * @param {Number} y
 */
// x: 462; y: 1071
function gcd(x, y) {
    // y是被取余对象
    // x是组成部分
    if (x === 0) {
        // 之前的余数为0, 可以整除
        return y
    }
    // 1071 = 2 * 462 + 147
    // x组成部分变成被取余对象
    // 余数变成组成部分
    return gcd(y % x, x)
}

/**
 * n个数的最大公约数
 * @param {Array} arr
 */
function nGcd(arr) {
    if (!Array.isArray(arr)) {
        throw TypeError('Param should be Array')
    }

    let result = arr[0],
        length = arr.length
    for (let i = 1; i < length; ++i) {
        result = gcd(result, arr[i])
    }
    return result
}

wrr 算法也是借助迭代器，当然，也可以一次性计算出所有的分配队列：

javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function* wrr(weights) {
    if (!Array.isArray(weights)) {
        throw TypeError('Param should be Array')
    }

    const hcf = nGcd(weights) // highest common factor: 最大公约数
    let i = -1,
        cw = 0

    while (1) {
        i = (i + 1) % weights.length
        if (i === 0) {
            cw = cw - hcf
            if (cw <= 0) {
                cw = Math.max(...weights) // Math.max(arg1, arg2, arg3, ...) // 注意参数的坑
            }
        }
        if (weights[i] >= cw) {
            yield i
        }
    }
}

测试代码如下。用生成器实现的好处显示出来了，不需要一次性计算全部，用到的时候，调用 next()  会继续计算。

javascript
1
2
3
4
5
6
7
8
9
10
console.log(gcd(1071, 462))
console.log(nGcd([1, 2, 4, 16]))

const weights = [3, 2, 4]
const sumWeight = weights.reduce((acc, current) => acc + current, 0)
const cluster = wrr(weights)
for (let i = 0; i < sumWeight; ++i) {
    console.log(cluster.next())
}
// 第一台机子被分配了3n次，其他机子也是按照比例的

参考链接

IPVS 和 Nginx 两种 WRR 负载均衡算法详解