Перейти к основному содержимому

Чтобы получить чистый Markdown-контент этой страницы, добавьте .md к этому URL. Полный индекс документации см. по адресу https://docs.nvidia.com/dynamo/llms.txt. Полное содержимое, включая API reference и примеры SDK, доступно по адресу https://docs.nvidia.com/dynamo/llms-full.txt.

Дизайн Router

В этом документе описывается внутренняя архитектура Dynamo KV Router, включая механизмы отслеживания blocks, систему оптимизации KV cache, обработку событий и режимы transport.

Архитектура KV Router​

KV Router отслеживает две ключевые метрики для каждого worker:

  1. Potential Active Blocks: количество blocks, которые будут использоваться для decoding, если request будет направлен на worker. Сюда входят как уже активные blocks, так и новые blocks из входящего request.

  2. Potential New Prefill Blocks: количество токенов, которые нужно вычислить с нуля на worker, рассчитывается как:

    • New prefill tokens = Total input tokens - (Overlap blocks × Block size)
    • Potential prefill blocks = New prefill tokens / Block size

Механизмы отслеживания blocks​

Router поддерживает информацию о blocks через две взаимодополняющие системы:

  • Active Decoding Blocks: отслеживаются локально router'ом на протяжении всего жизненного цикла request:

    • увеличиваются при добавлении нового request
    • обновляются во время генерации токенов
    • уменьшаются после завершения request

  • Cached Blocks: глобально поддерживаются KvIndexer'ом с использованием prefix tree, построенного на основе KV events, переданных workers. Это дает точную информацию о перекрытии для принятия routing decisions.

Router KV Cache​

Современные ведущие Large Language Models (LLM) являются autoregressive и основаны на transformer architecture. Один из ключевых приемов оптимизации inference - кэшировать уже вычисленные keys и values и повторно использовать их для будущих токенов. Это называется KV Cache.

Routing KV Cache и балансировка нагрузки​

graph TD
    T[Tokens] --> R[KV Aware Router]

    R -.-> W1["Worker 1<br/>Cached: 2 blocks<br/>Prefill: 8 blks<br/>Decode: 10 blks"]
    R ==>|Selected| W2["Worker 2<br/>Cached: 5 blocks<br/>Prefill: 5 blks<br/>Decode: 5 blks"]
    R -.-> W3["Worker 3<br/>Cached: 8 blocks<br/>Prefill: 2 blks<br/>Decode: 9 blks"]

    style T fill:#fff3e0,stroke:#333,color:#333
    style R fill:#2e8b57,stroke:#333,color:#fff
    style W1 fill:#f3e5f5,stroke:#333,color:#333
    style W2 fill:#c8e6c9,stroke:#333,color:#333
    style W3 fill:#f3e5f5,stroke:#333,color:#333

    linkStyle 0,1,2,3 stroke:#8b4513,stroke-width:2px

Router использует cost function, которая учитывает и стоимость prefill (на которую влияют cached blocks), и decode load, чтобы принимать оптимальные routing decisions.

Расчет стоимости​

  1. Prefill blocks: вычисляются как active prompt-side token load плюс входные tokens incoming request, деленные на block size. Система обновляет active prompt load, когда первый output token сигнализирует о завершении prefill.

  2. Decode blocks: оцениваются по input tokens request и активным sequences каждого worker. Значение обновляется, когда request завершается и его blocks освобождаются.

  3. Cost formula:

    adjusted_prefill_blocks = max(
        prefill_blocks
        - overlap_score_credit * device_overlap_blocks
        - host_cache_hit_weight * host_overlap_blocks
        - disk_cache_hit_weight * disk_overlap_blocks
        - shared_cache_multiplier * shared_beyond_blocks,
        0,
    )
    cost = prefill_load_scale * adjusted_prefill_blocks + decode_blocks
    • Более низкая стоимость означает лучший выбор routing
    • overlap_score_credit - это device-local prefix-overlap credit multiplier в диапазоне от 0.0 до 1.0
    • prefill_load_scale управляет скорректированной prompt-side load относительно decode blocks
    • Более высокий overlap credit поощряет повторное использование cache (улучшая TTFT), а более низкий - равномерное распределение нагрузки (улучшая ITL)

Выбор worker​

Router выбирает worker с наименьшей стоимостью. Когда router_temperature задан не равным нулю, router использует softmax sampling по нормализованным logits стоимости, чтобы добавить случайность в выбор, что может помочь с распределением нагрузки.

Example calculation with overlap_score_credit = 1.0:

  • Worker 1: raw prefill 10 blocks, device overlap 2 blocks, decode 10 blocks => cost = 8 + 10 = 18
  • Worker 2: raw prefill 10 blocks, device overlap 5 blocks, decode 5 blocks => cost = 5 + 5 = 10 (selected - lowest cost)
  • Worker 3: raw prefill 10 blocks, device overlap 8 blocks, decode 9 blocks => cost = 2 + 9 = 11

Оптимизации KV Cache​

У каждого inference framework есть KV Cache для каждого worker. Популярная библиотека inference framework - vLLM, где ключевым вкладом стал PagedAttention, позволивший эффективно управлять KV Cache, разбивая request'ы на blocks.

Еще один популярный inference framework, SGLang, внес вклад в виде RadixAttention, который представил prefix tree, позволяющее эффективно сопоставлять, вставлять и вытеснять blocks KV Cache. Структура prefix tree популяризировала повторное использование KV Cache.

В Dynamo мы вводим KVPublisher, который публикует KV Cache events, происходящие на каждом worker, и KVIndexer, который глобально отслеживает эти события.

Поток управления KV blocks​

Чтобы понять, как работает управление KV Cache на одном worker при включенном повторном использовании KV Cache и куда подключается KVPublisher, рассмотрим поток управления KV blocks:

  1. Request tokenization: входной prompt преобразуется в tokens
  2. Block partitioning: token sequence делится на blocks фиксированного размера (например, 16 или 64 tokens per block)
  3. Block hashing: каждый block токенов хэшируется для создания уникального идентификатора. Когда активен LoRA adapter, его имя включается в hash, чтобы blocks, закэшированные под разными adapters, давали разные идентификаторы.
  4. Cache lookup:
    • Для каждого block система проверяет, существует ли уже подходящий block в KV cache
    • Если совпадение найдено, существующий block KV cache повторно используется
    • Если совпадение не найдено, система переходит к следующему шагу
  5. Resource allocation:
    • Для blocks без совпадений система пытается выделить новое memory space
    • Если памяти достаточно, memory space выделяется, и система переходит к шагу 7
    • Если памяти недостаточно, система переходит к шагу 6
  6. Cache eviction (when necessary):
    • Система применяет eviction policy (например, LRU, LFU), чтобы определить blocks для удаления
    • Выбранные blocks вытесняются из cache
    • KVPublisher публикует KV removed event, уведомляя KVIndexer об удаленном block.
    • Альтернативно некоторые системы могут выгружать менее часто используемые blocks в memory CPU.
  7. KV computation:
    • Для новых blocks модель вычисляет key и value tensors
    • Эти tensors сохраняются в newly allocated blocks cache
    • KVPublisher публикует kv stored event, уведомляя KVIndexer о новых stored blocks.

Дополнительные сведения можно найти здесь: SGLang, TRT-LLM и vLLM.

События​

KVPublisher​

KVPublisher можно инициализировать, а затем вызывать в inference framework, где blocks выделяются и удаляются.

Есть два типа событий:

  • KV stored event
  • KV removed event

Publisher можно инициализировать и использовать через Python bindings.

Детерминированные Event ID​

Engines не обязаны публиковать детерминированные идентификаторы blocks в KV events, поскольку router использует локальные block hashes (вычисленные из содержимого токенов) для отслеживания и сопоставления blocks между workers. Однако крайне желательно, чтобы engines публиковали детерминированные идентификаторы blocks, так как это делает внутреннюю таблицу lookup KvIndexer'а меньше и эффективнее. Чтобы обеспечить детерминированное поведение, все workers должны использовать идентичные версии и конфигурации engine. Если ваш engine использует встроенную в Python hash() для каких-либо event ID, задайте PYTHONHASHSEED=0; в противном случае этот параметр не влияет.

KVIndexer​

KVIndexer строит и поддерживает глобальное представление cached blocks в prefix tree. Мы изменяем исходное prefix tree, дополнительно сохраняя worker id в каждом node. Это нужно, чтобы возвращать количество совпавших blocks для каждого worker.

У KVIndexer есть метод find_matches_for_request, который принимает tokens и возвращает dictionary, где ключи - это worker id, а значения - число совпавших KV Blocks.

KVIndexer поддерживает две backend-реализации, выбираемые через --router-event-threads:

  • Single-threaded RadixTree (--router-event-threads 1): события обрабатываются в отдельном single-threaded tokio runtime через channel-based dispatch. Также поддерживает TTL-based expiration для approximate mode --no-router-kv-events.

  • ConcurrentRadixTree (по умолчанию, --router-event-threads N, где N > 1): thread-safe radix tree с пулом из N worker threads для обработки events и записи approximate routing decisions (по умолчанию: 4). Использует sticky worker routing (events или synthetic approximate writes для одного и того же worker всегда попадают в один и тот же thread), чтобы обеспечить per-worker serialization. Операции чтения (find_matches) выполняются параллельно с записью.

Межроутерное взаимодействие​

In distributed deployments with multiple routers, each router maintains visibility over only a portion of the total requests. To ensure consistent routing decisions, routers synchronize their states through three event types:

  1. AddRequest: Notifies other routers when a request is assigned to a worker. Includes request ID, worker ID, token sequence blocks, and overlap score to track block usage across the system.

  2. MarkPrefillCompleted: Signals when a request moves from prefill to decode phase, allowing routers to update their worker load calculations by excluding completed prefill tokens.

  3. Free: Indicates request completion and resource release, enabling accurate block reference counting across all routers.

Каждое событие содержит уникальный router ID, чтобы исключить обработку собственных событий. Эта асинхронная система коммуникации обеспечивает оптимальные routing decisions за счет поддержания согласованного состояния KV cache на всех router'ах, даже когда они обрабатывают разные потоки requests.

Режимы передачи событий​

Router поддерживает два режима передачи событий для синхронизации состояния KV cache:

  • NATS Core / Event Plane with Local Indexer (по умолчанию): fire-and-forget pub/sub, где workers поддерживают локальные radix tree (включено по умолчанию). Router восстанавливает состояние, опрашивая workers при запуске. Меньшая задержка, более простая настройка. Работает и с NATS Core, и с event plane ZMQ.

  • JetStream (--durable-kv-events и на frontend, и на workers): постоянный event stream с durable consumers. Состояние сохраняется между перезапусками router'а через snapshots в NATS object store. Лучше всего подходит для production с согласованностью между несколькими replica. Важно: и frontend, и все workers должны указывать --durable-kv-events, чтобы JetStream mode работал корректно.

JetStream Mode (по желанию)​

KV events отправляются в постоянный NATS JetStream. Каждая replica KV router/indexer выступает как durable consumer и забирает сообщения из этого общего stream. Такая архитектура обеспечивает согласованность между replica router'а и сохранность состояния после перезапусков.

  • Лучше всего для: production-развертываний, где требуются durability и согласованность router'ов между несколькими replica
  • Компромиссы: требуется настройка JetStream; чуть более высокая задержка из-за гарантий сохранности
  • Включение: флаг --durable-kv-events и на frontend, и на всех workers

Both frontend and workers must specify --durable-kv-events for JetStream mode to work correctly. The frontend uses this flag to consume from JetStream, while workers use it to publish to JetStream instead of the local indexer.

graph TD
    subgraph Engines
        E1[Engine 1<br/>KVPublisher]
        E2[Engine 2<br/>KVPublisher]
        E3[Engine 3<br/>KVPublisher]
    end

    subgraph "NATS JetStream"
        JS[(Persistent KV Events Stream<br/>- Block created<br/>- Block removed)]
    end

    subgraph "NATS Object Store"
        OS[(Radix Tree<br/>State Snapshot)]
    end

    subgraph "Router Replicas"
        R1[Router 1<br/>KVIndexer]
        R2[Router 2<br/>KVIndexer]
    end

    E1 -->|Publish Events| JS
    E2 -->|Publish Events| JS
    E3 -->|Publish Events| JS

    JS -->|Consume as Durable Consumer| R1
    JS -->|Consume as Durable Consumer| R2
    JS -->|Periodic Snapshot| OS

    style JS fill:#e1f5fe,stroke:#333,color:#333
    style OS fill:#e1f5fe,stroke:#333,color:#333
    style E1 fill:#f3e5f5,stroke:#333,color:#333
    style E2 fill:#f3e5f5,stroke:#333,color:#333
    style E3 fill:#f3e5f5,stroke:#333,color:#333
    style R1 fill:#2e8b57,stroke:#333,color:#fff
    style R2 fill:#2e8b57,stroke:#333,color:#fff

    linkStyle 0,1,2,3,4,5 stroke:#2196f3,stroke-width:2px

NATS Core / Event Plane с Local Indexer (по умолчанию)​

По умолчанию у workers включен local indexer. Каждый worker ведет собственное local radix tree (local indexer) и публикует события через общий event plane (NATS Core или ZMQ, в зависимости от --event-plane). Каждый worker назначает событиям монотонно возрастающие event ID. Router обнаруживает разрывы в последовательности событий и восстанавливает пропущенные события, напрямую опрашивая local indexer worker'а.

  • Лучше всего для: конфигураций с низкой задержкой; более простых развертываний без JetStream; сценариев с одним router'ом; развертываний без NATS (с event plane ZMQ)
  • Компромиссы: состояние хранится на workers (не централизовано); восстановление зависит от доступности workers
  • Переход на JetStream: используйте флаг --durable-kv-events и на workers (SGLang, TRT-LLM, vLLM, mocker), и на frontend
graph TD
    subgraph Engines
        E1[Engine 1<br/>LocalKvIndexer]
        E2[Engine 2<br/>LocalKvIndexer]
        E3[Engine 3<br/>LocalKvIndexer]
    end

    subgraph "Event Plane (NATS / ZMQ)"
        NC[KV Events Pub/Sub<br/>- Block created<br/>- Block removed]
    end

    subgraph "Router Replicas"
        R1[Router 1<br/>KVIndexer]
        R2[Router 2<br/>KVIndexer]
    end

    E1 -->|Publish Events| NC
    E2 -->|Publish Events| NC
    E3 -->|Publish Events| NC

    NC -->|Subscribe| R1
    NC -->|Subscribe| R2

    style NC fill:#e1f5fe,stroke:#333,color:#333
    style E1 fill:#f3e5f5,stroke:#333,color:#333
    style E2 fill:#f3e5f5,stroke:#333,color:#333
    style E3 fill:#f3e5f5,stroke:#333,color:#333
    style R1 fill:#2e8b57,stroke:#333,color:#fff
    style R2 fill:#2e8b57,stroke:#333,color:#fff

    linkStyle 0,1,2,3,4 stroke:#2196f3,stroke-width:2px

Как работает обнаружение разрывов:

  1. Каждый worker назначает событиям монотонно возрастающие event ID, начиная с 0
  2. Router отслеживает последний полученный event ID для каждого worker
  3. Если приходит событие с event_id > last_id + 1, router обнаруживает разрыв
  4. Router запрашивает у local indexer worker'а пропущенный диапазон событий [last_id+1, event_id-1]
  5. При обнаружении worker'а (событие Added) router выгружает все состояние local indexer worker'а

Поведение при запуске:

  • Когда worker обнаружен, router запрашивает и загружает все его состояние local indexer
  • Когда worker удален, router удаляет все его blocks из глобального radix tree

По умолчанию у всех workers задано enable_local_indexer=true, поэтому router использует режим NATS Core / Event Plane с local indexer. Чтобы использовать JetStream mode, укажите --durable-kv-events и на frontend, и на всех workers.

Управление локальными active blocks с replica sync​

Помимо cached blocks, каждой replica router'а нужно отслеживать active blocks (blocks, которые используются для текущей генерации) как метрику нагрузки. Поскольку эта информация очень чувствительна ко времени, ее нужно прогнозировать сразу, когда:

  • Router получает request и направляет его
  • Генерируется первый token (prefill завершен)
  • Ответ заканчивается (request освобождается)

Это локально управляется в каждом router через "slot manager". Чтобы поддерживать согласованность по всей системе, router replicas синхронизируют эти локальные прогнозы друг с другом через сообщения NATS core.

sequenceDiagram
    participant C1 as Client 1
    participant R1 as Router 1<br/>(Slot Manager)
    participant R2 as Router 2<br/>(Slot Manager)
    participant C2 as Client 2

    Note over R1,R2: Включена синхронизация router replicas

    C1->>R1: Request A
    activate R1
    R1->>R1: Predict blocks и route к worker
    R1-->>R2: Sync: AddRequest(A)

    C2->>R2: Request B
    activate R2
    R2->>R2: Predict blocks и route к worker
    R2-->>R1: Sync: AddRequest(B)

    R1->>R1: Получен первый token<br/>(prefill завершен)
    R1-->>R2: Sync: MarkPrefillCompleted(A)
    R1->>C1: Stream response

    R2->>R2: Получен первый token<br/>(prefill завершен)
    R2-->>R1: Sync: MarkPrefillCompleted(B)
    R2->>C2: Stream response

    R1->>R1: Ответ завершен<br/>(blocks освобождены)
    R1-->>R2: Sync: Free(A)
    deactivate R1

    R2->>R2: Ответ завершен<br/>(blocks освобождены)
    R2-->>R1: Sync: Free(B)
    deactivate R2

    Note over R1,R2: Оба router'а имеют согласованное<br/>представление об active blocks

Этот двухуровневый подход - постоянное глобальное состояние KV cache через JetStream и ephemeral синхронизация active blocks между router replicas - позволяет системе принимать оптимальные routing decisions, балансируя reuse cache и распределение нагрузки.

См. также​