RequestQueue: FCFS and priority queues

源码版本v0.25.1

Responsibilities

The Scheduler maintains three queues internally: waiting, skipped_waiting, and running (waiting/running:181-184). The first two are instances of RequestQueue, responsible for queuing requests before they acquire KV blocks. RequestQueue (RequestQueue:20) is itself an abstract base class defining a common interface — add_request, pop_request, peek_request, prepend_request, remove_request, and so on. The actual ordering is decided by two implementations: FCFSRequestQueue (FCFSRequestQueue:75) and PriorityRequestQueue (PriorityRequestQueue:131).

The queue exists to give the scheduler a single entry point for "get the next request to schedule" — whether the underlying data structure is a deque or a heap, the main scheduling loop only calls peek_request() / pop_request() (peek_request:650). The queuing policy is chosen by scheduler_config.policy and injected in Scheduler.__init__ via create_request_queue(self.policy) (create_request_queue:181).

Design motivation

Why abstract the queue instead of just using list[Request]?

• Pluggable policy: The SchedulingPolicy enum (SchedulingPolicy:13) only lists FCFS and PRIORITY, but the abstract base class hides ordering details inside the implementations. The scheduler only deals with the RequestQueue interface; adding a new policy (e.g. fair scheduling) is just a new subclass.
• FCFS uses a deque: FCFSRequestQueue(deque[Request], RequestQueue) (FCFSRequestQueue:75) reuses Python's collections.deque directly — O(1) append/popleft on both ends is the optimal FCFS implementation. add_request is append, pop is popleft (add/pop:78-84).
• Priority uses a heap: PriorityRequestQueue uses heapq (heappush:144). Ordering is decided by Request.__lt__ itself — first by priority ascending, then by arrival_time ascending (docstring:131-139) — letting users assign a priority to each request.
• Unified prepend semantics: After preemption or async dependency resolution, a request needs to be put back at the head of the queue for re-scheduling. Both queues provide prepend_request, but priority queues have no notion of "head", so prepend_request degenerates to add_request (PriorityRequestQueue.prepend:160-165) — documented explicitly in the docstring.
• skipped_waiting reuses the same type: Requests skipped due to LoRA limits, async KV loading, etc. are pushed into skipped_waiting (step_skipped_waiting:638). It is the same queue type as waiting; the main scheduling loop uses _select_waiting_queue_for_scheduling() to pick whichever head is earlier (_select_waiting_queue_for_scheduling:1867-1877).

Key files

• SchedulingPolicy:13 — Enum with only FCFS and PRIORITY.
• RequestQueue ABC:20 — Abstract base class defining add_request / pop_request / peek_request / prepend_request / remove_request / __bool__ / __len__ / __iter__.
• FCFSRequestQueue:75 — Inherits deque[Request] + RequestQueue; all operations are native deque calls.
• FCFS add/pop:78-84 — add_request goes through append, pop_request through popleft — the standard FCFS implementation.
• FCFS prepend:92-94 — prepend_request uses appendleft, so a preempted request gets re-scheduled first in the next step.
• FCFS prepend_requests:96-103 — prepend_requests uses extendleft; note the docstring warns the prepended order is reversed.
• FCFS remove_requests:109-116 — remove_requests uses clear() + extend() because deque does not support in-place filter.
• PriorityRequestQueue:131 — Uses heapq to maintain _heap: list[Request].
• Priority add/pop:144-152 — heappush to enqueue, heappop to dequeue; ordering decided by Request.__lt__.
• Priority remove:175-184 — remove_request calls list.remove then heapify — O(n), but semantically correct.
• Priority __iter__:194-198 — Iteration copies the heap and pops element by element, guaranteeing priority-order traversal without mutating the original heap.
• create_request_queue:201 — Factory instantiating the matching queue per SchedulingPolicy.

Data flow

When the main scheduling loop needs to pick the next request from the waiting queue each step, it calls peek_request():

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

This is in scheduler.py:647-664. Note that it only peek_requests without popping immediately — the request is only detached via request_queue.pop_request() at pop_request:946 after it passes a long chain of checks (prefix cache, encoder budget, LoRA limits, etc.) and is promoted into running. If any check along the way fails, pop_request() + step_skipped_waiting.prepend_request() moves the request to the skipped queue so it does not block the requests behind it.

_select_waiting_queue_for_scheduling (_select_waiting_queue_for_scheduling:1867) decides whether this round pulls from waiting or skipped_waiting. FCFS mode is simple: skipped_waiting or waiting or None — skipped requests coming back are scheduled first. Priority mode compares the (priority, arrival_time) of both heads and picks the smaller one.

The enqueue path lives in Scheduler.add_request (add_request:2012), which calls _enqueue_waiting_request (_enqueue_waiting_request:1861) and then routes to either waiting or skipped_waiting based on the request status. The full lifecycle: enter waiting → promote to running → preempted back to waiting.prepend_request → promote to running again. All queue operations go through the RequestQueue interface.

Boundaries and failure modes

• peek_request raises IndexError on empty queue: FCFSRequestQueue.peek_request does raise IndexError("peek from an empty queue") when empty (FCFS peek:88-90); PriorityRequestQueue does the same (Priority peek:156-158). The scheduler uses _select_waiting_queue_for_scheduling to guarantee it never peeks at an empty queue, but the implementations themselves do not defend against it.
• remove_request is O(n): FCFS goes through deque.remove (O(n)); priority goes through list.remove + heapify (O(n) + O(n) re-heapify) (Priority remove:175-178). Expensive for long queues but semantically correct.
• remove_requests does not deduplicate: In the FCFS implementation filtered_requests = [req for req in self if req not in requests_to_remove] (FCFS remove_requests:109-116). requests_to_remove must be a set to be O(1); passing a list works but becomes O(n*m).
• prepend_requests reverses order: FCFS uses extendleft (the docstring warns the prepended order is reversed relative to the input order) (FCFS prepend_requests:96-103); the priority queue degenerates to per-element add_request, where order is meaningless (Priority prepend_requests:167-173).
• Priority queue __iter__ copies: heap_copy = self._heap[:] then pops element by element (Priority __iter__:194-198), guaranteeing priority-order traversal without destroying the original heap, at the cost of an O(n) memory copy.
• Unknown policy raises ValueError: create_request_queue (create_request_queue:201-208) directly raise ValueErrors on unknown SchedulingPolicy. The Scheduler constructor wraps this in a try/except to re-raise a friendlier error (policy validation:174-179).

Summary

RequestQueue is the scheduler's waiting-area abstraction. FCFSRequestQueue uses a deque, PriorityRequestQueue uses a heap, with a unified interface. The main loop of Scheduler.schedule() only deals with this interface; the queuing policy is decided by scheduler_config.policy. To see how schedule uses these two queues, read Scheduler.schedule; to see how a request is pushed back to the head on preemption, read Preemption and prefill throttle.

See official docs: vLLM docs · README