Web后端系统架构漫谈(3)——轮询和加权轮询

轮询

轮询是最简单的一种负载均衡手段，是非智能的，轮询按照一个固定的顺序依次将负载分配到下游服务器上去。

请求的编号n(n>=0)、下游服务器的数量x(x>0)和请求被路由到的服务器编号i(i>=0)之间有如下关系：

i = n % x

这种轮询很简单，但缺点也没明显，无法根据下游服务器的处理能力和实时的负载情况合理分配负载。因此人们又设计了加权轮询算法。

加权轮询

加权轮询的优点是可以根据服务器处理能力的不同分配不同比例的请求。每台服务器的权重一般是根据一些指标来综合计算的，常见的指标有：

1. CPU处理能力（CPU频率，高速缓存大小）
2. 内存大小和频率
3. 网络带宽
4. 当前处理的连接数

这里还可以分为静态权重和动态权重两种，静态权重是给每台服务器配置一个固定不变的权重值，动态权重则会根据每台服务器当前的状态来动态计算出一个权重值。两种方式各有利弊，静态权重实现简单但不一定能适应所有情况，动态权重能根据实际情况动态调整，使负载更加均匀，服务器使用效率更高，但实现起来也复杂。

下面要介绍两种加权轮询算法，最大公约数算法法和平滑加权轮询算法。

1. 最大公约数算法

最大公约数算法将计算所有服务器的权重值的最大公约数，然后将每台服务器的权重值和它们的最大公约数的比值相加得到数字x，然后继续使用公式算出一个值：

i = n % x

但此时i并不能直接作为服务器的编号使用，而是要判断i的范围。看一个例子：

假设有3台服务器：

1. A: weight: 4
2. B: weight: 2
3. C: weight: 1

它们权重值的最大公约数是1，将每台服务器的权重值和它们的最大公约数的比值相加：4+2+1=7。得到规则：

1. i∈[0, 4)的请求路由到A
2. i∈[4, 6)的请求路由到B
3. i∈[6, 7)的请求路由到C

于是请求编号i∈[0, 7)的请求路由到的服务器编号序列为：

[A, A, A, A, B, B, C]

最大公约数算法可以根据每台服务器的权重值来将请求按比例分配给下游服务器，但也有一个缺点，上面i∈[0, 7)的请求，前4个请求都分配给了A，中间两个请求给了B，最后一个请求分配给C。这种算法在数量上是按照权重分配的，但是请求的分布很不均匀。只有等高权重的服务器都分配过一遍后，才轮到低权重的服务器分配。不过这种算法已经基本做到了按权限分配，可用性还是很高的。

2. 平滑加权轮询算法

还是假设有3台服务器：

1. A: weight: 4
2. B: weight: 2
3. C: weight: 1

在平滑加权轮询算法中，旭要维护每台服务器的当前权重值weight_n和一个当前所有服务器的总权重值current_total_weight。每个请求进来时，先计算current_total_weight，然后将每台服务器的当前权重值加上自己的权重值，将请求分配给当前权重值最大的那台，请求处理完成后，将台服务器的当前权重值减去current_total_weight。周而复始地这样下去。下表记录了前7次请求的理由过程和每台服务器在每个请求时的当前权重值情况：

请求	请求处理前服务器的当前权重值	总权重值	选择的服务器	请求处理后服务器的当前权重值
1	[4, 2, 1]	7	A	[-3, 2, 1]
2	[1, 4, 2]	7	B	[1, -3, 2]
3	[5, -1, 3]	7	A	[-2, -1, 3]
4	[2, 1, 4 ]	7	C	[2, 1, -3]
5	[6, 3, -2]	7	A	[-1, 3, -2]
6	[3, 5, -1]	7	B	[3, -2, -1]
7	[7, 0, 0]	7	A	[0, 0, 0]

前7次请求路由的服务器序列为[A, B, A, C, A, B, A]，A被分配了4次，B被分配了2次，C被分配了1次，权重比例和最大公约数算法是一样的，不同的是分配的分布比较均匀了。