Rust in Everything

抢占

主线位置：调度这一段里「给请求分 KV 块」失败时的退路，紧挨着 02 部分的块分配。vLLM 在 Scheduler.schedule() 和 _preempt_request()，SGLang 在 update_running_batch() 和 ScheduleBatch.retract_decode()，两边都是 Python。

版本：vLLM v0.32.0、SGLang v0.5.22

结论：

  • 两边单机都只做重算：把被踢的请求的 KV 放掉，请求回等待队列，之后重新预填充 prompt 加已经生成的 token。v0.32.0 的 vLLM v1 调度器里没有换出到 CPU 的路径；SGLang 只在 PD 分离的解码端把 KV 备份到主机。
  • vLLM：运行中的请求这一步要的块分不到，就抢占 running 列表最后一个（最晚进来的）；被抢占的请求放回等待队列队首。这一步不再收新请求。
  • SGLang：每个解码步之前检查「下一步解码的 KV 放不放得下」，放不下就 retract，先踢输出最少、输入最长的；被踢的请求放回等待队列队尾，同时按实际进度重估新 token 比例，让之后的收请求更保守。
  • 重算的代价是一次额外的预填充。前缀缓存里还没被驱逐的块可以省掉一部分，两边都是如此。
stateDiagram-v2
  state "等待" as W
  state "运行" as R
  state "被抢占（vLLM PREEMPTED）" as P
  W --> R: 进批，分到 KV
  R --> P: KV 不够，被选为牺牲者
  P --> W: 放掉 KV，计数清零
  W --> R: 重新预填充 prompt 加已生成 token
  R --> [*]: 完成

vLLM v1：分不到块就从尾部踢

触发条件

只在第一段（running 循环）里发生。某个运行中的请求这一步要 num_new_tokens 个 token，allocate_slots 返回 None（空闲块不够），就开始抢占，直到分得到或者踢到自己：

vllm/v1/core/sched/scheduler.py

                while True:
                    new_blocks = self.kv_cache_manager.allocate_slots(
                        request,
                        num_new_tokens,
                        num_lookahead_tokens=self.num_lookahead_tokens,
                    )

                    if new_blocks is not None:
                        # The request can be scheduled.
                        break
                    # ...
                    # The request cannot be scheduled.
                    # Preempt the lowest-priority request.
                    if self.policy == SchedulingPolicy.PRIORITY:
                        preempted_req = max(
                            self.running,
                            key=lambda r: (r.priority, r.arrival_time),
                        )
                    else:
                        preempted_req = self.running[-1]
                    # ...
                    self._preempt_request(
                        preempted_req,
                        scheduled_timestamp,
                        drop_stale_output=self.requires_kv_delivery,
                    )
                    preempted_reqs.append(preempted_req)
                    if preempted_req == request:
                        # No more request to preempt. Cannot schedule this request.
                        break
  • fcfs（默认）下牺牲者是 running[-1]，也就是最晚进来的请求。running 循环是从头往后走的，排在前面的请求已经拿到了块，所以先进来的请求被保住。
  • priority 下牺牲者是优先级数值最大（最不优先）、平手时到达最晚的那个。它可能已经在本步排上了，这时把它占的预算退回来（第 808 行起）。
  • 踢到了请求自己，说明全让出来也不够，本步停止排 running（第 846 行）。

等待中的请求分不到块不触发抢占，只是停止扫描（第 1275 行）。而且本步只要抢占过，第二段整个跳过（第 900 行）。

被抢占之后

scheduler.py

    def _preempt_request(
        self, request: Request, timestamp: float, drop_stale_output: bool = False
    ) -> None:
        # ...
        self._free_request_blocks(request)
        self.encoder_cache_manager.free(request)
        self._inflight_prefills.discard(request)
        request.status = RequestStatus.PREEMPTED
        request.num_computed_tokens = 0
        # ...
        request.num_preemptions += 1
        # ...
        # Put the request back to the waiting queue.
        self.waiting.prepend_request(request)
  • num_computed_tokens = 0：KV 全部作废，回来时从头算。
  • 回来时要算的是 request.num_tokens，包括已经生成的输出 token，源码注释专门说了这是为了被恢复的请求（第 1127 行）。已经发给客户端的 token 不会重新采样。
  • prepend_request：FCFS 队列是一个 deque，被抢占的请求 appendleft 到队首（request_queue.py），有空间时第一个回来。

代价能省多少

放掉的块并不立刻清空。前缀缓存打开时（decoder 和 hybrid 生成模型默认打开，is_prefix_caching_supported），带块哈希的满块放回空闲队列时排在「最后驱逐」的一端（block_pool.py）。请求回来时走新请求的路径，先查前缀缓存；这些块要是还没被别人拿走，就直接命中，只重算没命中的尾部。抢占恰恰发生在块紧张的时候，这些块被复用的可能性不小，命中多少待实测（C3-2）。

减少抢占的参数

参数默认作用
scheduler_reserve_full_islTrue（config/scheduler.py）收新请求时检查整段输入放不放得下，而不只是第一块；注释说是为了防止分块预填充下的过量收入和 KV 抖动
watermark0.0（第 196 行）收等待中 / 被抢占的请求时额外留出这一比例的空闲块
max_num_seqs见连续批处理运行中请求数越少，解码阶段一起长 KV 的请求越少

检查发生在 allocate_slots 里（kv_cache_manager.py）。vLLM 不预估请求还会生成多少 token，解码过程中块不够就靠抢占兜底。

SGLang：解码前检查，先 retract 输出最少的

触发条件

SGLang 收新请求时已经按 new_token_ratio 给运行中的请求预留了未来的 token（见连续批处理），但这只是估计。真正的检查在每个解码步之前：

python/sglang/srt/managers/scheduler.py

        kv_full_retract_flag = not batch.check_decode_mem()
        if kv_full_retract_flag and finishing_reqs:
            # The queued result frees the finishing requests' KV at the end of
            # this step; decode the rest next step instead of retracting them.
            batch.batch_is_full = False
            return None
        # ...
            retracted_reqs, new_token_ratio, reqs_to_abort = batch.retract_decode()
            # ...
            self.new_token_ratio_tracker.current = new_token_ratio
            # ...
            for req in retracted_reqs:
                self._add_request_to_queue(req, is_retracted=True)
        else:
            self.new_token_ratio_tracker.decay_step()
  • 有请求本步就会因长度结束（重叠调度下结果还在队列里），就先不 retract，等它们释放。
  • 没有 retract 的解码步，new_token_ratio 往下衰减一点，收新请求变得更激进。

选谁

python/sglang/srt/managers/schedule_batch.py

        def length_key(req: Req) -> Tuple[int, int]:
            return (len(req.output_ids), -len(req.origin_input_ids))
        # ...
        sorted_indices.sort(
            key=lambda i: length_key(reqs[i]),
            reverse=True,
        )

retract_decode 从这个列表的末尾往外弹（第 3298 行）：

  • 先踢已生成 token 最少的，平手时踢输入最长的。生成得少，重算时丢的进度少；输入长，放出来的 KV 多。
  • 至少踢一个；一直踢到 check_decode_mem 通过。
  • 至少留一个（第 3310 行）。只剩一个还放不下，就把它以 OOM 中止，返回错误而不是让调度器崩溃（第 3363 行）。
  • --retraction-policy 默认 length，即上面这条；另一个选项 priority 先按优先级再按长度（schedule.py）。beam search 的组不能 retract，直接中止。

vLLM 的选法是「最晚进来的」，不看长度。两种选法在什么负载下差得多，待实测（C3-2）。

被 retract 之后

  • KV 释放，不插进前缀树：「release memory and don't insert into the tree because we need the space instantly」（第 3334 行）。之前已经 checkpoint 进树的前缀只解锁、变成可驱逐（free_kv_row 只放受保护长度之后的部分，common.py）；随后按「剩余请求数 × SGLANG_RETRACT_DECODE_STEPS（默认 20）」个 token 从树里驱逐（第 2274 行）。
  • 请求状态复位（prefix_len = 0 等，reset_for_retract），回来时重新匹配前缀、重新预填充。
  • 放回等待队列的队尾：普通模式下就是 waiting_queue.append（scheduler.py）。fcfs 下它要排在所有已经在等的请求后面；lpm 下它的前缀若还在树里，会被排到前面。
  • 新 token 比例改成按当前批实际进度重估（new_token_ratio_tracker.py）：
        total_decoded_tokens = sum(len(r.output_ids) for r in reqs)
        total_max_new_tokens = sum(r.sampling_params.max_new_tokens for r in reqs)

        new_estimate_ratio = (
            total_decoded_tokens + envs.SGLANG_RETRACT_DECODE_STEPS.get() * len(reqs)
        ) / (total_max_new_tokens + 1)  # avoid zero division

日志里会打一行「KV cache pool is full. Retract requests.」，带上 retract 了几个、腾出多少 token、比例从多少改到多少。频繁出现时，--schedule-conservativeness 调大（字段帮助就这么写，schedule.py），它乘在 new_token_ratio 的初值上。

换出只在 PD 解码端

release_req 只有在 PD 分离的解码角色下才先把 KV 备份到主机（第 2263 行），后端由 --disaggregation-decode-retraction-backup 选：cpu_tensor、host_pool 或 none，不设时按解码端的 KV 池推断（disagg.py）。源码注释说，这样回来时可以把 KV 读回来而不用重算；另有一条「重新 bootstrap」的路径走重算，会跳过这次拷贝。选 none 时被 retract 的请求以 503 中止、让客户端重试；host_pool 用尽时以 500 中止。

优先级抢占

这是另一条路，发生在收新请求时而不是解码前。--enable-priority-scheduling（默认关）打开后，enable_priority_preemption 默认跟着开（scheduler.py）。批满时，新请求的优先级比运行中某些请求高出 --priority-scheduling-preemption-threshold（默认 10）以上，就踢掉它们给新请求腾地方（preempt_to_schedule）。被踢的请求同样放回等待队列。

两边对照

vLLM v1SGLang
什么时候查给运行中的请求分块时解码步之前查整批下一步；收新请求时按预估预留
选谁fcfs：最晚进来的；priority：最不优先的输出最少、输入最长的（length）；或按优先级
KV 怎么处理放回块池，满块保留哈希、最后驱逐不进前缀树；已在树里的前缀解锁后可驱逐
回到哪里等待队列队首等待队列队尾
之后的收请求本步不收；不改后续策略重估 new_token_ratio，后续更保守
换出无只在 PD 解码端备份到主机

待实测

  • 高并发、输出长度差别大的负载下，两边的抢占 / retract 次数，以及被抢占请求的端到端延迟：待实测（C3-2）。
  • vLLM 被抢占请求回来时的前缀缓存命中比例：待实测（C3-2）。

小结

  • 两边单机都是重算，没有换出；SGLang 只在 PD 解码端备份 KV。
  • vLLM 是被动的：分不到块才踢，踢最晚进来的，放回队首，本步不收新请求。
  • SGLang 是先估后查：收请求时按比例预留未来 token，解码前再查；不够就踢输出最少的，放回队尾，同时把预留比例调到实际进度。
  • 重算的代价是一次预填充，前缀缓存里幸存的块能省掉一部分。

💬 关联讨论

发起讨论
加载中...