均衡负载里的算法

在均衡负载重,轮询算法是最常用的一个算法。 通常会使用带权重的轮询(wrr).

轮询

轮询的实现非常简单,假设我们有一组节点 [a,b,c,d] ,在不带有权重的时候,只需要一个 next 变量就可以完成。
使用 next 变量记录当前的位置,下一个就是当前位置加一后与节点的长度求余。

1
2
3
4
5
6
7
next := 0 // 当前选择
.....

func rr(){
next = (next+1)%len(servers)
return next
}

带权重的轮询

通常情况下,我们都会选择带权重的轮询来作为均衡算法,带权重有几个好处:

  • 将某个机器的权重调整为 0 来进行上下线的操作
  • 上线新功能或者新机器,可以逐步调大权重,来灰度部分流量来验证功能。

假设我们有这样一组节点 [ a:10 ,b:20,c:30] , 用来表示 3 个节点和其对应的权重。
我们在做计算的时候,需要对所有的权重求出他们的最小公倍数,让他们的表示成[a:1,b:2,c:3] 这样的值。

这里涉及到一个 gcd 的算法,用来求最小公倍数

gcd

gcd 的算法非常简单,叫做辗转求余,代码如下

1
2
3
4
5
6
func gcd(a int, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}

具体可以参看 gcd

wrr

通过 gcd 计算得到 [a:1,b:2,c:3] 后,我们需要按照权重来选择节点。这个时候,可以将前面的节点变成这样的数组 [a,b,b,c,c,c] ,数组中的每个节点都出现的权重指定的次数,这样我们就可以通过前面 rr 里面的算法 next = (next+1)%len(servers) 来进行计算。
但是这里会出现一个问题,a,b,c 的访问在时间片上面是不均衡的,可能会导致某个时间片对某个区间的直接访问。 这就需要对数组里的内容进行打散。
在 nginx 的 wrr 算法: https://github.com/phusion/nginx/commit/27e94984486058d73157038f7950a0a36ecc6e35 保证节点选择的平滑。

算法如下: 对于节点权重 {5,1,1} ,当前一个节点被选中后,权重减去所有权重和,这里是 7 ,当开始选择时,每个节点加上自身的权重。

这里稍微有一些理论,可以想象一下,这些节点在跑道上排成一队,在选择之前,每个人向前走自己的权重步,如果谁在最前面的话,就能够被选中,被选中的人需要向后退权重和的步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 a  b  c
0 0 0 (initial state)

5 1 1 (a selected) 第一次选择了 a ,那么 a 的权重 - 7
-2 1 1 第一次选择后的结果

对第一次选择结果加 5 1 1 得到 3 2 2
3 2 2 (a selected) 第二次选择 a ,那么 a 的权重 -7 得到 -4 2 2
-4 2 2 如此反复整过过程。

1 3 3 (b selected)
1 -4 3

6 -3 4 (a selected)
-1 -3 4

4 -2 5 (c selected)
4 -2 -2

9 -1 -1 (a selected)
2 -1 -1

7 0 0 (a selected)
0 0 0

这个算法能够很好的使算法能够均衡。

hash

使用 hash 作为均衡负载算法,会应用到很多地方,通常情况下我们会根据请求的一些值来作为均衡的 key。

特别是一致性的 hash 算法,处在网络请求的很多位置都会用到,可能所用到的 hash 算法不同,但是本质都是为了保证同一个数据包能够发送到一个位置。
通常会根据不同的需求,对 源 ip、源端口 、目标 ip、源端口、目标端口、协议号 这五元组来做 hash 算法。 比如以下的场景

  • 数据包到达网口,网卡多队列
  • cpu 支持 DUMA 的时,需要让相同的数据包进来在一个核上处理
  • 四层均衡负载中保证 tcp/udp 是到同一个后端
  • 七层均衡负载中保证同一个客户端到同一个后端处理

meglev

Maglev算法是Google开发的一种网络负载均衡器。在很多新的四层均衡负载中喜欢使用,比如 facebook 的 katran。
maglev 使用的一个大的槽位,通过一致性 hash 来将计算分布到槽位上。
使用时固定了槽位,查询效率为 O(1).

https://github.com/zhangweidev/meglevgo