均衡负载里的算法

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

轮询

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

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 的算法非常简单，叫做辗转求余,代码如下

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 ，当开始选择时，每个节点加上自身的权重。

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

 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