LLM 推理调度器优先级与调度策略详解

对比 vLLM 和 SGLang 的调度策略：FCFS、优先级调度、LPM 最长前缀匹配、抢占机制、Token Budget 分配与 Chunked Prefill。

1. 调度器要解决什么问题

LLM 推理时，多个请求同时竞争有限的 GPU 资源（KV Cache、计算预算）。调度器每个 step 都要回答：

• 哪些请求先做 prefill？ （等待队列中谁先执行）
• 哪些请求继续 decode？ （已在跑的请求怎么排序）
• 资源不够时抢占谁？ （谁被踢出去）
• prefill 和 decode 谁优先？ （新请求 vs 正在生成的请求）

2. vLLM V1 的调度策略

2.1 两种调度策略

vLLM V1 支持两种策略：

class SchedulingPolicy(Enum):
    FCFS = "fcfs"          # 先来先服务（默认）
    PRIORITY = "priority"  # 优先级调度

2.2 请求的排序规则

每个请求有三个排序维度：

# vllm/v1/request.py
def __lt__(self, other: "Request") -> bool:
    # 1. 优先级数值小的优先（priority=0 比 priority=10 更优先）
    if self.priority != other.priority:
        return self.priority < other.priority
    # 2. 同优先级下，先到的优先
    if self.arrival_time != other.arrival_time:
        return self.arrival_time < other.arrival_time
    # 3. 同时到达，按 request_id 字典序
    if self.request_id != other.request_id:
        return self.request_id < other.request_id
    return id(self) < id(other)

排序规则：priority (小优先) → arrival_time (早优先) → request_id

2.3 两种队列实现

FCFSRequestQueue:      使用 deque（双端队列）
  入队: append() → 队尾
  出队: popleft() → 队首
  特点: 严格先进先出，不看 priority

PriorityRequestQueue:  使用 heapq（最小堆）
  入队: heappush()
  出队: heappop() → 弹出最小元素
  特点: 始终弹出 priority 最小（最优先）的请求

2.4 V1 schedule() 的完整流程

schedule() 每个 step 调用一次:

┌─────────────────────────────────────────────────┐
│  Phase 1: 调度 RUNNING 请求 (decode)             │
│                                                  │
│  遍历 self.running 列表:                          │
│    对每个请求:                                    │
│      ├─ 尝试分配 KV cache blocks                  │
│      ├─ 成功 → 减少 token_budget, 继续           │
│      └─ 失败 → 需要抢占!                         │
│           ├─ FCFS:     抢占列表中最后一个请求     │
│           └─ PRIORITY: 抢占 priority 最大的请求   │
│                                                  │
│  token_budget 初始值 = max_num_scheduled_tokens  │
│  每调度一个 running 请求, budget 减 1 (decode)    │
└─────────────────────────────────────────────────┘
                    │
                    ▼
┌─────────────────────────────────────────────────┐
│  Phase 2: 调度 WAITING 请求 (prefill)            │
│                                                  │
│  前提: Phase 1 中没有发生抢占!                    │
│  (如果有抢占, 本轮不调度新请求)                   │
│                                                  │
│  从 waiting 队列取请求:                           │
│    ├─ FCFS:     取队首 (最早到达的)               │
│    └─ PRIORITY: 取堆顶 (priority 最小的)         │
│                                                  │
│  检查约束:                                        │
│    ├─ token_budget 是否够?                       │
│    ├─ KV cache 是否够分配?                       │
│    ├─ LoRA 适配器数量限制?                       │
│    └─ 其他约束 (FSM, encoder cache)              │
│                                                  │
│  通过 → 移入 running, 减少 budget                │
│  不通过 → 移入 skipped_waiting, 尝试下一个       │
└─────────────────────────────────────────────────┘

2.5 抢占策略详解

当 KV cache 不足以容纳所有 running 请求时，必须抢占（preempt）某个请求：

# FCFS 模式: 抢占最后加入的请求（最新的）
if policy == FCFS:
    victim = self.running.pop()    # 移除最后一个

# PRIORITY 模式: 抢占优先级最低的请求
if policy == PRIORITY:
    victim = max(
        self.running,
        key=lambda r: (r.priority, r.arrival_time),
    )
    # priority 最大 = 优先级最低 → 被抢占
    # 同 priority 时, arrival_time 最晚的被抢占

被抢占的请求：

def _preempt_request(self, request):
    self.kv_cache_manager.free(request)       # 释放 KV cache
    request.status = RequestStatus.PREEMPTED
    request.num_computed_tokens = 0            # 清除计算进度!
    request.num_preemptions += 1               # 抢占计数+1
    self.waiting.prepend_request(request)      # 放回等待队列头部

重要：被抢占的请求 num_computed_tokens 清零，下次调度需要重新 prefill，这是很大的浪费。所以调度器尽量避免抢占。

2.6 Token Budget 分配

token_budget = max_num_scheduled_tokens  (如 8192)

Phase 1 (decode):
  每个 running 请求消耗 1 token (decode 阶段)
  如果有 100 个 running 请求 → 消耗 100 tokens

Phase 2 (prefill):
  剩余 budget = 8192 - 100 = 8092 tokens
  新请求的 prompt 有 2048 tokens → 消耗 2048
  下一个请求 1024 tokens → 消耗 1024
  ...直到 budget 用完

长 prefill 处理:
  如果某个请求的 prompt 超过 long_prefill_token_threshold:
    实际调度 token 数 = min(prompt_len, threshold)
    剩余部分下一个 step 继续 (chunked prefill)

2.7 Prefill vs Decode 的优先级

vLLM V1 的策略是 decode 优先于 prefill：

Phase 1 先处理 running (decode) → Phase 2 再处理 waiting (prefill)

原因:
  1. decode 请求已经占用了 KV cache，不处理就浪费
  2. decode 每步只需 1 token 计算量，成本低
  3. 用户已经在等 decode 的响应，优先完成减少延迟
  4. 如果 Phase 1 发生了抢占，Phase 2 直接跳过
     → 确保 running 请求有足够资源

2.8 skipped_waiting 队列

有些 waiting 请求暂时无法调度（约束不满足），但不是永久不行：

场景:
  Request A: 需要 LoRA adapter "lora_1"
  Request B: 需要 LoRA adapter "lora_2"
  当前已加载 max_loras 个 adapter → A 暂时无法调度

处理:
  A 移入 skipped_waiting → 不影响后面 B 的调度
  下一个 step 重新检查 skipped_waiting

选择逻辑:
  FCFS:     优先从 skipped_waiting 取（它们等得更久）
  PRIORITY: 比较两个队列的队首，取 priority 更小的

3. SGLang 的调度策略

SGLang 提供了更丰富的调度策略。

3.1 六种调度策略

# Cache-Aware（感知前缀缓存的策略）:
LPM          # Longest Prefix Match: 优先调度与缓存共享前缀最长的请求
DFS_WEIGHT   # DFS 加权: 基于 Radix Tree 的深度优先搜索权重

# Cache-Agnostic（不感知缓存的策略）:
FCFS         # 先来先服务
LOF          # Longest Output First: 预计生成最多 token 的先做
RANDOM       # 随机
ROUTING_KEY  # 按路由键频率优先（适用于 LoRA 场景）

3.2 LPM（Longest Prefix Match）— SGLang 特色

场景: Radix Tree 中已缓存了 system prompt 的 KV cache

等待队列:
  Request A: tokens = [sys_prompt, query_1]   → 与缓存匹配 100 tokens
  Request B: tokens = [sys_prompt, query_2]   → 与缓存匹配 100 tokens
  Request C: tokens = [other_prompt, query_3] → 与缓存匹配 0 tokens

LPM 排序: A ≈ B > C
  优先处理能最大化复用缓存的请求 → 减少 prefill 计算量

为什么有效？ 如果先处理 C（没有缓存命中），C 的 KV cache 可能会把 A、B 的缓存驱逐出去。先处理 A、B 可以最大化缓存利用。

3.3 LOF（Longest Output First）

def _sort_by_longest_output(waiting_queue):
    waiting_queue.sort(key=lambda x: -x.sampling_params.max_new_tokens)

直觉：预计输出最长的请求先做。因为长输出请求会长时间占用 KV cache，越早开始越早释放。如果让短请求先做，长请求一直等着，最终整体吞吐反而下降。

3.4 优先级调度

SGLang 支持通过 API 指定请求优先级：

# 排序逻辑
def _sort_by_priority_and_fcfs(waiting_queue, priority_sign):
    waiting_queue.sort(
        key=lambda x: (
            x.priority * priority_sign,     # 优先级
            x.time_stats.wait_queue_entry_time,  # 同优先级按 FCFS
        )
    )

# priority_sign 控制方向:
#   +1: 数值小的优先 (priority=0 最优先)
#   -1: 数值大的优先 (priority=100 最优先)

优先级可以叠加到所有策略上：比如 LOF + Priority = 先按优先级排，同优先级内按输出长度排。

3.5 SGLang 的抢占与退让

# 主动抢占: 高优先级新请求到来时
if enable_priority_scheduling:
    # 找等待队列中优先级最低的请求
    idx, candidate = max(enumerate(waiting_queue), key=key_fn)
    # 如果新请求优先级更高 → 踢掉候选请求
    if new_req.priority < candidate.priority:
        abort_existing_req = True

# OOM 退让: KV cache 用完时
def retract_decode(running_batch):
    # 从 running batch 中移除请求, 放回 waiting queue
    # 标记 is_retracted = True
    # 下次调度时优先处理

3.6 动态 Token Budget

SGLang 使用动态 new_token_ratio：

vLLM: token_budget 是固定配置
SGLang: token_budget 根据实际情况动态调整

new_token_ratio = 预留给 decode 新 token 的 KV cache 比例

如果频繁 OOM retraction → 增大 new_token_ratio → 更保守
如果 KV cache 利用率低   → 减小 new_token_ratio → 更激进

4. Prefill vs Decode 的调度哲学

4.1 vLLM 的方式：Decode 优先

Step N:
  1. 先调度所有 running 请求 (decode, 每个 1 token)
  2. 剩余 budget 给 waiting 请求 (prefill)

优点: running 请求不被饿死，延迟可预测
缺点: 新请求可能等很久才开始 prefill

4.2 SGLang 的方式：分离 Prefill 和 Decode Batch

Step N:
  如果有新的 prefill batch → 执行 prefill
  否则 → 执行 decode batch

SGLang 把 prefill 和 decode 分成独立的 batch:
  prefill batch: 只做 prefill
  decode batch:  只做 decode

好处: prefill 和 decode 的计算特性不同，分开可以各自优化

4.3 Chunked Prefill（分块预填充）

长 prompt 可以分多个 step 完成 prefill，与 decode 共享 token budget：

prompt = 8000 tokens, token_budget = 4096

不用 chunked prefill:
  Step 1: prefill 8000 tokens  ← 这一步很慢，decode 全部阻塞!
  Step 2: decode...

用 chunked prefill:
  Step 1: prefill 前 4000 tokens + decode 其他请求的 96 tokens
  Step 2: prefill 后 4000 tokens + decode 其他请求的 96 tokens
  Step 3: 该请求也进入 decode

好处: 长 prefill 不会阻塞其他请求的 decode → TTFT↓ 不影响 TPOT

5. 对比总结

维度	vLLM V1	SGLang
默认策略	FCFS	FCFS（可选 LPM/LOF/等）
优先级支持	priority 字段 + 堆排序	priority + sign 方向 + 叠加策略
队列实现	deque (FCFS) / heapq (PRIORITY)	list + sort (每次重排)
缓存感知	无	LPM / DFS_WEIGHT
抢占选择	FCFS: 最新的; PRIORITY: 最低优先级	主动踢低优先级 + OOM 退让
被抢占处理	清零进度，放回 waiting 头部	标记 retracted，优先重新调度
Prefill/Decode	同一 step 混合，decode 先	分离 batch
Token Budget	固定配置	动态 new_token_ratio
Chunked Prefill	支持（显式开启）	支持（动态分块）

6. 调度器的核心权衡

吞吐量 (Throughput) ←────────→ 延迟 (Latency)

高吞吐:                         低延迟:
  大 batch → GPU 利用率高          小 batch → 单请求等待时间短
  decode 优先 → 不浪费 KV cache    prefill 优先 → 新请求快速开始
  LOF → 长任务早完成早释放          FCFS → 公平，无饿死

缓存利用率:
  LPM → 最大化缓存命中 → 减少计算 → 间接提升吞吐和延迟

7. 源码索引

组件	文件
vLLM V1 调度器	vllm/v1/core/sched/scheduler.py
vLLM 请求优先级比较	vllm/v1/request.py:281-292
vLLM 队列实现	vllm/v1/core/sched/request_queue.py
SGLang 调度器	sglang/srt/managers/scheduler.py
SGLang 调度策略	sglang/srt/managers/schedule_policy.py
教学代码（简化调度）	vllm_learn/code/course3/sche.py

8. 一句话总结

调度器按 priority → arrival_time 排序请求，FCFS 模式下先到先做，PRIORITY 模式下堆排序取最优先；资源不足时抢占优先级最低的请求（FCFS 抢最新的）；decode 优先于 prefill（已占资源的先做完）；SGLang 额外提供 LPM（最长前缀匹配）来最大化 RadixTree 缓存命中。