Round robin详解

最近在学习 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 到达最左侧。

上面所讲的轮询调度算法并没有考虑每台服务器的处理能力，在实际情况中，可能并不是这种情况。由于每台服务器的配置、安装的业务应用等不同，其处理能力会不一样。所以，我们根据服务器的不同处理能力，给每个服务器分配不同的权值，使其能够接受相应权值数的服务请求。

权重轮询调度算法流程

假设有一组服务器S = {S0, S1, …, Sn-1}，W(Si)表示服务器Si的权值，一个指示变量i表示上一次选择的服务器，指示变量cw表示当前调度的权值，max(S)表示集合S中所有服务器的最大权值，gcd(S)表示集合S中所有服务器权值的最大公约数。变量i初始化为-1，cw初始化为零。其算法如下：

在多台机器实现负载均衡的时候,经常用到轮询调度算法(Round-Robin Scheduling)。

轮询调度算法就是以循环的方式依次将请求调度不同的服务器，即每次调度执行i = (i + 1) mod n，并选出第i台服务器。

算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。

1、算法流程：
假设有一组服务器 S = {S0, S1, …, Sn-1} ，有相应的权重，变量i表示上次选择的服务器，权值cw初始化为0，i初始化为-1 ，当第一次的时候取权值取最大的那个服务器，通过权重的不断递减，寻找适合的服务器返回，直到轮询结束，权值返回为0

2、代码实现：

/*
 * 权重轮询调度算法(Weighted Round-Robin Scheduling)
 * 在多台机器实现负载均衡的时候,存在调度分配的问题.
 * 如果服务器的配置的处理能力都一致的话,平均轮询分配可以直接解决问题,然而有些时候机器的处理能力是不一致的.
 * 假如有2台机器 A和B , A的处理能力是B的2倍,则A的权重为2,B的权重为1.权值高的服务器先收到的连接，
 * 权值高的服务器比权值低的服务器处理更多的连接，相同权值的服务器处理相同数目的连接数。
 * */
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
using namespace std;

#define SERVER_COUNT 10
#define RAND_WEIGHT 10
#define BUFFER_SIZE 1024

struct srv_info
{
	srv_info()
	{
		ip  = new char[BUFFER_SIZE];
		weight = 0;
	}
		
	char* ip;
	int weight;
};

static vector<srv_info> server;		//服务器信息
static int i = -1;					//上一次选择的服务器
static int cw = 0;					//当前调度的权值

int get_gcd();						//获得所有服务器权值的最大公约数
int get_max_weight();				//获得所有服务器中的最大权值
int get_server(srv_info* s);		//轮询调度
		
int main(int argc, char **argv)
{
	srand(time(NULL));
		
	char tmp[BUFFER_SIZE];
	server.clear();
	for (int i = 0; i < SERVER_COUNT; i++) 
	{
				
		const char* s = "192.168.0.10";
				
		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次的轮询，其结果为：