Как работает scheduler в vLLM? Какие алгоритмы выбора запросов?

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

Scheduler в vLLM — это центральный компонент, который управляет очередями запросов и решает, какой запрос выполнять на каждой итерации генерации, учитывая доступную память для KV cache. Основные алгоритмы выбора: FCFS (по умолчанию), Priority-based (приоритеты пользователей) и Fairness (гарантированная доля для tenant'ов). При нехватке памяти scheduler применяет preemption (вытеснение) — приостанавливает или перезапускает запросы, чтобы освободить блоки.

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

vLLM — это библиотека для высокопроизводительного инференса больших языковых моделей (LLM). Её ключевые оптимизации:

• PagedAttention — эффективное управление KV cache через страничную организацию памяти, как в операционных системах.
• batching|Continuous batching — динамическое формирование батча на каждом шаге генерации: запросы могут добавляться и удаляться из батча по мере завершения.

Scheduler — это «диспетчер» vLLM. Он отвечает за:

• Приём новых запросов от API.
• Поддержание нескольких очередей (waiting, running, swapped).
• Выбор, какие запросы войдут в следующий батч.
• Управление памятью: выделение и освобождение блоков KV cache.
• Вытеснение (preemption) запросов при нехватке памяти.

Без scheduler'а vLLM не смогла бы эффективно использовать память и обеспечивать низкую задержку при высокой нагрузке.

2. Основные структуры данных scheduler'а

Scheduler оперирует тремя очередями:

Кроме того, scheduler взаимодействует с Block manager — компонентом, который отслеживает свободные и занятые блоки KV cache (каждый блок хранит attention-ключи и значения для нескольких токенов).

3. Алгоритмы выбора запросов

Scheduler использует политику (алгоритм) для выбора следующего запроса из waiting queue или для перераспределения ресурсов между running запросами. В vLLM реализованы три основных алгоритма.

3.1 FCFS (First Come, First Served) — по умолчанию

Принцип Запросы обрабатываются в порядке поступления. Первый пришёл — первый получил ресурсы.

• Как работает Scheduler берёт запросы из waiting queue в порядке их arrival time и пытается добавить их в running queue, пока есть свободные блоки памяти.
• Плюсы Простота, предсказуемость, отсутствие «голодания» (starvation) для отдельных запросов.
• Минусы Нет приоритезации — срочные запросы могут ждать, пока выполнятся все ранее пришедшие.

3.2 Priority-based

Принцип Каждому запросу (или пользователю) назначается числовой приоритет. Чем выше приоритет, тем раньше запрос получит ресурсы.

• Как работает Waiting queue сортируется по убыванию приоритета. Scheduler сначала пытается запустить запросы с максимальным приоритетом.
• Плюсы Гибкость — можно дать приоритет платящим пользователям или критическим задачам.
• Минусы Возможно «голодание» низкоприоритетных запросов, если постоянно поступают высокоприоритетные.

3.3 Fairness (справедливость)

Принцип Гарантирует каждому tenant (арендатору, группе пользователей) минимальную долю ресурсов (например, 20% пропускной способности). Реализуется через weighted fair queuing или round-robin между группами.

• Как работает Scheduler ведёт учёт потреблённых ресурсов для каждого tenant. Если один tenant превысил свою долю, его запросы получают меньший приоритет, пока другие не догонят.
• Плюсы Изоляция между разными пользователями/приложениями, предотвращение «захвата» ресурсов одним tenant'ом.
• Минусы Сложнее в настройке, требует мониторинга потребления.

Сравнение алгоритмов

4. Управление памятью и preemption

Scheduler не только выбирает запросы, но и следит за доступными блоками KV cache. Если при попытке добавить новый запрос в running queue не хватает блоков, scheduler запускает preemption (вытеснение).

4.1 Preemption

Вытеснение — это принудительное освобождение блоков, занятых одним или несколькими running запросами. Есть две стратегии:

• Swapping (выгрузка): KV cache вытесняемого запроса копируется в CPU-память (обычно медленнее, но сохраняет состояние). Запрос перемещается в swapped queue.
• Recomputation (пересчёт): KV cache просто отбрасывается. При возобновлении запроса его нужно пересчитать с нуля (дешевле по памяти, но дороже по времени).

Какой запрос вытеснять? Обычно scheduler выбирает запрос с наименьшим приоритетом (или самый старый в FCFS) или запрос, который потребляет больше всего блоков.

4.2 Пример работы scheduler'а

Допустим, есть 10 свободных блоков. Приходят запросы A (5 блоков), B (4 блока), C (3 блока). Scheduler (FCFS) запускает A и B — занято 9 блоков. Приходит запрос D (2 блока). Свободно 1 блок — не хватает. Scheduler вытесняет B (4 блока) в swapped, освобождая 5 блоков (1 + 4). Теперь можно запустить D (2 блока). Оставшиеся 3 блока ждут следующих запросов.

5. Псевдокод работы scheduler'а (упрощённо)

class Scheduler:
    def __init__(self, block_manager, policy='fcfs'):
        self.waiting = deque()
        self.running = []
        self.swapped = deque()
        self.block_manager = block_manager
        self.policy = policy  # 'fcfs', 'priority', 'fairness'

    def add_request(self, request):
        self.waiting.append(request)

    def schedule(self):
        # 1. Попытаться добавить waiting запросы в running
        if self.policy == 'fcfs':
            waiting_sorted = self.waiting  # по порядку
        elif self.policy == 'priority':
            waiting_sorted = sorted(self.waiting, key=lambda r: -r.priority)
        elif self.policy == 'fairness':
            waiting_sorted = self._fairness_sort(self.waiting)

        for req in waiting_sorted:
            needed_blocks = req.num_blocks
            if self.block_manager.free_blocks >= needed_blocks:
                self.block_manager.allocate(req)
                self.running.append(req)
                self.waiting.remove(req)
            else:
                # Preempt
                victim = self._select_victim()
                self._preempt(victim)
                # Повторная попытка (упрощённо)
                if self.block_manager.free_blocks >= needed_blocks:
                    self.block_manager.allocate(req)
                    self.running.append(req)
                    self.waiting.remove(req)

    def _select_victim(self):
        # Выбрать запрос с наименьшим приоритетом или самый старый
        return min(self.running, key=lambda r: r.priority)

    def _preempt(self, request):
        self.block_manager.free(request)
        self.running.remove(request)
        self.swapped.append(request)  # или recompute

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

Задача Написать симулятор scheduler'а vLLM с тремя алгоритмами (FCFS, Priority, Fairness) и визуализацией использования памяти.

Инструменты Python, simpy (дискретно-событийное моделирование), matplotlib для графиков.

Шаги:

1. Реализовать класс BlockManager с фиксированным числом блоков.
2. Реализовать класс Request с атрибутами: arrival_time, num_blocks, priority, tenant_id.
3. Реализовать три версии scheduler'а (FCFS, Priority, Fairness) с очередями и preemption.
4. Сгенерировать поток запросов (Poisson arrival) с разными приоритетами и tenant'ами.
5. Запустить симуляцию для каждого алгоритма, замерить:
   • Среднее время ожидания (latency).
   • Пропускную способность (throughput).
   • Количество preemption'ов.
6. Построить графики: занятость блоков во времени, распределение задержек.

Ожидаемый результат Вы увидите, что FCFS даёт равномерную задержку, Priority снижает latency для высокоприоритетных запросов, но увеличивает для низких, а Fairness сглаживает различия между tenant'ами.

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

8. Навигация

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

Навигация

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