vLLM 架构拆解

日本語

简体中文
English
Español
Français
Deutsch
繁體中文

日本語

简体中文
English
Español
Français
Deutsch
繁體中文

Appearance

RequestQueue:FCFS と優先度キュー ​

源码版本v0.25.1

役割 ​

Scheduler は内部に三つのキューを保持します:waiting、skipped_waiting、running(waiting/running:181-184)。前二つが RequestQueue のインスタンスで、request が KV ブロックを取得するまでの間の整列を担います。RequestQueue(RequestQueue:20)自体は抽象基底クラスで、add_request、pop_request、peek_request、prepend_request、remove_request といった汎用インターフェースを定義し、具体的な順序は二つの実装で決まります:FCFSRequestQueue(FCFSRequestQueue:75)と PriorityRequestQueue(PriorityRequestQueue:131)。

キューが存在する意義は、スケジューラに「次に配置すべき request を取り出す」統一的な入口を提供することです — 下層が deque であれ heap であれ、スケジューリングの主ループは peek_request() / pop_request()(peek_request:650)だけを呼び、整列ポリシーは scheduler_config.policy で決まり、Scheduler.__init__ で create_request_queue(self.policy)(create_request_queue:181)経由で注入されます。

設計動機 ​

なぜキューを抽象化し、直接 list[Request] を使わないのか?

  • ポリシー切り替え可能:SchedulingPolicy 列挙型(SchedulingPolicy:13)は FCFS と PRIORITY の二つだけを列挙しますが、抽象基底クラスがソートの詳細を実装に隠します。スケジューラは RequestQueue インターフェースとだけやり取りし、新しいポリシー(例:公平スケジューリング)の追加は新しいサブクラスを一つ書くだけです。
  • FCFS は deque で:FCFSRequestQueue(deque[Request], RequestQueue)(FCFSRequestQueue:75)は Python の collections.deque を直接再利用し、両端 O(1) の append/popleft がまさに FCFS の最適実装です。add_request は append、pop は popleft(add/pop:78-84)。
  • priority は heap で:PriorityRequestQueue は heapq を使います(heappush:144)。順序は Request 自身の __lt__ で決まります — まず priority 昇順、次に arrival_time 昇順(docstring:131-139)。各 request に優先度を付けられます。
  • prepend セマンティクスの統一:プリエンプションや非同期依存の解消後、request を先頭に戻して優先的に再整列させる必要があります。両キューとも prepend_request を提供しますが、priority キューには「先頭」の概念がないため、prepend_request は add_request に退化します(PriorityRequestQueue.prepend:160-165)。docstring で明記されています。
  • skipped_waiting は同型を再利用:LoRA 上限超過や非同期 KV ロード等原因でスキップされた request は skipped_waiting に入れられ(step_skipped_waiting:638)、waiting と同じキュー型です。スケジューリング主ループは _select_waiting_queue_for_scheduling() で二者のうち先頭が早い方を選びます(_select_waiting_queue_for_scheduling:1867-1877)。

主要ファイル ​

  • SchedulingPolicy:13 — Enum。FCFS と PRIORITY のみ。
  • RequestQueue ABC:20 — 抽象基底クラス。add_request / pop_request / peek_request / prepend_request / remove_request / __bool__ / __len__ / __iter__ インターフェースを定義。
  • FCFSRequestQueue:75 — deque[Request] + RequestQueue を継承し、すべての操作が deque ネイティブの呼び出し。
  • FCFS add/pop:78-84 — add_request は append、pop_request は popleft。FCFS の標準実装。
  • FCFS prepend:92-94 — prepend_request は appendleft で、プリエンプトから戻された request が次ステップで優先的に再整列されるようにします。
  • FCFS prepend_requests:96-103 — prepend_requests は extendleft を使用。docstring に prepended の順序が逆になる旨の注意書きあり。
  • FCFS remove_requests:109-116 — remove_requests は deque が in-place filter をサポートしないため clear() + extend() で実装。
  • PriorityRequestQueue:131 — heapq で _heap: list[Request] を管理。
  • Priority add/pop:144-152 — heappush で入队、heappop で出队。順序は Request.__lt__ で決定。
  • Priority remove:175-184 — remove_request は list.remove の後 heapify。O(n) だがセマンティクスは正しい。
  • Priority __iter__:194-198 — 反反時は heap をコピーしてから一つずつ heappop。priority 順で反復しつつ元のヒープを破壊しません。
  • create_request_queue:201 — ファクトリ関数。SchedulingPolicy に対応するキューをインスタンス化。

データフロー ​

スケジューリング主ループは各ステップで waiting キューから次の request を選ぶ必要があるとき、peek_request() を呼びます:

python
request_queue = self._select_waiting_queue_for_scheduling()
assert request_queue is not None

request = request_queue.peek_request()
request_id = request.request_id

# try to promote blocked statuses while traversing skipped queue.
if self._is_blocked_waiting_status(
    request.status
) and not self._try_promote_blocked_waiting_request(request):
    if request.status == RequestStatus.WAITING_FOR_REMOTE_KV:
        logger.debug(
            "%s is still in WAITING_FOR_REMOTE_KV state.",
            request_id,
        )
    request_queue.pop_request()
    step_skipped_waiting.prepend_request(request)
    continue

この部分は scheduler.py:647-664 にあります。ここでは peek_request だけで即座に pop しない点に注意してください — request が本当に prefix cache、encoder 予算、LoRA 上限などの長いチェック列を通過した後でのみ、pop_request:946 で request_queue.pop_request() して running に昇格します。途中でチェックが一つでも失敗したら pop_request() + step_skipped_waiting.prepend_request() でスキップキューに移し、後ろの人をブロックしません。

_select_waiting_queue_for_scheduling(_select_waiting_queue_for_scheduling:1867)はこのラウンドで waiting と skipped_waiting のどちらから取るかを決めます。FCFS モードはシンプル:skipped_waiting or waiting or None で、skipped から戻ってきた request を優先的に整列させます。priority モードは二つのキューの先頭の (priority, arrival_time) を比較し、より小さい方を選びます。

キューの末尾に入る経路は Scheduler.add_request(add_request:2012)で、_enqueue_waiting_request(_enqueue_waiting_request:1861)を呼び、request の状態に応じて waiting か skipped_waiting かを決めます。ライフサイクル全体:waiting に入る → running に昇格 → プリエンプトされて waiting.prepend_request に戻る → 再び running に昇格、すべてのキュー操作が RequestQueue というインターフェース層を通ります。

境界と失敗 ​

  • peek_request が空キューで IndexError:FCFSRequestQueue.peek_request は空のとき raise IndexError("peek from an empty queue")(FCFS peek:88-90)、PriorityRequestQueue も同様(Priority peek:156-158)。スケジューラは _select_waiting_queue_for_scheduling で空キューに対して peek しないことを保証しますが、実装自体は防御しません。
  • remove_request は O(n):FCFS は deque.remove(O(n))、priority は list.remove + heapify(O(n) + 再構築 O(n))(Priority remove:175-178)。長いキューにはコストがあるがセマンティクスは正しい。
  • remove_requests は重複排除しない:FCFS 実装は filtered_requests = [req for req in self if req not in requests_to_remove](FCFS remove_requests:109-116)。requests_to_remove は set でないと O(1) にならず、呼び出し側が list を渡しても動くが O(n*m) になります。
  • prepend_requests の順序は逆:FCFS は extendleft を使い(docstring に prepended の順序が元のキューの出現順序と逆になる旨の注意書きあり)(FCFS prepend_requests:96-103)、priority キューは単に一つずつ add_request に退化し順序に意味はありません(Priority prepend_requests:167-173)。
  • priority キューの __iter__ はコピー:heap_copy = self._heap[:] してから一つずつ heappop(Priority __iter__:194-198)。priority 順で反復しつつ元のヒープを破壊しませんが、O(n) のメモリコピーを伴います。
  • 未知ポリシーは ValueError:create_request_queue(create_request_queue:201-208)は未知の SchedulingPolicy に対して直接 raise ValueError。Scheduler コンストラクタでも try/except で包み、より親切なエラーとして再送出します(policy 検証:174-179)。

まとめ ​

RequestQueue はスケジューラの待機エリア抽象で、FCFSRequestQueue は deque、PriorityRequestQueue は heap を使い、インターフェースは統一されています。Scheduler.schedule() の主ループはこのインターフェースセットとだけやり取りし、整列ポリシーは scheduler_config.policy で決まります。schedule がこれら二つのキューをどう使うかは Scheduler.schedule を、プリエンプト時に request をどう先頭に戻すかは プリエンプションと prefill throttle を参照してください。

公式資料:vLLM ドキュメント · README