Mooncake

原文地址

缩写说明

• TTFT：time to first token
• TBT：time between token
• SLO: service level objective

架构

节点划分为两类，分别放入两个 pool

1. Prefill Pool：在保证 TTFT 不超上限的情况下尽可能多地复用 kv cache
2. Deocding Pool：在保证 TBT 不超上限的情况下尽可能增大吞吐量

每个节点都有自己的 prefix kv cache，算法按需在节点间传输 kv cache。

Prefill Node

Prefill 节点的特点

• CPU-GPU 之间的 kv cache 传输是分层的，计算和 CPU-GPU 传输相互重叠，这样使得整体的 CPU-GPU 传输延迟基本不随序列长度变化
• Chunked Pipeline Parallel：每 X 个节点组成一组，共同处理同一个请求。请求的输入切分为一些 chunk，每个节点处理一个 chunk，并在 pipeline stage 结束时将 kv cache 传递给下一个节点。
  • 并行带来了更低的 TTFT
  • 计算和通信可以重叠
  • 可以用同一个策略支持长输入/短输入的请求

Decoding Node

prefill 节点命中的 prefix kv cache 和新计算的 incremental kv cache 会全量传输到 decoding 节点，这个传输过程也是异步的，是的 prefill 过程和 kv cache 传输相互重叠。

调度算法会尽量选择低负载（TBT 低）的 decode 节点执行任务。但是在 decode 节点获取到请求后，会执行二次确认，如果当前的 TBT 高过上限，就会拒绝请求，这将导致已经执行的 prefill 全部浪费。

调度策略

调度策略会平衡资源利用和 TTFT/TBT 不超上限。对于每一个到达的请求，调度器会按照这样的方式进行调度

1. 在所有 prefill 节点中，获取命中的最长的 prefix kv cache，记这个 prefix 长度为 best_match_len，对应的 prefill 节点为 best_match_instance
2. 对所有 prefill 节点，估算如果把任务发送给该节点，对应的 TTFT，按照具体情况不同，有这样两种处理方法
   1. 如果该节点的 prefix match 长度大于 best_match_len * some_ratio，则认为该节点可以无需额外传输 kv cache 就可完成 prefill。预计的 ，其中some_ratio 是认为设定的一个比例， 是预估的排队时长， 是预估的 prefill 时长
   2. 如果该节点的 prefix match 长度小于上述数值，则该节点需要从 best_match_instance 获取 kv cache 才可完成 prefill，该节点已有的 prefix 无需传输，仅传输缺失的部分即可。预计的 ，其中 是指预估的 kv cache 传输时间。
3. 在所有 prefill 节点中，选取预估的 TTFT 最低的节点，用作 prefill。如果最低的预估 TTFT 仍然高于设定 TTFT_SLO，则拒绝该请求
4. 选择负载最低的 decoding 节点。如果负载最低的 decoding 节点对应的 TBT 预估数值仍然高于设定的 TBT_SLO，则拒绝该请求
5. 按照调度算法选择出的 prefill/decoding 节点，执行推理

上述调度算法不是直接将请求发送给最长的 prefix match 节点，而是允许一小部分的距离，这能带来几个好处

• 平衡了 TTFT 和 kv cache 复用，既能保证比较多的 kv cache 复用，又能保证比较低的 TTFT
• 自动在节点间传播热点 prefix。例如 system prompt 这种，会大量重复出现的 prefix，这种 prefix 会因为该算法而自动传播到全部的 prefill 节点

一些不清楚的地方

1. Chunked Pipeline Parallel 分组方案。论文的算法只描述了如何挑选一个 prefill 节点，没有说明 Chunked Pipeline Parallel 的多个节点如何挑选。
2. 预测算法不明确。文中并未解释 采用什么算法或模型预测