S23：FIFO 离散事件 Queue Simulator

内容类型：预习教材（不代表已完成）
日期：2026-12-15
阶段：P2 · AI Systems Engineering 90
总路线：Day 113 / 360
周次 / 节奏：W4 · 周二最小实现
状态：教材已备；学习未完成
主题：arrival、service time、FIFO、discrete-event simulation

一句话定义

FIFO 离散事件模拟器用请求到达时间与服务时间推进虚拟时钟，显式计算开始、完成和等待，从最小模型观察排队如何放大延迟。

学习目标

1. 能实现单 worker、非抢占 FIFO 队列的确定性小模拟。
2. 能计算每个请求的 wait、response/sojourn time 与 worker utilization。
3. 能区分模拟时间与真实 wall-clock，不用 sleep 驱动实验。
4. 能明确该模型省略 batching、prefill/decode、cache 和多 worker 等现实因素。

核心知识

离散事件模拟不需要真实等待。输入是请求列表，每个请求有 id、arrival time、service time；按 arrival 排序，worker 的开始时间是到达与上一请求完成时间的最大值。FIFO 简单、可解释，但短请求可能被前面的长请求阻塞，形成 head-of-line blocking。

观察至少包括 start_time、finish_time、wait_time、response_time。平均值可能掩盖 burst 中少量极慢请求，因此可计算 p50/p95，但小样本 percentile 只作教学。Utilization 表示观察窗口中 worker 忙碌比例，高 utilization 往往伴随较少余量；接近 100% 并不等于最佳用户体验。

输入单位必须一致。Service time 在本模型中是预先给定的固定量，现实里它受 prompt/output 长度、batch、cache 和硬件状态影响。Simulator 的价值是建立因果直觉，不是预测 vLLM 吞吐。

机制与推导

对按 arrival 排序的请求 i：

[ start_i=max(arrival_i,finish_{i-1}) ]

[ finish_i=start_i+service_i,\quad wait_i=start_i-arrival_i ]

[ response_i=finish_i-arrival_i ]

若到达率 λ 和平均服务时间 E[S] 稳定，单 worker 负载 ρ=λE[S]。ρ<1 是长期稳定的必要条件，但短期 burst 仍会产生队列；ρ 越接近 1，等待对波动越敏感。课堂公式通常假设特定随机分布，本日 fixture 不需要满足 M/M/1。

最小练习或观察步骤

1. 准备 8～12 个 fixture 请求，包含空闲期、burst 和一个长 service time。
2. 用纯函数按 arrival 顺序计算 start/finish/wait/response，避免真实 timer。
3. 输出每请求表及 mean、p50、p95；记录样本很小的限制。
4. 把长请求移到队尾但保持总工作量，观察 FIFO 等待分布怎样变化。
5. 写出 simulator 的 5 个假设；不要把结果称为生产容量测试。

常见误区与边界

• 用 setTimeout 或 sleep 模拟几秒任务，混入 OS 调度噪声。
• 只算 service time，不算 queue wait 和 response time。
• 按输入文件顺序处理，却未确认 arrival time 排序与同刻 tie-break。
• 小样本 p95 当作可靠 SLO 统计。
• 用固定 service time 模型证明 continuous batching 的真实收益。

系统场景连接

即使模型本身每次推理时间没有变化，burst 也能显著推高用户延迟。金融月末报告、市场波动或批处理任务与在线请求共享 worker 时，FIFO 会让低优先级长任务阻塞交互请求。最小 simulator 为 S24 策略对比、S25 容量降级和 W8 SLO/成本打基础。

自检问题

1. 为什么模拟时钟比真实 sleep 更适合本练习？
2. Wait time 与 response time 的公式分别是什么？
3. ρ<1 为什么仍不能保证每个 burst 都低延迟？
4. FIFO 最典型的公平性优点和延迟缺点是什么？

专业课程对齐

• 阅读 MIT 6.5840 的分布式系统与性能背景，关注并发请求、服务节点与故障如何改变等待，不要求进入共识实验。
• 阅读 vLLM 官方文档 的 serving/scheduler 概览，比较真实 sequence scheduler 比本日单 worker FIFO 多了哪些状态。
• 阅读 Stanford CS329S 的 deployment 与 monitoring 主题，把 queue wait、service 和 response 指标映射到生产 ML 系统观察面。

深入学习提示

先手算 3 个请求，再写循环。对每个输出字段给出守恒检查：finish 不早于 start，wait 非负，busy time 等于 service time 总和。然后只改请求顺序，不改总工作量，观察平均与 tail 为何变化。最后列出从 FIFO 升级到 LLM scheduler 至少要新增的状态，而不是立即实现它们。

学后填写区

• Fixture 与单位：
• 实际实现路径：
• 逐请求和汇总观察：
• 长请求位置变化的影响：
• 模拟器明确省略的内容：