六、负载均衡算法与实现

常用的负载均衡算法分为以下两类：

静态负载均衡

动态负载均衡

常见的静态均衡算法：轮询法、随机法、源地址哈希法、一致性哈希法、加权轮询法、加权随机法。

常见的动态负载均衡算法：最小连接数法、最快响应速度法。

6.1 随机法（Random）

将请求随机分配到各个节点。由概率统计理论得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配，也就是轮询的结果。

随机策略会导致配置较低的机器 Down 机，从而可能引起雪崩。一般采用随机算法时建议后端集群机器配置最好同等的，随机策略的性能取决于随机算法的性能。

优点：简单高效，易于水平扩展，每个节点满足字面意义上的均衡；

缺点：没有考虑机器的性能问题，根据木桶最短木板理论，集群性能瓶颈更多的会受性能差的服务器影响。

随机法

6.2 轮询法（Round Robin）

每一次来自网络的请求轮流分配给内部中的服务器，从 1 至 N 然后重新开始。此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。

假设 10 台机器，从 0-9 请求来临时从 0 号机器开始，后续每来一次请求对编号加 1。这样一直循环，上面的随机策略其实最后就变成轮询了。这两种策略都不关心机器的负载和运行情况，而且对变量操作会引入锁操作，性能也会下会下降。

优点：简单高效，易于水平扩展，每个节点满足字面意义上的均衡；

缺点：没有考虑机器的性能问题，根据木桶最短木板理论，集群性能瓶颈更多的会受性能差的服务器影响。

轮询法

6.3 加权轮询法（Weighted Round Robin）

不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重，让其处理更多的请求；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。

假设后端有  3台服务器，分别为 a、b、c。现在在负载均衡器中配置  a 服务器的权重为 7，b 服务的权重为 2，c 服务的权重为 1。当来了 10 次请求的时候，其中有 7 次请求 a，2 次请求 b，1 次请求 c。即最终结果是：

优点：可以将不同机器的性能问题纳入到考量范围，集群性能最优最大化；

缺点：生产环境复杂多变，服务器抗压能力也无法精确估算，静态算法导致无法实时动态调整节点权重，只能粗糙优化。

加权轮询

6.4 加权随机法（Weighted Random）

与加权轮询法一样，加权随机法也根据服务器的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。

加权随机

优点：可以将不同机器的性能问题纳入到考量范围，集群性能最优最大化；

缺点：生产环境复杂多变，服务器抗压能力也无法精确估算，静态算法导致无法实时动态调整节点权重，只能粗糙优化。

6.5 最快响应速度法（Response Time）

根据请求的响应时间，来动态调整每个节点的权重，将响应速度快的服务节点分配更多的请求，响应速度慢的服务节点分配更少的请求。

负载均衡设备对内部各服务器发出一个探测请求（例如 Ping），然后根据内部中各服务器对探测请求的最快响应时间来决定哪一台服务器来响应客户端的服务请求。此种均衡算法能较好的反映服务器的当前运行状态，但这最快响应时间仅仅指的是负载均衡设备与服务器间的最快响应时间，而不是客户端与服务器间的最快响应时间。

优点：动态、实时变化，控制的粒度更细，更灵敏；

缺点：复杂度更高，每次需要计算请求的响应速度。

最快响应速度

6.6 最少连接数法（Least Connections）

将请求分发到连接数/请求数最少的候选服务器，已达到负载均衡的目的。

客户端的每一次请求服务在服务器停留的时间可能会有较大的差异，随着工作时间加长，如果采用简单的轮循或随机均衡算法，每一台服务器上的连接进程可能会产生极大的不同，并没有达到真正的负载均衡。

最少连接数均衡算法对内部中需负载的每一台服务器都有一个数据记录，记录当前该服务器正在处理的连接数量，当有新的服务连接请求时，将把当前请求分配给连接数最少的服务器，使均衡更加符合实际情况，负载更加均衡。此种均衡算法适合长时处理的请求服务，如 FTP。

优点：动态，根据节点状况实时变化；

缺点：提高了复杂度，每次连接断开需要进行计数。

最少连接数

6.7 源地址哈希法（Source Hashing）

根据请求源 IP，通过哈希计算得到一个数值，用该数值在候选服务器列表的进行取模运算，得到的结果便是选中的服务器。

能够让同一客户端的请求，或者同一用户的请求，总是请求在后端同一台机器上。这种算法根据客户端 IP 求出 Hash 值然后对端集群总数求余，得到值就是服务器集合的下标。

一般这种算法用于缓存命中，或者同一会话请求等，但这种算法也有一定的缺点，某一用户访问量（黑产）非常高时可能造成服务端压力过大或者后端服务 Down 掉，那么客户端就会无法访问。所以也需要一定的降级策略。

优点：将来自同一 IP 地址的请求，同一会话期内，转发到相同的服务器；实现会话粘滞；

缺点：目标服务器宕机后，会话会丢失。

源地址哈希

6.8 一致性哈希（Consistency hash）

一些场景希望同样的请求尽量落到一台机器上。

比如访问缓存集群时，我们往往希望同一种请求能落到同一个后端上，以充分利用其上已有的缓存，不同的机器承载不同的稳定请求量（也可以理解为固定批用户的请求）。而不是随机地散落到所有机器上，那样的话会迫使所有机器缓存所有的内容，最终由于存不下形成颠簸而表现糟糕。

我们都知道 hash 能满足这个要求。比如当有 n 台服务器时，输入 x 总是会发送到第 hash(x) % n 台服务器上。但当服务器变为 m 台时，hash(x) % n 和 hash(x) % m 很可能都不相等，这会使得几乎所有请求的发送目的地都发生变化。如果目的地是缓存服务，所有缓存将失效，继而对原本被缓存遮挡的数据库或计算服务造成请求风暴，触发雪崩。

一致性哈希是一种特殊的哈希算法，在增加服务器时，发向每个老节点的请求中只会有一部分转向新节点，从而实现平滑的迁移。

一致性哈希

优点：

平衡性：每个节点被选到的概率是 O(1/n)；

单调性：当新节点加入时， 不会有请求在老节点间移动， 只会从老节点移动到新节点。当有节点被删除时，也不会影响落在别的节点上的请求；

分散性：当上游的机器看到不同的下游列表时（在上线时及不稳定的网络中比较常见），同一个请求尽量映射到少量的节点中；

负载：当上游的机器看到不同的下游列表的时候， 保证每台下游分到的请求数量尽量一致。

缺点：

在机器数量较少的时候，区间大小会不平衡；

当一台机器故障的时候，它的压力会完全转移到另外一台机器， 可能无法承载。

七、结语

负载均衡并不是真正确保网络流量能够“均匀”的分配到后端服务实例。它只是抱着在意外情况发生时候，也能保证用户体验。良好的架构设计和弹性扩容，能够使得负载均衡的功能事半功倍。