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

RR 算法

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

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

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

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

WRR 算法

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

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

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

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

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

/**
 * 求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;
}
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

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

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;
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

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次,其他机子也是按照比例的
1
2
3
4
5
6
7
8
9
10

参考链接

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