前缀缓存为何漏掉相同请求？并发复用与单飞协调实战

在自研 Rust LLM 推理引擎 mini-vllm-rs 中启用前缀缓存后，两个完全相同的请求同时抵达冷缓存，却一个 token 都没复用，双双执行了完整的预填充。问题出在缓存页的可见性时机：只有当请求完成时才发布可复用页，而两个请求都在对方发布之前就到达了。

这一冷启动失效引出了三个递进的设计决策：缓存页何时可见、其他请求是否需要等待、等待何时结束。

冷缓存问题与第一个基准测试

作者在 Mac mini 的 Metal GPU 上测试了 4-bit 量化的 Qwen2.5 0.5B 模型，缓存页大小 16 token，重复运行 3 次。初次复用基准对比了两种情况：

工作负载	结果
复用已预热的文档前缀	恢复 904 个输入 token 中的 880 个，首 token 延迟（TTFT）降低 96.2%
4 个相同请求同时到达冷缓存	全部恢复 0 token，执行完整预填充

这组数据说明，前缀缓存的优势在热路径上已经非常明显，但冷启动并发的场景下完全失效。问题的症结很明确：缓存的发布策略与并发到达的执行顺序之间存在竞态，而原始的“请求完成才发布”策略无法覆盖这种场景。

前缀缓存（prefix caching） 是 LLM 推理中复用注意力键值缓存（KV cache）的一类技术。在自回归解码中，每个 token 的注意力都需要其前面所有 token 的 Key 和 Value 向量，而这些向量对相同的前缀是确定的、可复用的。前缀缓存把提示词按固定大小（本文中为 16 token）切分为缓存页（cache page），每页对应一段 KV，并为其建立哈希索引。当新请求到达时，引擎逐页比对输入 token，命中即可直接引用这些已算好的 KV 页，跳过对应的预填充计算。这对多轮对话、RAG 中重复的长文档、以及批量相似提示词（如评测、分类）收益巨大，因为预填充往往占据首 token 延迟（TTFT）的主要部分。其关键约束是：缓存页必须在计算完成之后、且被正确发布之后才能被其他请求看见，可见性时机直接决定了并发场景下能否命中。

增量发布：边生成边共享

作者引入增量发布（incremental publication）：每次批量前向完成后，引擎立即将新完成的缓存页发布出去，使得它们在当前请求仍在生成时就可被复用。

测试方法是先启动一个请求，等它返回第一个输出 token 后，在其继续生成剩余 128 个 token 输出的过程中，提交更多相同提示词的请求，观察它们能否复用已缓存的前缀。结果是每个跟随请求恢复了 493 个提示词 token 中的 480 个。

在 2、4、8 个并发请求的组别中，相比“完成才发布”，增量发布的平均 TTFT 下降了 48–93%。不过，增量发布并没有消除冷同时到达的重复计算：请求可能只找到部分前缀，甚至什么都找不到，仍然需要自己计算剩余部分。复用与否取决于执行顺序和发布时机。

要消除这个竞态，需要决定“谁来算前缀”。

单飞协调：让一个请求算前缀，其他人等多久？

精确输入单飞（exact-input single flight）的策略是：一个请求成为领导者（leader），其他输入 token 完全相同的请求作为跟随者（follower）等待。协调的是提示词计算，不是答案——每个跟随者仍然按自己的生成设置（如 temperature）独立生成输出。

初版实现让跟随者等待领导者整个请求完成。缓存复用变得可预测，但等待穿过了整个解码阶段。

在 8 个各生成 128 token 输出的并发请求下，该策略相比独立执行同时降低了平均 TTFT 和最慢请求的完成延迟。但在只有 2 个请求时，平均 TTFT 反而比独立执行更差，尽管完成延迟有所改善。

既然提示词缓存已经就绪，为什么还要等过解码阶段？作者加入第二种释放策略：领导者的预填充完成后，立即发布其完成的缓存页，并让跟随者具备准入资格。

sequenceDiagram
    participant S as Scheduler
    participant C as Prefix cache
    participant L as Leader
    participant F as Followers
    S->>L: Admit leader
    S->>S: Block identical followers
    L->>L: Finish prompt prefill
    L->>C: Publish completed prefix pages
    L->>S: Report successful publication
    S->>S: Unblock followers
    S->>F: Admit as capacity allows
    F->>C: Look up matching prefix
    C-->>F: Return shared KV page references
    par Independent generation
        L->>L: Continue decode
    and Follower generation
        F->>F: Generate their own outputs
    end

下表对比两种释放策略（并发生成 128 个输出 token 的相同请求）：

并发请求数	请求完成时释放	预填充后释放	TTFT 降幅
2	1,357.5 ms	584.7 ms	56.9%
4	1,757.9 ms	617.1 ms	64.9%
8	1,984.4 ms	646.7 ms	67.4%

在 8 请求爆发的独立执行对比中（每个 532 token 提示词，128 token 输出）：

策略	每个跟随者恢复 token 数	平均 TTFT 变化	最慢请求完成时间变化
独立执行，完成时发布	0	基线	基线
单飞，请求完成时释放	528	降低 47.5%	降低 25.8%
单飞，预填充发布后释放	528	降低 82.9%	降低 32.4%

但更早释放并非所有指标都更好。在一个单独测试中，第二个请求在原请求进入解码阶段后到达。相比请求完成时释放，早释放将平均 TTFT 降低 72%，却把最慢请求的完成延迟增加了 14%。原因是原飞行已关闭，第二个请求开启了新的飞行并复用热前缀，两个请求并发解码而非顺序解码，改变了活跃批次。

早释放策略自身发布了所需的检查点，额外的增量发布在这些精确输入协调场景中收益甚微。但在无协调场景下，比如只共享部分前缀的请求，增量发布依然有用。

可以说：发布决定数据何时可复用，协调决定谁等待、等待多久。

单飞（single flight） 是并发编程中的经典模式，指对同一份工作只允许一个执行者实际运行，其余相同请求合并等待其结果，避免重复计算。Go 语言的 golang.org/x/sync/singleflight 是常见实现。将其引入 LLM 推理时存在一个区别：这里的“相同工作”只是提示词预填充，而非整个请求。因为每个请求仍要按各自的采样设置（temperature、top-p 等）独立解码，输出本就不同，所以协调只覆盖前缀计算这段共享成本。领导者（leader）负责计算并发布缓存页，跟随者（follower）等待其完成后直接引用这些页继续自己的解码。等待的终点是核心权衡点：等到领导者整个请求结束，等待时间长但顺序确定；等到领导者预填充结束就释放，则等待更短，但领导者与跟随者会并发解码，改变活跃批次的组成，可能抬高最慢请求的完成时间。

状态机简化：从 Draining 到责任分离

这个实现过程中，AI 辅助编写了代码，但审查其设计才是关键。

最初，AI 在释放跟随者时直接删除飞行记录，这在当时看合理——等待已经结束。但首个单飞基准测试暴露了问题：跟随者之后完成并通知协调器时，协调器已不识别它们的 ID。AI 提议移除未知请求检查，作者拒绝了，因为这会同时掩盖携带真正无效请求 ID 的终止通知。

原设计没有 FlightState。为了保留验证，团队加入了 Active 和 Draining 状态，并跟踪已释放的跟随者直到其终止：

enum FlightState {
    Active { leader_request_id: u64 },
    Draining,
}

struct Flight {
    input_token_ids: Arc<[u32]>,
    state: FlightState,
    follower_request_ids: VecDeque<u64>,
}

但早释放策略让这个表示更复杂：领导者可能在跟随者释放后仍在解码。AI 保留相同字段，只改了枚举：

enum FlightState {
    Active { leader_request_id: u64 },
    Draining { leader_request_id: Option<u64> },
}

可选领导者让作者暂停思考：不同释放策略需要不同组合。如果一个策略不应保留领导者，但状态里却有一个，是否需要再加检查？

退一步看：真的需要 Draining 状态吗？加入它是为了在已释放请求最终终止时能识别它们，这需要记住它们的 ID，但不需要保留它们的前属飞行关系。为什么不跨飞行单独收集这些 ID？

于是团队移除 FlightState，单独跟踪已释放的请求 ID：

pub(super) struct PrefixCacheFlightCoordinator {
    flights: HashMap<FlightId, Flight>,
    released_request_ids: HashSet<u64>,
    // Other fields omitted.
}

释放时移除飞行及其索引，只保留尚未终止的请求 ID。这样既保留了终止验证，又不保留已不影响执行的领导/跟随关系。未知请求 ID 仍然报错，相同提示词的新请求开启新飞行。

人类审查既意味着保护不变量，也意味着重新审视用来保护它的结构。 基准测试显示请求何时可以停止等待，代码审查显示飞行何时可以停止存在。

Rust 的 enum 携带数据的能力（代数数据类型，ADT）让状态机可以直接用类型表达：FlightState::Active { leader_request_id: u64 } 表示飞行进行中并绑定领导者，Draining 表示等待阶段已结束。这样做的好处是，某些字段只在特定状态下存在，编译器可以强制在使用前进行匹配，避免非法状态。但当不同释放策略需要不同字段组合时（如 Draining { leader_request_id: Option<u64> }），枚举会开始膨胀——出现“这个状态里到底该不该有领导者”这类需要额外检查的问题。一种常见的重构思路是把正交的职责拆到不同结构中：状态机只描述执行阶段，而“哪些请求已释放但尚未终止”属于生命周期追踪，用独立的集合（如 HashSet<u64>）维护即可。这样既避免了 Option 带来的分支判断，也让每个结构只承担单一语义，符合 Rust 偏向“让非法状态不可表示”的设计哲学。

这个小实现留下的开放问题

以上都是合成工作负载、单一后端、小模型的结果。精确输入协调在对照中未对独立输入造成有意义的完成时间退化，但基准无法确立生产流量下的行为。几个方向值得继续探索：

1. 部分前缀协调：请求可能共享长文档但末端问题不同，多大重叠值得等待？
2. 等待还是重算：跟随者的延迟目标和领导者的剩余预填充量会改变选择。
3. 不同注意力状态：滑动窗口和混合模型改变保留与复用策略，vLLM 的混合 KV 缓存管理器探索了这些约束。
4. 跨后端与内存层的复用：路由需权衡前缀局部性与速度、负载，SGLang HiCache 将缓存扩展到 GPU、主机和外部存储。

这些开放问题提醒我们，前缀缓存在并发场景下的协调策略远未定型，而这个基于 Rust 的小引擎提供了一个可观察、可迭代的实验平台。