最近在学习 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 算法如何根据权重分配流量，以及为什么在代码中计算所有数据的最大公约数，就需要理解它的原理，你可以称之为“锚点移动”。请看下面的图：
memset(tmp, '\0', BUFFER_SIZE);
sprintf(tmp, "%s%d", s, i);
struct srv_info sinfo;
memcpy(sinfo.ip, tmp, BUFFER_SIZE);
sinfo.weight = rand() % RAND_WEIGHT;
server.push_back(sinfo);
}
printf("server count: %ld\n", server.size());
for (size_t i = 0; i < server.size(); i++)
{
printf("%s weight: %d\n", server[i].ip, server[i].weight);
}
printf("====================================\n");
int used_count[SERVER_COUNT] = {0};
srv_info s;
for (int i = 0; i < 100; i++)
{
int ret = get_server(&s);
if (ret == -1)
continue;
printf("%s weight: %d\n", s.ip, s.weight);
int count = used_count[ret];
used_count[ret] = ++count;
}
printf("====================================\n");
for (int i = 0; i < SERVER_COUNT; i++)
{
printf("%s weight:%d called %d times\n", server[i].ip, server[i].weight, used_count[i]);
}
return 0;
}
int get_gcd()
{
return 1;
}
int get_max_weight()
{
int max = 0;
for (size_t i = 0; i < server.size(); i++)
{
if (server[i].weight > max)
max = server[i].weight;
}
return max;
}
/**
* 算法流程：
* 假设有一组服务器 S = {S0, S1, …, Sn-1} ，有相应的权重，变量i表示上次选择的服务器，
* 权值cw初始化为0，i初始化为-1 ，当第一次的时候取权值取最大的那个服务器，
* 通过权重的不断递减，寻找适合的服务器返回，直到轮询结束，权值返回为0
*/
int get_server(srv_info* s)
{
static int n = server.size(); //服务器个数
static int gcd = get_gcd();
static int max = get_max_weight();
while (true)
{
i = (i + 1) % n;
if (i == 0)
{
cw = cw - gcd;
if (cw <= 0)
{
cw = max;
if (cw == 0)
return -1;
}
}
if (server[i].weight >= cw)
{
s->weight = server[i].weight;
memcpy(s->ip, server[i].ip, BUFFER_SIZE);
return i;
}
}
return -1;
}
3、结果：
10个服务器为例：
进行100次的轮询，其结果为：