前置讲 P4 · 排队论与性能评估：延迟、吞吐、尾延迟与实验方法 · Queueing & Performance Evaluation

对应 Maps to：原课没有对应的一次课。第 1 讲看到了”利用率接近 100% 时延迟爆炸""利用率只有 36% 时 P99 也有 9 秒”；第 7、11、17 讲反复用到 Little 定律、M/D/1、开环 / 闭环、goodput。这篇前置讲把这些工具系统地讲一遍：读论文的评测部分、自己做实验，都需要它们。 依据说明：排队论部分依据 M. Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action（Cambridge, 2013），以及几个经典结果：J. Little（1961，L = λW）、Pollaczek–Khinchine 公式、J. Kingman（1961，重负载近似）、Erlang 公式。实验方法依据 B. Schroeder, A. Wierman, M. Harchol-Balter, Open Versus Closed: A Cautionary Tale（NSDI 2006）、G. Tene 的报告 How NOT to Measure Latency（coordinated omission）、J. Dean, L. A. Barroso, The Tail at Scale（CACM 2013）。LLM 负载依据 Splitwise（ISCA 2024）公开的 Azure LLM 推理 trace 的描述、BurstGPT（Wang 等，2024）和 DistServe（OSDI 2024）的 goodput 定义。 配套代码 Code：code/prereq4/（numpy；5 个脚本 + 1 个共享模块；全部几秒内跑完） 预计阅读时间：3 小时（含运行代码）

0. 本讲导航 · How to read this lecture

0.1 学习目标 Learning goals

学完这一篇，你应该能够：

1. 用 Little 定律在”到达率、停留时间、系统里的请求数”三者之间互相换算，并用它做容量规划。
2. 写出 M/M/1 的平均延迟和 P99，解释”曲棍球棒”曲线：为什么在线服务不追求 100% 利用率。
3. 用 Pollaczek–Khinchine 公式解释：为什么服务时间的方差决定排队，为什么 LLM 输出长度的长尾让低利用率下也有长尾延迟。
4. 说出到达的突发性、多服务器共享队列、扇出对延迟的影响。
5. 读懂一条延迟—吞吐曲线，区分吞吐、SLO 达成率和 goodput 的两种定义。
6. 设计一个不自欺欺人的性能实验：开环负载、避免 coordinated omission、预热和足够长的实验、足够多的样本、正确的置信区间、公共随机数。

0.2 先修与本讲范围 Prerequisites & scope

0.3 本讲地图 Map

§1  Little 定律：L = λW                                                       ← 代码 01
§2  M/M/1：利用率、平均与尾延迟、曲棍球棒、容量规划                             ← 代码 01
§3  M/G/1 与 P–K 公式：方差决定排队；LLM 的头部阻塞                             ← 代码 02
§4  突发到达、多服务器与扇出                                                    ← 代码 02
§5  批服务队列与延迟—吞吐曲线                                                  ← 代码 03
§6  SLO、达成率与 goodput                                                      ← 代码 03
§7  负载生成与实验方法：开环与闭环、coordinated omission、trace、预热与实验时长   ← 代码 04
§8  实验统计：分位数要多少样本、置信区间、相关的样本、公共随机数                  ← 代码 05
§9  与推理系统的联系（只想快速浏览的读者读这一节）
§10–14  小结、常见误区、练习、延伸阅读、下一篇

0.4 记号 Notation

排队模型用 Kendall 记号 A/S/c 描述：到达过程 / 服务时间分布 / 服务器个数。M 表示”马尔可夫”（泊松到达或指数服务），D 表示确定，G 表示一般分布。M/M/1 就是”泊松到达、指数服务、一个服务器”。

0.5 关于数字 · About the numbers

本篇的数字都来自模拟：用 Python 实现的小队列，和公式互相核对。时间单位多是”平均服务时间”，结论是规律和量级，不是某个推理引擎的实测。第 17 讲在完整的迷你推理引擎上重新验证了其中关于评测方法的几条。

1. Little 定律 · Little’s law

1.1 定律

一个处于稳态的系统里，平均有多少个”东西”，等于它们进入的速率乘以每个平均待多久：

这是排队论里最有用的一条结果，因为它几乎没有前提：不管到达是不是泊松、服务时间是什么分布、有几个服务器、按什么顺序服务，只要系统处于稳态（进来的和出去的一样多），它就成立。

直觉：画出”系统里有几个请求”随时间变化的曲线 $N(t)$。曲线下的面积可以按时间加（$L$ × 总时长），也可以按请求加（每个请求贡献它待在系统里的那段时间，$W$ × 请求数）；两种加法算的是同一块面积，除以总时长就得到 $L = \lambda W$。

代码 01 演示 1 用两种独立的方法核对：直接对”系统里有几个请求”做时间平均，以及到达率 × 平均逗留时间。五种完全不同的系统——M/M/1、长尾服务时间的 M/G/1、四个服务器共享一个队列、批服务、闭环——两边都相等（例如 M/M/1：4.074 vs 4.074；批服务：3.974 vs 3.974）。

1.2 三种用法

• 容量规划（代码 01 演示 4）：一个聊天服务每秒进来 20 个请求，每个请求平均在系统里待 8 秒，系统里平均同时有 160 个请求；以 Llama-3-8B、上下文 2K 计，光 KV 就要约 43 GB。推理模型的回答更长，每秒 20 个请求、每个待 60 秒，就要同时容纳 1,200 个请求、约 322 GB 的 KV。长输出的请求贵，不只因为算得多，还因为它们同时占着显存。
• 反推吞吐上限：显存最多容纳 $L_{\max}$ 个请求时，吞吐 $\lambda \le L_{\max} / W$。
• 在途的工作量：前置讲 P1 用它算”要多少条在途的访存才能用满 HBM 带宽”（带宽 × 延迟），第 9 讲的 Strata 用它算”要多少个在途的 I/O 才能用满 PCIe”。

2. M/M/1：利用率与曲棍球棒 · The M/M/1 queue

2.1 公式

泊松到达（到达率 $\lambda$）、指数服务时间（服务率 $\mu$）、一个服务器、先到先服务：

M/M/1 的逗留时间恰好服从速率为 $\mu - \lambda$ 的指数分布，所以 P99 = $\ln(100) / (\mu - \lambda) \approx 4.6\, T$。

代码 01 演示 2（平均服务时间 1）：

公式里的 $1 - \rho$ 是”空闲的比例”：利用率从 0.5 到 0.9，空闲比例从一半降到一成，延迟涨到 5 倍。注意最后一行：$\rho = 0.95$ 时模拟了 40 万个请求，平均值只差 1%，P99 却差了 16%。高负载下相邻请求的等待高度相关，“有效样本”很少，尾部尤其难估准（§8）。

2.2 曲棍球棒

代码 01 演示 3 把 $1/(1-\rho)$ 列出来：利用率 50% 时再加 1 个百分点，延迟只涨 2%；95% 时涨 25%；98% 时直接翻倍；到 100%，队列无限增长。这条曲线叫”曲棍球棒”（hockey stick）：前面很平，过了拐点陡然上升。

这就是为什么在线服务从不追求 100% 的利用率：延迟的目标（SLO）决定了能跑到多高的利用率，而成本由利用率决定。第 1 讲 §4.5 的排队实验看到的正是这条曲线；整门课里”延迟 vs 成本”的权衡，在排队论里就是它。

3. M/G/1：方差决定排队 · Variance drives queueing

3.1 Pollaczek–Khinchine 公式

把指数服务换成任意分布（M/G/1），平均排队时间是：

推导的直觉：一个新到达的请求要等两部分——正在服务的那个请求剩下的服务时间，加上排在前面的所有请求的服务时间。第二部分平均是 $L_q \cdot E[S]$；第一部分是关键：随机到达的人更可能”撞上”一个长的服务（长的服务占的时间多），所以剩余时间的平均是 $E[S^2] / (2 E[S])$，而不是 $E[S]/2$。二阶矩 $E[S^2]$ 就这样进入了公式。

代码 02 演示 1（$\rho = 0.7$，平均服务时间都是 1）：

负载一样、平均服务时间一样，SCV 从 0 到 25，平均排队时间涨了二十多倍。直觉：偶尔来一个特别大的作业，它占着服务器的时候，所有后来的作业都要等它——这叫头部阻塞（head-of-line blocking）。确定性服务时间（SCV = 0）的排队只有指数服务的一半：第 7 讲用 M/D/1 分析 prefill 的排队，就是这个特例。

3.2 LLM 服务的头部阻塞

把一个 LLM 请求看成一个作业，它的”服务时间”和输出长度成正比，而输出长度是长尾的。代码 02 演示 2：输出长度取对数正态（中位数 120 个 token，长尾到上千），每个 token 6 ms，逐个处理，利用率只有 36%：

利用率只有三分之一，排队时间的 P99 却有二十多秒，而排队时间正是 TTFT 的一部分——这就是第 1 讲在利用率 36% 时看到 9 秒 P99 TTFT 的原因（数字不同是因为设定不同，机制相同）。

P–K 公式也指出了出路：问题不在利用率，而在”短作业排在长作业后面”。第 2 讲的迭代级调度和连续批处理让新请求不用等前面的请求全部生成完，从根本上消除了这种头部阻塞；前置讲 P3 §2 的 SRPT、MLFQ 则是从调度顺序上解决同一个问题。

4. 突发到达、多服务器与扇出 · Bursts, pooling, and fan-out

4.1 到达的突发性

到达也可以不是泊松的。Kingman 近似（G/G/1，重负载时很准）把到达间隔的变异也放进公式：

泊松到达时 $c_a^2 = 1$，它就退化成 P–K。代码 02 演示 3（Gamma 分布的到达间隔，指数服务，$\rho = 0.7$）：

请求来得越”一阵一阵”，排队越久：一阵请求同时涌进来，服务器只能一个一个处理；之后又有一段空闲，而空闲的能力存不起来。Kingman 近似在 $\rho = 0.7$ 这样的中等负载下只给出量级和趋势（突发时低估、均匀时高估）。

真实的 LLM 流量是突发的。BurstGPT 收集了 Azure OpenAI GPT 服务（一个区域）213 天、约一千万条请求的 trace，用 Gamma 分布描述请求的突发性，每 20 分钟重新拟合一次：参数在工作时间里变化剧烈；对话类服务有工作日、工作时间的周期，API 调用则没有周期、更不规则（作者猜测其中有自动化的调用）。相比之下，此前常用的 Azure Functions 的 trace 均匀得多。如果真实流量比泊松更突发，只用泊松到达做评测就会低估真实部署时的排队。

4.2 一个共享队列 vs 各排各的

代码 02 演示 4：8 台服务器，总负载 $\rho = 0.8$：

（M/M/8 的公式：排队概率由 Erlang C 给出，45.8%；平均排队 $C / (c\mu - \lambda) = 0.286$。）同样的服务器、同样的负载，共享一个队列的平均排队只有各排各的约 1/14：共享队列里，只要任何一台空闲就不会有人等；各排各的时，经常一台排长队、另一台闲着。这叫合并的收益（pooling）。

推理集群的多个副本前面有一个路由器，它就在”各排各的”条件下尽量逼近”一个共享队列”：看各副本的负载派发、随机选两个挑轻的（二选一），同时还要照顾前缀缓存的命中——这是第 11 讲的主题。

4.3 扇出放大尾延迟

一个请求如果要等 $k$ 个并行的子任务全部完成，它的延迟是 $k$ 个子任务里最慢的那个。每个子任务以 1% 的概率超过某个阈值，整个请求超过它的概率就是 $1 - 0.99^k$。代码 02 演示 5（子任务延迟对数正态，中位数 10 ms、P99 约 100 ms）：$k = 10$ 时 9.6% 的请求超过 100 ms，$k = 100$ 时 63%，整个请求的中位延迟（114 ms）已经超过单个子任务的 P99。这是 Dean 和 Barroso《The Tail at Scale》的核心观察：规模越大，“罕见的慢”越常见。

推理系统里的扇出无处不在：张量并行、专家并行的每一步要等最慢的那块卡（第 6、8 讲的负载不均和冗余专家）；agent 工作流要等所有并行的工具调用（第 13 讲）。所以大规模系统要专门对付尾延迟，评测里也必须报告 P99 而不只是平均值。

5. 批服务队列与延迟—吞吐曲线 · Batch service and latency–throughput curves

5.1 批越大越划算

GPU 服务的特点是一次处理一批：一批的时间 = 固定开销 + 每个请求的边际开销。固定开销（读权重、启动内核）被一批里的所有请求分摊。代码 03 演示 1 用”一批 5 ms + 每个请求 0.5 ms”（假设值；像 Clipper 服务的图像分类、嵌入模型，或者只做 prefill 的请求）：

批从 1 到 32，最大吞吐提高 8 倍多；再往上收益递减，上限是 1 / 0.5 ms = 2,000 个/秒。第 1 讲”decode 的批越大、每个 token 越便宜，但不会无限便宜”是同一个形状。

5.2 延迟—吞吐曲线

代码 03 演示 2 用动态凑批（服务器一空闲，就把等着的请求都拿走，最多 B 个），扫描到达率：

读一条延迟—吞吐曲线，要找三样东西：

1. 低负载时的延迟：这是系统的”最好情况”，由服务时间决定。
2. 拐点：延迟开始急剧上升的地方。拐点之前加负载几乎免费，之后加一点延迟就翻倍。
3. 最大吞吐：曲线竖起来的地方。比较两个系统时，要在同一个延迟目标下比吞吐（或者在同一个吞吐下比延迟），而不是只比最大吞吐——最大吞吐附近的延迟是不可用的。

动态凑批会自动适应负载：负载低时服务器一空闲就只拿到一两个请求（到达率 100 时平均批大小 1.1），延迟和不凑批一样；负载高时排队的请求多，批自然变大（1,450 时 26.4），吞吐跟着变大。允许的批越大，曲线的拐点越往右。这正是第 2 讲连续批处理”让批随负载伸缩”的思想。

5.3 为了凑批而等，值不值

代码 03 演示 3：超时凑批（等批满，或者最早的请求等满 20 ms）在低负载时让每个请求白白多等十几毫秒（到达率 100 时平均 20.2 ms，动态凑批 7.0 ms），却换不来任何吞吐——服务器反正闲着；负载高时两种做法差不多。所以”故意等”只在”批大带来的效率提升”超过”等待的代价”时才值得。Clipper（第 2 讲）用 AIMD 动态调整批大小和等待时间，就是在找这个平衡点。

6. SLO、达成率与 goodput · SLOs, attainment, and goodput

6.1 SLO 与达成率

SLO（service-level objective）是对延迟的承诺，例如”TTFT ≤ 2 秒、TPOT ≤ 50 毫秒”。SLO 达成率是满足 SLO 的请求所占的比例。LLM 服务通常有多个 SLO：TTFT（用户多快看到第一个字）、TPOT（之后每个字多快）、有时还有端到端延迟；一个请求要同时满足所有 SLO 才算”达标”。第 17 讲还指出，平均 TPOT 会掩盖生成中途的长时间卡顿，要单独看”最长的一次停顿”。

6.2 吞吐 ≠ goodput

代码 03 演示 4（B = 32，SLO：延迟 ≤ 50 ms，每个到达率跑 60 秒）：

过载时吞吐和 goodput 分道扬镳：到达率 2,000 时，服务器照样每秒完成 1,524 个请求，吞吐看起来很好，可几乎所有人都超时了。只报吞吐的评测会掩盖这一点。

goodput 有两种常见的定义，读论文时先看清楚用的是哪一种：

• 定义 (a)：能承诺的最大负载——满足”至少 90%（或 99%）的请求达到 SLO”的最大到达率。这里约 1,450 个/秒，比最大吞吐低一截，差的那部分就是为延迟留的余量。第 7 讲的 DistServe、第 17 讲的评测都用这个定义。
• 定义 (b)：达标的吞吐——每秒完成的、达到 SLO 的请求数（或 token 数），是随负载变化的一条曲线：先上升、在拐点附近达到最大、过载后掉下去。

定义 (a) 对实验方法非常敏感：实验多长、有没有预热、只看平均还是也看实验末尾的请求，都会改变结论。第 17 讲 §5.2 在完整的推理引擎上演示过：固定请求个数的实验会把 goodput 高估六到九成。

7. 负载生成与实验方法 · Load generation and methodology

7.1 开环与闭环

压测工具产生负载有两种模型：

• 开环（open loop）：请求按自己的节奏到达（例如泊松过程），不管系统有没有处理完前面的。面向公众的在线服务更接近开环：用户不会因为你慢了就少来。
• 闭环（closed loop）：固定 N 个”用户”，每个用户发一个请求、等它完成、思考一会儿（$Z$）、再发下一个。很多压测工具（固定并发数）其实是闭环。

代码 04 演示 1（同一个服务器，平均服务时间 1）：开环时到达率逼近 1，响应时间按 $1/(1-\rho)$ 爆炸（0.99 时 69.9）；闭环时用户越多，吞吐越接近 1 但永远不会超过，响应时间随用户数线性增长（N = 100 时 91.2），不会爆炸。闭环里每一行都满足交互式响应时间定律：

它是 Little 定律套在”用户 + 系统”整个圈上的结果。闭环压测里，“每秒多少请求”不是你设定的，而是系统自己的速度决定的；它永远看不到过载——系统一慢，用户就发得慢。

代码 04 演示 2：即使测得的吞吐一样，闭环测出的延迟也更低（吞吐 0.92 时，闭环 4.1，同样到达率的开环 12.3）：闭环里排队越长、新来的越少，是一种负反馈。Schroeder、Wierman、Harchol-Balter 2006 年的论文专门讨论了这一点：同一个系统、同一个调度策略，在开环和闭环下的表现可以差很多，压测模型要和真实用户的行为匹配。

7.2 coordinated omission

代码 04 演示 3：服务器平时 1 ms 处理一个请求，但每 10 秒卡顿 1 秒（例如一次垃圾回收、一次权重热更新）；真实用户每秒发 100 个请求。

单连接的闭环压测工具在卡顿期间只发出了一个请求（它在等这个请求返回），1 秒的卡顿只留下一个慢样本；其余样本都是正常的 1 ms 左右，于是 P99 只有 5 ms。压测工具和被测系统”协调”好了，一起把最糟糕的那段时间漏掉——Gil Tene 把这个现象叫做 coordinated omission。修正的办法是按”本来计划发出的时刻”计延迟，或者干脆用开环的负载生成器。

7.3 负载从哪里来

评测 LLM 推理系统的负载，要同时描述到达过程（什么时候来）和请求本身（提示多长、输出多长、有没有共享前缀）：

• 真实 trace：Splitwise（ISCA 2024）公开了 Azure 的两条 LLM 推理 trace（2023 年 11 月收集），带时间戳和输入、输出 token 数：代码补全服务的提示长度中位数约 1,500、输出中位数只有 13；对话服务提示长度中位数约 1,020、输出中位数 129（近似双峰）。两种服务的 prefill / decode 比例完全不同，适合的部署也不同（第 7 讲）。BurstGPT 提供了 Azure OpenAI 服务的到达模式。
• 对话数据集：ShareGPT（用户分享的 ChatGPT 对话）、LMSYS-Chat-1M（Chatbot Arena 收集的一百万段对话）常被用来采样提示和输出长度；它们没有真实的到达时间，通常配合泊松或 Gamma 到达。
• 合成分布：输出长度用对数正态或者从 trace 里抽样，到达用泊松（基线）和更突发的过程（压力测试）。

两个常见的错误：只用一种长度分布（例如所有请求都是 1,000 / 200）；从一个小数据集里反复抽同一批提示，让前缀缓存”作弊”（第 17 讲 §5.5）。

7.4 预热与实验时长

代码 04 演示 4（M/M/1，$\rho = 0.95$，从空系统开始，理论平均排队时间 19）：

只跑 1,000 个请求，平均排队时间平均只有 14.9，而且每次差别很大：系统从空的开始，队列还没来得及”长”到稳态的样子，实验就结束了——短实验会低估延迟（因而高估能承受的负载）。去掉开头的预热段有帮助，但高负载下真正需要的是足够长的实验。第 17 讲在推理引擎上的做法是：固定时长、只统计稳态窗口里到达的请求、并检查窗口末尾的请求也达标；把实验加长一倍，结论不变才算可信。

8. 实验统计 · Statistics for experiments

8.1 P99 要多少样本

代码 05 演示 1（对数正态，变异系数 2，每种样本数重复 200 次，看估计值的相对标准差）：

P99 的估计由 P99 以上的那几个样本决定。经验法则：P99 以上要有几十到上百个样本——P99 至少要上万个请求，P99.9 至少十万个。只跑几百个请求就报 P99 的实验，数字基本是噪声。

8.2 置信区间

报告一个延迟数字时，最好同时报告它的置信区间：如果把实验重做很多次，真实值有 95% 的把握落在哪个范围里。

• bootstrap：从样本里有放回地重抽很多次，每次算一遍统计量，取这些统计量的 2.5% 和 97.5% 分位数。代码 05 演示 2：样本独立时它大致可靠（100 次实验里 93 次包含真实的 P99），区间宽度是真实值的 40%——2,000 个样本的 P99 本身就有这么大的不确定性。
• 但排队系统里的样本不独立。代码 05 演示 3（M/M/1，$\rho = 0.9$）：相邻两个请求的等待时间相关系数高达 0.99——一段拥堵期里大家都在等，一段空闲期里大家都不等。把 3 万多个等待时间当成独立样本做 bootstrap，区间窄了一个数量级，60 次实验里只有 5 次包含真实值；批均值法（把序列切成 10–20 段很长的段，用段的均值算区间）回升到 50–52 次，仍略低于名义的 95%。最稳妥的做法是用不同的种子做几次独立重复的实验（每次都足够长），用它们之间的差别算区间。

8.3 比较两个系统：公共随机数

代码 05 演示 4：系统 B 的服务时间比 A 快 1%（$\rho = 0.8$ 时平均延迟理论上低 4.8%）。每次各跑 5,000 个请求，重复 40 次：

用独立的种子各跑一次，和扔硬币差不多：差值的随机波动比差别本身大好几倍。公共随机数（common random numbers）让两个系统面对同一串到达、同一串服务时间的随机数，波动在相减时被抵消，每一次都比出了正确的方向。比较两个调度策略、两个引擎时，用同一个 trace 驱动它们，再在几个不同的 trace（种子）上检查结论是否一致（第 17 讲 §5.6）。

8.4 一份评测清单

1. 负载：开环、到达过程（泊松 + 更突发的）、长度分布来自 trace 或从 trace 抽样、共享前缀的结构写清楚。
2. 实验：固定时长、去掉预热、足够长（加长一倍结论不变）；过载时如实报告”不稳定”，而不是报告一个有限实验里的数字。
3. 指标：TTFT、TPOT 的平均和 P99，最长停顿，SLO 达成率，goodput（说清是哪种定义），吞吐，成本。
4. 统计：P99 至少上万个样本；多个种子；同一 trace 下比较；报告区间或范围。
5. 曲线而不是点：扫描一串到达率，画延迟—负载曲线和达成率曲线。

9. 与推理系统的联系 · Connections to inference systems

有系统背景的读者可以只读这一节。

10. 小结 · Summary

1. Little 定律 $L = \lambda W$ 几乎处处成立：用它在到达率、停留时间、系统里的请求数之间换算，做容量规划。
2. M/M/1：$T = E[S] / (1 - \rho)$，P99 ≈ 4.6 T。利用率越高，每多一个百分点越贵——SLO 决定能跑多满。
3. P–K 公式：排队时间正比于 $(1 + c_s^2)/2$。服务时间的方差决定排队；LLM 输出长度的长尾让低利用率下也有长尾 TTFT，连续批处理从根本上消除这种头部阻塞。
4. 突发到达让排队更长（Kingman）；共享一个队列远好于各排各的；扇出让罕见的慢变得常见。
5. 批服务：批越大越划算，动态凑批让批随负载伸缩；读延迟—吞吐曲线要看拐点，在同一个延迟目标下比较吞吐。
6. 吞吐 ≠ goodput：过载时吞吐不变、goodput 归零；goodput 有”能承诺的最大负载”和”达标的吞吐”两种定义。
7. 实验方法：用开环负载；避免 coordinated omission；预热并跑足够长；P99 要上万个样本；相关的样本不能当独立样本算区间；比较系统时用公共随机数和多个种子。

11. 常见误区 · Common pitfalls

• “利用率 50% 很浪费，应该跑到 95%“。95% 时平均延迟是 50% 时的 10 倍；能跑多满由延迟目标决定。
• “平均服务时间一样，排队就一样”。排队由服务时间的方差决定（P–K）；长尾的服务时间在低利用率下也会造成长尾延迟。
• “压测时并发数开到 256，测出的吞吐就是系统的能力”。那是闭环压测：它永远看不到过载，测出的延迟也偏低。
• “压测工具报告 P99 只有 5 ms”。先确认它是不是一个”等上一个请求返回才发下一个”的工具（coordinated omission）。
• “跑 500 个请求，看平均和 P99”。短实验低估高负载下的延迟，500 个样本的 P99 误差在三成左右。
• “我有 3 万个延迟样本，bootstrap 的区间很窄，所以结论很可靠”。排队系统里的样本高度相关，区间会窄一个数量级；用独立重复实验或批均值。
• “B 比 A 快 3%，我各跑了一次”。差别小于随机波动时，独立的两次实验和扔硬币差不多；用同一个 trace（公共随机数）、多个种子。
• “吞吐提高了，所以服务更好了”。要看 SLO 达成率和 goodput：过载时吞吐最高，goodput 却是零。

12. 练习 · Exercises

练习 1（Little 定律）。一个推理服务的监控显示：平均同时在跑 120 个请求，吞吐每秒 15 个请求。每个请求平均在系统里待多久？如果平均输出 150 个 token、TPOT 40 ms，那么排队 + prefill 平均占多少时间？

$W = L / \lambda = 120 / 15 = 8$ 秒。decode 约 150 × 40 ms = 6 秒，所以排队和 prefill 平均约 2 秒。（这里假设”在跑”的请求包括排队的；如果监控只统计正在 decode 的，就要分开算。）

练习 2（SLO 决定利用率）。M/M/1，平均服务时间 0.2 秒（$\mu = 5$）。(a) 要求平均响应时间 ≤ 1 秒，最大到达率和利用率是多少？(b) 要求 P99 响应时间 ≤ 2 秒呢？

(a) $1/(5 - \lambda) \le 1$，$\lambda \le 4$，利用率 80%。(b) $\ln(100) / (5 - \lambda) \le 2$，$\lambda \le 5 - 2.30 = 2.70$，利用率只有 54%。尾延迟的 SLO 比平均值的 SLO 严格得多——同样的硬件，能承诺的负载少了三分之一。

练习 3（P–K）。$\rho = 0.9$，平均服务时间为 1。服务时间确定和服务时间指数分布时，平均排队时间各是多少？服务时间的变异系数为 3 呢？

$W_q = 9 \times (1 + c_s^2)/2$：确定时 4.5，指数时 9，变异系数 3（SCV = 9）时 45。

练习 4（合并的收益）。两台服务器、各自的利用率 0.9（M/M/1，平均服务时间 1），各排各的平均排队时间是多少？如果合并成一个共享队列（M/M/2）呢？用 queue_lab.mmc_wait 验证。

各排各的：$W_q = 0.9 / 0.1 = 9$。合并后：mmc_wait(1.8, 1.0, 2) ≈ 4.26（排队概率 Erlang C ≈ 85%）。只合并两台就让平均排队时间减半。

练习 5（闭环）。一个闭环压测有 50 个用户，每人思考 5 秒，测得吞吐每秒 8 个请求。平均响应时间是多少？把用户加到 100 个，吞吐只涨到每秒 8.3 个，说明了什么？

$R = N/X - Z = 50/8 - 5 = 1.25$ 秒。100 个用户时 $R = 100/8.3 - 5 \approx 7$ 秒：系统已经饱和（最大吞吐约每秒 8 个多），多出来的用户只是在排队。开环压测在同样的情况下会看到队列无限增长。

练习 6（coordinated omission 的规模）。一个压测工具开了 10 个连接，每个连接”上一个返回才发下一个”。服务器每分钟卡顿 2 秒，正常情况下每秒处理 200 个请求。一次卡顿期间，真实用户（开环、每秒 200 个）有多少个请求受影响？压测工具记录了几个慢样本？

真实用户：2 秒 × 200 = 400 个请求被卡住（等待从几毫秒到 2 秒不等）。压测工具：10 个连接各有一个请求被卡住，只记录 10 个慢样本——少了 40 倍。

练习 7（扇出）。每个子任务以 0.1% 的概率超过阈值。扇出到多少个子任务时，一半的请求会超过这个阈值？

$1 - 0.999^k \ge 0.5$，$k \ge \ln 0.5 / \ln 0.999 \approx 693$。

练习 8（样本量）。要让 P99.9 以上至少有 100 个样本，至少要多少个请求？如果每秒 50 个请求，实验至少要跑多久？

100 / 0.001 = 10 万个请求；每秒 50 个时要约 2,000 秒（半个多小时）。这还没算预热和样本之间的相关性——所以 P99.9 的承诺需要很长的实验，或者在线的长期监控。

13. 延伸阅读 · Further reading

• M. Harchol-Balter. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013。前几章（Little 定律、M/M/1、M/G/1、闭环系统）就够本课程用。
• J. D. C. Little. A Proof for the Queuing Formula: L = λW. Operations Research, 1961。
• B. Schroeder, A. Wierman, M. Harchol-Balter. Open Versus Closed: A Cautionary Tale. NSDI 2006。
• G. Tene. How NOT to Measure Latency（报告与幻灯片）。coordinated omission 的来源。
• J. Dean, L. A. Barroso. The Tail at Scale. Communications of the ACM, 2013。
• P. Patel et al. Splitwise: Efficient Generative LLM Inference Using Phase Splitting. ISCA 2024（Azure LLM 推理 trace）；Y. Wang et al. BurstGPT: A Real-World Workload Dataset to Optimize LLM Serving Systems. 2024。
• Y. Zhong et al. DistServe. OSDI 2024（goodput 的定义，第 7 讲）。

14. 下一篇 · Next

前置讲 P5：分布式与通信基础。§4 说”张量并行的每一步要等最慢的那块卡”——那多块卡之间到底要传多少数据、走什么链路、要多久？P5 讲互连（PCIe、NVLink、InfiniBand、RDMA）、集合通信（all-reduce、all-gather、all-to-all……）与它们的算法和代价模型、几种并行方式各自要通信什么，以及怎样让通信和计算重叠。