连续批处理完全拆解：Orca 的迭代级调度与选择性批处理，如何把 LLM 服务吞吐提升 36.9 倍

推理服务系统的两层结构#

先铺垫一下服务系统的通用结构。典型的机器学习推理服务分两层：

• 服务层（serving layer）：负责接收客户端请求、排队、把请求组成批次（batch）交给执行引擎、把结果返回给客户端。代表是 NVIDIA Triton Inference Server、TensorFlow Serving 等。
• 执行引擎（execution engine）：真正执行张量运算。代表是 NVIDIA FasterTransformer、TensorRT、TVM 等。

这两层之间的交互模式决定了调度粒度。在 Orca 之前，服务层与执行引擎只在两个时刻发生交互：一是服务层把一批新请求交给空闲的引擎时；二是引擎处理完整个批次、把结果交回服务层时。也就是说，引擎一旦接到一个批次，就会把这个批次从头跑到尾，中途不会更换批次成员。这种模式被称为请求级调度（request-level scheduling）——调度的基本单位是整个请求。

为什么这对生成式模型是灾难#

训练和推理有一个关键差异。训练时模型用教师强制（teacher forcing）技术，把整批训练数据在一次前向传播里处理完；而生成式模型（如 GPT）是自回归（autoregressive）的——每生成一个 token，就要把模型完整跑一遍（一个”迭代”），下一次迭代的输入是上一次迭代的输出。因此：

• 处理一个请求需要的迭代次数 = 输入 token 数 + 生成 token 数；
• 不同请求的输入长度、生成长度完全不同，需要的迭代次数天差地别；
• 系统里的请求是异步到达的，随时有新请求进来。

请求级调度与”多迭代 + 异步到达”的工作负载一组合，立刻产生三个问题：

1. 早完成的请求被滞留。一个批次里总有请求先结束生成，但它们不能立即返回客户端——引擎要等批次里最慢的请求全部结束，才把结果统一交回服务层。先完成的请求白白多等了很多时间，直接变成用户感知到的尾延迟。
2. 晚到的请求被长期阻塞。新请求必须在当前批次全部处理完之后才有机会被调度，排队延迟取决于批次里最慢请求的剩余时间，而不是单个迭代的时间。
3. 对已结束请求的无效计算。批次里的请求一旦结束，引擎并不知道，仍然在每次迭代里为它执行完整的矩阵运算。

论文 Figure 3 用一个极简例子把这三个问题画得清清楚楚：

图：请求 x1（“I think”）与 x2（“I love”）输入长度相同（各 2 个 token），但生成长度不同——x1 生成 “this is great <EOS>”（4 个迭代），x2 生成 “you <EOS>”（2 个迭代）即完成。阴影部分是输入 token；”−” 表示请求级调度强加的额外计算：x2 在第 2 个迭代后已经结束，引擎仍然为它计算到第 4 个迭代，同时 x2 的结果要等 x1 生成完才能返回。（来源：Orca 论文 Figure 3）

在这个例子里，x2 实际上在第 2 个迭代（生成 <EOS>）后就已结束，第 3、4 个迭代为它做的一切计算全是浪费；x2 的生成结果也要等到第 4 个迭代结束才发给客户端。而如果此时有新的请求 x3 到达，它至少要等完这 4 个迭代才可能被调度。

任意两个请求为什么难以批量#

GPU 的批量执行（batched execution）要求合并后的张量形状一致：传统上，一个 Transformer 层每迭代接受形状为 $[B, L, H]$ 的三维输入张量，其中 B 是批次大小（batch size），L 是一次处理的 token 数，H 是隐藏维度（hidden size）。例如图 3 中”iter 1”（初始化阶段）的输入是 $[2, 2, H]$，“iter 2”（增量阶段）的输入是 $[2, 1, H]$。

但迭代级调度选出的请求，任意两两之间都可能无法合并。论文归纳出三种不可批量（cannot be batched）的情形：

1. 两个请求都在初始化阶段（initiation phase），但输入 token 数不同。例如 Figure 4 中的 x3（2 个输入 token）与 x4（3 个输入 token），前者输入形状是 $[2, H]$，后者是 $[3, H]$，无法拼成 $[B, L, H]$；
2. 两个请求都在增量阶段（increment phase），但当前处理的 token 索引不同。注意力（attention）运算需要读取该请求此前所有 token 的键（key）和值（value），token 索引不同意味着键值张量形状不同；
3. 两个请求处于不同阶段。初始化阶段一个迭代处理全部输入 token，增量阶段一个迭代只处理 1 个 token，输入形状天然不同。

在请求级调度里不存在这个问题，因为引擎统一处理整个批次：同一批次的所有请求一起进入初始化、一起进入增量。而迭代级调度下，请求到达时间、进度各异，符合”同阶段、同形状”可批量条件的请求很少，且批次越大，两两匹配的概率越低——论文指出这种匹配概率随批次大小指数级下降。如果坚持传统批量化，调度器的选择空间会被严重压缩，迭代级调度带来的灵活性就白费了。

观察：并非所有算子都要求”请求边界”#

Orca 的关键观察是：不同算子对输入形状的要求不一样。

• 非注意力算子——线性层（Linear）、层归一化（LayerNorm）、残差加（Add）、GeLU 等——处理的是每个 token 的独立变换，不需要区分 token 属于哪个请求。把 x3 与 x4 的输入拼成形状 $[\sum_i L_i, H]$（即 $[5, H]$）的二维张量，它们照样正确执行；
• 注意力算子必须知道请求边界：它要计算”同一请求内部” token 之间的相关性，不能让不同请求的 token 互相做注意力，通常用 cuBLAS 的批量矩阵乘（batched matrix multiplication）实现。

于是 Orca 提出选择性批处理（selective batching）：对非注意力算子按 token 粒度（token-wise）批量执行，对注意力算子按请求逐个执行。

论文 Figure 5 画出了执行引擎在一个 Transformer 层内的完整数据流：

图：Orca 执行引擎对一个包含 4 个请求（x1~x4）的批次跑一层 Transformer。这一轮共有 7 个输入 token，拼成 $[7, H]$ 输入张量喂给非注意力算子；进入注意力前插入 Split 操作，按请求切分；每个请求的注意力单独执行（x1 需读取此前生成的 x11、x12、x13 的键值，x2 读取 x21 的键值）；注意力输出经 Merge 拼回 $[7, H]$，交给后续算子。Attention K/V 管理器按请求保存历史键值。（来源：Orca 论文 Figure 5）

执行流程拆解：

1. 本轮 4 个请求共有 7 个 token 要处理（x1 的 x14、x2 的 x22、x3 的 x31/x32、x4 的 x41/x42/x43），输入张量直接展平为 $[7, H]$；
2. QKV 线性层（QKV Linear）等非注意力算子以 $[7, H]$ 为输入正常执行，输出按请求切分（Split）；
3. 每个请求的注意力单独执行。增量阶段的请求需要历史键值——Attention K/V 管理器（Attention K/V manager）按请求保存此前所有 token 的键值，直到调度器显式释放；例如 x1 本轮用管理器里的 $(x_{11}, x_{12}, x_{13})$ 与当前 token 的查询、键、值计算注意力；
4. 各请求的注意力输出合并（Merge）回 $[7, H]$，继续执行注意力输出线性层（Attn Out Linear）等后续算子。

为什么注意力”不批量”的损失很小#

一个直觉问题是：批量执行除了增加并行度，还有一个重要收益——参数复用（parameter reuse）。权重参数要从显存读进 GPU 计算单元，一次读取可以让批次里所有请求共享，批次越大，每个请求摊分的参数读取成本越低。对大规模模型而言，从显存读参数往往就是端到端耗时的主要瓶颈。

但注意力算子没有参数——它只做查询与键的点积、softmax、与值的加权求和，全部操作发生在激活值（activation）之间。因此不批量注意力不会损失任何参数复用收益，损失的只是并行度层面的效率，而这个损失很小（论文的引擎微基准实验证实了这一点，见后文）。反之，如果为了凑批量而把不同形状的注意力强行对齐（padding），浪费反而更大。

论文把这条设计原则概括为：在每一轮参数读取中完成尽可能多的计算——把所有”准备好”的 token 都塞进一轮执行，不管它们能否被批量（非注意力算子批量、注意力算子逐个）。这与之前的 RNN 服务系统 BatchMaker 形成鲜明对比：BatchMaker 在 RNN 细胞（cell）粒度上寻找”相同计算的细胞”凑批量；但对 Transformer，不同 token 索引对应不同的键值集合，理论上最多有 L 种不同细胞（L 是请求总长度，在 Orca 的测试 trace 里从 33 到 640 不等），同一时刻几乎不可能出现两个相同细胞，凑批量的概率极低。Orca 放弃了”找相同计算”，改为”非注意力全部批量、注意力逐个执行”，这正是选择性批处理与细胞批处理（cellular batching）的本质区别。

迭代级 FCFS#

调度器保证迭代级先来先服务（first-come-first-served, FCFS）：对任意两个请求 $x_i$、$x_j$，如果 $x_i$ 比 $x_j$ 早到达，那么 $x_i$ 已运行的迭代数不少于 $x_j$。注意这是”迭代级”的 FCFS——晚到的请求只要需要的迭代更少，仍可能比早到的请求更早返回客户端。保持处理顺序不被乱序，是为了公平、避免饥饿，也让行为可预测。

两个约束：max batch size 与 GPU 显存#

调度器还要考虑两个现实约束：

1. 批次大小收益递减。批次越大吞吐越高，但延迟也越高，且收益递减。Orca 沿用服务系统的惯例，设置最大批次大小（max batch size）参数，由运维人员根据延迟预算调优。
2. 显存约束。注意力 K/V 管理器占用的显存不能无限增长。一个朴素实现可能死锁：请求池里明明有请求，但所有显存都被 K/V 占满，任何新请求都调度不了。因此调度器必须感知 K/V 内存的剩余空间。

Orca 的做法是按请求预留下限、按需分配：调度器为每个首次调度的请求预留 max_tokens 个 K/V 槽位（slot，一个槽位 = 存一个 token 的键和值所需显存），只有预留成功才把请求纳入批次；n_slots 是运维配置的 K/V 内存总量（按槽位数计）。论文给出了完整的调度算法：

1
Algorithm 1: ORCA scheduling algorithm
2
Params: n_workers: number of workers, max_bs: max batch size,
3
        n_slots: number of K/V slots
4
1  n_scheduled ← 0
5
2  n_rsrv ← 0
6
3  while true do
7
4      batch, n_rsrv ← Select(request_pool, n_rsrv)
8
5      schedule engine to run one iteration of the model for the batch
9
6      foreach req in batch do
10
7          req.state ← RUNNING
11
8          n_scheduled ← n_scheduled + 1
12
9      if n_scheduled = n_workers then
13
10         wait for return of a scheduled batch
14
11         foreach req in the returned batch do
15
12             req.state ← INCREMENT
16
13             if finished(req) then
17
14                 n_rsrv ← n_rsrv − req.max_tokens
18
15                 n_scheduled ← n_scheduled − 1
19

20
17 def Select(pool, n_rsrv):
21
18     batch ← {}
22
19     pool ← {req ∈ pool | req.state ≠ RUNNING}
23
20     SortByArrivalTime(pool)
24
21     foreach req in pool do
25
22         if batch.size() = max_bs then break
26
23         if req.state = INITIATION then
27
24             new_n_rsrv ← n_rsrv + req.max_tokens
28
25             if new_n_rsrv > n_slots then break
29
26             n_rsrv ← new_n_rsrv
30
27             batch ← batch ∪ {req}
31
28     return batch, n_rsrv

算法要点：

• max_tokens 是每个请求的属性（输入 token 数 + 最大生成 token 数），表示该请求生命周期内至多需要的 token 数。由于预留按 max_tokens 计算，只要预留成功，就能保证该请求运行期间 K/V 内存一定够用；
• Select 函数按到达时间排序，最多取 max_bs 个请求；只有初始化阶段（尚未调度过）的请求才需要预留（增量阶段的请求已预留过）；
• n_rsrv 记录当前已预留槽位数，预留检查失败就停止挑选（break）——注意此时不允许跳过该请求继续选后面的，因为按到达时间排序，跳过会导致处理顺序违背 FCFS。

值得对比的是 K/V 内存的分配方式。FasterTransformer 等系统按模型最大序列长度（例如 2048）为每个请求固定预分配完整键值空间，导致 13B 模型下批次大小到 8 就显存溢出（论文 Figure 9a 的缺失数据点）。Orca 则按每个请求自己的 max_tokens 预留，避免了按最大长度分配造成的冗余——这个”预分配整段 vs 按需分配”的对比，正是后来 vLLM 的 PagedAttention 所解决的核心问题的前奏，只是 Orca 的粒度还是”每请求一段连续预留”，PagedAttention 把它细化到了”分块、可共享”。

控制面与数据面分离#

分布式执行最微妙的工程点在通信。FasterTransformer、Megatron-LM 这类系统通过 NCCL 在 GPU 之间交换所有消息——包括每个迭代都要传的控制消息（批次大小、序列长度、请求是否完成等元数据）。由于 NCCL 通信要求 CPU 侧同步，每次控制消息交换都会引入一次 CPU-GPU 同步，而控制消息每迭代都会发生，开销不可忽视。

Orca 把通信分成两条独立的通道：

• 控制面（control plane）：引擎主控（engine master）与各 worker 控制器之间用 gRPC 等不经过 GPU 的通道传控制消息和 token 文本；
• 数据面（data plane）：中间张量数据仍然走 NCCL——这些数据由 GPU 产生、被 GPU 消费，NCCL 是正确选择。

另外一个细节是同步策略：Worker1 收到控制消息后立即向自己的 GPU 发 kernel、不等 kernel 完成就把控制消息转发给下一个 worker；只有最后一个 worker（Worker2）等待 GPU kernel 完成，负责把输出 token 收集回引擎主控。这样 CPU 与 GPU 之间的同步被压到最小。论文的微基准实验显示，在 175B 模型（2 个层间分区）上 Orca 引擎比 FasterTransformer 快最多 47%，作者把这归因于控制面与数据面分离带来的同步开销减少。

把 worker 流水线化，不需要微批次#

请求级调度下，服务层一次只能给引擎注入一个批次，为了利用多个层间分区（多个 worker 串成一条执行链），FasterTransformer 只能把一个批次拆成多个微批次（microbatch）做流水线（pipeline）执行——这是从训练里借来的标准技巧。但微批次拆分有两个代价：一是每个分区每次只批量执行一个微批次，批次变小、批量收益缩水；二是微批次太少而分区太多时，流水线会出现气泡（bubble，空闲时段）。

Orca 的调度器不等待单个批次返回：它持续注入批次，直到在途批次数 n_scheduled 达到 n_workers（即每个 worker 都各有活干），再等待最早的那个批次返回。论文 Figure 8 对比了两者的流水线时序：

图：3 个 worker（层间分区）、max batch size 为 2 时的执行时序。左侧（a）ORCA：批次 AB 依次经过 Worker1→2→3 后，调度器不等它返回就继续注入 CD、EF，每个 worker 始终在处理某个批次，全程无气泡，且每个批次都保持完整（2 个请求一起批量）。右侧（b）FasterTransformer：必须把批次 AB 拆成微批次 A、B 分别流水，一旦微批次大于分区数还会插入气泡。（来源：Orca 论文 Figure 8）

FasterTransformer 需要在”更大的微批次（更好的批量效率）“与”更少的微批次（更少的流水线气泡）“之间做 tradeoff；Orca 依托迭代级调度，无需拆分批次就能让流水线始终满载——批量效率与流水线效率同时拿到。图 8a 中 A1B1 表示批次 AB 的第 1 个迭代；每轮迭代完整批次 AB 一起流过 3 个 worker，C1D1、E1F1 依次跟上，三个 worker 永不停歇。

环境与模型配置#

实验在 Azure ND96asr A100 v4 虚拟机上进行：每台 8 张 40GB A100 GPU，通过 NVLink 互联；最多用 4 台虚拟机，跨机用 Mellanox 200Gbps HDR InfiniBand（每机 8 个网卡，合计 1.6Tb/s 跨机带宽）。模型采用 GPT-3 系列配置的 GPT 模型，fp16 精度，最大序列长度 2048：

基线是 NVIDIA FasterTransformer（当时支持分布式执行且面向推理优化的主流引擎）。由于当时没有公开的生成式模型请求 trace，作者用合成 trace 驱动实验：每个请求的输入 token 数从 U(32,512) 均匀分布采样，最大生成 token 数从 U(1,128) 采样，请求到达时间按泊松过程（Poisson process）生成，通过调节到达速率模拟不同负载；为了让 trace 可复现，假设模型永不输出 <EOS>（无真实 checkpoint，无法判断真实结束时机）。

引擎微基准：不批注意力到底损失多少#

第一个实验刻意绕开调度器，把同一批完全相同的请求反复注入引擎（等价于请求级调度），只比引擎本身的 kernel 效率。结果显示（论文 Figure 9）：

• 13B（单卡）与 101B（8 卡）上，Orca 引擎与 FasterTransformer 性能相当或略差——差异来自注意力没有批量执行，但正如前文分析，注意力无参数、不批几乎没有参数复用损失，差距很小；
• 175B（16 卡、2 个层间分区）上 Orca 反而快最多 47%，归因于控制面/数据面分离减少了同步开销；
• 关键的可观测差异在显存：FasterTransformer 按最大序列长度固定预分配键值空间，13B 模型批次到 8、101B 批次到 16 就 OOM（图上直接缺失这些数据点）；Orca 按请求的 max_tokens 预留，同显存下能支持更大的批次。

端到端：36.9 倍吞吐的由来#

第二个实验测试完整系统（含调度器），用合成 trace 对比 Orca 与”FasterTransformer + 自定义调度器”（按到达顺序取最多 max batch size 个请求组批，即 Triton、TensorFlow Serving 等的主流做法）。结果（论文 Figure 10）在 175B 模型上：

图：中位端到端延迟（按生成 token 数归一化）与吞吐量，三个子图分别为 101B（8 卡）、175B（16 卡）、341B（32 卡）模型。orca(max_bs) 表示 Orca 用 max batch size 为 max_bs；ft(max_bs, mbs) 表示 FasterTransformer 用 max batch size 为 max_bs、微批次大小为 mbs。横轴为归一化延迟（对数坐标），纵轴为吞吐量（req/s）。（来源：Orca 论文 Figure 10）

要点：

• 同延迟下吞吐高一个数量级。论文给出的代表性数据点：175B 模型上，要达成 190ms 的中位归一化延迟（约为 orca(128) 归一化执行时间的 2 倍），FasterTransformer 只能提供 0.185 req/s，而 Orca 提供 6.81 req/s——36.9 倍的吞吐提升；
• 重负载下优势最明显。负载轻时请求不足以填满批次，延迟主要取决于引擎本身（与微基准一致，101B 低负载下两者接近）；负载变重后，Orca 的调度器让晚到请求”搭上”正在运行的批次（hitch a ride），吞吐随负载上升而延迟增幅很小，而 FasterTransformer 面对”到达时间不同、迭代数不同、输入长度不同”的混合请求时吞吐封顶在 0.49 req/s，延迟也大幅恶化；
• 批次大小调节是纯收益。对 Orca，增大 max batch size 提高吞吐且不损害延迟（迭代级调度解决了早完成/晚到问题，批次增大不再意味着”等最慢的人”）；对 FasterTransformer，增大 max batch size 甚至可能有害——首轮迭代会按最短请求的输入长度处理所有请求，且早完成的请求被绑在批次里。

论文还做了同质请求 trace 的对照实验（所有请求输入长度、生成长度相同，即”早完成/晚到”问题不存在）：此时 FasterTransformer 增大批次也能受益（Orca 仍是更好，除非 max batch size 为 1）。这组对照很干净地证明了：请求级调度的问题核心不在 batch 大小本身，而在批次成员的动态性。