常用负载均衡算法

背景

项目开发时，调用第三方服务集群，集群有多台机器，当机器之间没有主从之分时，需要应用层自己做负载均衡以保证各机器之间的流量均衡。

负载调度算法介绍

分布式系统中，常用负载调度算法有轮询、加权轮询、哈希、随机、加权随机、最小连接数。

轮询法

将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。
随机法

系统的随机算法，根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。
源地址哈希法

通过客户端 IP 和服务端 IP 生成唯一的 Hash key。

4、加权轮询法

　　不同机器的配置不同，因此所能承受的负载也不同，因此根据机器的性能分配负载权重也不同。

5、加权随机法
和加权轮询类似，后续详解。

6、最小连接数法

最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前

积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。

轮询法、随机法和源地址哈希都是比较简单的，本文重点展开加权轮询、加权随机和最小连接数法。

加权轮询

Nginx 的负载均衡配置中，支持加权轮询，其配置如下：

upstream tomcats {
    server 192.168.0.100:8080 weight=2;  # 2/6次
    server 192.168.0.101:8080 weight=3;  # 3/6次
    server 192.168.0.102:8080 weight=1;  # 1/6次
}

通常的轮询算法在执行第 $i$ 次请求时，通过 $k = (i + 1) % n $ 选举出第$k$台机器，算法简洁、无需记录所有连接状态，是一种很常用的负责均衡算法。其缺点也很明显，就是不能分配各机器的权重，假设有 $n$ 台机器如果宕机 1 台就会导致命中率下降为$1/n$，为此加权轮询算法应运而生。

加权轮询 WRR(weighted round-robin)算法分为普通加权轮询和平滑加权轮询。加权轮询核心是将一组机器按照权重扩充得到一个序列，然后和普通的轮询算法一样取模求得当前请求应该访问的机器。比如权重为{a:5, b:1, c:1}的一组服务器，加权轮询算法的扩充序列为{ c, b, a, a, a, a, a }，然而这样的序列导致机器 a 集中分布，会造成某部分服务器集群压力过大。平滑加权轮询算法就是将扩充序列随机打散以保证序列的随机性，如权重为{a:5, b:1, c:1} 的机器的平滑扩充序列可能是 { a, a, b, a, c, a, a }。

加权随机

从不重复的含有 n 个元素中不放回随机选取 m 个元素，如果每个元素被选中的概览都相等则把这个过程叫随机抽样（RS——Random Sampling）。加权随机抽样(WRS——Weighted Random Sampling)是指每个元素都带有一个权重，权重决定了该元素被选中的概览。

Pavlos S. Efraimidis 等人在论文Weighted Random Sampling中提出了一种 WRS 算法A，以及基于算法 A 的变种 A-Res 和 A-ExpJ。

A 算法

对于集合 $V$ 中的元素 $v_i \in V$，选取均匀分布的随机数 $u_i=rand(0,1)$ ，计算元素的特征 $k_i = u_i^{(1/w_i)}$
将集合按 $k_i$ 排序，选取前 $m$ 大的元素。

算法的核心是元素特征 $k_i$ 的计算，其正确性在 Weighted random sampling with a reservoir给出了详细的证明。

A-Res—— 基于 A 算法的改进算法
A-Res(Algorithm A with Reservoir) 是 A 算法的”蓄水池“版本，假设从 $n$ 个元素的集合$V$中按权重选取 $m$ 个元素，该算法维护了 $m$ 个元素的集合 $S$，遍历集合$V$中的元素，计算特征值$k_i = u_i^{(1/w_i)}$，当当前元素的特征值大于集合$S$中的特征值时，用当前元素替换集合$S$中特征值最小的元素。具体步骤如下：
1. 将集合 $V$ 的前 $m$ 个元素放入结果集合 $S$。
2. 计算集合$S$中每个元素的特征值 $k_i = u_i^{(1/w_i)}$，其中 $u_i = rand(0,1)$
3. 对于$v_i \in {m+1, m+2,….,n}$ 重复如下步骤 4 ~ 6
4. 将结果集中最小的特征 $k_{min}$作为当前的阈值 $T$
5. 对于元素 $v_i$，计算其特征值$k_i = u_i^{(1/w_i)}$
6. 如果 $k_i > T$ 则使用当前元素$V_i$替换集合$S$中特征值最小的元素(T 所对应的元素)。
如上步骤，该算法只需对集合 $V$ 遍历一次，且并不需事先知道该集合的长度 $m$，因此该算法非常适合数据流场景。论文证明了该算法插入$S$的次数为$O(m \log(\frac{n}{m}))$。该算法实现也不难，核心是维护一个最小堆。

最小连接数法

在实际生产中，客户端的每一次请求并非是相同的请求，服务端处理的时间也不相同，因此无论使用源地址哈希还是随机亦或是轮询都只是即用户请求数量层面的负载均衡。最小连接数法是记录了各服务器的当前连接数量，新请求来时将请求分配到当前连接数最少的服务器。其他负载均衡算法中，当宕机时失败率会瞬间增加，需要手动将机器摘除或将该机器的权重置为0 ，而最小连接法是一种动态调度算法，当发生宕机时，甚至可以实现自动切流量，提高成功率。

背景

负载调度算法介绍

加权轮询

加权随机

最小连接数法

参考资料