NGINX与“二选一”负载均衡算法

NGINX | 2018年11月12日

新的用例有时需要新的负载均衡算法。我们在NGINX Plus R16和NGINX Open Source 1.15.1中新增了一种特别适合分布式负载均衡器的方法，即“二选一”算法的实现。

为什么需要新的负载均衡算法？

传统负载均衡方法（例如“最少连接”）在仅运行一个主动负载均衡器，且该负载均衡器能够全面掌握各负载均衡节点状态时，效果非常好。“二选一”方法在单个负载均衡器上的效果不如传统方法，但在横向扩展到多个独立负载均衡器时，可以巧妙避免极端情况下可能出现的“羊群行为”。

这种情况不仅会在高性能环境中横向扩展时出现，也会出现在容器化环境中。在容器化环境中，多个代理分别对发往同一组服务实例的流量进行负载均衡。

采用分布式负载均衡器的集群拓扑

这种场景的一个常见示例是使用NGINX Ingress Controller for Kubernetes，并为每个Kubernetes节点部署一个负载均衡实例。

该算法在文献中称为“双随机选择”，因为它最早见于Michael Mitzenmacher 1996年的博士论文《随机负载均衡中的双随机选择》。在NGINX和NGINX Plus中，该算法作为随机负载均衡算法的一种变体实现，因此也称为“双随机选择”。

“两次选择的力量”如何运作？

先从一个可能很熟悉的场景说起。经过漫长的国际航班旅程后，您刚刚落地，与其他400名旅客一同走进繁忙的到达大厅。

照片：Caroline M.A Otieno，自有作品，采用CC BY 2.0许可协议

许多机场会在入境大厅安排引导员。他们负责引导每位旅客加入各个入境检查柜台前的其中一条队伍。如果将这些引导员视为负载均衡器：

您和同行旅客相当于请求，都希望尽快得到处理。
入境检查柜台相当于（后端）服务器，每台服务器都在处理积压的请求。
引导员通过为每个请求选择最合适的服务器来尽可能提高效率。
指南用于选择合适服务器的方法对应于负载均衡算法。

下面以入境大厅为例，看看几种可选算法在分布式负载均衡场景中的表现。

轮询负载均衡

轮询是一种简单的负载均衡方法。在这种方法中，引导员依次选择各个队列：第一位旅客被引导至队列A，下一位旅客被引导至队列B，以此类推。当一位旅客被引导至最后一个队列后，该过程将从队列A重新开始。轮询是NGINX默认使用的负载均衡算法：

这种方法原本运行尚可，直到其中一个队列出现延误。例如，某位旅客可能遗失了证件，或引起了移民官员的怀疑：

队列停止移动，但引导员仍不断将旅客分配到该队列。积压的旅客越来越多，这可不会让那些不耐烦的旅客心情变好！

最少连接负载均衡

还有一种更好的方法。引导员会观察每个队列，每当有旅客到达时，就将其引导至最短的队列。这种方法类似于NGINX中的最少连接负载均衡方法，该方法会将每个新请求分配给未完成（排队）请求数最少的服务器：

最少连接负载均衡可以有效处理耗时不同的请求。它会尽量平衡各队列的长度，并避免向已停滞的队列添加更多请求。

最短时间负载均衡

我们已经看到，处理不同旅客所需的时间各不相同；此外，有些队列的处理速度比其他队列更快或更慢。例如，一名移民官可能因计算机出现问题而降低旅客处理速度；另一名移民官可能非常注重细节，会仔细询问旅客。还有一些移民官可能经验丰富，能够更快地处理旅客。

假设每个入境检查窗口上方都有一个计数器，显示过去一段时间（例如10分钟）内已处理的旅客人数，会怎么样？这样，引导员就可以根据队伍长度和处理速度，将旅客引导至相应队伍。这是一种更有效的负载分配方式，也是NGINX Plus中的Least Time负载均衡算法所采用的方式：

此算法仅适用于NGINX Plus，因为它依赖通过NGINX Plus的“扩展状态”指标收集的其他数据。此算法在云环境或虚拟环境中尤其有效，因为这些环境中各服务器的延迟可能出现不可预测的变化，仅凭队列长度不足以估算延迟。

多个指南会让一切陷入混乱

到目前为止，只有一名向导（即负载均衡器）能够全面掌握到达大厅的排队情况和响应时间。这名向导会根据已知信息，尽量为每位旅客作出合适的选择。

现在，假设有多名引导员，各自独立引导旅客，看看会发生什么。每名引导员对队列长度和排队等待时间都有各自的了解，只会考虑自己引导至各队列的旅客。

这种场景容易出现一种不良行为：所有向导都发现某个队列暂时更短、速度更快，于是都将旅客引导至该队列。模拟结果表明，这种“羊群行为”会导致旅客分配失衡且不公平。同样，无论使用哪种“最佳选择”算法，多个独立的负载均衡器都可能使部分上游服务器过载。

“二选一”负载均衡算法

解决方案在于“二选一”负载均衡算法。该算法不会根据不完整的数据试图做出绝对最优的选择，而是随机选取两个队列，并从中选择较优的一个，从而避开较差的选择。

“二选一”算法的实现效率很高。无需每次比较所有队列来选出最佳选项，只需比较两个队列即可。也许有悖直觉的是，在大规模环境中，它的效果优于最佳选择算法。其方法很简单：避开最差的队列，并以一定的随机性分配流量，从而避免不必要的羊群行为。

在NGINX和NGINX Plus中使用“二选一”算法

在NGINX和NGINX Plus中，“二选一”负载均衡方法作为Random算法的一种变体实现，因此称为Random with Two Choices。

在 NGINX Open Source 中，Random with Two Choices 会从随机选出的两台服务器中，选择当前活动连接数较少的一台。这与 Least Connections 算法采用的选择标准相同。（这也是 NGINX Plus 中的默认算法，可通过添加 least_conn 参数进行显式配置。）

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two; 
}

NGINX Plus还支持least_time参数，该参数采用与最短时间算法相同的选择标准。与该算法一样，您还可以选择考虑以下任一项：

接收响应标头所需的时间（least_time=header）
接收完整响应所需的时间（least_time=last_byte），如下方代码片段所示。Least Time准则适用于各上游服务器延迟可能不同的情况。

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two least_time=last_byte; # use header or last_byte
}