Prefix Cache 路由：概率调度与平滑切流

Prefix Cache 路由先根据 cache 和负载计算调度得分，生产系统还要决定这些分数对应怎样的流量分配。每次都选择当前最优项会把暂时的分数优势放大成持续的流量集中。少数实例或部署逐渐成为热点，新部署也难以获得足够流量建立 cache。因此，调度既要把得分转换成平滑的路由概率，也要在部署切流时让流量和 cache 逐步迁移。

基于部署权重的流量比例

生产系统通常允许人工调整各部署的权重，以控制它们的流量比例。灰度发布就是一个典型用途：新部署先接收少量流量，验证通过后再逐步提高权重，直到替换旧部署。部署级调度负责落实这组比例，实例级调度再在选定部署内根据 cache、排队和容量选择实例。

如果部署之间不区分权重差异，router 就会把所有实例放进同一个候选集，各部署的流量比例只由实例数量和得分决定。假设部署 A 有 2 个实例，部署 B 有 8 个实例，并且所有实例得分相同，B 就会获得 80% 的流量。如果目标是按实例均匀分配，这正符合预期。但若希望两个部署各承担 50%，便不符合预期。

存在部署比例配置时，请求概率需要按两层计算。设 $d$ 表示部署， $i$ 表示部署内的实例：

P(d,i\mid r,t)=P(d\mid r,t)P(i\mid d,r,t)

$P(d\mid r,t)$ 根据部署权重确定请求进入部署 $d$ 的概率。 $P(i\mid d,r,t)$ 再把这部分概率分配给部署内的实例，并且所有实例的条件概率之和为 1：

\sum_{i\in d}P(d,i\mid r,t) =P(d\mid r,t) \cdot\underbrace{\sum_{i\in d}P(i\mid d,r,t)}_{=1} =P(d\mid r,t)

因此，部署内所有实例的概率相加后，仍然等于请求进入该部署的概率。实例级的 cache 和负载可以改变由哪个实例处理请求，但不会改变部署 $d$ 分到的总流量。

从计算成本到调度概率

选定部署后，实例选择可以从 least workload 出发，将已有任务的剩余工作与当前请求的新增工作统一为成本。接下来要决定的是：成本更低的实例，应获得多少流量。

基于阈值截断的随机选择

以 RTP-LLM 的 FlexLB Prefill 策略为例，实例成本 $S_i$ 由当前请求考虑 cache 命中后的 Prefill 时间、已有 Prefill 的剩余时间和 router 组 batch 等待时间组成，数值越小越优。通过可用性和容量检查后，以最低分 $S_{\min}$ 为基准，默认保留满足下式的实例：

S_i-S_{\min}\le \max\left(0.1S_{\min},20\text{ ms}\right)

FlexLB 在这个范围内均匀随机选择。阈值内的分差不再影响选择概率，超过阈值的实例则不参与本次选择。

基于指数衰减的调度概率

若希望成本差连续影响流量比例而非阈值截断，可以让实例之间的概率比随成本差按指数衰减。

以两个实例为例，固定最低成本 $S_{\min}=100$ ms，观察另一实例的成本上升时，两种策略的选择概率。此时截断阈值为 20 ms，指数衰减参数也取 20 ms。

阈值截断与连续衰减

阈值截断指数衰减

成本差 0 ms · 截断 50.0% · 衰减 50.0%

将实例 $i$ 的选择概率记为 $p_i$ 。上图的衰减参数 $\Delta$ 控制概率随成本差变化的快慢：约定成本差每增加 $\Delta$ ，高成本实例与低成本实例的选择概率之比减半。图中 $\Delta=20$ ms，两实例的成本相差 20 ms 时，选择概率分别为 $1/3$ 和 $2/3$ 。这项规则写成：

\frac{p_i}{p_j} =2^{-(S_i-S_j)/\Delta}

概率比确定后，再要求所有候选实例的概率之和等于 1，便得到：

p_i= \frac{2^{-S_i/\Delta}} {\sum_j2^{-S_j/\Delta}}

其中 $j$ 遍历所有候选实例。该式等价于对负成本做 softmax。

为了看清 $\Delta$ 如何影响流量分配，将两个实例的成本差固定为 40 ms，只改变 $\Delta$ 。两条曲线分别表示最低成本实例和另一实例的选择概率。横轴是 $\Delta$ ，沿横轴向右看，可以看到两者从选择明确逐渐趋向选择均匀，即 $\Delta$ 越小，流量越集中在低成本实例。 $\Delta$ 越大，实例间的概率越接近均匀分配。

Δ 与流量分散

最低成本实例另一实例

Δ 20 ms · 最低成本 80.0% · 另一实例 20.0%

之所以用底数 2 只是为了让 $\Delta$ 容易解释。令 $\tau=\frac{\Delta}{\ln 2}$ 便有 $2^{-S_i/\Delta}=e^{-S_i/\tau}$ 。

这条曲线也可以从调度目标推导：总是选择最低成本实例等价于最小化期望成本 $\sum_i p_iS_i$ ，总是均匀分配又会忽略成本。为了兼顾两者，可以在期望成本之外加入流量集中的惩罚。

用 $u$ 表示均匀分配的概率，KL 散度衡量实际概率 $p$ 偏离 $u$ 的程度：

\mathrm{KL}(p\Vert u) =\sum_i p_i\ln\frac{p_i}{u_i}

KL 散度也叫相对熵。它先计算各实例的概率比 $p_i/u_i$ ，取对数后，再按实际选择概率 $p_i$ 加权求和。因此 $p=u$ 时取 0，而概率越偏离均匀分配，数值越大。

以两个实例为例，柱形表示实际概率，叠加的虚线框表示均匀分配时的 0.5，下方曲线显示在 A、B 给定实际概率下的 KL 散度。

流量越集中，KL 越大

实际分配 p 均匀分配 u

调度目标可以写成：

p^*=\operatorname*{argmin}_{p} \left[ \sum_i p_iS_i +\tau\,\mathrm{KL}(p\Vert u) \right], \qquad p_i\ge0,\quad \sum_i p_i=1

第一项降低预期请求成本，第二项限制实例流量偏离均匀分配。 $\tau>0$ 决定两者的取舍：越小越偏向低成本实例，越大越重视流量分散。

该目标的最优解满足 $p_i^*\propto u_i e^{-S_i/\tau}$ 。由于 $u$ 均匀，归一化后正是前面的指数衰减公式。完整证明见附录。

部署切流与调度的联系

新部署需要请求来建立 cache，一次转入过多流量又会集中触发重算。更合理的做法是先让少量请求在新部署建立 cache，从而让相同前缀的后续请求更多地转入。调度根据前缀的命中情况自动调整部署分流，既能推进迁移，也能分散预热期间的重算开销。

假设旧部署 A 已经有 cache，新部署 B 仍然是冷的。将当前请求在部署 $d$ 的前缀命中比例记为 $H_d$ ，在配置权重上加入命中率的影响：

P_d= \frac{w_d2^{\lambda_hH_d}} {\sum_k w_k2^{\lambda_hH_k}}

其中 $P_d$ 是选择部署 $d$ 的概率， $k$ 遍历候选部署， $\lambda_h$ 控制对 cache 命中的偏好。 $\lambda_h=10$ 时，其他条件不变，命中比例每提高 10 个百分点，该部署与其他部署的概率比翻倍。

取 $\lambda_h=10$ ，将配置权重设为 $w_A:w_B=1:9$ 并保持不变。对于 A 完整命中、B 完全未命中的前缀，请求进入 B 的概率只有：

P_B=\frac{9}{2^{10}+9}\approx0.87\%

两边都没有 cache 的新前缀仍按配置权重分配，其中 90% 会进入 B。已经在 A 上有 cache 的前缀则大多留在 A，少量请求进入 B 并完成第一次 Prefill。B 建立这份 cache 后，两边的 cache 收益相同，后续流量便回到配置的 1:9。每个前缀都经历同一过程，切流所需的 cache miss 因而分散在整个迁移期间。

保持旧部署完整命中，调整 $\lambda_h$ 和部署权重，可以看到新部署的选择概率如何随命中比例变化：

命中变化与流量转移

新旧部署权重比 9:1 cache 偏好 λ_h 10

仅按配置权重加入命中率

命中 0.0% · 新部署 0.9%

这样，流量可以随着新部署的预热逐步转移，减少集中 cache miss 带来的命中率波动。不过，命中率平稳还不等于延迟平稳。如果大量请求仍留在旧部署，即使命中率很高，也可能因为排队而增加延迟。此时需要让部署负载参与分流：当等待的代价超过保留 cache 的收益，就应允许更多请求进入新部署。

最终能否下线旧部署，要看新部署承接全部流量后，能否在承担额外重算的同时满足延迟要求。若旧部署的 cache 消失后增加的计算量可以接受，就无需等待所有前缀完成预热。确认新部署能够承接后，将旧部署权重设为 0，等待已有请求完成，就可以下线旧部署。总之，下线依据是失去旧 cache 后的服务表现，而非 cache 是否全部迁移。

具体来说，低频前缀通常直接忽略，下次访问时重算，但也要评估长前缀重算对单次请求延迟的影响。热门前缀若仍只能在旧部署命中，可以定向回放这些请求到新部署预热。如果一些前缀因 LRU 淘汰而反复 miss，不能当作是低频前缀而忽略，需要按重算压力评估部署的承载能力。

将部署级的命中偏好与实例级的指数采样组合，完整的选择概率为：

P(d,i\mid r,t)= \underbrace{ \frac{w_d2^{\lambda_hH_d}} {\sum_k w_k2^{\lambda_hH_k}} }_{P_d} \cdot \underbrace{ \frac{2^{-S_i/\Delta}} {\sum_{j\in d}2^{-S_j/\Delta}} }_{P_i}

部署权重给出分流基准，前缀命中决定迁移时对这个基准的偏离，实例成本决定进入部署后的请求由谁执行。实例概率在部署内合计为 1，因此局部选择不会额外改变部署已经分到的流量。

结语

least workload 加概率平滑，为 Prefix Cache 路由提供了一套通用的设计思路。前者判断请求在哪里处理更划算，后者决定这份成本优势值得集中多少流量。调度既要利用实例的性能优势，也要控制流量集中所付出的代价。

平滑切流是在用少量当前重算换取后续请求的复用。对已有 cache 的偏好越强，当前命中越容易保留，但新部署获得预热请求的机会也越少。概率规则需要同时为复用和预热留出空间，而不能只优化眼前的一次命中。

附录：指数采样的最优性证明

证明最优性，需要找到所有可行解都无法低于的目标值，并证明指数分布恰好达到它。将目标写成“常数 + 非负项”，就能同时完成这两件事。

给定有限个候选实例、各自的成本 $S_i$ 和参数 $\tau>0$ 。参考分布 $u$ 满足 $u_i>0$ 且 $\sum_i u_i=1$ 。这些量在求解时保持不变，待求的是选择概率 $p$ ：

\sum_i p_iS_i+\tau\,\mathrm{KL}(p\Vert u), \qquad p_i\ge0,\quad\sum_i p_i=1

这里使用 KL 散度的非负性： $\mathrm{KL}(p\Vert q)\ge0$ ，且仅在 $p=q$ 时取等号。

利用 $x=\ln e^x$ ，先合并成本项与 KL 中的对数项：

\begin{aligned} \sum_i p_iS_i+\tau\sum_i p_i\ln\frac{p_i}{u_i} &=\tau\sum_i p_i\left(\frac{S_i}{\tau}+\ln\frac{p_i}{u_i}\right)\\ &=\tau\sum_i p_i\ln\frac{p_i}{u_i e^{-S_i/\tau}} \end{aligned}

每个实例 $i$ 都对应一个 $u_i e^{-S_i/\tau}$ ，这些值之和不一定为 1。为了构成概率分布，将每个实例对应的值除以所有候选实例对应值的总和 $Z$ ，定义候选解：

Z=\sum_j u_j e^{-S_j/\tau}, \qquad p_i^*=\frac{u_i e^{-S_i/\tau}}{Z}

由定义可知 $u_i e^{-S_i/\tau}=Zp_i^*$ ，将它替换到刚才合并后的分母中，再用对数的商法则展开：

\begin{aligned} \tau\sum_i p_i\ln\frac{p_i}{u_i e^{-S_i/\tau}} &=\tau\sum_i p_i\ln\frac{p_i}{Zp_i^*}\\ &=\tau\sum_i p_i\ln\frac{p_i}{p_i^*} -\tau\ln Z\sum_i p_i\\ &=\tau\,\mathrm{KL}(p\Vert p^*)-\tau\ln Z \end{aligned}

最后一步使用了 $\sum_i p_i=1$ 。因此，对任意可行的 $p$ ，都有：

\underbrace{\sum_i p_iS_i+\tau\,\mathrm{KL}(p\Vert u)}_{\text{原目标}} =\underbrace{-\tau\ln Z}_{\text{常数}} +\underbrace{\tau\,\mathrm{KL}(p\Vert p^*)}_{\text{非负项}}

$Z$ 只由给定的量决定。根据 KL 非负性，目标值不低于 $-\tau\ln Z$ ，而 $p=p^*$ 时恰好取到这个值，因此候选解确实最优。以上各式中， $p_i=0$ 的项按极限取 0。

正文采用均匀参考分布，各项 $u_i$ 相同，在分子与分母中抵消：

p_i^* =\frac{u_i e^{-S_i/\tau}}{\sum_j u_j e^{-S_j/\tau}} =\frac{e^{-S_i/\tau}}{\sum_j e^{-S_j/\tau}} =\frac{2^{-S_i/\Delta}}{\sum_j2^{-S_j/\Delta}}, \qquad \tau=\frac{\Delta}{\ln 2}