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

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

vLLM — это высокопроизводительная библиотека для инференса LLM, ключевая особенность которой — эффективное управление памятью через PagedAttention. Scheduler в vLLM отвечает за то, какие запросы (промпты) попадают в батч на каждом шаге генерации, учитывая доступные блоки KV-кэша и приоритеты. По умолчанию используется First-Come-First-Serve (FCFS), но поддерживаются также priority-based и fairness-алгоритмы, а при нехватке памяти применяется preemption (вытеснение) с возможностью swapping или recomputation.

1. Термин: vLLM и его архитектура

vLLM — open-source библиотека для инференса больших языковых моделей, разработанная в UC Berkeley. Её главное нововведение — PagedAttention, которая разбивает KV-кэш на блоки фиксированного размера (обычно 16 токенов), что позволяет:

• Избежать фрагментации памяти (не нужно резервировать место под максимальную длину последовательности).
• Делить память между запросами в батче.
• Поддерживать continuous batching — добавлять новые запросы в батч по мере завершения старых, без ожидания полного завершения всех.

Scheduler — центральный компонент, который решает, какие запросы выполнять на каждом шаге декодирования, и управляет аллокацией/освобождением блоков.

2. Основные понятия: блоки, sequence, батч

• Block — единица KV-кэша (фиксированное число токенов, например 16). Каждый блок имеет уникальный идентификатор и состояние (free / allocated / swapped).
• Sequence — один запрос (промпт + генерируемые токены). Каждая sequence хранит логическую таблицу отображения токенов на физические блоки (page table).
• Batching — группировка нескольких sequences для параллельного выполнения на GPU. vLLM использует continuous batching: батч динамически меняется между шагами.

Scheduler оперирует этими сущностями: он решает, какие sequences добавить в батч (на основе доступных блоков и политики), а какие приостановить (preempt).

3. Задачи scheduler'а

Основные функции:

1. Выбор запросов для включения в текущий батч (scheduling policy).
2. Управление памятью: проверка, хватит ли свободных блоков для нового запроса или для продолжения существующего.
3. Preemption — вытеснение части sequences при нехватке памяти.
4. Обработка завершённых запросов — освобождение блоков и удаление из очереди.

Scheduler работает на каждом шаге генерации (после выдачи очередного токена для всех sequences в батче). Он получает информацию о текущем состоянии памяти (сколько блоков свободно) и решает, можно ли добавить новые запросы из очереди ожидания.

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

4.1 First-Come-First-Serve (FCFS) — по умолчанию

Запросы обрабатываются в порядке поступления. Очередь — FIFO. Если для нового запроса не хватает блоков, он ждёт, пока освободятся блоки от завершённых sequences.

Плюсы: простота, предсказуемость, отсутствие голодания (starvation). Минусы: нет приоритетов; длинные запросы могут блокировать короткие, если память ограничена.

4.2 Priority-based

Каждому запросу присваивается приоритет (например, от 0 до 10). Scheduler выбирает запросы с наивысшим приоритетом, которые могут быть обслужены с учётом доступных блоков. При равных приоритетах — FCFS.

Плюсы: гибкость для SLA (например, платные пользователи выше). Минусы: возможное голодание низкоприоритетных запросов; требуется механизм назначения приоритетов.

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

Scheduler стремится равномерно распределять ресурсы (блоки) между запросами или между группами (например, по пользователям). Реализуется через weighted fair queuing или round-robin с учётом потребления блоков.

Плюсы: предотвращает монополизацию одним запросом. Минусы: сложнее в реализации; может увеличить latency для отдельных запросов.

4.4 Комбинированные стратегии

На практике часто используют гибриды: например, приоритет + fairness внутри одного приоритета. vLLM позволяет задавать политику через конфигурацию (параметр --scheduling-policy).

5. Учёт available blocks

Scheduler перед добавлением запроса проверяет:

• Сколько блоков нужно для префилла (промпта) — вычисляется как ceil(len(prompt) / block_size).
• Сколько блоков нужно для декодирования (обычно 1 блок на шаг, но может быть больше при использовании speculative decoding).
• Текущее количество свободных блоков в пуле.

Если блоков достаточно — запрос добавляется в батч. Если нет — scheduler либо ждёт, либо применяет preemption.

6. Preemption (вытеснение)

Когда свободных блоков не хватает для нового запроса, а очередь ожидания не пуста, scheduler может вытеснить одну или несколько уже выполняющихся sequences. Есть два режима:

6.1 Swapping (свопинг)

KV-кэш вытесняемой sequence выгружается из GPU в CPU (в специальный буфер). Когда блоки снова освобождаются, sequence может быть восстановлена (загружена обратно). Это дорого по latency, но позволяет не терять прогресс генерации.

6.2 Recomputation (перевычисление)

Sequence полностью удаляется из GPU, а её KV-кэш отбрасывается. Позже, когда ресурсы появятся, sequence начинается заново с префилла (промпт обрабатывается снова). Это дешевле по памяти, но требует повторного вычисления.

Выбор режима зависит от конфигурации: --preemption-mode (swap / recompute / hybrid). По умолчанию — recompute, так как он проще и не требует CPU-памяти.

7. Continuous batching и роль scheduler'а

Continuous batching — ключевая особенность vLLM. В традиционном статическом батчинге все запросы в батче начинаются и заканчиваются одновременно. В continuous batching:

• На каждом шаге scheduler может добавить новые запросы (после префилла) и удалить завершённые.
• Батч динамически меняется, что повышает утилизацию GPU.

Scheduler решает, когда добавить новый запрос: обычно после того, как хотя бы одна sequence завершилась (освободились блоки) или если есть свободные блоки, но нет активных sequences (начало работы).

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

9. Пример псевдокода scheduler'а (упрощённо)

class Scheduler:
    def __init__(self, policy='fcfs', block_pool, max_blocks_per_seq):
        self.policy = policy
        self.waiting_queue = deque()
        self.running = set()
        self.block_pool = block_pool  # manages free/used blocks

    def schedule_step(self):
        # 1. Remove finished sequences, free their blocks
        for seq in list(self.running):
            if seq.finished:
                self.block_pool.free(seq.blocks)
                self.running.remove(seq)

        # 2. Try to add new sequences from waiting queue
        while self.waiting_queue:
            seq = self._select_next(self.waiting_queue)
            needed = seq.num_blocks_needed()
            if self.block_pool.available() >= needed:
                self.block_pool.allocate(seq, needed)
                self.running.add(seq)
                self.waiting_queue.remove(seq)
            else:
                # 3. Preempt if needed
                if self._should_preempt():
                    victim = self._select_victim()
                    self._preempt(victim)
                    continue
                else:
                    break

    def _select_next(self, queue):
        if self.policy == 'fcfs':
            return queue[0]
        elif self.policy == 'priority':
            return max(queue, key=lambda s: s.priority)
        elif self.policy == 'fairness':
            # Simplified: round-robin among groups
            ...

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

Задача: Реализовать симулятор scheduler'а vLLM на Python, который моделирует continuous batching с разными политиками.

Инструменты: Python, NumPy (для генерации запросов), Matplotlib (для визуализации).

Шаги:

1. Создать класс BlockPool с фиксированным числом блоков (например, 1024).
2. Создать класс Sequence с полями: prompt_len, max_tokens, priority, group_id.
3. Реализовать Scheduler с методами add_request, step, preempt.
4. Реализовать три политики: FCFS, priority, fairness (по группам).
5. Сгенерировать случайные запросы (длины, приоритеты) и прогнать симуляцию.
6. Измерить метрики: среднее время ответа, пропускная способность, количество preemption'ов.
7. Построить графики зависимости latency от нагрузки для разных политик.

Ожидаемый результат: Вы увидите, что FCFS даёт наименьшую вариативность latency, priority — ускорение для высокоприоритетных запросов, fairness — равномерное распределение ресурсов между группами.

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

12. Навигация

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

Навигация

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