Continuous Batching 与核心指标

与静态 batch 的差别

静态 batch 往往等一组请求凑齐，按最大 prompt/output 长度一起运行；短请求完成后仍可能留下 padding 或等待 batch barrier。Continuous batching（iteration-level scheduling）在每个模型 iteration 重新选择工作：

1. 让 active decode 请求各前进一步；
2. 回收已完成/取消请求的 KV blocks 和 slots；
3. 在 token、sequence、KV 容量和优先级预算内接纳新 prefill/chunk；
4. 形成下一次模型执行 batch。

它是服务 scheduler 机制，不改变 Prefill/Decode 的模型数学，也不等同动态 shape 的普通 DataLoader batching。

Benchmark 方法与容量模型进一步定义 warmup、同步、统计口径、active KV token capacity 和 SLO goodput；调度对比应复用同一 arrival trace。

同一 trace 的 worked example

请求记为 (arrival, prompt tokens, output tokens)：

A = (0, 4, 5)
B = (0, 2, 2)
C = (3, 3, 4)
token-work budget = 8 / tick

教学模型假设每个 prompt/decode token-work 成本相等。静态 batch 在 t=0 把 A/B prompt padding 到 4，B 完成后仍留下 3 个 decode padding slots；直到 A 在 t=6 完成才接纳 C。Continuous scheduler 在 t=3 让 A decode 的同时 prefill C，并立即复用 B 的空槽。

图中把 token-work 设成等成本单位，省略 attention 长度、GEMM shape、chunked prefill、CUDA Graph buckets、KV block 分配、priority、preemption 与设备执行重叠。真实 prefill token 和 decode token 的成本不能直接相加，模拟器只验证调度语义和指标计算。

核心指标边界

• Queue time：请求可执行前等待 scheduler/容量的时间。
• TTFT：arrival 到首个输出 token；包括 queue、tokenization/template、prefill、sampling、streaming。
• TPOT / inter-token latency：首 token 后输出 token 间隔；可按请求均值或 step 分布报告。
• Throughput：单位时间完成的 output tokens/requests；未必满足每个请求 SLO。
• Goodput：满足指定 TTFT/TPOT/端到端 SLO 的有效请求或 tokens。
• Makespan：给定 trace 全部完成所需时间，适合离线调度对比。

同一 workload、同一 arrival trace、同一模型/硬件/输出语义才可公平 A/B。吞吐实验还要说明 warmup、请求长度分布、并发上限、scheduler budgets、采样和 streaming 是否计入。

可运行离散事件模拟

from dataclasses import dataclass,field
import platform,statistics

@dataclass
class Request:
    name:str; arrival:int; prompt:int; output:int
    emitted:list[int]=field(default_factory=list); completed:int|None=None
    def clone(self): return Request(self.name,self.arrival,self.prompt,self.output)

TRACE=[Request("A",0,4,5),Request("B",0,2,2),Request("C",3,3,4)]
CAPACITY=8

def metrics(reqs,makespan,waste):
    total=sum(r.output for r in reqs)
    return {"makespan":makespan,"padding_waste":waste,
            "throughput":total/makespan,
            "ttft":{r.name:r.emitted[0]-r.arrival for r in reqs},
            "tpot":{r.name:(statistics.mean(b-a for a,b in zip(r.emitted,r.emitted[1:]))
                    if len(r.emitted)>1 else 0.) for r in reqs},
            "completion":{r.name:r.completed for r in reqs}}

def static_batching(trace):
    reqs=[r.clone() for r in trace]; time=waste=0; pending=reqs[:]
    while pending:
        ready=[r for r in pending if r.arrival<=time]
        if not ready:
            time=min(r.arrival for r in pending); ready=[r for r in pending if r.arrival<=time]
        batch=ready
        for r in batch: pending.remove(r)
        padded=len(batch)*max(r.prompt for r in batch)
        waste+=padded-sum(r.prompt for r in batch)
        time+=(padded+CAPACITY-1)//CAPACITY
        remaining={r.name:r.output for r in batch}
        while any(remaining.values()):
            for r in batch:
                if remaining[r.name]>0:
                    remaining[r.name]-=1; r.emitted.append(time+1)
                    if remaining[r.name]==0: r.completed=time+1
                else: waste+=1
            time+=1
    return reqs,metrics(reqs,time,waste)

def continuous_batching(trace):
    reqs=[r.clone() for r in trace]; time=0; pending=reqs[:]; active=[]
    while pending or active:
        budget=CAPACITY
        for r in active[:]:
            if budget==0: break
            r.emitted.append(time+1); budget-=1
            if len(r.emitted)==r.output: r.completed=time+1; active.remove(r)
        for r in pending[:]:
            if r.arrival<=time and r.prompt<=budget:
                budget-=r.prompt; pending.remove(r); active.append(r)
        time+=1
    return reqs,metrics(reqs,time,0)

def main():
    static_req,static=static_batching(TRACE)
    cont_req,cont=continuous_batching(TRACE)
    assert static["completion"]=={"A":6,"B":3,"C":11}
    assert cont["completion"]=={"A":6,"B":3,"C":8}
    assert static["padding_waste"]==5 and cont["padding_waste"]==0
    assert sum(r.output for r in static_req)==sum(r.output for r in cont_req)==11
    print(f"python={platform.python_version()} capacity={CAPACITY} token-work/tick")
    print("trace="+str([(r.name,r.arrival,r.prompt,r.output) for r in TRACE]))
    print(f"static metrics={static}")
    print(f"continuous metrics={cont}")

if __name__=="__main__": main()

完整文件位于 examples/continuous_batching_simulator.py。实际结果：静态 makespan 11、padding waste 5、throughput 1.0 output token/tick、C TTFT 5；continuous makespan 8、waste 0、throughput 1.375、C TTFT 2；本例所有请求 TPOT 都为 1。

模拟器没有 GPU 性能含义，不证明生产吞吐提高 37.5%。它只在明确假设下证明“每轮重组 + 槽位复用”如何改变 trace。生产验证必须用真实 prefill/decode costs、KV 容量、batch kernel 和 arrival distribution。

Scheduler 真正还要解决什么

Scheduler Budget 与 Admission Control用可运行 block reservation 模型进一步区分本轮 token budget、长期 KV capacity、保守 reservation 与乐观 overcommit。

• Token budget：一轮允许多少 prefill/decode tokens，避免长 prompt 垄断。
• KV block budget：是否有足够 PagedAttention blocks；不足时 reject、queue、preempt、swap 或 recompute。
• Prefill/decode interference：大 prefill 可能拉长同轮 decode 的 TPOT；chunked prefill 用更多轮换公平性。
• CUDA Graph buckets：active batch 改变时选哪个固定 graph，padding 多少，还是 eager fallback。
• Fairness/priority：FIFO、deadline、priority、aging 与多租户配额。
• Cancellation：停止请求要及时回收 KV、取消 streaming，同时保持 collective/order 安全。

上下游关系

• Tokenizer/Chat Template决定 prompt token 数，进入 admission 和 prefill budget。
• Prefill/Decode定义每个请求的阶段与 TTFT/TPOT；本页决定多个请求如何交错。
• PagedAttention提供动态 KV block 分配与回收，是 slot reuse 的物理基础。
• CUDA Graph要求静态 shape/address；scheduler 常用 batch buckets 和固定 slots 调和动态 active set。
• 投机解码让一个请求每轮可能提交多个 token，会改变 token budget 与 verification scheduling。
• MoE Router让同样数量的 active tokens 因路由分布不同形成不同 expert batch 与 All-to-All split，scheduler 的 batch size 不能单独预测 MoE iteration latency。
• Request Lifecycle定义 admission 前后、cancel/timeout 与 streaming backpressure；scheduler 必须在安全边界移除终止请求并回收资源。
• 服务可靠性、Backpressure 与 Observability把有界输出 credits 作为请求是否继续推进的条件，并用 generated/sent waste、finish reasons 与 SLO goodput 检查调度结果。

参考资料

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention — iteration-level scheduling 与 KV 管理背景。
• vLLM — Metrics — request queue、prefill、decode、TTFT 与 inter-token latency 指标。