CHAPTER 31

批处理调度

单个请求的算子变快，并不意味着同时到达的一组请求都能及时完成。服务系统还必须决定何时接纳请求、哪些请求共同执行、长提示如何穿插，以及资源不足时谁应等待。调度改变的是请求共享资源的方式，其收益与到达过程、长度分布和服务目标有关。

第30章《增量解码》给出可复用状态及其容量，第33章《推理计算优化》给出一次执行的成本。本章将二者放入随时间变化的工作负载中。部署、连接协议与实例生命周期见第32章《模型服务架构》。

31.1请求、时间及容量的计量边界

本章主要符号见表31.1。

表 31.1　批处理调度的主要符号与计量对象。

符号	含义
\(a_i,b_i,c_i\)	请求 \(i\) 到达、首次获得执行和终止的时间。
\(u_{i,j}\)	客户端收到请求 \(i\) 的第 \(j\) 个输出词元的时间。
\(P_i,O_i\)	输入长度与实际输出长度；\(O_i^{\max}\) 为接纳时约定的输出上限。
\(W_i,T_i,S_i\)	首次执行前等待时间、系统逗留时间、理想队列模型中的服务时间。
\(N(t),N_q(t)\)	时刻 \(t\) 系统内和等待队列内的请求数。
\(\lambda,\mu,\rho\)	队列模型中的到达率、单服务台服务率和利用率。
\(B,K,M\)	单轮新计算词元预算、活动序列上限和可用缓存字节预算。
\(q_i,s_i,m_i\)	单轮为请求分配的新位置数、已有上下文长度及缓存字节数。
\(d_i,w_j\)	请求截止时间与租户 \(j\) 的调度权重。

首词元时延（Time to First Token，TTFT）与词元间时延（Inter-Token Latency，ITL）分别为

\[ \operatorname{TTFT}_i=u_{i,1}-a_i,\qquad \operatorname{ITL}_{i,j}=u_{i,j}-u_{i,j-1}\quad(j\ge2). \tag{31.1}\]

请求生成至少两个词元时，其平均输出词元时间（Time per Output Token，TPOT）定义为

\[ \operatorname{TPOT}_i=\frac{u_{i,O_i}-u_{i,1}}{O_i-1}. \tag{31.2}\]

因此最后一个词元到达的时延恰为 \(\operatorname{TTFT}_i+(O_i-1)\operatorname{TPOT}_i\)。这里的 TTFT 已包含到首次词元之间的排队，不能再次加上 \(W_i=b_i-a_i\)。只有一个词元时 TPOT 不定义；无输出的失败请求必须进入失败统计，不能以零时延代替。

客户端时间还包含网络和缓冲，工作进程内的执行时间不包含这些部分。二者都可记录，但必须说明观测位置。流式协议可能一次传输多个词元；若只能观察数据块，应称为块间隔，而不是把它冒充逐词元 ITL。¹

吞吐也有不同口径：请求完成数、输入词元数、输出词元数和满足服务目标的完成数。预填充与解码的计算和搬运成本不同，\(\lambda\mathbb E[P_i+O_i]\) 仅表示词元流量，不能直接视为统一的设备需求。缓存命中又会使输入长度与实际计算长度不同。

31.2连续批处理

静态批处理的容量浪费

静态批处理（Static Batching）在批次开始时确定成员，通常在当前批次退出后才加入下一组请求。已完成序列可以提前返回结果，但空出的执行位置若不能补入新请求，仍会降低资源利用率。不能把静态批处理一概等同于禁止提前返回。

考虑一个仅用于计算的调度模型：所有预填充均已完成，一轮解码固定耗时10毫秒，最多容纳两条序列。三个请求同时到达，剩余输出长度分别为 \(A=4,B=1,C=1\)。静态顺序先选 \(A,B\)，\(B\) 在10毫秒完成，\(A\) 在40毫秒完成，\(C\) 在50毫秒完成；平均完成时延为 \(\frac{100}{3}\) 毫秒。若在第二轮将 \(C\) 加入空位，则完成时间变为40、10、20毫秒，平均为 \(\frac{70}{3}\) 毫秒。

连续批处理（Continuous Batching）在迭代边界调整活动成员。Orca 将这种决策落实为迭代级调度，并根据算子特性选择批处理方式(Yu 等 2022)。真实系统的轮时会随批大小、上下文长度和算子形状变化，故图31.1只证明该构造中的收益，不是吞吐预测。

长度分桶及等待窗口

若内核把同批 \(n\) 条序列填充到最大长度 \(P_{\max}\)，线性层与显式完整平方注意力矩阵的长度利用率分别为

\[ \eta_{\mathrm{linear}}=\frac{\sum_iP_i}{nP_{\max}},\qquad \eta_{\mathrm{attention}}=\frac{\sum_iP_i^2}{nP_{\max}^2}. \tag{31.3}\]

使用变长分块内核后，不能继续拿这两个比率当作实际计算浪费。

长度分桶（Length Bucketing）把相近长度放入同一执行组，减少形状差异。但等待相近请求会增加时延。动态聚批应同时设置最大等待时间与最大批量：任一条件触发就执行。仅为填满批次持续等待，会在低流量下恶化 TTFT。桶边界附近的长度抖动还可能造成低占用桶，应与第33章《推理计算优化》中的形状分桶中的编译缓存共同设计。

31.3分块预填充及多资源预算

分块预填充的上下文边界

分块预填充（Chunked Prefill）将一个提示的新增位置分多轮处理，每块仍读取合法历史状态；它改变执行时序，不必改变模型可见上下文。SARATHI 研究了预填充分块与解码共同组批的执行方式(Agrawal 等 2023)。具体分块长度须服从设备、批次和服务目标，不能把论文中的某个配置变成普遍最优值。

在已有 \(s_i\) 个位置时处理 \(q_i\) 个新位置，因果注意力所涉及的键查询配对数为

\[ q_i s_i+\frac{q_i(q_i+1)}2. \tag{31.4}\]

推导是将第 \(r\) 个新查询可见的 \(s_i+r\) 个键对 \(r=1,\ldots,q_i\) 求和。每块重读历史会产生搬运与启动开销；块越小，交互机会越多，但不保证总时间越短。解码通常每序列新增一个位置，预填充则可新增许多位置，因此一个简单预算是

\[ \sum_i q_i\le B,\qquad |\mathcal A|\le K,\qquad \sum_{p\in\mathcal P_{\rm live}}\operatorname{bytes}(p)+M_{\rm workspace}\le M. \tag{31.5}\]

其中 \(\mathcal P_{\rm live}\) 是实际驻留物理页集合，共享前缀只计一次。临时工作区要在可用容量中扣除，不能把设备总显存直接当 KV 预算。

仅限制 \(B\) 仍不够：同样的新词元数在不同 \(s_i\) 下有不同注意力成本。调度器还需使用经测量校准的批次成本估计 \(\widehat t(\{q_i,s_i\})\)，在交互目标允许的轮时内选择组合。该函数一般不是各请求独立成本之和，因为共同执行会改变权重重用和有效带宽。

假设与适用范围

以下资源算例假设普通非共享 KV，每词元缓存为64 KiB，页包含16个词元；设备分区已扣除权重与工作区，可用 KV 为64 MiB。实际缓存公式应依据模型层数、键值头数、精度和并行分片确定，不能跨模型复用这个常数。

每页为1 MiB。两条活动序列长度分别为257、255，需 \(17+16=33\) 页。若为它们各解码一步，长度变为258、256，仍为33页。此轮另处理一个新请求的256词元提示块，需要16页，共49页；若该请求声明最终最多使用1024位置，则其完整上界需64页，与已有33页合计97页，不能在64页容量下承诺三者同时完整驻留。

这说明本轮可执行与完整请求可接纳是两个判断。系统可选择保守地预留完整上界，也可动态增长并提供可兑现的抢占、换出或等待策略。不能既按平均输出长度超额接纳，又声称所有请求都有无抢占完成保证。页级管理减少碎片及支持共享，但不创造物理容量(Kwon 等 2023)。

预填充及解码的优先级

始终优先解码可以降低活动请求的词元间隔，却可能使等待提示长期得不到首词元。始终优先新提示又可能使活动输出停顿。可为预填充保留最低服务份额，并在交互轮时预算下分配剩余额度；当多个目标冲突时，应记录超额负载和拒绝，不能用一个平均吞吐数掩盖取舍。

31.4排队关系的推导及适用条件

Little 关系来自驻留面积

Little 关系联系长期平均人数、吞吐与驻留时间(Little 1961)。下面从样本路径面积说明其机制。对观察区间 \([0,H]\)，系统内请求数可以写成指示函数之和：

\[ N(t)=\sum_i\mathbf1\{a_i\le t<c_i\}. \tag{31.6}\]

交换有限求和与积分，得到

\[ \int_0^H N(t)\,dt =\sum_i |[a_i,c_i)\cap[0,H]|. \tag{31.7}\]

右侧为每个请求在观察窗内的驻留时间。若系统稳定，长期到达率存在，边界截断对单位时间的贡献趋于零，则除以 \(H\) 并令 \(H\to\infty\)，得到

\[ \overline N=\lambda\mathbb E[T],\qquad \overline N_q=\lambda\mathbb E[W_q]. \tag{31.8}\]

第二式对等待状态重复相同面积论证。LLM 请求可能在多轮之间反复等待，此时 \(W_q\) 应包括所有被统计的等待区间；它与首次执行前的 \(W_i\) 不必相等。

式(31.8)不要求泊松到达或指数服务，但要求人数、吞吐和时间来自同一系统边界与同一请求总体。若将被拒请求计入到达率，却只对接纳请求计算驻留时间，等式失去对应关系。例如稳定系统每秒完成20个请求，平均驻留0.4秒，则平均系统内请求数为8；这不能推出 p99 驻留时间，也不能推出队列必须恰好设置为8。

M/M/1 模型解释高利用率风险

假设与适用范围

设到达为速率 \(\lambda\) 的泊松过程，单服务台独立服务时间服从速率 \(\mu\) 的指数分布，先到先服务、无限等待空间且无放弃，\(\rho=\frac{\lambda}{\mu}<1\)。该模型用于解释机制；连续批处理的服务率随活动集合变化，不直接满足这些条件。

令稳态系统人数概率为 \(\pi_n\)。相邻状态的概率流平衡给出 \(\lambda\pi_n=\mu\pi_{n+1}\)，因此 \(\pi_n=\rho^n\pi_0\)。利用几何级数归一化得

\[ \pi_n=(1-\rho)\rho^n,\qquad \mathbb E[N]=\sum_{n\ge0}n(1-\rho)\rho^n=\frac{\rho}{1-\rho}. \tag{31.9}\]

结合式(31.8)，有

\[ \mathbb E[T]=\frac1{\mu-\lambda},\qquad \mathbb E[W_q]=\frac{\rho}{\mu-\lambda}. \tag{31.10}\]

后式从总时间减去平均服务时间 \(\frac{1}{\mu}\) 得到。当 \(\rho\) 接近1，等待呈非线性增长；把设备长期推到饱和不能视为无代价的效率提升。

还可以推导完整逗留时间尾部。独立泊松到达在到达前看到的状态分布为时间稳态分布：直观上，任一短区间发生到达的概率 \(\lambda\,dt\) 不因当时状态改变，因此不会额外偏向某状态。到达看到 \(n\) 个请求时，自身完成需等待 \(n+1\) 个独立指数服务阶段；其中正在服务者的剩余时间利用无记忆性处理。于是对 \(z\ge0\)，

\begin{align} \mathbb E[e^{-zT}] &=\sum_{n\ge0}(1-\rho)\rho^n \left(\frac\mu{\mu+z}\right)^{n+1}\tag{31.11}\\ &=\frac{\mu-\lambda}{\mu-\lambda+z}. \tag{31.12}\end{align}

这是速率 \(\mu-\lambda\) 的指数分布的拉普拉斯变换，故

\[ \Pr(T>t)=e^{-(\mu-\lambda)t},\qquad t_{0.99}=\frac{\log100}{\mu-\lambda}. \tag{31.13}\]

若 \(\mu=100\) 请求每秒，\(\lambda=80\)，平均逗留50毫秒，p99约230毫秒；到达率升至95时，二者分别为200和921毫秒。这个构造只改变到达率，就产生明显尾部增长。

结论

批处理的请求共享服务轮次，长输出又使驻留长度分布发生变化。不能把上述 \(\mu\) 换成一次离线词元吞吐，就声称获得了真实服务 p99。实际系统应使用按长度、阶段和负载测得的服务曲线，必要时以到达轨迹驱动离散事件模型，并用独立观测校准。

31.5准入、期限及背压

准入控制（Admission Control）发生在承诺接受任务的边界。至少要核查模型与租户配额、请求体与长度上限、缓存增长、队列空间和期限。可以用

\[ \widehat W_i+\widehat S_i+\Delta_i\le d_i-a_i \tag{31.14}\]

作为风险判断，其中 \(\Delta_i\) 为估计误差和协议开销余量。分位数也不能随意相加得到相同分位数的总和；要么直接估计联合总时延，要么使用明确的概率上界。²

背压（Backpressure）把下游容量不足传递给上游。它必须贯穿入口、有界等待队列、活动序列和输出缓冲。如果只限制设备并发，慢客户端仍可能使主机缓冲无限增长。若输出缓冲以每秒 \(r_g\) 字节生成、每秒 \(r_c\) 字节消耗，则积压近似按 \(r_g-r_c\) 增长；当 \(r_g>r_c\)，容量 \(H_b\) 的空缓冲将在 \(\frac{H_b}{r_g-r_c}\) 秒后填满。持续消费不足时应暂停、取消或终止，并传播资源释放。

突发到达时，队列吸收的是暂时差额，而不是永久不足。若一段时间内输入速率为 \(\lambda_b\)、有效完成速率为 \(\mu_b<\lambda_b\)，持续 \(\tau\) 秒，则新增积压粗估为 \((\lambda_b-\mu_b)\tau\)。这是流体近似，忽略随机波动；必须另外考虑突发形状和请求工作量。扩容有加载延迟时，不能把尚未就绪的设备计入即时服务能力。

31.6公平性及可恢复的抢占

（选修）

公平调度的分配单位

先到先服务（First-Come, First-Served，FCFS）简单且可解释，但长请求可能造成队首阻塞（Head-of-Line Blocking，HOL Blocking）。按最短作业优先在已知独立作业时长等条件下改善平均等待，但输出长度未知，估计误差和长作业饥饿会削弱其适用性。

租户公平可以按请求数、词元数或计算成本定义。每请求一票会偏向长请求，每词元一票又忽略长上下文解码与短上下文解码的成本差异。应选可测量、能核算的成本单位，并公开权重的业务含义。

一种实现是为租户 \(j\) 维护信用额 \(D_j\)，每轮增加 \(w_jQ\)，执行后减去计费成本 \(c\)。信用不足的候选等待后续轮次；允许有限结转可以容纳较大任务，但应限制无限积累造成的突发。预测成本用于选择，实际成本用于事后纠偏，二者差额不能长期由其他租户承担。共享批次成本难以精确归因，实践中需固定一致的分摊口径，而不能声称存在唯一物理真值。

老化（Aging）随等待增加优先级，可缓解饥饿，但不能在持续超载下保证每个请求都按时完成。截止时间优先也不是无条件最优：本系统同时具有缓存驻留、多资源约束和不可抢占设备片段，不满足许多经典单处理器期限结论的前提。

抢占成本

抢占（Preemption）应发生在安全的迭代边界。已完成输出保持不变，未提交候选与执行状态按明确规则处理。若丢弃缓存，恢复需重算已提交前缀；若换出，则需传输及恢复页映射，并确认模型修订、位置和缓存格式一致。

设重算成本为 \(C_r\)，换出和换入共需移动 \(2m\) 字节，有效传输带宽为 \(b\)，另有同步成本 \(C_s\)。粗略比较 \(C_r\) 与 \(\frac{2m}{b}+C_s\) 有助于选择，但链路竞争与恢复时设备占用还可能改变结果。频繁抢占会产生反复重算，使观测到的忙碌增加而有效完成减少。应记录重算词元与原始词元的比例，并设置冷却或最小执行份额。

算法31.1　计算过程

单轮有界调度。 输入为等待队列、活动请求、物理页状态、租户信用和本轮预算。

在安全边界处理完成、取消和到期事件，释放引用与预留；已发布终止状态不得重新入队。

增加各租户信用，更新活动解码与等待预填充的期限、年龄和成本估计。

为交互解码与等待预填充分别保留最低服务份额；按权重、期限及年龄选择候选。

对候选确定 \(q_i\)，同时检查新词元、序列槽、物理页、工作区和轮时预算。无法容纳时考虑其他可行候选，避免无限队首阻塞。

对本轮计划原子预留页与状态版本。若预留失败，撤销该计划并重新选择，不以部分成功的预留直接执行。

执行一轮；按实际进度提交缓存和输出，按实际计费规则扣减信用，保留尚未完成者。

记录排队、批形状、资源、重算和输出阻塞；若不存在可行计划，等待资源事件或执行明确的拒绝、抢占策略，禁止空转。

31.7尾延迟及有效容量

请求级 TPOT 平均值会掩盖单次长停顿，也会与把所有 ITL 汇总后的均值不同：后者让长输出拥有更大权重。应分别报告请求级分布与词元级分布，并说明权重。输入长度、输出长度、缓存命中、租户和模型修订都可能形成不同的时延切片。

开放环负载（Open-Loop Load）按独立于完成速度的计划提交请求，能够显露过载积压；闭合环负载（Closed-Loop Load）在固定并发用户收到响应后再提交，其到达率会在服务变慢时自行下降。两种模型都可有意义，但回答不同问题。若原目标是固定外部到达流，测试却在每个响应后才继续，就会遗漏拥塞期间本应到达的请求，这种测量偏差常称为协调遗漏（Coordinated Omission）。不能只用闭合环的低尾延迟证明外部突发下的稳定性。

将满足质量与时延目标的成功请求数除以观察时长，可定义该目标下的有效吞吐（Goodput）。例如一个构造性窗口内共提交1000个请求，拒绝100个、失败50个、成功850个，其中700个满足所有目标，窗口100秒，则提交率10、成功吞吐8.5、有效吞吐7请求每秒。若只在成功者中报告满足率，得到 \(\frac{700}{850}\)；若从所有提交者看，则是70%。二者必须注明分母。

调度策略比较应保持模型、生成参数、输入轨迹与输出预算一致；随机生成导致工作量不同，应多次重复或使用可解释的受控长度实验。报告原始到达计划、被接纳请求、失败与取消，不把超时样本删除后再计算漂亮的 p99。质量变化带来的短输出也不能冒充纯调度加速。

同一请求的终止控制消息可能晚于最后一个词元；因此完整协议时延 \(c_i-a_i\) 还可包括收尾开销。↩︎
若 \(\Pr(W>w)\le\epsilon_1\)、\(\Pr(S>s)\le\epsilon_2\)，则不要求独立也有 \(\Pr(W+S>w+s)\le\epsilon_1+\epsilon_2\)。这来自并集界，而不是分位数可加性。↩︎

WORKBOOK / 习题

配套习题与解析

先独立作答，再展开参考解析。选修题保留原书标记。

习题 31.1

某请求在0秒到达，0.1秒开始执行，0.3秒收到首词元，0.9秒收到第31个词元。计算 TTFT、TPOT 和首执行等待，并指出哪些量可以相加。

展开参考解析

TTFT 从到达到首词元，为 \(0.3\) 秒；首执行等待为 \(0.1\) 秒。31个输出间有30个间隔，\(\mathrm{TPOT}=\frac{0.9-0.3}{30}=0.02\) 秒。总完成时间为 \(0.3+30(0.02)=0.9\) 秒。等待已包含在TTFT内，不能再加一次；只有先扣除等待，才能把TTFT分成互不重叠阶段。

习题 31.2

将图31.1的轮时改为单序列6毫秒、双序列10毫秒，重新计算两种策略的完成时间。解释固定轮时假设的影响。

展开参考解析

补充约定：已完成成员不继续参与计算，静态策略只禁止补入新成员。静态第一轮双序列耗10毫秒，B完成；随后A独占三轮共18毫秒，A在28毫秒完成；C再耗6毫秒，在34毫秒完成，均值 \(\frac{10+28+34}{3}=24\) 毫秒。连续策略第一轮B完成，第二轮A与C耗10毫秒，C在20毫秒完成；A再独占两轮，在32毫秒完成，均值 \(\frac{62}{3}\approx20.67\) 毫秒。连续策略改善均值但A稍晚；若静态内核仍计算填充槽，其轮时模型不同，须重新计数，不能沿用上述结果。

习题 31.3

对长度为64、64、256的三个提示，计算线性填充与完整平方注意力的长度利用率。为何不能将结果直接用于变长内核？

展开参考解析

最大长度256。线性利用率为 \(\frac{64+64+256}{3\times256}=\frac{1}{2}\)；平方注意力利用率为 \(\frac{64^2+64^2+256^2}{3\times256^2}=\frac{3}{8}\)。两式假定每条序列真实执行到同一填充长度。变长内核可跳过部分无效位置，且块对齐、掩码和工作区还有其他成本，因此这两个比例不是其实际加速比。

习题 31.4

从逐查询可见键数推导式31.4，并解释分块后注意力数学总量与历史重读次数的区别。

展开参考解析

第\(r\)个新查询看见\(s+r\)个键，故 \(\sum_{r=1}^q(s+r)=qs+\frac{q(q+1)}{2}\)。将长度\(q\)拆成\(q_1,q_2\)时，第二块历史变为\(s+q_1\)，两块配对数之和仍等于原式。数学配对总数保持，而第二块需要重新读取历史键值，并多一次启动；配对守恒不能推出搬运或墙钟时间不变。

习题 31.5

在缓存算例中，已有257、255长度的序列各再生成两个词元，需要多少页？说明页内碎片为何会影响边际接纳成本。

展开参考解析

每页16位置，增长后长度为259、257，页数为 \(\lceil\frac{259}{16}\rceil+\lceil\frac{257}{16}\rceil=17+17=34\)，较初始33页增加1页。第一条仍位于既有第17页，第二条跨过256边界。每词元64 KiB只描述有效数据增长，实际边际分配按整页发生，此处增加1 MiB而非按四词元只预留256 KiB。

习题 31.6

给出一个系统人数的阶梯函数，直接计算驻留面积以验证式31.7。解释有限观察窗两端截断如何处理。

展开参考解析

取两请求驻留区间\([0,2)\)和\([1,3)\)，观察窗\([0,3]\)。人数在三段依次为1、2、1，面积为 \(1+2+1=4\)，也等于两请求各2的驻留时间之和。窗内平均人数\(\frac{4}{3}\)、完成率\(\frac{2}{3}\)、平均驻留2，三者满足Little关系。存在窗外开始或结束请求时，有限窗恒等式使用区间交集长度；不能把完整驻留时间与截断人数面积混配。长期式需要边界残余除以窗长趋零。

习题 31.7选修

推导 M/M/1 的空闲概率、平均队列长度和式31.13。指出连续批处理违反其中哪些假设。

展开参考解析

记\(\rho=\frac{\lambda}{\mu}<1\)。出生死亡平衡给 \(\pi_{n+1}=\rho\pi_n\)，归一化得 \(\pi_0=1-\rho\)、\(\pi_n=(1-\rho)\rho^n\)。由几何级数求导，\(L=\frac{\rho}{1-\rho}\)，服务中概率为\(\rho\)，故\(L_q=\frac{\rho^2}{1-\rho}\)。泊松到达看见稳态人数，条件于\(n\)个在系统者，总驻留为\(n+1\)个参数\(\mu\)指数变量之和；其拉普拉斯变换为 \(\sum_n\pi_n[\frac{\mu}{\mu+s}]^{n+1}=\frac{\mu-\lambda}{\mu-\lambda+s}\)，所以 \(P(W>t)=e^{-(\mu-\lambda)t}\)。连续批处理的多请求协同服务、依长度变化的轮时和调度优先级违反单服务台独立指数、FCFS等前提。

习题 31.8

当两个随机阶段的 p99 分别为100与200毫秒时，能否断言总时延 p99为300毫秒？使用并集界给出一个成立的陈述。

展开参考解析

不能。非负阶段\(X,Y\)满足 \(\{X+Y>300\}\subseteq\{X>100\}\cup\{Y>200\}\)，因而已知两个尾概率各不超过0.01时，\(P(X+Y>300)\le0.02\)；300毫秒是一个98%覆盖上界。要保证99%，可分别选择p99.5阈值再相加，或直接测量同请求的阶段和。独立性也不能使两个分位点直接相加成为精确分位数。

习题 31.9选修

构造每请求公平与每词元公平结果相反的两租户负载，并说明长上下文为何进一步影响成本公平。

展开参考解析

设租户A每请求10词元，B每请求1000词元，均持续积压。每轮各完成一请求给予B约100倍输出份额；每轮各给1000词元则A完成100请求、B完成1请求。两者对应不同公平对象。再令B具有更长历史，则同一输出词元还读取更多KV，词元公平未必计算时间公平；可用经校准设备时间记账并配合最低服务份额，但成本估计误差必须监测。

习题 31.10

输出产生速率为每秒12 KiB，客户端消费每秒4 KiB，空缓冲容量为64 KiB。求填满时间，并设计到达上限后的状态转换。

展开参考解析

净流入 \(12-4=8\) KiB/s，填满时间 \(\frac{64}{8}=8\) 秒。上限到达后进入暂停生产或慢消费者状态，停止为其新增生成，继续排空并设置期限；若不能暂停或期限耗尽，则取消并释放其资源。不得无界累积，也不得丢词元后仍声称完整流；终态与最后已确认事件号一并记录。

习题 31.11

设计一个记录取消、页释放和重新入队的事件序列，证明调度器不会让已终止请求复活，也不会重复释放共享页。

展开参考解析

事件可为：请求r持有共享页p的一次引用；取消CAS将r置为终止；释放记录以\((r,p)\)唯一键提交并将引用计数减一；迟到的抢占完成事件试图重新入队时因r已终止被拒绝；重复取消只读既有释放记录。p只有全体引用归零且设备在途读写已通过完成事件或fence确认结束后回收，使用页代次防止旧事件释放复用后的新页。终态单调、释放唯一键和页代次共同构成不变量，单靠队列中删除一次不够。

习题 31.12

比较开放环和闭合环压测，列出一个能识别过载、重算放大和慢消费者的证据方案，并明确所有统计分母。

展开参考解析

开放环按外部时钟发请求，能暴露积压增长；闭合环受前一响应限制，过载时到达率可能自动降低。固定时长报告提交、接纳、成功、达标成功、拒绝、取消和未知数，分别以时间或对应请求集合为分母；记录全体已完成时延及未完成的删失/截止状态。用新生成词元与总执行词元比识别重算，关联缓存换出事件；用输出缓冲占用、消费速率与慢客户端数识别背压。不能只测成功请求平均速度而丢弃超时者。

习题 31.13

服务显存尚有余量，但尾延迟持续恶化。设计一次诊断，区分持续超载、长提示阻塞解码与慢客户端造成的输出积压；说明不同证据下应调整准入、调度还是扩容，并给出扩容生效前的处置原则。

展开参考解析

在相同到达负载下关联队列年龄、预填充块时长、解码间隔及输出缓冲，使用开放环负载观察队列是否持续增长。若排队增长且设备有效容量饱和，应限制准入并增加对应阶段容量；若长提示使解码间隔突增，应检查预填充分块和阶段预算，同时保留必要预填充份额；若生成完成但输出缓冲积压，应检查慢客户端、背压和取消传播。显存余量只表示部分容量余量，不能证明计算或输出路径仍可满足期限。扩容需要启动与预热时间，其间应按队列预算和期限执行排队或拒绝策略，并验证积压能够消退。

REFERENCES

参考文献

Agrawal, Amey, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, 和 Ramachandran Ramjee. 2023. 《SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills》. 2023年. https://arxiv.org/abs/2308.16369.

Kwon, Woosuk, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, 和 Ion Stoica. 2023. 《Efficient Memory Management for Large Language Model Serving with PagedAttention》. 2023年. https://arxiv.org/abs/2309.06180.

Little, John D. C. 1961. 《A Proof for the Queuing Formula: \(L=\lambda W\)》. Operations Research 9 (3): 383–87. https://doi.org/10.1287/opre.9.3.383.

Yu, Gyeong-In, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, 和 Byung-Gon Chun. 2022. 《Orca: A Distributed Serving System for Transformer-Based Generative Models》. 收入 16th USENIX Symposium on Operating Systems Design and Implementation, 521–38. USENIX Association. https://www.usenix.org/conference/osdi22/presentation/yu.