负载均衡：轮询调度算法实现

最近在学习 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);
}

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;
}

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;
    }
  }
}

测试代码如下。用生成器实现的好处显示出来了，不需要一次性计算全部，用到的时候，调用 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次，其他机子也是按照比例的

参考链接

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

Weighted Round-Robin Scheduling：http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling
IPVS 和 Nginx 两种 WRR 负载均衡算法详解：https://blog.csdn.net/dog250/article/details/80115358
辗转相除法求最大公约数：https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95

大师兄

RR 算法

WRR 算法

参考链接