RequestQueue: FCFS y cola por prioridad

源码版本v0.25.1

Responsabilidades

El Scheduler mantiene internamente tres colas: waiting, skipped_waiting y running (waiting/running:181-184). Las dos primeras son instancias de RequestQueue, encargadas de poner en cola los requests antes de que reciban bloques KV. RequestQueue (RequestQueue:20) es una clase base abstracta que define un conjunto común de interfaces (add_request, pop_request, peek_request, prepend_request, remove_request, etc.); el orden concreto lo deciden dos implementaciones: FCFSRequestQueue (FCFSRequestQueue:75) y PriorityRequestQueue (PriorityRequestQueue:131).

El motivo de ser de la cola es ofrecer al planificador un punto único de "dame el siguiente request a planificar": da igual que por debajo haya un deque o un heap, el bucle principal del planificador solo llama peek_request() / pop_request() (peek_request:650). La política de encolado la decide scheduler_config.policy, y se inyecta en Scheduler.__init__ vía create_request_queue(self.policy) (create_request_queue:181).

Motivación de diseño

¿Por qué abstraer la cola en vez de usar directamente list[Request]?

• Política intercambiable: el enum SchedulingPolicy (SchedulingPolicy:13) solo lista FCFS y PRIORITY, pero la clase base esconde los detalles de ordenación en la implementación. El planificador habla solo con la interfaz RequestQueue; añadir una nueva política (p. ej. fair scheduling) basta con escribir una nueva subclase.
• FCFS va con deque: FCFSRequestQueue(deque[Request], RequestQueue) (FCFSRequestQueue:75) reutiliza directamente collections.deque de Python; append/popleft en O(1) por ambos extremos es justo la implementación óptima para FCFS. add_request es append, y pop es popleft (add/pop:78-84).
• Priority va con heap: PriorityRequestQueue usa heapq (heappush:144); el orden lo decide el __lt__ del propio Request: primero por priority ascendente, luego por arrival_time ascendente (docstring:131-139), permitiendo asignar a cada request una prioridad.
• Semántica unificada de prepend: tras una preemption o cuando se desbloquea una dependencia asíncrona, hace falta devolver un request a la cabeza de la cola para que se reprograne primero. Ambas colas ofrecen prepend_request, pero en la cola priority no existe el concepto de "cabeza", así que prepend_request degenera en add_request (PriorityRequestQueue.prepend:160-165), aclarado en el docstring.
• skipped_waiting reutiliza el mismo tipo: los requests saltados por exceder LoRA, por async KV load, etc., se meten en skipped_waiting (step_skipped_waiting:638); es la misma clase de cola que waiting, y el bucle principal del planificador usa _select_waiting_queue_for_scheduling() para elegir entre las dos la que tenga la cabeza más temprana (_select_waiting_queue_for_scheduling:1867-1877).

Archivos clave

• SchedulingPolicy:13 — Enum, solo FCFS y PRIORITY.
• RequestQueue ABC:20 — clase base abstracta que define add_request / pop_request / peek_request / prepend_request / remove_request / __bool__ / __len__ / __iter__.
• FCFSRequestQueue:75 — hereda de deque[Request] + RequestQueue; todas las operaciones son llamadas nativas del deque.
• FCFS add/pop:78-84 — add_request va por append, pop_request por popleft; la implementación estándar de FCFS.
• FCFS prepend:92-94 — prepend_request usa appendleft, de modo que un request devuelto tras preemption se reprograne primero en el siguiente paso.
• FCFS prepend_requests:96-103 — prepend_requests usa extendleft; ojo al docstring que recuerda que el orden de los prepended queda invertido respecto al original.
• FCFS remove_requests:109-116 — como el deque no soporta filter in-place, remove_requests hace clear() + extend().
• PriorityRequestQueue:131 — mantiene _heap: list[Request] con heapq.
• Priority add/pop:144-152 — heappush para encolar, heappop para desencolar; el orden lo decide Request.__lt__.
• Priority remove:175-184 — remove_request primero hace list.remove y luego heapify; O(n), pero semánticamente correcto.
• Priority __iter__:194-198 — al iterar, copia el heap y luego hace heappop uno a uno, garantizando un recorrido por orden de prioridad sin romper el heap original.
• create_request_queue:201 — función factoría que instancia la cola correspondiente según SchedulingPolicy.

Flujo de datos

Cuando el bucle principal del planificador necesita, en cada step, elegir el siguiente request desde la cola waiting para planificar, llama 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

Esto está en scheduler.py:647-664. Ojo: aquí solo se hace peek_request sin hacer pop inmediato; solo cuando el request pasa de verdad por toda la cadena de comprobaciones (prefix cache, presupuesto de encoder, límites de LoRA, etc.) se llama request_queue.pop_request() en pop_request:946 para sacarlo y promoverlo a running. Si cualquier comprobación intermedia falla, se usa pop_request() + step_skipped_waiting.prepend_request() para moverlo a la cola skipped sin bloquear a los que vienen detrás.

_select_waiting_queue_for_scheduling (_select_waiting_queue_for_scheduling:1867) decide de cuál de las dos colas (waiting o skipped_waiting) se saca en esta ronda. En modo FCFS es simple: skipped_waiting or waiting or None, priorizando los requests que vuelven de skipped. En modo priority compara las dos cabezas por (priority, arrival_time) y elige la menor.

La entrada por la cola se hace en Scheduler.add_request (add_request:2012), que llama a _enqueue_waiting_request (_enqueue_waiting_request:1861) y luego, según el estado del request, lo manda a waiting o a skipped_waiting. El ciclo de vida completo: entra en waiting → asciende a running → es preemptado y vuelve vía waiting.prepend_request → vuelve a ascender a running; toda manipulación de colas pasa por la interfaz RequestQueue.

Límites y fallos

• peek_request lanza IndexError en cola vacía: FCFSRequestQueue.peek_request cuando está vacía hace raise IndexError("peek from an empty queue") (FCFS peek:88-90); PriorityRequestQueue igual (Priority peek:156-158). El planificador usa _select_waiting_queue_for_scheduling para garantizar que nunca hace peek sobre una cola vacía, pero la implementación no se defiende por sí misma.
• remove_request es O(n): FCFS pasa por deque.remove (O(n)), priority por list.remove + heapify (O(n) + O(n) de reordenación) (Priority remove:175-178); para colas largas hay coste, pero la semántica es correcta.
• remove_requests no deduplica: la implementación FCFS hace filtered_requests = [req for req in self if req not in requests_to_remove] (FCFS remove_requests:109-116); requests_to_remove debe ser un set para que la comprobación sea O(1); si el llamador pasa una lista, se degrada a O(n*m).
• prepend_requests invierte el orden: FCFS usa extendleft (el docstring avisa de que el orden de los prepended queda invertido respecto al orden de aparición en la cola original) (FCFS prepend_requests:96-103); la cola priority degenera en llamadas sueltas a add_request, donde el orden no importa (Priority prepend_requests:167-173).
• __iter__ de la cola priority copia: heap_copy = self._heap[:] y luego heappop uno a uno (Priority __iter__:194-198) para garantizar un recorrido por orden de prioridad sin romper el heap original, a cambio de una copia O(n) en memoria.
• Política desconocida lanza ValueError: create_request_queue (create_request_queue:201-208) hace raise ValueError para SchedulingPolicy desconocido; el constructor de Scheduler además lo envuelve en un try/except que relanza un error más amable (policy 校验:174-179).

Resumen

RequestQueue es la abstracción de sala de espera del planificador: FCFSRequestQueue va con deque, PriorityRequestQueue va con heap, con interfaz unificada. El bucle principal de Scheduler.schedule() solo habla con esta interfaz; la política de encolado la decide scheduler_config.policy. Para ver cómo schedule usa estas dos colas, leer Scheduler.schedule; para ver cómo se devuelve un request a la cabeza tras preemption, leer Preempt y prefill throttle.

Véase la documentación oficial: Documentación de vLLM · README.