Как работают inference schedulers (FCFS, Priority, Fairness)?

Краткий тезис

Inference schedulers — это компоненты LLM-инференсных систем (например, vLLM, TensorRT-LLM), которые управляют порядком выполнения запросов к модели. Они решают задачу распределения вычислительных ресурсов (памяти GPU, времени на вычисления) между конкурирующими запросами. Основные алгоритмы: FCFS (простая очередь, но несправедлива к коротким запросам), Priority-based (гарантирует время отклика для премиум-пользователей, но может привести к starvation) и Fairness (в духе max-min fairness) — обеспечивает равную долю ресурсов для каждого тенанта или пользователя. В системах вроде vLLM по умолчанию используется FCFS с preemption (вытеснением) при нехватке памяти, что позволяет эффективно использовать ресурсы.

1. Что такое inference scheduler и зачем он нужен

Inference scheduler (планировщик инференса]]) — программный модуль, расположенный между фронтендом (API) и бэкендом исполнения модели (GPU). Его задачи:

• Управление очередью — запросы, пришедшие одновременно или быстрее, чем модель может их обработать, ставятся в очередь.
• Распределение памяти — особенно для авторегрессионных LLM, которые хранят KV cache для каждого запроса. Память GPU ограничена, поэтому scheduler решает, какие запросы можно добавить в батч, а какие нужно вытеснить (preempt).
• Обеспечение SLA — время ответа не должно превышать заданного порога для разных классов пользователей.

В контексте Agentic RAG (особенно при мультиагентных сценариях, где множество агентов параллельно делают запросы к LLM) правильная работа scheduler’а критична: задержки одного агента могут заблокировать весь пайплайн.

2. FCFS (First-Come-First-Served) — «первый пришёл — первый обслужен»

Принцип запросы обслуживаются в порядке поступления — строгая FIFO-очередь.

Пример

Поступили: запрос A (длинный текст), B (короткий), C (короткий)
Порядок исполнения: A → B → C
Время ожидания B и C = время выполнения A.

Плюсы

• Предельно прост в реализации.
• Предсказуемое поведение (нет starvation в классическом смысле — каждый рано или поздно будет обслужен).
• Естественная справедливость по времени прибытия.

Минусы

• Конвойный эффект (convoy effect): длинный запрос, пришедший первым, задерживает все последующие короткие. Среднее время ожидания может быть высоким.
• Несправедливость к коротким запросам короткий запрос, пришедший через секунду после длинного, будет ждать столько же, сколько длинный.
• Плохо подходит, если требуется дифференциация SLA (все равны).

Где применяется

Как базовый режим в vLLM и рантаймах, когда не задано никаких приоритетов.

3. Priority-based scheduling — планирование на основе приоритета

Принцип каждому запросу назначается числовой приоритет (например, 0 — низкий, 10 — высокий). Scheduler выбирает запрос с наивысшим приоритетом среди всех ожидающих.

Виды приоритетов

• Статический задаётся при поступлении (например, «premium» vs «free»).
• Динамический может меняться со временем (например, увеличивается, если запрос долго ждал — это анти-starvation механизм).

Пример

Поступили: A (приоритет 5), B (приоритет 10), C (приоритет 1)
Порядок исполнения: B → A → C

Плюсы

• Позволяет гарантировать низкую задержку для критичных запросов (real-time, interactive).
• Простота приоритетных очередей (можно реализовать на heap’е).

Минусы

• Starvation (голодание): запросы с низким приоритетом могут никогда не получить ресурс, если постоянно поступают высокоприоритетные.
• Инверсия приоритетов если высокоприоритетный запрос ждёт ресурс, занятый низкоприоритетным, а средний приоритет вытесняет низкий — всё может заблокироваться. (В LLM-инференсе релевантно при shared KV cache).
• Сложность настройки правил приоритета.

Борьба со starvation

• Aging (старение): со временем приоритет запроса повышается до тех пор, пока он не будет обслужен.
• Priority ceiling при входе в критическую секцию приоритет временно поднимается до максимального.

4. Fairness scheduling — «справедливое» распределение ресурсов

Принцип ресурсы (время GPU, память KV cache) делятся пропорционально между активными пользователями/тенантами. Классическая реализация — max-min fairness.

Формула max-min fairness

Дано: общая пропускная способность C (например, токенов/сек), количество потребителей N.
Сначала каждому выделяется C/N. Если какой-то потребитель не использует свою долю полностью, избыток распределяется между остальными.

Пример в LLM-инференсе

• Три тенанта: A, B, C.
• Каждый тенант может отправить запросы. Scheduler гарантирует, что ни один тенант не получит меньше, чем C/3 ресурса, если он его использует.
• Если A неактивен, B и C делят его долю поровну.

Weighted Fairness (WFQ)

Добавляются веса: тенант с весом 2 получает вдвое больше ресурсов, чем тенант с весом 1.

Плюсы

• Исключает starvation — каждый гарантированно получает минимальную долю.
• Понятная модель для мультитенатных систем (SaaS, разные проекты).

Минусы

• Сложнее реализовать, чем FCFS или Priority.
• Требует мониторинга использования каждого тенанта.
• При burst’ах (всплесках запросов) может не успеть перераспределить ресурсы быстро.

5. Сравнительная таблица

6. Preemption (вытеснение) — ключевой механизм для памяти

В LLM-инференсе критический ресурс — KV cache. Если памяти не хватает, scheduler может прервать (preempt) один из активных запросов:

• Preemption by swap KV cache выгружается из GPU в CPU RAM (или SSD). Когда в будущем запрос продолжит генерацию, его KV cache загружается обратно.
• Preemption by recomputation запрос полностью удаляется из памяти. При возобновлении его нужно запускать заново с самого начала (recompute). Дорогой способ.

vLLM по умолчанию использует FCFS-очередь и preemption при нехватке памяти. При этом запросы, которые уже начали генерировать, сохраняются в памяти, а новые ставятся в очередь или вытесняются из пайплайна.

7. Как работает vLLM scheduler (на примере)

vLLM (проект LMSYS) использует потоковый scheduler с двумя состояниями:

• Running запросы, которые сейчас генерируют токены (их KV cache в GPU).
• Waiting запросы, ожидающие места в батче.

При нехватке памяти:

1. Scheduler выбирает запросы из Running, которые вытесняются (сначала наименее приоритетные — в vLLM нет приоритетов, поэтому просто те, которые меньше продвинулись? На самом деле vLLM использует FCFS, поэтому вытесняются последние добавленные — LIFO-эвристика для минимизации перевычислений).
2. Высвободившуюся память получают запросы из Waiting.

Таким образом, FCFS с preemption даёт эффект относительной справедливости: короткие запросы, пришедшие позже, могут вытеснить длинный, если памяти под него не хватает — хотя это не true fairness.

8. Пример кода: симуляция трёх стратегий на Python

import heapq
from collections import deque

# --- FCFS ---
class FCFSScheduler:
    def __init__(self): self.queue = deque()
    def enqueue(self, req): self.queue.append(req)
    def schedule(self): return self.queue.popleft() if self.queue else None

# --- Priority (max-heap via negation) ---
class PriorityScheduler:
    def __init__(self): self.heap = []
    def enqueue(self, req, prio): heapq.heappush(self.heap, (-prio, req))
    def schedule(self): return heapq.heappop(self.heap)[1] if self.heap else None

# --- Fairness (round‑robin across tenants) ---
class FairScheduler:
    def __init__(self, tenants_weights):
        self.tenants = {t: deque() for t in tenants_weights.keys()}
        self.weights = tenants_weights
        self.current_tenant = None
        self.tokens = 0  # для дефицитного round-robin
    def enqueue(self, tenant, req): self.tenants[tenant].append(req)
    def schedule(self):
        # Упрощение: round-robin с учётом весов (weighted RR)
        total_weight = sum(self.weights.values())
        while True:
            for t in self.tenants:
                if self.tenants[t]:
                    # каждый tenant получает квант = его вес
                    self.tokens += self.weights[t]
                    if self.tokens >= total_weight:
                        self.tokens -= total_weight
                        return self.tenants[t].popleft()
            break
        return None

Примечание: в реальных системах fairness реализуется через deficit round robin или WFQ, но идея та же.

9. Проблемы и нюансы

• Starvation в Pure Priority требует механизмов aging.
• FCFS без preemption может быть катастрофой для latency-sensitive приложений (типичный случай в Agentic RAG, когда агенту нужно быстро ответить пользователю).
• Fairness плохо работает, если нет чёткого разделения на тенанты. Также сложно определить справедливую долю, если запросы имеют разную длину (большой output потребляет больше памяти и времени).
• Batching scheduler’ы должны учитывать, что запросы можно группировать в батчи для эффективного использования GPU (vLLM делает это transparently).

10. Применение в Agentic RAG

В системах с несколькими агентами (каждый агент может делать несколько вызовов LLM внутри одного пользовательского сеанса) scheduler должен:

• Разделять ресурсы между разными сеансами (tenant = пользователь).
• Внутри одного сеанса возможно приоритезировать определённые шаги агента (например, plan → act → observe).
• При использовании tool calls (вызов внешних функций) scheduler может дать меньший приоритет генерации, пока агент ждёт ответа от внешнего сервиса, чтобы освободить ресурсы.

Пет-проект для закрепления

Задача Реализовать симулятор inference scheduler’а, который сравнивает три стратегии на случайной нагрузке.

Инструменты Python, asyncio (для асинхронного поступления запросов), simpy (для дискретно-событийного моделирования) или просто threading + очереди.

Шаги:

1. Создать класс Request с полями: arrival_time, duration (время генерации), tenant_id, priority.
2. Реализовать три класса наследуемых от BaseScheduler: FCFSScheduler, PriorityScheduler, FairScheduler.
3. В главном цикле генерировать запросы по пуассоновскому процессу, отправлять их в scheduler.
4. Вычислять среднее время ожидания, время выполнения (такт), max latency, количество starvation-событий (для priority).
5. Визуализировать результаты (matplotlib).

Ожидаемый результат

• Графики зависимости среднего времени ожидания от нагрузки (запросов/сек) для каждой стратегии.
• Вывод: для сценария burst-запросов с короткими и длинными сообщениями FCFS даёт высокое среднее ожидание, Priority даёт низкое для премиум, Fairness сглаживает различия.
• Таблица с метриками.

Связь с другими вопросами

Навигация

• Предыдущий: 849
• Следующий: 851
• Индекс: 00. Индекс разборов