夜雨聆风学习资料网

ARTICLE · 1385006

Nano-vLLM源码学习(5):Scheduler 与连续批处理

Nano-vLLM源码学习(5):Scheduler 与连续批处理

📑 目录

  • 1. 调度器要回答的三个问题
  • 2. 两个队列与一次 schedule
  • 3. Prefill 调度:吃 Token Budget
  • 4. Decode 调度:抢占来腾地方
  • 5. postprocess:写回与结束判定
  • 总结
  • 自我检验清单
  • 参考资料

1. 调度器要回答的三个问题

引擎每跑一步(step),都要先问调度器:这一轮算谁?是 prefill 还是 decode?它们的 KV 放得下吗?scheduler.py只有 90 多行,职责就是回答这三个问题。它不碰矩阵乘法,只做资源分配和批次组装的决策。

调度器可以类比成餐厅领位员:门口排队的客人是 waiting,已经落座点菜的是 running。领位员每轮先看门口还能不能再安排一桌,安排不了才去照顾已经落座的客人;桌子不够时,就请最后落座的那桌先起身,回门口重新排队。

nano-vllm 采用和 vLLM V0 默认调度相同的做法:一轮要么全是 prefill,要么全是 decode,不混批。两个阶段的输入形状不同:prefill 是多条变长的整段 prompt,走 flash_attn_varlen_func;decode 是每条序列 1 个 token,走 flash_attn_with_kvcache,还能用 CUDA Graph 回放(见 3.3、3.6)。分开调度后,每一步只需要准备一种输入、走一条执行路径。

2. 两个队列与一次 schedule

调度器维护两个双端队列(deque)和若干预算约束:

●●●Pythonclass Scheduler:
def__init__(self, config):
self.max_num_seqs = config.max_num_seqs                   # 一轮最多几条序列
self.max_num_batched_tokens = config.max_num_batched_tokens  # 一轮最多几个 token
self.eos = config.eos
self.block_size = config.kvcache_block_size
self.block_manager = BlockManager(config.num_kvcache_blocks,
                                          config.kvcache_block_size)
self.waiting = deque()    # 还没 prefill 完的序列(新请求、chunked 未算完、被抢占的)
self.running = deque()    # prefill 已完成、正在逐 token decode 的序列

一条序列的流动路径如下,黄色是 waiting 队列,蓝色是 running 队列,下方的弧线是抢占:

schedule()返回 (seqs, is_prefill),即选中的这批序列,以及这一轮是 prefill 还是 decode。它的逻辑是 prefill 优先:只要 prefill 分支选出了至少一条序列,本轮就做 prefill;一条都选不出来(waiting为空,或队头序列的块不够),才去 running做 decode。

3. Prefill 调度:吃 Token Budget

Prefill 分支从 waiting队头依次取序列,往一个 batch 里塞,直到撞上任一预算上限:

●●●Pythondefschedule(self):
    scheduled_seqs = []
    num_batched_tokens = 0
whileself.waiting andlen(scheduled_seqs) < self.max_num_seqs:
        seq = self.waiting[0]
        remaining = self.max_num_batched_tokens - num_batched_tokens  # 剩余 token 预算
if remaining == 0:
break
ifnot seq.block_table:                     # 首次调度:查前缀缓存,确认块够用
            num_cached_blocks = self.block_manager.can_allocate(seq)
if num_cached_blocks == -1:             # 块不够,放不下
break
            num_tokens = seq.num_tokens - num_cached_blocks * self.block_size
else:                                        # chunked prefill 续算:块已分配
            num_tokens = seq.num_tokens - seq.num_cached_tokens
if remaining < num_tokens and scheduled_seqs:
break# 预算不够、且已有序列:收手
ifnot seq.block_table:
self.block_manager.allocate(seq, num_cached_blocks)
# 允许对「本轮第一条」做 chunked prefill:只算预算内的部分
        seq.num_scheduled_tokens = min(num_tokens, remaining)
        num_batched_tokens += seq.num_scheduled_tokens
if seq.num_cached_tokens + seq.num_scheduled_tokens == seq.num_tokens:
            seq.status = SequenceStatus.RUNNING     # 整段 prompt 算完才转 running
self.waiting.popleft(); self.running.append(seq)
        scheduled_seqs.append(seq)
if scheduled_seqs:
return scheduled_seqs, True# is_prefill = True
# ...否则进入 decode 分支(见第 4 节)

两个预算共同构成 Token Budget:

  • 🔑 max_num_batched_tokens:一轮最多处理多少 token,主要约束 prefill(prompt 可能很长)。超了就停止往 batch 里加。
  • 🔑 max_num_seqs:一轮最多多少条序列,主要约束 decode(每条只算一个 token,但条数不能无限多)。

循环里有三个出口,含义各不相同:

  • can_allocate返回 -1就 break:队头序列的块不够时,后面即使有更短、放得下的请求也不会被调度。这是严格的先来先服务,代价是队头阻塞。
  • remaining < num_tokens and scheduled_seqs就 break:只有 batch 里已经有序列时,预算不够才收手。如果队头是一条超长 prompt,batch 还空着,调度器就用 min(num_tokens, remaining)只排预算内的一段,这就是 chunked prefill。源码注释写的是 "only allow chunked prefill for the first seq"。
  • remaining == 0就 break:第一条序列被截断后预算正好用完,下一轮循环直接退出,所以被截断的序列总是本轮唯一的一条。

被截断的序列不会离开 waiting:它仍在队头,block_table在第一次调度时已经整段分配好,状态还是 WAITING,is_prefill还是 True。下一轮它走 else分支,num_tokens按 num_tokens - num_cached_tokens算出剩余部分继续 prefill,直到最后一段被调度时才移进 running。

💡 提示:prefill 优先意味着只要 waiting队头能排上,running里的序列这一轮就不 decode。一条很长的 prompt 分成多段 chunked prefill 时,已经在生成的请求会停顿好几步,出词间隔随之变长。vLLM V1 的调度器去掉了 prefill/decode 的阶段区分,每步按固定的 token 预算给每个请求分配要算的 token 数(调度结果就是 {request_id: num_tokens}),prefill 片段和 decode token 可以在同一个 batch 里。

4. Decode 调度:抢占来腾地方

当 prefill 分支一条都没选出来,schedule()转去给 running里的序列做 decode。decode 每条序列每步只 +1 个 token,风险在于这个 token 正好要开新块,而空闲块已经用完。nano-vllm 的处理方式是抢占(preemption):

●●●Python# decode 分支
whileself.running andlen(scheduled_seqs) < self.max_num_seqs:
        seq = self.running.popleft()
whilenotself.block_manager.can_append(seq):
ifself.running:
self.preempt(self.running.pop())   # 牺牲 running 队尾的序列
else:
self.preempt(seq); break# 没有别人可牺牲,牺牲自己
else:
            seq.num_scheduled_tokens = 1
            seq.is_prefill = False# 第一次进 decode batch 时在这里置 False
self.block_manager.may_append(seq)     # 真的跨块就取新块
            scheduled_seqs.append(seq)
assert scheduled_seqs
self.running.extendleft(reversed(scheduled_seqs))  # 选中的序列按原顺序放回队头
return scheduled_seqs, False# is_prefill = False

内层 while可能连续抢占好几条,直到当前序列能追加为止。循环结束后,extendleft(reversed(...))把本轮选中的序列按原来的先后放回 running队头;因为 max_num_seqs没轮到的序列一直留在队里,排在它们后面。

抢占做的事:

●●●Pythondefpreempt(self, seq):
    seq.status = SequenceStatus.WAITING   # 打回等待队列
    seq.is_prefill = True# 下次要重新 prefill
self.block_manager.deallocate(seq)    # 释放它占的所有 KV 块,num_cached_tokens 清零
self.waiting.appendleft(seq)          # 插回队头,下一轮优先重新调度

📌 关键点:nano-vllm 的抢占策略是重计算(recomputation)而非换出(swap)。被抢占的序列直接释放 KV、打回 waiting,下次把 prompt 和已生成的 token 当成一整段重新 prefill。这比把 KV 搬到 CPU 内存再搬回来简单得多,代价是重算。重算的量通常比整段小:deallocate只把块放回空闲队列、不清哈希(见 3.4),只要这些块还没被别的请求覆盖,重新 prefill 时就能命中前缀缓存。

被牺牲的是 running队尾,也就是最近才完成 prefill 的序列。先来的请求因此能继续推进,整体接近先来先服务。它已生成的 token 通常也最少,但占用的 KV 还取决于 prompt 长度,不一定是最小的。

⚠️ 注意:while ... else的 else只在循环条件变为假(can_append成功)时执行,被 break跳出则不执行。牺牲自己的分支以 break结束,所以这条序列不会进入本轮 batch,它已经在 preempt里被插回了 waiting队头。

5. postprocess:写回与结束判定

模型算完、采样出 token 后,引擎调用 scheduler.postprocess把结果写回序列并判断是否结束:

●●●Pythondefpostprocess(self, seqs, token_ids, is_prefill):
for seq, token_id inzip(seqs, token_ids):
self.block_manager.hash_blocks(seq)   # 本轮新填满的块登记哈希(见 3.4)
        seq.num_cached_tokens += seq.num_scheduled_tokens   # 本轮算过的 token 记为已缓存
        seq.num_scheduled_tokens = 0
if is_prefill and seq.num_cached_tokens < seq.num_tokens:
continue# chunked prefill 还没算完:丢弃本轮采样结果
        seq.append_token(token_id)            # 追加采样出的新 token
if (not seq.ignore_eos and token_id == self.eos) \
or seq.num_completion_tokens == seq.max_tokens:
            seq.status = SequenceStatus.FINISHED
self.block_manager.deallocate(seq)   # 结束就释放 KV
self.running.remove(seq)

几个要点:

  • chunked prefill 的中间段也会采样:模型照常对这一段的最后一个位置算 logits、采样出一个 token,但那个位置不是 prompt 的末尾,结果没有意义,continue直接丢掉。只有最后一段算完,采样出的才是真正的第一个生成 token。
  • 结束条件:命中 EOS(且没设 ignore_eos),或生成数达到 max_tokens。满足任一就标记 FINISHED、释放 KV 块、从 running移除;未结束的序列留在 running里等下一轮 decode。max_tokens = 1的请求在 prefill 这一步就会结束,这时它已经在 schedule里被移进 running,remove不会出错。
  • ignore_eos/max_tokens是 Sequence的实例属性(构造时从 SamplingParams摊平而来,见 3.4)。

把这一节串起来,每一步的调度闭环如下图。左边是 prefill 路径(黄色),右边是 decode 路径(蓝色),红色框是 decode 时 KV 不够触发的抢占:

📝 总结

  • 调度器只做决策、不算矩阵:维护 waiting/running两个 deque,schedule()返回 (seqs, is_prefill)。
  • Prefill 优先、不混批:prefill 分支选出序列就做 prefill,否则才 decode。waiting队头放不下时直接停,严格先来先服务。
  • Token Budget= max_num_batched_tokens(约束 prefill)+ max_num_seqs(约束 decode)。只有本轮第一条序列可以被 chunked prefill 截断,截断后它留在 waiting队头续算,中间段的采样结果被丢弃。
  • Decode 遇到空闲块不足时抢占 running队尾,采用重计算而非换出:打回 waiting队头、重置 is_prefill=True、释放 KV。释放的块保留哈希,重新 prefill 时可能命中前缀缓存。
  • postprocess先登记新填满块的哈希、更新 num_cached_tokens,再追加 token;命中 EOS 或达到 max_tokens则 FINISHED并释放 KV。

📚 参考资料

  • nano-vllm GitHub 仓库
  • Efficient Memory Management for Large Language Model Serving with PagedAttention(Kwon et al., 2023)
  • Orca: A Distributed Serving System for Transformer-Based Generative Models(Yu et al., 2022)
  • vLLM 官方文档 - 架构概览
  • vLLM V1: A Major Upgrade to vLLM's Core Architecture(vLLM 官方博客,2025-01-27)

📚 推荐阅读

AI Infra学习路线

AIInfraGuide : 开源全栈AI Infra 学习教程

推理优化系列:

AIInfra推理优化(1):LLM 推理基础

AIInfra推理优化(2):vLLM 快速入门

AIInfra推理优化(3):PagedAttention - 像操作系统管理内存一样管理 KV Cache

AIInfra推理优化(4):Continuous Batching - 让 GPU 不再空等的动态批处理

AIInfra推理优化(5):Prefix Cache 与 RadixAttention 复用共享前缀的 KV

AIInfra推理优化(6):Chunked Prefill 与统一 Token Budget 调度

AIInfra推理优化(7):Attention 后端与CUDA Graph

Nano-vLLM源码学习(1):项目全景与四层架构

Nano-vLLM源码学习(2):配置、入口与一次 generate 的全流程

Nano-vLLM源码学习(3):模型骨架与核心算子

Nano-vLLM源码学习(4):KV Cache 与 BlockManager

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料