使用Envoy检查负载平衡算法

如果你处理网络系统，你可能会很关心延迟（latency）。在面对一组服务器时，你还可能需要决定使用哪种负载平衡算法。在做这些决策时，对不同负载平衡器配置中预期的行为建立直觉非常有帮助，这样你就可以在没有任何意外行为的情况下最小化环境中的延迟。

希望我们都能同意负载平衡器的工作，是将请求分发到一些服务器上（在Envoy被称为“上游”upstream）。其目标是最大限度地，提高为这些请求提供服务的效率。效率可以意味着服务器的最佳CPU利用率，或发送方的最小等待时间（延迟）。通常，在发现延迟的地方，你还会发现某个地方正在形成一个队列，因此我将继续研究负载平衡器方案，以最小化upstream上的排队。

我将对Envoy中的各种负载平衡算法进行（非详尽的）概述，并通过一些模拟来展示它们的行为。有很多东西需要复习，所以我会尽量保持简单和集中。这里不会讨论重试策略、断路、紧急路由、负载平衡器优先级等等，或者它们对负载平衡的（重要的）影响。这些特性的效果非常重要，所以要知道它们在实际（而不是模拟）工作负载中发挥了很大的作用！

模拟流量

接下来的每个模拟将通过一个Envoy进程向10个HTTP服务器发送带有一些固定RPS的HTTP请求。服务器简单地接受一个请求，休眠一段时间（我们称之为“服务时间”），并以200的状态进行响应。

模拟的一般拓扑结构。

如果一个特定的服务器同时处理多个请求，它将重复随机选择一个并休眠100us，直到满足该请求的“服务时间”，这是请求并发性对延迟的影响的近似体现。当每个服务器中形成一个队列并为多个请求提供服务时，每个响应的延迟将会增加。请记住，如果我们没有让每个请求在相同的服务时间休眠，并且有实际的延迟分布（就像我们在现实生活中所做的那样），那么在服务器上排队将不成比例地影响我们的尾部延迟。

延迟和RPS数字的细节将被省略，因为我们关心形成的队列以及队列和负载平衡算法之间的关系。因为我控制着RPS和请求延迟，所以只有这两者之间的关系对排队行为有影响。

现在让我们来看看好的东西——负载平衡器！

随机负载平衡

Envoy支持的最简单的负载平衡器是随机负载平衡器，其中节点/端点是通过均匀随机选择选择的。

均匀随机选择是将请求分发到一组上游节点的最简单方法，也是最容易实现的方法。我们可以合理地预期，经过均匀随机选择算法处理的10个节点池在100万次选择之后会出现一个平面分布：

采用均匀随机选择的节点选择直方图。看起来很均匀！

请求的平均分配！这就是我们想要的，对吧？

实际上，事情并没有这么简单。让我们来看一个场景，其中这10个节点通过随机负载平衡分配请求。

下面是我们的结果，其中每一行代表一个不同的端点，Y轴是在实验期间某一特定时间点上该端点的未完成请求数：

每个节点对随机LB的活跃请求数。

每个端点的活跃请求的具体数量并不重要，但是值得注意的是请求在端点之间的分布。某些节点在特定时间点上的未完成请求比其他节点多一个数量级！看起来，即使均匀随机选择的渐近行为产生了均匀分布，在任何时间点上，端点都可能因为太多的请求而负担过重。这可能会导致延迟增加、在服务中形成请求队列，并最终导致级联失败。

我们可以通过确保每个节点以可预测的方式接收请求来对抗这种行为，因此让我们引入循环（round-robin）选择。

循环负载平衡

Envoy的循环（或“next-in-loop”）负载平衡策略将在每个上游节点上依次旋转。这样做的好处是为我们提供了一个可预测的请求分布，不仅渐进地（比如在均匀随机选择的情况下），而且在任何时间点都是如此。运行相同的测试，但是与上面的随机选择实验相比，在config中使用循环负载平衡策略可以在上游节点中产生更紧密的活跃请求分布：

每个节点对循环LB的活跃请求数。

对于完全相同的测试，我们还将比较使用循环和随机负载平衡时，每个节点上的请求数。我们将定义一个称为请求漂移（request drift）的指标，通过查看在每个时间点上接收到最多请求的节点和接收到最少请求的节点之间的差距：

活跃请求数最高的节点与活跃请求数最低的节点之间的差异。

这就解决了！使用循环负载平衡，以最小的活跃请求漂移实现请求的均匀分布！简单！优雅！

不！

到目前为止，所有上游节点都是同构的，具有相同的延迟配置文件。如果向上流的某个子集是功能非常强大的节点，而它们没有得到充分利用，或者向上流的某些子集是马铃薯（potato，慢）计算机，情况又会如何呢？下面，我们进行了相同的循环实验/配置，但是现在我们有3个闪电般快的节点几乎在瞬间完成请求，3个马铃薯节点完成请求的速度比以前慢了25%。如你所见，有3组明显的活跃请求数：

对于高延迟/较弱的节点（A）、我们在以前的模拟中熟悉的标准节点（B）和快闪节点（C），活跃请求数。

我们现在遇到的问题是，A组中较慢的节点（potato）一次处理太多请求，并经历了较高的延迟，而C组中最快的节点却没有得到充分利用。请注意，对于速度较慢的节点（等待发生级联故障），请求队列正在增长，而对于速度较快的节点，实际上没有队列。

如果负载平衡器能够考虑到发送给每个节点的未完成请求的数量，并根据这些信息对其转发决策进行倾斜，那就太好了。

很方便地，Envoy有一个负载平衡器做这个！

最小请求负载平衡

Envoy的最小请求负载均衡器考虑到发送给每个节点的未完成请求的数量，并根据活跃请求数对其转发决策进行偏置。当讨论循环方法时，我们遇到了节点利用率过高/不足的问题，但这里的实现细节很重要——“偏置”节点选择究竟意味着什么？

考虑分配给节点的某个权重，该权重与该节点的未完成请求数成反比。如果我们有100个节点，其权值在[0,100]范围内，我们有一些不同的选项来根据权值对选择进行偏置。

加权比例选择

进行加权选择的最明显的方法，是简单地使一个对象的选择概率与权重成正比，类似于旋转轮盘赌。这也被称为适合度比例选择。通过模拟可以看出，选择数的比例收敛于选择池中每个对象的权值（X轴为对象的权值）：

加权比例选择不同时间点的选择数直方图。X轴上的每个对象权重表示一个具有相应权重的单独对象。

这次怎么了……

可以预见的是，齿轮上有个扳手。与对象权重成比例的选择概率可能是一把双刃剑。这种选择方法很好，因为我们的负载均衡器将向请求较少的节点发送更多的流量，更主动地发送和更主动地回退。但是，如果负载平衡池中的所有节点都被划红线，并且我们将一个新节点插入池中（就像你在放大规模中看到的那样），那么这可能是问题的根源。这不是一些人所熟悉的典型的thundering herd问题，但它肯定属于同一类别。

如果我们有9个权重在[0,9]范围内的节点和一个权重在~1000的单个节点，就可以观察到这种行为：

加权比例选择不同时间点的选择数直方图。

你会注意到，与其他主持人相比，一个高权重的主机是压倒性的首选。如果你斜视看看，你甚至可以看到其他9个主机！有些人可能认为这不重要，因为它会在第10个节点上产生一个即时队列，并且权重会相应地进行调整——他们是正确的。但是，你应该记住，这些决策是在许多不同的负载平衡器之间做出的，因此节点将接收来自每个人的大量流量。

我们需要一种有偏置的选择算法，它能够适应这种羊群行为，同时优先考虑权重更高的主机。Envoy很方便地实现了最小请求负载均衡器中的一个。

两种选择的力量P2C

假设我们只是随机选择两个节点，然后选择权重更高的节点。这种令人惊讶的、简单的、优雅的有偏选择方法通常被称为“两个选择的力量（P2C）”，由Michael Mitzenmacher在2001年的论文中创造。然而，与许多引用这种选择方法的负载平衡文档相反，我们应该赞扬Azar et. al.在1999年发表这方面的开创性工作！

让我们看一下前面的两个模拟，但现在使用的是P2C选择。你会注意到我们仍然倾向于更高权重的节点：

P2C选择时不同时间点的选择数直方图。X轴上的每个对象权重表示一个具有相应权重的单独对象。

更重要的是，P2C并不表现出利用权重比例选择观察到的羊群行为！你不必眯着眼睛就能看到池中的其他对象：

P2C选择时不同时间点的选择数直方图。

对于Envoy的最小请求负载均衡器的应用，这正是我们想要的。我们只是想向活跃请求较少的节点发送更多的请求，并依赖于这些节点增加的RPS来创建与集群中的其他节点一致的队列。此外，P2C的时间复杂度是恒定的，而不是权重比例选择的时间复杂度线性（或对数，取决于你的实现的美妙程度）。

Envoy对P2C的实现允许进行可配置数量的选择，因此从理论上讲，我们将能够让负载平衡器对节点进行全面扫描，并每次选择请求量最少的节点。虽然在一些应用程序中这可能会很有用，但是Azar et. al.的论文的一个关键观点是，执行两个以上的选择几乎不会带来额外的好处。随着我们执行的每一个额外选择，我们也会逐渐接近羊群行为，因此Envoy的最小请求负载均衡器的默认配置执行两个选择。

高延迟节点、正常节点和快速节点的活跃请求数。

很大的区别！活跃请求在具有不同延迟特性的不同节点上的分布要均匀得多。当轮询调度向所有节点发送相同数量的请求时，你将看到最小请求负载均衡器向不同的节点组发送不同数量的请求。这完全是基于每个节点上的活跃请求数量，并试图保持它们都在同一范围内：

每个节点接收的请求数。

…一个负载均衡器来管理所有这些？

如果你的目标是在负载平衡请求时让集群中的所有节点都有一致的延迟，那么使用Envoy的最小请求负载平衡器是非常安全的。这并不是说它总是一个好主意——这里没有灵丹妙药。存在最小请求负载平衡无效的情况。在本文中，我提供了一个简化的客户机/服务器模拟环境，其中只增加了最少的特使配置和简单的服务器行为。由于这些额外的复杂性而产生的问题从来没有机会像随机和循环负载平衡的排队问题那样显示出来。

有哪些问题？！

如果某些应用程序更关心请求的平均分配而不是可预测的延迟，又会怎样呢？在进行加权负载平衡时，有关请求粘性或特定行为的问题呢？最小请求负载平衡并不总是适合这些情况（特别是考虑到与重试策略、断路、紧急路由、负载平衡器优先级等更复杂的交互时）。我们还应该指出，如果有非常、非常多的客户端缓慢地将请求发送给少量的upstream，那么upstream上的负载信息就不足以正确地选择它们——我们将退化为随机负载平衡！

我承认我举了一个病态的例子，但有这些特征的环境不会让人太惊讶。我们甚至可以想象这样一种场景：一个坏节点失败请求的速度比其他节点服务请求的速度更快，因此最小的请求负载平衡器将有利于这个坏节点，并破坏你的成功率（实际上，异常值检测将阻止这个节点）。

总结

希望本文对你有所帮助，并对使用Envoy的一些可配置负载平衡器的基本行为和动机提供了一些见解。这里还没有讨论其他负载平衡器，所以我建议查看一下文档，看看有什么可用的。我也鼓励你加入Envoy Slack频道、谷歌群组和Github来了解更多关于这个伟大项目的信息。这个社区充满了非常聪明、非常友好的人！