负载均衡系统的惊人经济学

# 负载均衡系统出人意料的经济学 来源：https://brooker.co.za/blog/2020/08/06/erlang.html M/M/c 模型的表现可能与你预期的不同。 我有一个系统，包含 `c` 台服务器，每台服务器同时只能处理一个请求，且内部没有排队。这些服务器位于一个负载均衡器之后，负载均衡器拥有一个无限队列。平均而言，无限数量的客户端每秒向负载均衡器发送 `c * 0.8` 个请求。换句话说，我们随着 `c` 线性增加负载，以保持每台服务器的负载恒定。请求到达服务器后，平均处理时间为 1 秒。那么，客户端观察到的平均请求时间如何随 `c` 变化？ 选项 A：平均延迟快速下降，随着 `c` 增加，渐近趋近于 1 秒（也就是说，在队列中花费的时间趋近于零）。选项 B：恒定不变。选项 C：线性改善。选项 D：延迟线性恶化。凭直觉，你认为延迟会遵循哪条曲线？ 我在 Twitter 上问了同样的问题，得到了一个有趣的混合结果：  分解一下这个问题有助于找出正确答案。首先，命名。在排队论的术语中，这被称为 **M/M/c**（https://en.wikipedia.org/wiki/M/M/c_queue）排队系统：泊松到达过程、指数分布的服务时间、以及 `c` 台后端服务器。在话务工程中，这是 **Erlang**（https://en.wikipedia.org/wiki/Agner_Krarup_Erlang）的延迟系统（或者，因为术语有趣，也叫 M/M/n）。我们可以使用排队论的一个经典结果来分析这个系统：Erlang C 公式 *E₂ₙ(A)*，它根据服务器数量（`n` 即 `c`）和提供的话务量 `A`，计算新到达的客户请求被排队（而非立即处理）的概率。详情请参见《话务工程手册》第 194 页（https://www.itu.int/dms_pub/itu-d/opb/stg/D-STG-SG02.16.1-2001-PDF-E.pdf）。下图展示了曲线的基本形状（使用我们的相同参数）：  沿着蓝色线条上升到饱和度的一半（即 2.5 rps 的负载），可以看到概率约为 13%。现在查看紫色线条在其饱和度的一半处（5 rps），概率仅为 3.6%。因此，在半负载下，5 台服务器的系统处理了 87% 的流量而无需排队；而当负载翻倍、服务器数量也翻倍时，我们处理了 96.4% 的流量而无需排队。这意味着只有 3.6% 的流量会经历额外的延迟。 事实证明，这种改善确实渐近趋近于 1。因此，Twitter 投票的正确选项是 A。 使用平均值来衡量延迟是有争议的（尽管 **或许不应该如此**（http://brooker.co.za/blog/2017/12/28/mean.html））。为了避免这种争议，我们需要知道百分位数是否以相同的速率改善。用封闭形式来计算有些复杂，但这个系统非常简单，因此我们可以使用蒙特卡洛模拟来绘制结果。结果如下：  这完全是好消息。中位数（p50）很好地跟随平均值曲线，而高百分位数（p99 和 p99.9）呈现出类似的形状。没有隐藏的问题。 这对云服务和经济学也是好消息。更大的 `c` 可以在相同的利用率下获得更好的延迟，或者在相同的延迟下获得更高的利用率，同时每台服务器的吞吐量保持不变。这不仅仅对大型服务有利，因为大部分好处在相对较小的 `c` 时就已经显现。与规模和分布式系统相关的问题很少会随着 `c` 增加而变得更容易。而这正是其中之一。 有一些合理的后续问题。我们的任意选择 0.8 是否稳健？是的，结果确实是稳健的¹（https://brooker.co.za/blog/2020/08/06/erlang.html#foot1）。M/M/c 对泊松到达和指数服务时间的假设对于典型服务是否合理？我认为它们是合理的，尽管并不完全准确。指数服务时间尤其不准确：实际服务往往更像对数正态分布。但这可能无关紧要。另文再谈。 *更新：* Dan Ports 对我的推文做出了回应，发布了一条有趣的 Twitter 线程（https://twitter.com/danrkports/status/1291517540280070144），指出来自 SoCC’14 的《尾巴的故事：硬件、操作系统和应用层面的尾延迟来源》（https://drkp.net/papers/latency-socc14.pdf），这篇文章考察了现实中的这一效应。 **脚注** 1. 有一定限度。一旦平均到达率超过系统完成请求的能力，队列将无限增长，延迟趋于无穷。在我们的例子中，这种情况发生在请求负载超过 `c` 时。更一般地说，要使系统稳定，`λ / cμ` 必须小于 1，其中 `λ` 是平均到达率，`μ` 是服务器处理一个请求的平均时间。