均衡负载里的算法
在均衡负载重，轮询算法是最常用的一个算法。 通常会使用带权重的轮询(wrr).
轮询
轮询的实现非常简单，假设我们有一组节点 [a,b,c,d] ，在不带有权重的时候,只需要一个 next 变量就可以完成。
使用 next 变量记录当前的位置，下一个就是当前位置加一后与节点的长度求余。
1 | next := 0 // 当前选择 |
带权重的轮询
通常情况下，我们都会选择带权重的轮询来作为均衡算法，带权重有几个好处：
- 将某个机器的权重调整为 0 来进行上下线的操作
- 上线新功能或者新机器，可以逐步调大权重，来灰度部分流量来验证功能。
假设我们有这样一组节点 [ a:10 ,b:20,c:30] , 用来表示 3 个节点和其对应的权重。
我们在做计算的时候，需要对所有的权重求出他们的最小公倍数，让他们的表示成[a:1,b:2,c:3] 这样的值。
这里涉及到一个 gcd 的算法，用来求最小公倍数
gcd
gcd 的算法非常简单，叫做辗转求余,代码如下
1 | func gcd(a int, b int) int { |
具体可以参看 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 | a b c |
这个算法能够很好的使算法能够均衡。
hash
使用 hash 作为均衡负载算法，会应用到很多地方，通常情况下我们会根据请求的一些值来作为均衡的 key。
特别是一致性的 hash 算法，处在网络请求的很多位置都会用到，可能所用到的 hash 算法不同，但是本质都是为了保证同一个数据包能够发送到一个位置。
通常会根据不同的需求，对 源 ip、源端口 、目标 ip、源端口、目标端口、协议号 这五元组来做 hash 算法。 比如以下的场景
- 数据包到达网口，网卡多队列
- cpu 支持 DUMA 的时，需要让相同的数据包进来在一个核上处理
- 四层均衡负载中保证 tcp/udp 是到同一个后端
- 七层均衡负载中保证同一个客户端到同一个后端处理
meglev
Maglev算法是Google开发的一种网络负载均衡器。在很多新的四层均衡负载中喜欢使用，比如 facebook 的 katran。
maglev 使用的一个大的槽位,通过一致性 hash 来将计算分布到槽位上。
使用时固定了槽位，查询效率为 O(1).
