1. 负载均衡算法
1.1. 随机(Random)
随机选择指的是从已有的后端列表中随机选择一个节点出来提供服务。 一种随机选择的方法是把所有的节点看做一个一个的点，并把这些点连起来排成一条直线， 随机选择就是在这条直线上随机选择一个点：
A - B - C
1.2. 带权重的随机选择 (Weighted Random)
实际使用中各个节点往往都带有不同的权重，即虽然是随机选择但是期望不同权重的节点被选择的几率不一样， 权重高的被选中的几率大，权重低的被选中的几率小。
我们还是可以把带权重信息的节点排成一条直线，不过这一次根据不同的权重把对应的节点重复不同的次数。 假设有三个节点 A、B、C 它们的权重分别是 3、2、4 ，那么就可以这样表示:
A1 - A2 - A3 - B1 - B2 - C1 - C2 - C3 - C4
然后还是随机选择一个点，因为每个节点根据权重重复了相应的次数，所以不同权重的节点被随机选中的概率也不一样， 就简单实现了带权重的随机选择。
上面的按权重重复节点的方式有以下缺点：
- 不支持权重信息包含小数的情况
- 当权重的值很大时要重复很多次浪费资源
一种改进方法是：还是连成一条直线，不过这次是用各个节点的权重值组成一条直线，直线的不同区域属于不同的节点:
A B C
|---|--|----|
然后取直线上的任意一个点，这个点属于直线上哪个节点的区域内就是选择了哪个节点：
- 所有权重相加得到 S（其实就是直线的长度）
- 从 [0, S) 的区间内取一个随机数 R（直线中随机选择一个点）
- 遍历节点列表，把访问过的节点的权重相加得到 V，比较 V 与 R 的值，如果 V > R 当前节点即为选中的节点。（查找 R 在直线中的位置属于哪个节点所在的区域）
1.3. 两次随机选择（Two Random Choices）
两次随机选择策略的主要思想是：
- 从可用节点列表中做两次随机选择操作，得到节点 A、B
- 比较 A、B 两个节点，选出负载最低（一般是正在处理的连接数/请求数最少）的节点作为被选中的节点
1.4. 轮询(Round Robin)
轮询选择指的是从已有的后端节点列表中按顺序依次选择一个节点出来提供服务。
一种轮询选择的方法是把所有的节点看做一个一个的点，并把这些点连起来组成一个圆， 轮询选择就是在这个圆上按顺时针选择一个点。可以通过用请求次数取模来实现这个顺时针选择的功能。
如果所有的服务器有相同或者相近的性能那么选择这种方式会使服务器负载形同。基于这个前提，轮循调度是一个简单而有效的分配请求的方式。然而对于服务器不同的情况，选择这种方式就意味着能力比较弱的服务器也会在下一轮循环中接受轮循，即使这个服务器已经不能再处理当前这个请求了，这可能导致能力较弱的服务器超载。
Nginx的配置
upstream my_service {
server 192.168.3.8:9000;
server 192.168.3.8:9001;
}
Nginx无法保证同一客户端每次都会请求到同一个服务器。
1.5. 加权轮询(Weighted Round Robin)
加权轮询是轮询的一种特殊形式，其主要目的就是为了解决不同服务器处理能力有差异的问题：传入的请求按顺序被分配到集群中服务器，但是会考虑提前为每台服务器分配的权重。权重高的被选中的次数多，权重低的被选中的次数少。
管理员只是简单的通过服务器的处理能力来定义各台服务器的权重。例如，能力最强的服务器A给的权重是100，同时能力最低的服务器给的权重是50。这意味着在服务器B接收到第一个请求之前前，服务器A会连续的接受到2个请求，以此类推。
我们还是可以把带权重信息的节点排成一个圆，不过这一次根据不同的权重把对应的节点重复不同的次数。
然后还是顺时针选择一个点，因为每个节点根据权重重复了相应的次数，所以不同权重的节点被选中的次数也不一样并且选中的次数跟它本身的权重有关，这样就就简单实现了带权重的轮询选择。
上面的按权重重复节点的方式有一个明显的问题就是不够平滑：
权重高的节点会先被选中直至达到权重次数才会选择下一个节点或者说会出现请求连续的打在同一个节点上的情况，导致权重低的节点可能会处于空闲状态，没有平滑分配请求。
一种改进方法是：使用 nginx 中实现的一种平滑的带权重轮询的方法
算法逻辑
For edge case weights like { 5, 1, 1 } we now produce { a, a, b, a, c, a, a } sequence instead of { c, b, a, a, a, a, a } produced previously.
Algorithm is as follows: on each peer selection we increase current_weight of each eligible peer by its weight, select peer with greatest current_weight and reduce its current_weight by total number of weight points distributed among peers.
In case of { 5, 1, 1 } weights this gives the following sequence of current_weight’s:
a b c
0 0 0 (initial state)
5 1 1 (a selected)
-2 1 1
3 2 2 (a selected)
-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
To preserve weight reduction in case of failures the effective_weight variable was introduced, which usually matches peer’s weight, but is reduced temporarily on peer failures.
每个节点有三个属性，这三个属性的含义如下：
weight: 节点权重值，这个值固定不变。effective_weight: 节点的有效权重。初始值等于weight。之所以有个effective_weight是为了 在发现后端节点异常次数过多时（比如响应完成时发现选择的节点有问题，错误次数有点多）临时降低节点的权重。 在轮询遍历选择节点时这个effective_weight的值会逐步增加恢复到weight的值，所以只是为了在异常时临时降低权重不会永久影响节点的权重（节点正常时会逐步恢复到原有的权重）。- current_weight: 节点当前权重。初始值为 0，后面会动态调整：
- 每次选取节点时，遍历可用节点，遍历时把当前节点的
current_weight的值加上它的effective_weight， - 同时累加所有节点的
effective_weight值为total。 - 如果当前节点的
current_weight值最大，那么这个节点就是被选中的节点，同时把它的current_weight减去total - 没有被选中的节点的
current_weight不用减少。
- 每次选取节点时，遍历可用节点，遍历时把当前节点的
Nginx的配置
upstream my_service_weight {
server 192.168.3.8:9000 weight=1;
server 192.168.3.8:9001 weight=2;
}
Nginx无法保证同一客户端每次都会请求到同一个服务器。
1.6. 最少连接数(Least Connection)
以上方法都没有考虑的是系统不能识别在给定的时间里保持了多少连接。因此可能发生，服务器B收到的连接比服务器A少但是它已经超载，因为服务器B上的用户打开连接持续的时间更长。这就是说连接数即服务器的负载是累加的。这种潜在的问题可以通过“最少连接数”算法来避免：传入的请求是根据每台服务器当前所打开的连接数来分配的。即活跃连接数最少的服务器会自动接收下一个传入的请求。
活跃连接数 = 正在处理的连接数/请求数（对于七层负载均衡器来说可能更多的是说的最少请求数）
基本上和简单轮询的原则相同：所有拥有虚拟服务的服务器资源容量应该相近。值得注意的是，在流量率低的配置环境中，各服务器的流量并不是相同的，会优先考虑第一台服务器。这是因为，如果所有的服务器是相同的，那么第一个服务器优先，直到第一台服务器有连续的活跃流量，否则总是会优先选择第一台服务器。
upstream my_service_least_conn {
least_conn;
server 192.168.3.8:9000;
server 192.168.3.8:9001;
}
Nginx无法保证同一客户端每次都会请求到同一个服务器。
1.7. 加权最少连接(Weighted Least Connection)
如果服务器的资源容量各不相同，那么“加权最少连接”方法更合适：由管理员根据服务器情况定制的权重所决定的活跃连接数一般提供了一种对服务器非常平衡的利用，因为他它借鉴了最少连接和权重两者的优势。通常，这是一个非常公平的分配方式，因为它使用了连接数和服务器权重比例;集群中比例最低的服务器自动接收下一个请求。但是请注意，在低流量情况中使用这种方法时，请参考“最小连接数”方法中的注意事项。
实际使用中各个节点往往都带有不同的权重，比较连接数时需要同时考虑节点的权重信息， 被选中的节点的连接数与权重的比要最小。 即，被选中的节点满足下面的条件：
- 假设用 C 表示连接数、W 表示权重、S 表示被选中的节点、Sn 表示未被选中的节点
- 那么 S 必须满足 C(S) / W(S) < C(Sn) / W(Sn) ，这个条件也可以表示为 C(S) * W(Sn) < C(Sn) * W(S)
当有多个节点满足条件时，上面的方法可能会连续多次选中同一个节点， 导致结果不够平滑。
解决这个瑕疵的方法也比较简单，那就是把所有满足条件的节点都选出来，然后对这些节点应用其他负载均衡策略来选出合适的节点（比如使用前面介绍过的轮询策略、随机选择策略等）。
1.8. 最少连接数慢启动时间(Least Connection Slow Start Time)
对最少连接数和带权重的最小连接数调度方法来说，新加了一个节点到负载均衡器中，但是后端节点是需要一段时间的预热才能处理大量连接， 当我们使用的是类似 【最少连接】这种负载均衡策略时，因为是新增的节点连接数最少会出现短时间连接大量涌入新节点的情况， 此时就会出现节点过载的情况（前面说了假设我们的节点需要预热才能处理大量连接），甚至出现打垮新节点的情况。
所以当一个节点刚加入负载均衡器时，可以为其配置一个时间段，在这段时间内连接数是有限制的而且是缓慢增加的。这为服务器提供了一个‘过渡时间’以保证这个服务器不会因为刚启动后因为分配的连接数过多而超载。
对于这种类似需要预热的场景，需要负载均衡器支持类似 slow start 模式： slow start 模式下，节点的权重和最大连接数会从 1 开始随着时间线性增长，直至增长到配置的权重和最大连接数的值。 slow start 模式给予了节点一段时间的预热期，并且预热期间的连接数是线性缓慢增长的， 既达到了预热的效果又不会出现瞬间涌入大量连接打垮后端节点的情况，非常适合需要预热的情况。
那么，在什么情况下一个节点会自动进入 slow start 模式呢，一般在下面的情况会考虑自动进入 slow start 模式：
- 新增节点。
- 节点健康状态从不健康切换到健康。此时一般是后端节点之前在发布或重启，亦或是刚刚从故障中恢复。
- 节点状态从 Down 状态切换为可以接受新连接的状态。这个状态切换可能是手动通过页面或API进行的操作，也可能是程序内部的状态自动切换。 原因一般跟上面的健康检查状态切分类似。
关于这个 slow start 模式有一点需要注意的是：在负载均衡器启动的时候一般不会触发 slow start 模式，虽然满足上面的新增节点的情况。因为如果在负载均衡器启动的时候就触发的话，会出现所有节点都进入 slow start 模式，可能会导致只能处理少量连接的情况，无法实际需求。如果确实需要启动时就进入 slow start 模式的话需要考虑一下这种情况会导致的容量问题。
1.9. 一致性哈希
所谓的一致性哈希策略指的是根据后端节点的某个固定属性计算 hash 值，然后把所有节点计算出来的 hash 值组成一个 hash 圆环。 请求过来的时候根据请求的特征（比如，来源 ip 、cookie、用户名等特定信息）计算该特征的 hash 值（使用跟计算后端节点 hash 值相同的 hash 函数进行计算）， 然后顺时针查找 hash 环上的 hash 值，第一个比请求特征的 hash 值大的 hash 值所对应的节点即为被选中的节点。
参考 一致性hash算法
1.10. 有限负载一致性哈希
一致性哈希策略有一个缺陷，那就是没有解决热点问题：当有部分资源是热点资源或者部分用户请求量比较大的时候，会出现部分节点需要处理大量请求（这些请求根据一致性哈希策略都选中了固定的部分节点），出现负载非常不均的情况，因为是一致性哈希所以这些请求没法分摊到其他节点上，导致出现持续的负载不均和热点问题。
有限负载一致性哈希主要思路是，根据当前负载情况对所有节点限制一个最大负载，在一致性哈希中对 hash 环进行查找时将跳过达到最大负载限制的节点，通过把过载的请求转移到其他节点上来解决热点和不均衡问题。
1.11. 加权响应(Weighted Response)
加权轮循中所使用的权重是根据服务器有效性检测的响应时间来计算。每个有效性检测都会被计时，用来标记它响应成功花了多长时间。，比如后端连续多次返回的响应码是 5xx 或者响应时间或后端服务负载超出阈值等，此时可以根据需要降低一下该节点的权重和最大连接数限制（注意要在适当的时机把权重恢复回来，比如一段时间不再返回 5xx 或后端负载恢复到正常水平 则逐步恢复到原来的权重值）或者把节点切换为不接受新请求的状态，一段时间后进入 slow start 模式慢慢恢复正常。
但是需要注意的是，这种方式假定服务器心跳检测是基于机器的快慢，但是这种假设也许不总是能够成立。所有服务器在虚拟服务上的响应时间的总和加在一起，通过这个值来计算单个服务物理服务器的权重;这个权重值大约每15秒计算一次。
1.12. 源IP哈希(Source IP Hash)
这种方式通过生成请求源IP的哈希值，并通过这个哈希值来找到正确的真实服务器。这意味着对于同一主机来说他对应的服务器总是相同。使用这种方式，你不需要保存任何源IP。但是需要注意，这种方式可能导致服务器负载不平衡。
upstream my_service_ip_hash {
ip_hash;
server 192.168.3.8:9000;
server 192.168.3.8:9001;
}
1.13. url哈希
按访问url的hash结果来分配请求，使每个url定向到同一个后端服务器，后端服务器为缓存时比较有效
upstream my_service_url_hash {
hash $request_uri;
server 192.168.3.8:9000;
server 192.168.3.8:9001;
}
1.14. CPU/IO 负载最低优先
如果我们自己开发负载均衡系统，可以根据业务特点来选择指标衡量系统压力。如果是 CPU 密集型，可以以“CPU 负载”来衡量系统压力；如果是 I/O 密集型，可以以“I/O 负载”来衡量系统压力。
CPU 负载最低优先的算法要求负载均衡系统以某种方式收集每个服务器的 CPU 负载，而且要确定是以 1 分钟的负载为标准，还是以 15 分钟的负载为标准，不存在 1 分钟肯定比 15 分钟要好或者差。不同业务最优的时间间隔是不一样的，时间间隔太短容易造成频繁波动，时间间隔太长又可能造成峰值来临时响应缓慢。
2. 参考资料
https://mp.weixin.qq.com/s/4GuAT1TncctCdPIyK2bGWQ
https://mp.weixin.qq.com/s/5K36wNsZjFnuQMfuFcNv8Q
https://mozillazg.com/2019/01/load-balancing-strategy-algorithm-weighted-random.html
https://mozillazg.com/2019/02/load-balancing-strategy-algorithm-weighted-round-robin.html
https://mozillazg.com/2019/02/load-balancing-strategy-algorithm-weighted-least-connection.html
https://mozillazg.com/2019/03/load-balancer-load-balancing-dynamic-weight-max-connections-slow-start-mode.html
