马克·布鲁克揭秘负载均衡系统经济学：M/M/c 模型延迟随服务器数量渐近改善

关于我我叫马克·布鲁克Marc Brooker喜欢打造实用且酷炫的东西热衷于构建大型项目。此外我还涉足机械加工、焊接、烹饪和滑雪等领域。我是西雅图亚马逊云服务AWS的一名工程师主要从事自主人工智能agentic AI相关工作尤其关注自主人工智能的安全性和策略。在此之前我参与过 EC2、EBS、数据库、无服务器计算以及无服务器数据库等项目。本博客所表达的观点仅代表我个人。链接我的出版物和视频Mastodon 账号 marcbrookerTwitter 账号 MarcJBrooker这个博客是由人工智能撰写的吗负载均衡系统的惊人经济学M/M/c 模型的表现或许和你想的不一样。假设有个系统有 c 台服务器每台只能处理一个并发请求且无内部队列。这些服务器在一个有无限队列的负载均衡器后面。平均来说无限数量的客户端每秒向负载均衡器发 c * 0.8 个请求。也就是说我们随 c 增加线性提高请求负载让每台服务器负载恒定。请求到服务器后平均要一秒处理。那客户端观察到的平均请求时间会怎么随 c 变化呢选项 A随着 c 增加平均延迟快速降低渐近趋近于一秒即排队时间趋近于零。选项 B保持恒定。选项 C呈线性改善。选项 D延迟呈线性恶化。凭直觉你觉得延迟会是哪条曲线呢我在 Twitter 上问了粉丝同样的问题得到了有趣的不同结果深入分析这个问题能找出正确答案。首先了解相关术语。在排队论里这是个 M/M/c 排队系统即泊松到达过程、指数分布的客户端服务时间和 c 台后端服务器。在电信流量工程中它是 埃尔朗Erlang 延迟系统或者因术语多样也叫 M/M/n。我们能用排队论的经典结果——埃尔朗 C 公式 _E 2,n(A)_ 来分析这个系统该公式根据服务器数量n 即 c和提供的流量 A 计算传入客户请求进入队列而非立即处理的概率。具体细节可参考 《电信流量工程手册》 第 194 页。以下是该曲线的基本形状用相同参数沿着蓝色线到半饱和点提供的负载为 2.5 rps能看到概率约为 13%。再看紫色线的半饱和点5 rps概率仅为 3.6%。所以半负载时5 台服务器的系统能不排队处理 87% 的流量负载和服务器数量都翻倍时能不排队处理 96.4% 的流量意味着只有 3.6% 的请求会有额外延迟。事实证明这种改善确实渐近趋近于 1。Twitter 投票的正确答案是 A。用平均值衡量延迟有争议尽管 也许不应该如此。为避免争议我们得知道百分位数是否以相同速率改善。用封闭形式计算有点复杂但这个系统简单我们能用蒙特卡罗模拟绘制结果。结果如下这完全是个好消息。中位数p50和平均线吻合得好高百分位数99 分位和 99.9 分位也有类似形状没隐藏问题。这对云计算和服务经济也是好消息。随着 c 增大相同利用率下能有更好延迟或相同延迟下实现更高利用率且每台服务器吞吐量不变。这不仅对大型服务有利因为大部分好处在 c 相对较小时就有了。在和规模及分布式系统相关的问题中很少有随 c 增加变容易的这就是其中一个。有一些合理的后续问题。我们随意选的 0.8 这个值会影响结果稳定性吗答案是肯定的但有一定限度。一旦平均到达率超过系统处理请求的能力队列就会无限增长延迟也趋于无穷大。在我们例子中请求负载超过 c 时就会这样。更一般地说这个系统要稳定λ/cμ 必须小于 1其中 λ 是平均到达率μ 是服务器处理请求的平均时间。M/M/c 模型中泊松到达和指数服务时间的假设对典型服务合理吗我觉得虽不完全对但有一定合理性。指数服务时间尤其不准实际服务更接近对数正态分布但这可能不重要以后再详细讨论。更新丹·波茨Dan Ports在我的 Twitter 帖子下回复了一个精彩的 Twitter 线程指向了 SoCC’14 的 《尾部延迟的故事硬件、操作系统和应用层的尾部延迟来源》该文章探讨了现实中的这种效应。脚注1. 有一定限度。一旦平均到达率超过系统处理请求的能力队列就会无限增长延迟趋于无穷大。在我们例子中请求负载超过 c 时就会这样。更一般地说这个系统要稳定λ/cμ 必须小于 1其中 λ 是平均到达率μ 是服务器处理请求的平均时间。 返回博客索引相关文章2021 年 8 月 5 日 » 延迟悄然来袭2021 年 4 月 19 日 » 尾部延迟的影响可能比你想象的更大2026 年 6 月 19 日 » 认识爱丽丝。爱丽丝很没耐心。其他文章2015 年 5 月 24 日 » 碳酸钠与拉面化意大利面