超越轮循:为了延迟的负载均衡
原文: BEYOND ROUND ROBIN: LOAD BALANCING FOR LATENCY
作者: STEVE JENSON, 时间: 2016-3-16
这个帖子是与 Ruben Oanta 合作编写的。
负载均衡是任何大型软件部署的关键组成部分。但是有很多方法可以进行负载均衡。哪种方式是最好？我们如何评估不同的选择？
在现代软件生态系统中，负载均衡扮演了几个角色。首先，它是扩展性概念的根本。软件部署在多个相同的副本中。我们通过部署额外的副本来“scale”软件。流量必须分布在副本上，而这种分布是负载均衡的行为。
负载均衡提供了另一个必要的功能: 弹性。直观地说，弹性系统是单个组件的故障不会导致系统本身失效的系统。软件或其运行的硬件总是会失败的。通过仅将流量分配给能够提供服务的实例，负载均衡使我们能够将多个可能失败的组件组合成一个单一的弹性系统。
我们可以将这种弹性模型进一步扩展，以解决分布式系统中另一个不受欢迎的访问者：延迟。正如系统的组件可能会失败一样，它们也可能以各种方式变慢。良好的负载均衡器必须防止延迟，正如它防止故障一样。即使存在缓慢的复副本，整个系统也必须保持快速。
这第三个标准比前两个更为微妙。从算法上来说，解决可伸缩性和弹性是非常直白的：给定一组副本，在所有活动副本上分配流量，并且不将流量分发给失败的副本。（我们将忽略,现如今,评估副本的健康状况的不是毫无意义的挑战。）对于延迟，故事不太清晰：给定一组以各种速度执行的副本，在他们之间分发负载的最佳策略是什么？
在本文中，我们运行一个简单的实验，使用三种算法：轮循(round robin)，最少负载(least loaded)和峰值指数加权移动平均值（“peak EWMA”）。这三种算法作为一个测试台，用于说明负载均衡算法的正确选择或错误选择的影响。特别地，我们测试这些算法在处理组件延迟时的有效性。
简单来说，这三种算法的行为如下：
轮询：依次向每个副本分发请求。
最少负载：保持对每个副本的未完成请求的计数，并将流量分配给具有最少未完成请求的副本。
峰值EWMA：保持每个副本的往返时间的移动平均值，以未完成请求的数量加权，并将流量分配给成本函数最小的副本。
在这三种算法中，轮询在实践中最常见，并且在大多数软件负载均衡器中可用，包括 Nginx 和 HAProxy。另外两种算法较不常见，但两者的生产测试实现都可以在 Finagle(Twitter的客户端RPC库) 中使用。
实验设置
我们运行一个简单的模拟来测量组件延迟对整个系统延迟的影响，使用以下场景：
11个后端服务器，每个重播从生产系统捕获的延迟。该延迟分布的中位数为167ms，标准偏差为5ms，没有明显的峰值。
一个客户端，运行在1000 qps，在所有11个后端间平衡。
总共运行一分钟。
15秒后，某个服务器的延迟时间固定为2秒,持续30秒，然后恢复正常。（这模拟了一个后端服务遭受垃圾收集暂停或其他暂时性问题）。
我们使用了一个用Finagle编写的基本RPC客户端进行这些实验。
（请注意，Finagle 默认情况下不包括轮循的实现。为了降低整个实验条件的变化，我们为对这个实验增加了的实现。您可以 在这里 下载这个实验中使用的代码。）
结果
实验结果如上图所示。y轴表示延迟，x轴（对数刻度）表示延迟分布中超过延迟的百分位数。
面对慢速服务器的三种算法之间的性能差异很明显。轮循影响次数最多，95%以上就表现为低性能。最少负载表现更好，保持快速性能直到99%，而EWMA峰值表现更好，保持速度直到99.9%。
在分布式系统中, 由于延迟和故障经常通过超时捆绑在一起，我们还可以根据故障表示结果。如果我们系统的调用者使用了1秒的超时时间，其成功率将大约为轮循95％，最少负载99％，峰值EWMA99.9％，显著不同。
讨论
轮循显然是三项算法中表现最差的一种。在某些方面，这并不奇怪：这也是最天真的。
然而，轮循不仅仅是一个更糟糕的算法 - 它没有利用可用于最少负载和峰值EWMA的信息。由于 Finagle 在OSI模型中的第5层（“会话”层）运行，因此可以访问诸如队列深度和RPC延迟的信息。最少负载利用队列深度，并显示出比轮循显著改善的性能; 峰值EWMA考虑了RPC延迟和队列深度，并显示出更好的性能。三个选项之间的区别不仅仅在于算法差异,而是用于进行平衡决策的信息的差异。
当然，在实践中，影响负载均衡性能的因素有很多，不仅仅是算法的选择。在高并发下，实现可能性能不佳。该算法可能不适用于某些类别的请求，例如长轮询请求（在这种情况下，高延迟是预期中的，而不是故障症状）。该算法可能不适用于特定的客户端/服务器关系，例如高度不对称的副本计数。在这篇文章中，我们没有试图提出一个全面的分析，并是只花了最少的努力来控制这些变数。我们的意图只是简单提供一个例子,关于算法选择可能带来的差异。
也就是说，Twitter上的大规模生产实验已经验证了最少负载和峰值EWMA（以及其他负载平衡算法）的有效性，而且这些算法在规模上可以用于大部分Twitter的基础设施。
结论
对于需要负载均衡高级连接（如RPC或HTTP调用）的系统，其中第5层信息（如端点延迟和请求深度）可用，那么在存在慢端点的情况下，轮循负载均衡可能会比其他算法执行得更差。通过使用可以利用第5层信息的算法，这些系统可能会在面临慢端点时显著提高性能。
如果上述结果适用于您的情况，您可能希望利用像最少负载和峰值EWMA这样的算法。这些算法的经过生产测试的实现方法现在在 Finagle 中可用，也在 linkerd(用于云原生应用程序的开源服务网格) 中可用。（有关如何在linkerd中配置负载均衡算法，请参阅 [此处][]。）
致谢
感谢 Marius Eriksen，Alex Leong，Kevin Lingerfelt 和 William Morgan 对本文档早期草稿的反馈意见。
进一步阅读
The Tail at Scale. http://cacm.acm.org/magazines/2013/2/160173-the-tail-at-scale/abstract
Michael Mitzenmacher. 2001. The Power of Two Choices in Randomized Load Balancing. IEEE Trans. Parallel Distrib. Syst. 12, 10 (October 2001), 1094-1104.
Last updated
