深度解读 📅 2026-11-11 ✍️ MagicNetWorld 编辑部

Fairway 拆解:前缀缓存让 prefill 工作量可差约 100 倍,调度顺序该怎么改

深读 2026-11-01 提交的 arXiv:2611.02082v1(UC Irvine 与 Apiphany)。前缀缓存把「请求长度」换成「未缓存 token 数」后,Mooncake 轨迹里同一队列的未缓存量跨度约 100 倍(别与四个负载按 FCFS 统计的 P90/P10 = 70–250 倍混读)。Fairway 用双虚拟车道加工作量记账,把一步之内排在最老请求前面的便宜活压到约其自身工作量的 1/w(w=4;严格界还含首末请求工作量之差);11 个场景中 10 个相对各场景不饿死的最佳基线 p99 低 2–18%,另一个基本持平;尖峰下保住 FCFS 的尾部、把中位压到 0.82 秒。摘要的「最高 8.6 倍」只对应会饿死请求的复用优先基线。本文为论文口径转述,未做端到端复现。

前缀缓存Prefill 调度TTFTvLLMSGLang推理服务

先说直觉:排队排的不是「请求数」,是「没算过的 token 数」

一个 RAG 服务里,两条请求同时进队列。第一条把系统提示词、五段检索到的财报、问题一起送进来,前面一万多 token 全在缓存里,只有最后几十个 token 没算过;第二条只命中了系统提示词,后面 1.3 万 token 全要重算。对一个按「请求先来后到」办事的调度器,这两条是平等的:一人一个名额。但对 GPU 完全不是一回事——第一条只花几十个 token 的算力,第二条要花一万多。

论文给出的量化是:在 Mooncake 的生产 agent 轨迹里,同一个等待队列内各请求真正要算的未缓存 token 数(下称「工作量」)跨度约 100 倍,从几百到约 1.8 万。这里先把两个容易混的数字分开:约 100 倍是 Mooncake 轨迹内单个队列的跨度;70–250 倍是论文四个负载按 FCFS 服务时统计的 P90/P10 比值,两者统计对象不同,后文还会再钉一次。

在这种队列里,调度顺序不只是「谁先谁后」,它直接决定了尾延迟:你把一个便宜请求提前,它省下的是几十个 token 的时间;你把它排在一个贵请求前面,贵请求等的是几十个 token 的时间;而你如果把一百个便宜请求都提前,贵请求就要等到它们全部算完。

Fairway(arXiv:2611.02082v1,2026 年 11 月 1 日提交,UC Irvine 与 Apiphany 的作者团队;本文 2026-11-11 读取该版本,下文数字均指此版本)要解决的就是这件事。它没有发明新的缓存结构,也没有改 eviction、没有改 chunked prefill 的步长——它只改一件事:引擎每一步从等待队列里先接谁进来。

结论按论文口径是:在 11 个场景、7 个基线的对比里,10 个场景相对「该场景下不饿死请求的最好基线」把 p99 首 token 延迟压低 2–18%,第 11 个基本持平;在 60 秒负载尖峰里保住 FCFS 的尾部,同时把中位 TTFT 从 5.1–5.9 秒压到 0.82 秒。这里必须先把两个口径分开:摘要里「最高 8.6 倍」的 p99 优势,是对会把请求饿死的那几类复用优先基线算出来的;对不饿死的最好基线,优势是 2–18%,不是 8.6 倍。

术语与符号约定

后面所有公式都用下表记号。行内公式同样按本站约定写成 …… 形式。表中 SLO\mathrm{SLO} 是借来的名字,本文只把它当作「耐心的归一化尺度」,不是对外承诺的截止时间。

记号含义单位/取值
LrL_r请求 rr 的 prompt 总长度token
hrh_rrr 进入调度时,其前缀已命中缓存的长度token
crc_rrr 真正要计算的未缓存 token 数,即「工作量」token
wrw_rrr 在等待队列里的已等待时间秒
est(L)\mathrm{est}(L)空闲引擎上长度为 LL 的 prompt 的 prefill 耗时秒
SLOr\mathrm{SLO}_rrr 的「耐心」,即相对等待的分母秒
BB每个调度步允许携带的 prompt token 预算token,论文取 2048
wwFast 车道的工作量权重论文取 4
ρ\rho负载,到达率与服务率之比(动态轨迹按未缓存 token 计)无量纲
A, FA,\ FFast 车道与 Fair 车道各自已排入顺序的「工作量欠账」token

前缀缓存把「请求长度」替换成了「本地工作量」

块级前缀匹配:命中是一条链,不是一棵树

论文所述的 vLLM 0.16.0 把 KV 缓存按固定大小的块管理,每块 16 个 token;一个块能被复用,前提是它之前的所有块也都匹配。SGLang 的 radix tree 语义相同:复用从根开始,遇到第一个不同的块就停。这条「链式」规则是后面所有现象的根:命中长度不是「有多少段文本相同」,而是「从头开始连续相同的长度」。

于是「同一份文档在缓存里」不等于「你的请求能用到它」。论文给了一个很干净的例子:假设更早的请求 [S∣A∣B∣C∣q1][S \mid A \mid B \mid C \mid q_1] 已经把 S,A,B,CS,A,B,C 留在缓存里。那么

  • [S∣A∣B∣D∣q2][S \mid A \mid B \mid D \mid q_2] 能用 S,A,BS,A,B,从 DD 开始重算;
  • [S∣D∣A∣B∣q3][S \mid D \mid A \mid B \mid q_3] 只能用 SS,尽管 A,BA,B 明明在缓存里;
  • [S∣A∣B∣C∣q4][S \mid A \mid B \mid C \mid q_4] 只需算它的提问 q4q_4。

对调度器来说,这三条请求的「工作量」完全不是一个量级,而它们在队列里长得一模一样。

工作量的定义

cr=Lr−hr,cr≥1c_r = L_r - h_r , \qquad c_r \ge 1

本文按未缓存 token 数近似计量新增的 prefill 工作量,它不是精确的耗时模型:同样的 crc_r,在批大小、上下文长度、kernel 选择不同时耗时会差。但在这个问题的量级上(几十 vs 一万多),这个近似足以解释调度为什么重要。

注意 crc_r 不是一个请求的固有属性:它取决于你把它排在哪一刻。一条请求在队列里等得越久,前面被接纳的请求越可能把缓存挤掉(论文的评测里 KV 容量只放得下整条轨迹可复用块的四分之一到三分之一,eviction 很频繁),它轮到自己时的 hrh_r 就越小。

命中率不是充分的调度目标

一个常见的误读是:既然命中越多越快,那就把命中率当成优化目标。问题是调度器不能直接设定命中率——它由负载结构、缓存容量和驱逐策略共同决定;调度只能间接影响它(后面的请求会不会把你等待中的前缀挤掉,确实和顺序有关)。所以命中率不是错的目标,而是不充分的目标:命中率相同的两组请求,可以有完全不同的 crc_r 分布,而等待怎么分配才是调度能直接控制的。

把命中率写出来看得更清楚:

H=∑rhr∑rLrH=\frac{\sum_r h_r}{\sum_r L_r}

HH 相同的一组请求,∑rcr\sum_r c_r 可以差很多。比如两条都长 10k 的请求,一条命中 9k(c=1kc=1\text{k})、一条全 miss(c=10kc=10\text{k}),H=45%H=45\% 是固定的;但先服务谁,决定了另一条要等 1k 还是 10k 的工作量。

在「每条请求的工作量已经给定、服务台串行」这个简化模型里,队列的总等待工作量是

∑rQr=∑rnr cr,Qr=Wr服务率\sum_r Q_r=\sum_r n_r\,c_r ,\qquad Q_r=\frac{W_r}{\text{服务率}}

其中 QrQ_r 是以「工作量」计的等待(换成秒要除以服务率),nrn_r 是排在 rr 后面、会被它阻塞的请求数。这个式子说明:一条请求越靠前,它的工作量就被越多的人承担。最短作业优先(SPT/SRPT)能让这个和最小——这是 1968 年就有的经典结论(Schrage,收在论文参考文献里)——代价是长作业可能永远排不上。所以「平均更快」与「最慢的那条别等太久」在这里是结构性冲突,不是实现水平问题。论文的四条需求本质上是在给这个冲突划一条可计算的边界。

队列内的差距有多大

论文在四个负载上量了「按 FCFS 服务时,每条请求真正计算的 token 数」:第 90 百分位与第 10 百分位之比是 70–250 倍。注意这个数字与开头的「约 100 倍」不是同一件事:

  • 70–250 倍:跨论文的四个负载(SEC QA、SEC 长文档 QA、MuSiQue、Mooncake)统计的 P90/P10 比值;
  • 约 100 倍:Mooncake 生产轨迹里同一个队列内未缓存 token 的跨度(从几百到约 1.8 万),也是摘要里那个 100×;论文统计「部分命中」的口径是「一个块只要被此前任一请求包含就算已缓存」;
  • 30–35%:SEC QA 里「部分命中」的请求占比,它们承担了全部 prefill 工作的 54–64%;另有约一半请求是全命中,只需要算自己的提问(几十个 token)。

Mooncake 的生产分布里,58% 的会话请求、65% 的工具型 agent 请求是部分命中。这解释了为什么这件事不是合成负载的怪癖:agent 每轮把历史与工具输出重发一遍,天然形成「长共享前缀 + 短新尾巴」。但要注意评测时它被缩放过:论文为把它塞进一张卡,只保留八分之一会话、prompt 长度乘 1/4(Appendix B),所以 0.3–16k 是缩放后的评测长度,1.8 万是原始轨迹的统计——两个数不能直接对比。

为什么任何固定顺序都必然有一头崩

先算一笔账:TTFT 由谁决定

TTFTr=Wr+Pr\mathrm{TTFT}_r = W_r + P_r

WrW_r 是在队列里等的时间,PrP_r 是自己 prefill 的时间(严格说,TTFT 是「排队 + 完整 prefill 直到首 token 产出」,所以 PrP_r 指整段 prefill,而不是它的第一块)。在 P/D 分离部署里,一条请求的 TTFT 几乎全部耗在 prefill 节点上(论文只针对这个节点),而 PrP_r 与 crc_r 近似成正比:作者实测 1k token 约 0.14 秒、10k token 约 1.4 秒,即约 7.1k token/s 的量级(本文据论文两个数据点自行换算,不是论文直接给出的吞吐数字)。

排队一侧的关键变量是负载,而有了前缀缓存后,负载不能再按「请求数/秒」算:

ρ=λ E[c]μcapacity,μcapacity≈BTstep\rho=\frac{\lambda\,\mathbb{E}[c]}{\mu_{\text{capacity}}} ,\qquad \mu_{\text{capacity}} \approx \frac{B}{T_{\text{step}}}

也就是说,在到达率持续的前提下,缓存命中率一降,负载就升。论文的动态轨迹正是这么设计的:从 ρ≈0.75\rho \approx 0.75 的平稳段,进入 300 秒的突发(ρ≈0.9–1.0\rho \approx 0.9\text{–}1.0,其中 topic shift 把 40% 的请求打到冷门文档上,SEC 上的 miss 比例从 17% 升到 24%),再插一个 60 秒、ρ≈1.05–1.15\rho \approx 1.05\text{–}1.15 的尖峰。

代一组数体会一下(本文自算,不是论文数据):若引擎服务能力按 7.1k token/s 计,平均每条请求要算 2000 个未缓存 token,那么让它工作在 ρ=0.9\rho=0.9 需要

λ≈0.9×71002000≈3.2 req/s\lambda \approx \frac{0.9 \times 7100}{2000} \approx 3.2\ \text{req/s}

而如果同一批请求因为缓存被挤掉、平均未缓存量涨到 4000,同样的 3.2 req/s 就把 ρ\rho 推到 1.8——队列开始无界增长,任何调度都只剩「谁先淹死」的选择。这就是为什么论文把负载定义在「未缓存 token 到达率」上,而不是请求速率上;也是为什么它把「尖峰」只设到 1.05–1.15:再高就没有调度空间可谈了。

这就是为什么「按命中长度排序」和「按到达顺序排序」都能在某一半指标上胜出,也解释了这篇论文为什么不去改缓存、只改准入顺序:在给定缓存的这一刻,总量已经定了,顺序决定的是分配。

同一次 60 秒尖峰实验中,FCFS、复用优先与 Fairway 的中位与 p99 取舍
图 1 三类调度在同一次 60 秒尖峰实验中的取舍:FCFS 中位高、尾部短,复用优先中位低、尾部失控,Fairway 想同时拿两边(本文自绘,数字取自论文 Figure 1 与 §5.2)

这张图想说明的一件事:中位与尾部在同一个队列里是被两条不同的机制决定的,所以不存在「调一个参数同时优化两者」。

三条曲线:便宜的先走、老实的先走,各有各的崩法

论文的 Figure 1 是这张图最好的一版:60 秒尖峰内,复用优先(LPM、RAGCache 一类)把中位 TTFT 保持在 0.8 秒,但 p99 冲到 15–42 秒;FCFS 把 p99 守在 7.8 秒,代价是中位升到 5.9 秒。这不是调参能同时拿到的两条边:

  • 复用优先:按最长命中前缀(LPM)或命中比例排序,缓存最热的请求永远插队。落在冷文档上的请求在持续洪流下可能等上几分钟,这是无界等待,不是「慢一点」。
  • FCFS:不允许后来者插队,所以在这次实验里尾部最短;但每一个便宜命中都要排在贵请求后面,中位被拉高。(这不是「持续过载下尾延迟有界」的承诺——过载时它一样会积压。)
  • 计数公平:每 kk 次复用优先插一次最老请求(k-LPM),或者按命中比例分组发名额(Preble)。问题是一次 pick 的成本可能是几十个 token,也可能是一万多,按次数记公平等于把 1 元和 1000 元当成同一笔账。

这里「饿死」是论文的实验判据,不是理论定义:同一次运行里,某条请求的 TTFT 超过该次运行 p99 的 3 倍,就记这次运行里存在饿死。它描述的是「p99 好看、但个别请求等了几分钟」这种形态,而不是数学上的「永不服务」。

用排队论的话说,ρ>1\rho>1 时积压持续增长,任何「只看等待秒数」的规则都必须配一个权重或阈值,而这个阈值随负载与命中结构漂移:论文的实测是 k-LPM 的 k=4k=4 在 traffic surge 场景的整体 p99 只比 Fairway 高 6%,但 topic shift 之后 p99 比 Fairway 高 92%;k=8k=8 反过来,在稳定分级复用下高出 42–61%。没有单一的 kk 适配所有场景,这是它必须自适应而不是加参数的理由。

用排队模型看尾部:方差比均值更致命

把 prefill 节点看成一个单服务台,请求的服务时间就是 Sr∝crS_r \propto c_r。在 FCFS 下,M/G/1 的等待时间有一条经典公式(Pollaczek–Khinchine,排队论教材里的结果;本文用它做直觉,不是论文的推导):

E[Wq]=λ E[S2]2 (1−ρ)\mathbb{E}[W_q]=\frac{\lambda\,\mathbb{E}[S^2]}{2\,(1-\rho)}

注意分子是服务时间的二阶矩。P90/P10 到 70–250 倍说明这个分布很分散,会放大二阶矩驱动的等待;而当 ρ→1\rho \to 1 时,分母趋零,任何顺序都救不了总量,只能决定「谁先被服务、谁承担积压」。

这条公式有一个前提被前缀缓存破坏了:服务时间不再是独立同分布,它取决于前面的请求是否把你的缓存挤掉。所以它只能当直觉用。但它解释了论文为什么强调「负载要按未缓存 token 计」——按请求数算的 ρ\rho 会严重低估真实负载。

论文由此提出的四条需求

需求内容反面证据
R1队列短时按 KV 复用优先;接近或超过容量时,限制老请求被后来者插队的程度FCFS 中位 5.9 s vs 复用优先 0.8 s
R2用「相对自己 prefill 时间」的等待,而不是绝对秒数同为 1 秒等待,对 1k 请求是 7 倍自身 prefill,对 10k 请求不到 1 倍
R3对最老请求,把它前面被服务的工作量限制在它自身规模的固定比例内只加相对等待时,flood 场景最老 miss 仍等 59 秒
R4以上都不靠按负载调参最好的 kk、最好的顺序随场景变化

Fairway 的两个车道与一笔「工作量欠账」

三个组件与一次调度步

Fairway 的改动面小到可以画成一张图:它在引擎每一步开始之前重排等待队列,然后按这个顺序做准入。命中长度先由 KV 缓存管理器查出,交给 Fast 车道排序;Fair 车道按到达时间排;两条顺序再用欠账合并。缓存驱逐、步预算全部沿用引擎原有实现。

Fairway 在推理引擎中的位置:KV 缓存管理器提供命中长度,双车道排序后按欠账合并,再按步预算准入
图 2 Fairway 在推理引擎里的位置:一个准入 hook、两条虚拟车道、一次按欠账的合并(本文自绘,对应论文 Figure 5 与 Algorithm 1;B=2048 是论文评测配置)

这张图想说明的一件事:它没有新增一条缓存通路,只把「等待队列的排序」这一件事换掉了,所以在论文的实现里能与其它策略协同工作、也能单独回滚;换到别的版本或部署仍要自己验证兼容性。

Fast 车道:命中比例 + 相对等待

Fast 车道给每条等待请求打一个分:

sr=hrcr+wrSLOr,SLOr=max⁡(1 s, 3⋅est(Lr))s_r=\frac{h_r}{c_r}+\frac{w_r}{\mathrm{SLO}_r} ,\qquad \mathrm{SLO}_r=\max\bigl(1\,\mathrm{s},\ 3\cdot \mathrm{est}(L_r)\bigr)

三项设计各有明确的替代方案被否掉:

  1. 为什么是 hr/crh_r/c_r 而不是 hrh_r:按命中长度排序(SGLang 的 LPM)会把「命中 8000、还要算 4000」的长请求排在「命中 200、只需算 20」的短请求前面,代价是把它后面的所有人都多拖 4000 个 token。比值天然偏向「便宜且命中深」的那一条。
  2. 为什么分母用 LrL_r 而不是 crc_r:crc_r 随缓存状态变化,而且已经进了比值项;用固定的 LrL_r 算耐心,一个请求的「紧迫度」才有稳定含义。
  3. 为什么两项直接相加、不再乘权重:给等待项乘一个系数只是把耐心整体缩放,等价于改 SLO\mathrm{SLO} 的倍数,信息上是重复的。

耐心倍数取 3 的直觉可以手算:按 7.1k token/s,1k 请求的 prefill 约 0.14 秒,3×0.143\times0.14 不足 1 秒,于是被 1 秒的地板兜住;10k 请求约 1.4 秒,耐心约 4.2 秒。同为「已等 1 秒」,短请求的相对等待已经接近 1,长请求只有 0.24——这就是 R2 想要的效果:短请求先变急,因为它先让出位置对别人的伤害最小。

为什么只靠「等待加分」给不出按自身工作量的硬界

先说清楚要证明什么:不是「等待加分没用」,而是「它给不出与请求工作量挂钩的边界」。假设洪流里一条高命中请求的命中比是 50(例如命中 15k、只需算 300),队列里一条 miss 要算 6000 个 token、按上式计算耐心约 2.5 秒(3×6000/71003\times6000/7100)。只用「命中比 + 相对等待」时,miss 的分数是

smiss=06000+wr2.5s_{\text{miss}}=\frac{0}{6000}+\frac{w_r}{2.5}

要让这条 miss 排到那条命中前面,需要 wr/2.5≥50w_r/2.5 \ge 50,即等约 127 秒。也就是说,它大致等得起,但那个时间尺度完全由别人的复用优势决定,而不是由自己的工作量或已经等了多少决定;洪流持续多久,它就要等同一量级的时间。论文的 flood 实验把这件事推到极限:LPM 下最老 miss 等了 123.9 秒,RAGCache 201.4 秒。

这就是 R3 必须写成「按工作量」而不是「按时间」的原因:只有工作量欠账能在步内给出与请求规模成比例的硬边界,等待时间只能给出一个随负载漂移的软排序。

Fair 车道:按到达顺序,与 Fast 车道按欠账合并

只有 Fast 车道还是不够:当一大批高命中请求同时到达(某份文件刚公开、或者 planner 同时发出几十个子调用),每条新请求的分数都远高于排队的 miss,miss 的等待就由「别人有多便宜」决定,而不是由自己等了多久。论文的 flood 实验就是构造这个最坏情况:先攒一分钟的 miss 积压,再灌入一串高命中请求。结果是 LPM 下最老 miss 等了 123.9 秒,PEEK 66.3 秒,RAGCache 201.4 秒。

Fair 车道按到达时间排队,把最老请求放在队头;真正的机制是两条车道按已经排入顺序的工作量合并,这是 stride scheduling 的思路:

A←A+w cr(Fast 车道),F←F+cr(Fair 车道)A \leftarrow A + w\,c_r \quad(\text{Fast 车道}),\qquad F \leftarrow F + c_r \quad(\text{Fair 车道})

每一步开始前,两条车道的欠账分别初始化为各自第一条请求的工作量(Fast 车道乘 ww,Fair 车道的第一条就是最老请求 oo,所以从 coc_o 起)。之后谁欠得少,谁排下一条,两条车道各自跳过已被对方排过的请求。取 w=4w=4,Fast 车道每排一个便宜命中就先背上 4 倍的工作量,于是它能插队的额度很快用光。

关键引理:最老请求前面最多有多少活

这是整篇论文最值得记住的一条,也是它敢说「有界」的依据。论文 Lemma 1 的结论是:设 a1,…,aka_1,\dots,a_k 是最老请求 oo 之前被排入的请求,W=∑icaiW=\sum_i c_{a_i} 是它们的工作量总和,则

W  ≤  cow+cak−ca1W \;\le\; \frac{c_o}{w} + c_{a_k} - c_{a_1}

证明(本文复述并核对):Fair 车道第一条必然是 oo,所以在 oo 被排入之前 FF 恒等于 coc_o。Fast 车道能排入最后一条 aka_k,说明排它之前那一刻 A≤FA \le F;而那一刻的欠账是

A=w(ca1+W−cak)A = w\bigl(c_{a_1} + W - c_{a_k}\bigr)

代入 A≤coA \le c_o 即得。这个证明只用到欠账,与打分函数无关——所以换成别的评分,界仍然成立。

如果 oo 前面这些请求工作量相同,cak=ca1c_{a_k}=c_{a_1},界就退化成 co/wc_o/w:w=4w=4 时就是最老请求自身工作量的 25%。这解释了两件事:为什么论文把 ww 说成「最老请求前面的便宜活上限」;以及为什么 flood 场景里 Fairway 的最老 miss 只等 22.0 秒,而 FCFS 是 22.5 秒、k-LPM 4 是 22.4 秒——它退化成了接近到达顺序,但没有退化到「完全不看缓存」。

从份额看,把欠账数到每一次 pick,Fair 车道拿到的是 w/(w+1)w/(w+1),w=4w=4 时即 80% 的工作量。这是「整个队列的合并排序」这一口径下的名义份额,不是每一步 GPU 实际执行的算力比例:真实一步会被预算 BB 截断,离散请求的大小也不整齐,实际执行前缀会明显偏离 80%(下面 1500 / 548 的算例就是如此)。它还只在单个调度步内成立,不是长期份额。

为什么份额恰好是 w/(w+1)

这一步可以自己推:设一次调度步里 Fair 车道排入的总工作量为 FF、Fast 车道为 WW。两条车道交替到队列排完,最后几次交替时两边的欠账必然在同一量级,取「刚轮到对方」的时刻近似有

w W≈Fw\,W \approx F

于是两条车道的名义份额是

FW+F=ww+1=80%,WW+F=1w+1=20%\frac{F}{W+F}=\frac{w}{w+1}=80\% ,\qquad \frac{W}{W+F}=\frac{1}{w+1}=20\%

这是 stride scheduling 的标准结果:每条车道按自己已经消耗的服务量推进计数器,份额与权重成反比。方向要说清:ww 调大,Fair 车道的名义份额变大,允许插到最老请求前面的便宜工作变少,保护更强、复用收益更小;ww 调小则相反。w=4w=4 是论文在所有负载上用的同一个值。

为什么欠账必须每步清零

这是全文最容易被读错的一处,也是它与其他「公平调度」实现最大的区别:欠账每次调度步重启,不跨步累计。约束的是「这一步里有多少便宜活能跑到最老请求前面」,而不是「长期算力怎么分」。一旦跨步累计,长期份额就真的变成 80%,而过载时队列不空,顺序会退化成接近 FCFS——论文明确说这会丢掉中位的优势。

这个选择的边界也写在论文里:一步的预算是 BB,所以界只能覆盖未缓存工作量 cc 约 wBwB 以内的最老请求——B=2048B=2048、w=4w=4 时是 8192 个未缓存 token。这不是 prompt 长度上限:论文评测里最长 prompt 到 16k(那是总长度 LL),是否超过这个范围取决于它命中了多少。更长的请求依靠相对等待:它等得越久分数越高,而新到请求的分数顶多比它的命中比例高一点,所以最终仍会浮到 Fast 车道顶部。论文在最长 16k 的 prompt 上没观察到饿死,最坏等待不超过该次运行 p99 的 2.3 倍——这是实验观察,不是跨步的形式化保证。

另外,让最老请求「在这一步开始」还需要 Appendix A 的 Corollary 1 三个条件同时成立:剩余步预算够(超过 co/wc_o/w 加一条请求)、KV 能容纳这些请求与它的首块且不驱逐其缓存前缀、每步请求数上限未达到。

手算一遍:6 条命中为什么只能插 5 条

论文 Figure 6 的例子是:最老请求 MM 要算 6000 个 token,后面还有六条命中,每条只要 300 个 token,w=4w=4,每步预算 B=2048B=2048。按算法逐步算:

步Fast 欠账 AAFair 欠账 FF决策
初始4×300=12004\times300=120060006000(最老请求)A≤FA \le F,Fast 排 H1H_1
224006000Fast 排 H2H_2
336006000Fast 排 H3H_3
448006000Fast 排 H4H_4
560006000A≤FA \le F,Fast 排 H5H_5
672006000A>FA > F,Fair 排 MM

前五条命中一共 1500 个 token,恰好等于 co/w=6000/4c_o/w = 6000/4,与引理一致;第六条命中要等 MM 排进去之后。放进 B=2048B=2048 的步预算里:1500 个 token 给命中,剩下 548 个 token 开始算 MM 的第一段,于是 MM 在这一步成为 running 请求,后续步优先续算。这就是「不饿死」在理想算例里的含义:不是把贵请求提前到第一位,而是保证它不再滞留等待队列;一般情形还要满足上面 Corollary 1 的三个条件。

同一算例换 w:保护强度与复用收益是同一个旋钮

把 ww 改成 2 和 8,用同样的队列(co=6000c_o=6000,六条命中各 300)重算一遍,就能看清这个旋钮在调什么:

ww初始 AA排在 MM 前的命中数前面的工作量占 coc_o 比例引理上界 co/wc_o/w
26006(全部)180030%3000
412005150025%1500
82400260010%750

w=2w=2 时六条命中全都能排在 MM 前面(1800 < 3000),复用收益最大、保护最弱;w=8w=8 时只有两条能插队,MM 几乎立刻开始,但便宜请求被压得更久。论文选 4,是在这两端之间取一个「让几条便宜命中先走、同时把最老请求的等待控制在其工作量约四分之一以内」的点——它把 ww 说成上限而不是「最优值」:换负载时最优 ww 会变,而论文的目标是「不调参也不崩」,不是「每个负载都最优」。(这张表是本文自算,论文只评测了 w=4w=4。)

评测怎么读:11 个场景、7 个基线,以及三个容易串的口径

平台是单张 A6000(48 GB)上跑 Llama-3.1-8B,论文使用的 vLLM 0.16.0 配置,ρ\rho 用未缓存 token 计,每条请求只生成 1 个 token(所以报的就是 TTFT)。基线包括 FCFS、LPM、k-LPM(k=4,8k=4,8)、RAGCache 的 cache-aware 重排、PEEK、Preble。所有方法共用同一套 eviction(PEEK 的 demand-aware 策略),所以差异只来自「先接谁」。

四个负载各自在考什么

论文的 11 个场景不是同一件事重复 11 次,每个负载都在压一个不同的维度:

负载prompt 规模缓存结构主要考什么
SEC QA1.2–1.5k20 份 10-Q,256 token 分块,取 top 5同长 prompt 下,命中深浅造成的差距(约一半是全命中)
SEC 长文档 QA1.0–13.2k整份文档,三种长度长度差异与命中差异叠加(相对等待的价值)
MuSiQue0.9–3.4k2.1 万段维基段落,取 top 11多跳问答下更分散的命中分布
Mooncake0.3–16k(缩放后)原始生产轨迹自带会话共享;评测保留 1/8 会话、长度乘 1/4真实到达的突发性与部分命中比例

公开 QA(LongBench、LooGLE)是另一组:它不控制 prompt 长度,按自然长度跑,主要看尾部在「长度不可控」时的表现。这四个负载的结论方向一致,但强弱不同——这也是论文强调「每个场景都对上最好的基线」而不是只报一个平均的原因。

口径一:8.6 倍只对「会饿死」的基线。 按上文那个实验判据(最坏 TTFT 超过该次运行 p99 的 3 倍),RAGCache 在 10 个场景里被判为饿死请求(最坏等待 16–365 秒),PEEK 在 3 个场景里被判为饿死;对这些基线,p99 的优势可以到 8.6 倍。而对不饿死的最好基线,优势是 2–18%(10 个场景更低,第 11 个基本持平:Mooncake 过载下 Fairway p99 27.57 秒,k-LPM 4 低 2%)。把 8.6 倍说成「普遍快 8.6 倍」是错的。

口径二:尖峰下的 6 倍是「中位对中位」。 FCFS 在尖峰里的中位是 5.1–5.9 秒,Fairway 是 0.82 秒,六到七倍;同时它的 p99 是 8.4 秒与 7.6 秒(分属两条不同的动态轨迹:一条 traffic surge、一条 topic shift,不要读成同一条曲线上的两个点),与 FCFS 的 7.8 秒同一档。这不是「比 FCFS 全面快 6 倍」,而是「付 FCFS 的尾部,拿复用优先的中位」。

口径三:p99 会掩盖极端值。 论文用「最坏 / p99」这一比值单独检查,Fairway 在所有场景不超过 2.3 倍。基线那边要分开读:RAGCache 在被判饿死的那 10 个场景里最坏等待是 16–365 秒;在第 11 个场景它的 p99 达到 162 秒。原文并没有把 162 秒与 365 秒配成同一场景的一对数字,这里也不这么写。

场景(论文 Table 4 摘录)Fairway p99k-LPM 4 相对 Fairwayk-LPM 8 相对 Fairway
SEC QA,ρ=0.9\rho=0.93.82 s+12%+42%
SEC QA,ρ=1.1\rho=1.110.55 s+22%+61%
traffic surge6.44 s+6%+14%
topic shift6.71 s+92%+19%
SEC 长文档 QA14.26 s+4%+3%
MuSiQue,ρ=1.1\rho=1.112.62 s+14%+10%
Mooncake,ρ=1.1\rho=1.127.57 s−2%+30%

注意这张表里的 6.44 秒与 6.71 秒是整条动态轨迹的 p99(含平稳段),不是尖峰窗口内的 p99;前面说的 8.4 / 7.6 秒才是尖峰窗口的。两个口径都来自论文,但不能互相替代。

flood 场景(一分钟 miss 积压 + 高命中洪流)是最能说明问题的一组:Fairway 把最老 miss 控制在 22.0 秒,代价是洪流请求的中位从 LPM 的 1.6 秒涨到 18.2 秒——与 FCFS 的 18.6 秒几乎一样。它不是找到了两全其美的顺序,而是明确选择「保护尾部、牺牲便宜请求的即时收益」,并在积压清空后把命中重新放回前面。

消融实验(论文 Table 2)把机制一个个加上去,能看清每一项在挡什么:

顺序topic shift p99(最坏等待)混合长度:短 p99混合长度:长 p99flood 最坏等待
只按命中比例5.9 s(62.9 s)3.1 s25.3 s201.4 s
+绝对等待6.7 s(7.9 s)13.6 s15.1 s33.4 s
+相对等待6.7 s(8.1 s)5.9 s20.2 s59.1 s
+Fair 车道(Fairway)6.7 s(7.9 s)8.6 s18.1 s22.0 s

这张表值得多看两眼:加上 Fair 车道之后,短请求的 p99 从 5.9 秒退到 8.6 秒(比「+绝对等待」的 13.6 秒仍好很多),换来长请求从 20.2 秒回到 18.1 秒、flood 最坏等待从 59 秒降到 22 秒。每一项机制都是拿一个指标换另一个指标,没有免费的午餐。

与相邻工作的差异:改的都是「先接谁」,但计量单位不同

方法排序依据公平怎么计量主要失效模式(论文实测)
FCFS到达时间不需要(不插队)中位被便宜命中拉高,尖峰到 5.9 s
LPM(SGLang)最长命中前缀无冷文档请求在洪流下可等上百秒,flood 最坏 123.9 s
RAGCache 重排命中/未命中比无10 个场景被判饿死,最坏 16–365 s
k-LPM复用优先,每 k 次插一条最老按次数k 小换场景失效(topic shift +92%),k 大丢中位(+42–61%)
Preble按命中比分组发名额按组份额不饿死,但 p99 比 Fairway 高 5–53%
PEEK命中节省的 prefill靠 eviction 保护等待块3 个场景饿死,另 4 个 p99 超 FCFS 两倍
Fairway命中比 + 相对等待,双车道按工作量合并按工作量欠账持续过载且命中只便宜一点时中位退让(MuSiQue 3.0 s vs 0.9 s)

这张表想说明的一件事:前面几种方法不是「做得不够好」,而是它们的公平计量单位(次数、组、秒)与真实成本(未缓存 token 数)不在同一量纲上——这才是 Fairway 唯一真正新增的东西。

在 P/D 分离与 chunked prefill 之间:它的边界由步预算决定

Fairway 的位置有几条硬约束,理解它们比记住倍数更有用。

第一,TTFT 的等待全在 prefill 节点上。 在 P/D 分离部署里,请求在 prefill 节点排队、prefill、算出首 token,然后把 KV 交给 decode 节点;论文的评测里每条请求只生成 1 个 token,所以报出的 TTFT 就是「等待 + prefill」,不含 KV 传输。真实系统里 KV 交接与 decode 排队会再加一段,这段不受 Fairway 影响。

第二,界的大小与步预算成正比。 引理给出的是「一步之内」的界,能覆盖的最老请求(按未缓存量 cc 计)约为 wBwB。B=2048B=2048、w=4w=4 时是 8192 个未缓存 token;如果为了别的目标把 BB 调小(例如为了压 decode 抖动而缩短每步),这个界的覆盖面会同比例缩小,超过它的请求就退回「靠相对等待浮上来」。换句话说,Fairway 的保护范围不是一个固定常数,它跟着引擎配置走。

第三,chunked prefill 让「开始」与「完成」分离。 长 prompt 被切成多步计算,所以「这一步让最老请求开始」只意味着它不再滞留等待队列,不等于 TTFT 已经兑现:TTFT 还包含后续所有分块的计算,直到首 token 产出。「开始得早」与「首 token 早」是两件事,前者是调度保证,后者还取决于预算与该请求的规模。

第四,它假设 eviction 是给定的。 论文让所有基线共用 PEEK 的 demand-aware 驱逐策略,目的正是把差异收窄到「排序」这一个变量。真实系统里排序与驱逐会互相影响:你越保护老请求,越可能需要为它保住缓存块;而保块又会挤压新请求的命中。论文把「与 eviction 联合优化」明确列为未来工作,也就是说这条耦合目前没有被解掉。

第五,cache-aware 路由会放大它要处理的分布。 路由器为了命中率会把共享前缀的请求送到同一节点,这会让该节点的队列里「命中率高度不均」——正是 Fairway 擅长的场景;但如果一个超热前缀把某台机器打满,任何准入策略都无法凭空变出算力。准入、路由、驱逐是三件不同的事,任何一件都不能替代另外两件。

它没有回答的三个问题

跨步的形式化保证。 引理只覆盖单个调度步内「最老请求前面有多少工作」,跨步的公平性依赖「相对等待只增不减」这个单调性,加上「新到请求的分数顶多比命中比高一点」这个经验事实。论文用「最坏等待 ≤ 2.3× p99」作为经验证据,但这不是「任意到达序列下都有界」的定理。

多租户的权重。 论文的耐心对所有请求一视同仁,只按自身 prefill 时长缩放。真实服务里不同客户有不同截止时间要求,这意味着 SLOr\mathrm{SLO}_r 需要一个租户维度的乘子——而一旦引入这个乘子,ww 与耐心的「一套参数通吃」就不再成立,需要重新验证。

超过 wBwB 的大请求,以及多机 prefill。 论文的最长 prompt 到 16k,靠相对等待兜住;如果一类请求的未缓存量常态就在 32k 以上(长文档问答、整库 RAG),单步界覆盖不到它,行为退回到「等待驱动的软排序」。多 GPU 的 prefill 实例、跨实例的路由与迁移也都在未来工作里。

一页速查:九个判断

  1. 先量队列内未缓存 token 的 P90/P10。 接近 1 时任何顺序的差别都很小;上到两位数、并且有请求等到分钟级,这类调度才值得做。
  2. 8.6 倍与 2–18% 是两个口径。 前者只对「会饿死请求」的复用优先基线,后者才是对不饿死的最好基线,且只在 10 个场景成立。
  3. 尖峰里的 6 倍是「中位对中位」。 它的尾部与 FCFS 同一档,收益来自「便宜命中不用排在贵请求后面」。
  4. 80% 是排序口径下的名义份额,不是每步实际执行比例,也不是长期算力分配。 预算截断会让实际前缀偏离它。
  5. 它不是吞吐优化。 收益全部在 TTFT 分位数上;吞吐仍由算力、步预算与缓存容量决定。
  6. 混部时先校准服务率。 耐心依赖「空闲引擎的 prefill 时间」画像,decode 抢资源会让它整体偏乐观;资源隔离是可选的前置手段,不是论文验证过的必要条件。
  7. 命中查询成本决定它能不能按步跑。 远端 KV 池要走网络时,先把查询批量化,否则排序再怎么便宜也白搭。
  8. 它是几行排序代码,不是一个新系统。 论文在 vLLM 0.16.0 上只替换等待队列的准入顺序;换版本、换卡、换模型仍要自己验兼容。
  9. 别把论文数字当自家预期。 全部结论来自单卡实验,上线前必须用自己轨迹复测 topic shift 与 flood 两类场景。

代价、边界与论文没做的事

代价是明确写出来的。 在 MuSiQue、ρ=1.1\rho=1.1 的持续过载下,Fairway 的中位是 3.0 秒,LPM 是 0.9 秒,换来的是 p99 12.6 秒对 14.2 秒。原因也直白:队列长期不空时,老请求的相对等待会压过「部分命中只便宜一点」的优势。反过来,在复用深或队列短命(busy、burst、spike)的场景里,它保持 LPM 的中位。如果去掉等待项,中位会回到 LPM 水平,但 p99 在 MuSiQue 上高 37%、Mooncake 上高 12%。

开销可以忽略(在论文的设置下)。 重排等待队列本身在中位队列长度 7 时是 0.02 ms,在最大 509 时是 0.6 ms;论文随后把「加上缓存前缀查询」的完整开销报为典型队列低于步长(106–355 ms)的 0.1%、并发上限时 1–3%。两个数字要分开读:0.02/0.6 ms 只是排序,0.1%/1–3% 才是含查询后的相对开销。

什么时候不该用它

  • 队列很少形成(论文的观察是 ρ<0.8\rho<0.8 时队列几乎不积压):此时各种顺序给出的 TTFT 很接近,改调度主要增加复杂度。
  • 请求长度与命中都均匀:没有「便宜 vs 贵」的结构,双车道退化成近似 FCFS,收益很小。
  • 缓存不在本机、命中查询要走网络:每步重排的成本会被放大,需要先把查询批量化。
  • 有严格先来后到语义的多租户场景:某些合规或计费设计要求 FIFO 可解释性,此时「老请求可以被便宜请求插队(有界)」这件事本身就需要业务侧确认。

把这几条与前面的「什么时候该用」合起来看,它其实是一个很窄的工具:只在「缓存命中高度不均 + 队列真的会积压 + 命中有明确的经济价值」三条同时成立时才值得上。

范围限制(论文自己列出的):只测了单张 GPU 的单模型 prefill 节点;超过 wBwB 的请求靠相对等待而非硬界;eviction 用的是 PEEK 的策略,不是本文贡献;Mooncake 轨迹为塞进一张卡做了缩放(见 Appendix B),所以它的绝对值不能直接当生产预期;未来工作包括把界扩展到「一步装不下」的大请求、多 GPU prefill 实例,以及与集群路由、eviction 的联合优化。

还有一处需要读者自己保持警惕:论文的「不饿死」判据是相对该次运行 p99 的 3 倍,这是合理的工程判据,但不是形式化的无饥饿证明。界(Lemma 1)只保证单个调度步内老请求前面最多有 co/wc_o/w 加一条的工作量,跨步的公平性靠的是「相对等待只增不减」这个单调性。

工程含义:这类调度器该在什么位置接进去

  1. 它改的是「准入顺序」,不碰缓存结构。论文把它作为 vLLM 0.16.0 scheduler 里 waiting queue 的重排 hook 实现,与 chunked prefill、eviction、preemption 共用同一套机制并协同工作;这不等于「换到任何部署都天然兼容」,其他版本、模型与多机配置仍需自己验证。
  2. 它需要一次性的 prefill 时间画像。est(⋅)\mathrm{est}(\cdot) 每块 GPU 只测一次,用来算耐心。这意味着换模型、换卡、换精度都要重测,否则耐心尺度会错。
  3. 它与路由层是互补的,不是替代的。cache-aware 路由会故意把共享前缀的请求送到同一节点,这恰好会加剧「同一队列内命中率高度不均」——也就是 Fairway 要处理的那种分布。反过来说,路由器如果把一个超热前缀集中到一台机器,任何准入策略都无法凭空变出算力。
  4. 判断该不该上,先量三个数:队列内未缓存 token 的 P90/P10 比值、全命中请求占比、以及 miss 在过载时的最坏等待。比值接近 1 时,任何顺序都差不多(论文说 ρ<0.8\rho<0.8 时队列很少形成);比值上到两位数、且有请求等到分钟级时,这类调度才有意义。
  5. 不要指望它提升吞吐。它是延迟分配策略:论文的收益全部体现在 TTFT 的分位数上,吞吐由算力与预算决定。

复现时最容易踩的三个坑

  • 块大小决定命中粒度为 16 token。 你按字符去对齐「共享前缀」会得出偏乐观的命中率;论文所述实现是按块链式匹配,一个块不同,后面全部作废。自己写脚本对账时要用块,不要用 token 位置。
  • 步预算随硬件与版本变。 论文提到同一份 vLLM 在小显存卡上 B=2048B=2048、在 H100 级上是 8192,而它自己用的是 2048。换成 8192 后,界能覆盖的最老请求从 8192 个未缓存 token 变成 32768 个,同样的调度器行为会明显不同——这不是实现 bug,是口径变了。
  • 不压 KV 容量,现象会明显减弱。 论文把缓存压到只放得下整条轨迹可复用块的四分之一到三分之一,eviction 频繁,才会出现「等得越久、命中越差」的耦合。缓存富余且工作集稳定时,因驱逐造成的命中损失会减少,调度带来的差异也随之减弱(首次访问与新文档的 compulsory miss 仍然存在)。

还有一条不算坑但容易误读:论文每条请求只生成 1 个 token,所以「TTFT」里没有 decode 的成分。真实服务里 decode 与 prefill 共享 SM(除非做了 Green Contexts 一类的资源隔离),算力压力会更高,绝对值不可直接照搬。

两个容易被忽略的实现假设

  • prompt 入队后不再变化。 RAG 是「先检索、拼好、再送」,符合这个假设;如果应用在流式追加工具输出、边生成边改前缀,那么 hrh_r 在等待期间就会失效,每次变更都要重新算命中并重新入队。对这类负载,「按步重排」带来的收益会被重新对齐的成本吃掉一部分。
  • 命中查询足够便宜。 排序本身只要 0.02–0.6 ms,前提是命中查询也是本机内存操作(论文报的含查询开销是典型队列的 0.1% 以下)。如果缓存跨节点(远端 KV 池),一次查询要走网络,每步重排就从「可忽略」变成「必须批量化」,整个设计的前提要重新评估。

还有一条与资源隔离相关:论文假设 decode 不会在同一个 SM 上与 prefill 抢资源(它把 prefill 节点单独拿出来测)。真实混合部署里,prefill 的实际服务率会被 decode 拖低,此时「按未缓存 token 计的 ρ\rho」需要重新标定,否则耐心的尺度会整体偏乐观。

如果我要复现,会按这个顺序验

  • 先固定一个基线环境:vLLM 0.16.0 + 单卡,B=2048B=2048,KV 容量压到只放得下 1/4–1/3 的可复用块,让 eviction 真的发生(否则整个现象明显减弱)。
  • 用论文的四个负载里最容易被外部复现的两个:SEC 10-Q 的 KG-RAG 数据集与 MuSiQue(都能公开取到),按 Zipf α=0.9\alpha=0.9 + 泊松到达合成请求序,先在 ρ=0.9\rho=0.9 上对齐 FCFS 的中位与 p99。
  • 造一条 60 秒尖峰轨迹,检查三件事:FCFS 的 p99 是否在 8 秒量级、复用优先的 p99 是否上到十几秒、它们的中位是否相差六倍以上。三个都复现不出来,说明环境和论文差太远,后面的对比没有意义。
  • 再验 flood:这个实验最能区分「真的按工作量记账」与「只是加了一个等待项」——只加等待项时最坏 miss 会停在 59 秒附近,加了 Fair 车道才会掉到 22 秒附近。
  • 最后才看 11 个场景的完整对比。论文的核心主张是「一套参数、11 个场景里 10 个不输」,这个主张只能靠全场景矩阵证伪,单场景调出来的好数字不算。

本站没有做上述复现,本文所有性能数字都是论文口径的转述;上表中的算例(1500 与 548、co/wc_o/w)是本文按论文参数自行推导,论文正文给出的对应描述是「五条命中排在 M 前面,共 1500 token,约为其工作的四分之一」。

它怎么定「赢了」:六目标法

这篇论文在「怎么算赢」上有一个值得借的做法:它不报一个综合分,而是给每条动态轨迹定六个目标——平稳、突发、尖峰三段的中位要对上 LPM(±10%),三段的 p99 要对上 FCFS(±10%)。理由是这两个基线分别代表两个极端,任何「同时不输给两边」的调度才算真的自适应。

结果是 Fairway 在两条动态轨迹上六个目标全中,没有任何基线超过四个。这个指标设计比「平均 TTFT 降了百分之几」有用得多:它把「你在哪一段赢了、哪一段输了」摊开,读者能自己判断自己的流量更像哪一段。

三个常见追问

「是不是把 FCFS 换成它就行了?」 不是。先看两个前提:队列内未缓存工作量是否有两位数以上的差距、队列是否真的会积压(论文的观察是 ρ<0.8\rho<0.8 时几乎不积压)。两个都不成立时,各种顺序的差别很小,改调度只是增加维护面。

「为什么不直接用最短作业优先(SRPT)?」 因为 SRPT 优化的是「平均等待」,长请求可能永远排不上。Fairway 的 R3 是在给这件事设保底:一步之内,最老请求前面最多 co/wc_o/w 加一条的工作量。但注意这是步内界的经验效果:论文在最长 16k 的评测里没有观察到饿死,并不意味着对任意到达序列都有无饥饿证明。

「8.6 倍能拿去做对外承诺吗?」 不能。它只对应「会饿死请求」的复用优先基线;对不饿死的最好基线是 2–18%,而且全部数字来自单张 A6000 + Llama-3.1-8B、每条请求只生成 1 个 token 的实验设置,本轮没有任何本站实测。

实验设计里几个可以照搬的做法

  • 先冻结再复测。 论文在一条 SEC 轨迹上调参,然后把参数冻结,换新 seed 的 SEC、MuSiQue、Mooncake 上跑。这避免了「在同一批数据上调参、同一批数据上报」的常见问题。
  • 控制变量到只剩一个。 所有基线共用同一套 eviction、同一套 running 处理与抢占逻辑,差异只允许来自「先接谁」。
  • 用比值判饿死,而不是用绝对阈值。 「最坏 TTFT > 3× 该次运行 p99」这个判据把不同场景的量级差异消掉了,也让「p99 好看但有个别请求等了几分钟」这类情况无法藏起来。
  • 消融按压力场景设计。 三个压力(topic shift、混合长度、flood)分别对应三条需求,加一个机制看一个指标——比「全量加完再看总收益」更能说清每个部件的职责。
  • 限制要写清位置。 单卡、单模型、只测 prefill 节点这些在评测节明说,Mooncake 的缩放细节在 Appendix B——读者要能顺着一句话找到它,而不是被埋在脚注里。

一个更贴近生产的读法:RAG 与 agent 是两种不同的分布

论文同时用了 RAG 基准和 Mooncake 的 agent 轨迹,但这两类负载「为什么会命中」完全不同,收益来源也不同:

  • RAG 的命中来自文档热度。 一批文档被反复检索,命中率由外部事件决定:某份财报刚发布,所有人都问它,缓存瞬间变热;过一阵没人问,命中率回到基线。论文的 topic shift 实验就是把这件事压缩到 300 秒里——40% 的请求转向冷门文档,SEC 上的 miss 比例从 17% 升到 24%。对这类负载,Fairway 的价值主要是别让冷文档上的请求在洪流里等上几分钟。
  • agent 的命中来自会话本身。 每轮把历史与工具输出重发,命中长度通常随轮次增长;每轮还会产生一段新的未缓存尾部,其长度取决于当轮新增的历史与工具输出(工具输出可长可短,不是必然递增)。Mooncake 里 58% 的会话请求、65% 的工具请求是部分命中。对这类负载,Fairway 的价值是别让一条长会话的第一步把整个队列堵住。

这个区分对工程判断有用:如果你的流量以 RAG 为主,重点看 topic shift 那类「命中率骤降」的场景;如果以 agent 为主,重点看长会话尾部与 flood(同一上下文被大量并发子调用复用)的场景。同一套参数在两类负载上的表现并不相同,论文的结论是「11 个场景里 10 个不输、1 个基本持平」,不是「都最优」。

与「SM 资源隔离」那类工作的关系

2026-11-10 那篇拆的 GC-MoE 解决的是「通信与计算抢同一批 SM」,用 Green Contexts 把 SM 划成不相交的分区。Fairway 解决的是「同一批 SM 上,先算谁的请求」——两者作用在完全不同的层面:

  • 资源隔离决定「有多少算力可分配」,它改变的是 μcapacity\mu_{\text{capacity}};
  • 准入调度决定「这些算力先给谁」,它改变的是等待的分配。

一个直接推论:如果 decode 与 prefill 混跑,prefill 的实际服务率会被 decode 拖低,Fairway 里按闲置引擎画像得到的 est(⋅)\mathrm{est}(\cdot) 就会偏低,耐心整体变乐观。所以混部部署里先校准服务率、或评估是否需要资源隔离,再调准入顺序;这只是本文的推论,不是论文验证过的必要条件。

小结

前缀缓存把一件直觉上简单的事变复杂了:请求的「大小」不再是 prompt 长度,而是「轮到它时还没被算过的 token 数」,而这个数取决于调度顺序本身。于是调度器同时控制两件事——谁先走,以及每个人要付多少——这就是为什么 FCFS 与复用优先会在中位与尾部上各赢一半,也是为什么「按次数」或「按秒数」记公平都不够。

Fairway 的答案是两点:用 h/ch/c 加相对等待决定「便宜的、等急了的先走」,用双车道工作量记账把一步之内排在最老请求前面的便宜活压到约其自身工作量的 1/w1/w(w=4w=4 时约四分之一;严格界还要加上首末请求工作量之差,只有插队请求工作量相等时才恰好是四分之一)。它的收益是有条件的——对不饿死的最好基线是 2–18%,在尖峰里是「付 FCFS 的尾部换复用优先的中位」;它的代价也是明确的——持续过载且命中只便宜一点时,中位会明显退让。

回到开头那个场景:一万多 token 在缓存里、只差几十个 token 的那条请求,应该先走;但「先走」的额度必须有限,否则另一条只命中系统提示词的请求会排很久。有界地让便宜的先走——这七个字是整篇论文的核心,也是它比「换一个更好的缓存」更难做到的地方:它要求调度器同时回答「多快」与「多公平」,而且不给你按负载换档的机会。

📋 来源与核验记录

本轮逐条打开并核对的一手来源(2026-11-11 读取;论文数字均指 2026-11-01 提交的 v1):

  1. Fairway 论文摘要页:https://arxiv.org/abs/2611.02082 (arXiv:2611.02082v1,cs.DC,2026-11-01 提交;作者 Hamidreza Alikhani、Nazmul Takbir、Matin Khajavi、Rajat Bhattacharjya、Sangeetha Abdu Jyothi、Nikil Dutt;UC Irvine 与 Apiphany)
  2. Fairway 论文 HTML 全文:https://arxiv.org/html/2611.02082v1 (§3 的 70–250× 与 100× 两个口径、R1–R4、§4 评分公式与 Algorithm 1、Lemma 1 与 Appendix A 的界和 Corollary 1 条件、§5 全部评测数字与 Table 1/2/4、§5.6 开销、Appendix B 的负载与 Mooncake 缩放、Appendix C 的 eviction 说明)
  3. vLLM 官方仓库:https://github.com/vllm-project/vllm (前缀缓存与 PagedAttention 的块式 KV 管理实现;论文评测版本 vLLM 0.16.0)
  4. PagedAttention 论文(vLLM 的缓存与分页基础):https://arxiv.org/abs/2309.06180 (Kwon 等,SOSP 2023)
  5. SGLang 论文(radix tree 前缀复用与 LPM 策略的出处):https://arxiv.org/abs/2312.07104 (Zheng 等,NeurIPS 2024)
  6. Mooncake 论文(生产 agent 轨迹与 KV 中心化架构):https://www.usenix.org/conference/fast25/presentation/qin (Qin 等,FAST 2025)
  7. Sarathi-Serve 论文(chunked prefill 与步预算的出处):https://arxiv.org/abs/2403.02310 (Agrawal 等,OSDI 2024)

本文自行推导的部分(不与论文数字混列):1k/10k prompt 的 prefill 时间换算(约 7.1k token/s)、由 est\mathrm{est} 推出的耐心 1 s / 4.2 s / 2.5 s、co/w=1500c_o/w=1500 与步内剩余 548 token、wB=8192wB=8192 的上界、w=2/8w=2/8 对照表、ρ\rho 算例(3.2 req/s 与 1.8)。经典排队论与调度结论(M/G/1、SPT/SRPT)只作直觉引用,不是论文结论。本站未对 Fairway 做端到端实测,所有延迟数字(含 8.6×、6×、2–18%、22.0 s 等)均为论文在单张 A6000 + Llama-3.1-8B 上的报告值,不同硬件、模型与负载下不应直接套用。