NGINX 和“两种选择的力量”负载平衡算法

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

为什么我们需要新的负载平衡算法？

当您操作单个活动负载均衡器并维护负载均衡节点状态的完整视图时，诸如最小连接之类的经典负载均衡方法会非常有效。 “两种选择的力量”方法在单个负载均衡器上并不那么有效，但它巧妙地避免了在扩展到多个独立负载均衡器时可能发生的糟糕情况“群体行为”。

这种情况不仅在高性能环境中扩展时观察到；在容器化环境中也可以观察到，其中多个代理每个都将流量负载平衡到同一组服务实例。

当您使用NGINX Ingress Controller for Kubernetes 时，会出现这种场景的常见情况，每个 Kubernetes 节点有一个负载平衡实例。

该算法在文献中被称为“两种选择的力量”，因为它最早是在 Michael Mitzenmacher 1996 年的论文《随机负载平衡中的两种选择的力量》中描述的。 在 NGINX 和 NGINX Plus 中，它被实现为随机负载平衡算法的变体，因此我们也将其称为“两种选择的随机”算法。

“两种选择的力量”如何发挥作用？

让我们从一个可能熟悉的情况开始。 您刚刚结束了长途国际飞行，与其他 400 名旅客一起走进了繁忙的到达大厅。

许多机场在到达大厅雇用导游。 他们的工作是引导每位旅客加入各个移民柜台的多个队列之一。 如果我们将指南视为负载均衡器：

• 您和您的旅伴都是请求，每个人都希望尽快得到处理。
• 移民柜台是（后端）服务器，每个柜台负责处理积压的请求。
• 该指南通过为每个请求选择最佳服务器来最大限度提高效率。
• 指南中可用的选择最佳服务器的方法与负载平衡算法相对应。

让我们考虑一下某些可能的算法在像到达大厅这样的分布式负载平衡场景中运行得如何。

循环负载平衡

循环调度是一种简单的负载均衡方法。 在这种方法中，导游会轮流选择每个队列——第一个旅客会被引导到队列 A，下一个旅客会被引导到队列 B，依此类推。 一旦旅行者被引导到最后一个队列，该过程将从队列 A 重复。循环是 NGINX 使用的默认负载均衡算法：

这种方法可以有效发挥作用，直到其中一个队列出现延迟。 也许某位旅客遗失了自己的证件，或者引起了移民官员的怀疑：

队列停止移动，但导游继续将旅客分配到该队列。 积压的时间越来越长——这不会让不耐烦的旅行者更高兴！

最少连接负载平衡

有一个更好的方法。 导游会监视每个队列，每当有旅客到达时，他就会将该旅客引导至最短的队列。 此方法类似于 NGINX 中的最少连接负载平衡方法，它将每个新请求分配给具有最少未完成（排队）请求的服务器：

最少连接负载均衡可以非常有效地处理需要不同时间处理的旅行者。 它试图平衡队列的长度，并避免向已停滞的队列添加更多请求。

最少时间负载平衡

我们发现，不同的乘客需要不同的时间来处理；此外，有些队列的处理速度比其他队列更快或更慢。 例如，一名移民官员可能遇到了计算机问题，这意味着他处理旅客的速度较慢；另一名官员可能对细节非常挑剔，会非常仔细地询问旅客。 其他官员可能非常有经验，能够更快地处理旅客。

如果每个移民亭上方都有一个计数器，显示在过去 10 分钟内有多少旅客办理了手续，那会怎样？ 然后，导游可以根据队列的长度和处理速度引导游客到队列中。 这是一种更有效的负载分配方式，也是 NGINX Plus 中最少时间负载平衡算法的作用：

该算法特定于 NGINX Plus，因为它依赖于使用 NGINX Plus 的扩展状态指标收集的附加数据。 它在云或虚拟环境中特别有效，因为每个服务器的延迟可能无法预测地变化，因此仅凭队列长度不足以估计延迟。

一切都因多个指南而分崩离析

到目前为止，我们已经有一个指南（即负载均衡器），可以全面了解到达大厅的排队和响应时间。 该导游试图根据他所掌握的信息为每位旅行者做出最佳选择。

现在想象一下如果我们有几个导游，每个导游都独立带领旅行者，会发生什么情况。 导游对队列长度和队列等待时间有独立的视角——他们只考虑他们送到每个队列的旅客。

这种情况很容易出现不良行为，即所有导游都注意到一个队列暂时更短、更快，并且所有导游都会将旅行者引导到该队列。 模拟表明，这种“从众行为”会以不均衡和不公平的方式分配旅行者。 同样，无论您使用哪种“最佳选择”算法，多个独立的负载均衡器都可以使某些上游服务器过载。

“两种选择的力量”负载平衡算法

解决方案在于“两种选择的力量”负载平衡算法。 您无需使用不完整的数据来做出绝对最佳的选择，而是利用“两种选择的力量”随机选择两个队列并从中选出更好的选项，避免更差的选择。

“双重选择的力量”实施起来十分有效。 您不必每次都比较所有队列来选择最佳选项；相反，您只需比较两个。 而且，也许不符合直觉的是，它在规模上比最佳选择算法效果更好。 它通过避开最差队列并以一定程度的随机性分配流量的简单方法来避免不良的从众行为。

在 NGINX 和 NGINX Plus 中使用“两种选择的力量”

在 NGINX 和 NGINX Plus 中，“两种选择的力量”负载平衡方法是作为随机算法的变体实现的，因此我们称之为两种选择的随机。

在 NGINX 开源中，两种随机选择功能会根据当前活跃连接数较少的服务器在两个随机选择的服务器之间进行选择。 这与最小连接算法所用的选择标准相同。 （这也是NGINX Plus中的默认算法，可以通过添加least_conn参数进行明确配置。）

上游服务 1 {区域服务 1 64k；服务器 192.168.1.11；服务器 192.168.1.12；服务器 192.168.1.13；随机两个；}

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

• 接收响应头的时间（ least_time=header ）
• 接收完整响应的时间（ least_time=last_byte ），如以下代码片段所示。 最短时间标准非常适合每个上游服务器的延迟可能有所不同的情况。

上游服务 1 { 区域服务 1 64k；服务器 192.168.1.11；服务器 192.168.1.12；服务器 192.168.1.13；随机两个 least_time=last_byte ；# 使用 header 或 last_byte }

结论

NGINX 和 NGINX Plus 支持一系列负载平衡方法；在本文中，我们没有考虑确定性哈希和IP 哈希方法。

当负载均衡器可以完整了解分配给每个节点的工作负载及其过去的性能时，最少连接（对于 NGINX Plus，还有最少时间）方法对于平衡负载非常有效。 当多个负载均衡器分配请求，且每个负载均衡器对工作负载和性能的了解不完整时，它们的效率会降低。

“两种选择的力量”使用一种有偏差的随机算法，并且已被证明在每个负载均衡器具有不完整或延迟视图时能够有效地平衡负载。 它避免了其他算法所表现出的“从众行为”，即试图对每个请求做出最佳决策。

考虑使用“两种选择的随机数”，即 NGINX 对“两种选择的力量”的实现，适用于高性能环境和分布式负载平衡场景。 在 Kubernetes 上使用多个Ingress 控制器时会出现一个很好的用例。