FCFS 排队下的长请求饥饿：队首阻塞、抢占选取与队列顺序

2024-09-11

在一台 8 卡 **** 的 ****（8 卡，单卡 64GB HBM，卡间互联 392 GB/s）上，用 **** 的基础软件栈配合 vLLM（v<版本>，v0 引擎）起 OpenAI 兼容服务，--max-num-seqs 与 --max-num-batched-tokens 取默认，分块预填充未开。压测用 benchmarks/benchmark_serving.py 提交混合长度负载，长 prompt 与短请求交错到达。曲线里 vllm:num_requests_waiting 长期不为零，周期日志行的 Pending: 不回落，vllm:gpu_cache_usage_perc 贴顶，短请求的 TTFT 出现长尾；把长 prompt 从负载里撤掉后等待队列随即排空。该版本的调度器实际只跑 FCFS，对外没有可切换的策略开关，队列里的先后顺序决定了谁先被服务、谁先被抢占。

三个队列与 FCFS

调度器持有三个队列，都是无界双端队列：waiting（Deque[SequenceGroup] = deque()）、running、swapped。新请求由 add_seq_group 追加到 waiting 队尾；调度时按 FIFO 取队首（waiting_queue[0] 后 popleft），队尾位置只在抢占时用到。该版本的 SchedulerConfig 没有 policy 字段。策略抽象本身是有的：vllm/core/policy.py 定义了 Policy 基类、FCFS 实现和 PolicyFactory 注册表，但注册表里只有 _POLICY_REGISTRY = {'fcfs': FCFS} 一项，调度器还在 _schedule_prefills 与 _schedule_running 里各把策略名硬编码成 PolicyFactory.get_policy(policy_name="fcfs")，所以换不了。这个抽象实际起作用的地方是两处 sort_by_priority 调用（分别排 running 与 swapped 队列），而 FCFS.get_priority 返回 now - seq_group.metrics.arrival_time，排出来的结果等价于按到达时间。

三处顺序决定谁先被服务

位置	代码行为	后果
新请求入队	`self.waiting.append(seq_group)`	严格 FIFO，先到先服务
prefill 选取	从队首开始；`can_allocate == AllocStatus.LATER` 时 `break`；`budget.can_schedule` 不足时 `break`	队首请求占不下就整段停止，队首之后的请求本步全部跳过
超限 prompt	`num_new_tokens > prompt_limit` 时置 `SequenceStatus.FINISHED_IGNORED`、`popleft` 后 `continue`	超限请求被丢弃，不阻塞队列
抢占 victim	`victim_seq_group = running_queue.pop()`	抢占取 `running` 队尾，即最近进入 running 的序列
被重算的抢占者	`self.waiting.extendleft(running_scheduled.preempted)`	被抢占序列插到 `waiting` 队首，优先于纯新请求重新调度
swapped 优先	`if not self.swapped:` 才调用 `_schedule_prefills`	只要 `swapped` 非空，新的 prefill 完全停摆

prompt_limit 的取法随分块预填充变化：未开分块时为 min(max_model_len, max_num_batched_tokens)，开了分块时为 max_model_len。因此未开分块时，长度超过 max_num_batched_tokens 的 prompt 直接被判 FINISHED_IGNORED，日志打 Input prompt (%d tokens) is too long and exceeds limit of %d。

饥饿的三条路径

队首阻塞。_schedule_prefills 只从队首开始尝试，遇到 AllocStatus.LATER 或 token 预算不足即 break。一个长 prompt 排在队首时，它占不下就让整步的前缀阶段停摆，排在它之后的短请求同一步全部得不到调度，即使短请求单独看完全放得下。
抢占者插回队首。显存紧张时 _schedule_running 逐个弹出 running 队尾并抢占（PreemptionMode 为 RECOMPUTE 或 SWAP），被重算的序列经 extendleft 回到 waiting 队首。长序列占用块多，反复触发抢占并重算，每次回到队首，新到的请求持续被插队；抢占累计每 50 次打一条 Sequence group %s is preempted by %s mode because there is not enough KV cache space. ... total_num_cumulative_preemption=%d。
swap 优先。_schedule_default 在 self.swapped 非空时跳过整个前缀阶段，被换出的解码序列优先于 waiting 里的新请求回来。--swap-space 给得越大，这条路径的持续时间越长。

该版本的抢占 victim 取 running 队尾，意味着在 running 里待得最久、通常也是最长的那批序列反而不容易被抢占；被踢出的是最近进入 running 的短请求。这与按到达时间或按优先级挑选 victim 的策略方向相反。

触发条件与现象

负载长度方差大：长 prompt 与短请求混合，且长 prompt 的 token 数接近或超过 max_num_batched_tokens。
未开分块预填充：前缀与解码不混批，前缀步不产出解码 token，长 prompt 占满单步预算。
显存预算偏紧：--gpu-memory-utilization 低或模型大，num_gpu_blocks 偏小，抢占频繁。
swapped 长期非空：--swap-space 给得大而显存不足，前缀阶段被持续跳过。
可观测形态：vllm:num_requests_waiting 高位不降，vllm:num_requests_swapped 与 vllm:gpu_cache_usage_perc 同时偏高，TTFT 分布出现长尾而 TPOT 的均值变化不大。

定位步骤

抓周期日志行，读 Running: %d reqs, Swapped: %d reqs, Pending: %d reqs, GPU KV cache usage: %.1f%%, CPU KV cache usage: %.1f%%。Pending 高位不降是等待队列积压的直接证据。
看等待队列的构成。统计积压请求的 prompt 长度，判断是否与队首长 prompt 的长度分布重合；若积压集中在长 prompt 到达之后，指向队首阻塞。
查抢占计数。搜 is preempted by 与 total_num_cumulative_preemption，计数持续增长说明重算路径被反复触发。
查被丢弃的超限请求。搜 Input prompt (%d tokens) is too long，区分「被丢弃」与「在排队」两种不同的长请求结局。
对照块数。读 # GPU blocks: %d, # CPU blocks: %d，与显存预算配置核对，判断预算是否被压缩到不足以容纳并发长序列。
复现对照。同一请求集下把负载里的最长 prompt 去掉或把 --max-num-batched-tokens 调大，若等待队列随之排空，饥饿来自队首阻塞而非到达速率。

# 混合长度负载，有限到达率（字段名与默认值取自该版本压测脚本）
python benchmarks/benchmark_serving.py \
  --backend vllm \
  --model <model-path> \
  --dataset-name sharegpt \
  --dataset-path <dataset-path> \
  --num-prompts 512 \
  --request-rate 8 \
  --percentile-metrics ttft,tpot,itl,e2el \
  --metric-percentiles 50,95,99 \
  --save-result --result-dir ./results

# --request-rate 默认为 inf，即全部请求在第 0 时刻发出；要复现排队必须给有限值（泊松到达）。
# --random-range-ratio 默认 1.0，配合 --dataset-name random 时控制长度采样区间的宽度。

# 观察队列与抢占
grep -E "Pending:|is preempted by|Input prompt .* is too long" server.log
# 抓 Prometheus 指标
curl -s <endpoint>:8000/metrics | grep -E "vllm:num_requests_(waiting|running|swapped)|vllm:gpu_cache_usage_perc"

处置

方向	动作	代价 / 前提
队首阻塞	开 `--enable-chunked-prefill`，让长 prompt 按块混入解码	分块开启后调度改为解码优先，`TTFT` 上升
单步预算不足	调大 `--max-num-batched-tokens`	峰值激活显存上升，画像后 KV 池变小
抢占频繁	提高 `--gpu-memory-utilization` 或加 `--tensor-parallel-size`	需重新画像，留出激活余量；告警文本即给出这两条
抢占路径	缩小 `--swap-space`，减少 swap 优先的持续窗口	swap 容量小则长序列更易被重算
并发过高	调低 `--max-num-seqs`	稳态吞吐下降
长输出占用	限制 `max_tokens`，或校验客户端的 `ignore_eos`	请求侧行为需一并约束
需要按优先级调度	该版本没有此开关；按优先级调度是更晚的版本才进入（`v<版本>`）	本版本只能在队列顺序之外腾预算

记录字段

# 一条排队与饥饿记录（字段名示意）
engine:                    # vLLM v0 引擎
scheduling_policy: fcfs    # 该版本无策略开关，恒为 FIFO
max_num_seqs:
max_num_batched_tokens:
enable_chunked_prefill:
swap_space:                # GiB
gpu_memory_utilization:
block_size:
load:
  input_len_dist:          # 长度分布，写明最长 prompt 的 token 数
  request_rate:            # 到达率；inf 表示全部在第 0 时刻发出
  num_prompts:
observe:
  num_requests_waiting:    # vllm:num_requests_waiting
  num_requests_running:
  num_requests_swapped:
  gpu_cache_usage_perc:    # vllm:gpu_cache_usage_perc
  pending_line:            # 周期日志里的 Pending 值
  preemption_count:        # total_num_cumulative_preemption
  ignored_prompts:         # 被 FINISHED_IGNORED 的超限请求数
  ttft_p99_ms:
  tpot_p99_ms:
pools:
  num_gpu_blocks:          # 取自 # GPU blocks
  num_cpu_blocks:
status:                    # 队首阻塞 / 抢占插队 / swap 优先

小结

该版本的调度是纯 FCFS：waiting 严格先进先出，抢占取 running 队尾，被重算的抢占者经 extendleft 回到等待队首，swapped 非空时新前缀停摆。长请求饥饿因此有三条来源：队长 prompt 在队首占不下而使整步停摆、被抢占的长序列反复插回队首、以及 swap 优先让新请求持续等待。判定顺序是先读 Pending 与 num_requests_waiting 确认积压，再按长度分布与 is preempted by 计数区分阻塞路径，最后用去长 prompt 或放大 max_num_batched_tokens 的对照确认归因。本版本没有 --scheduling-policy，能动的只是预算、并发与分块三项。