For clean Markdown content of this page, append .md to this URL. For the complete documentation index, see https://docs.nvidia.com/dynamo/llms.txt. For full content including API reference and SDK examples, see https://docs.nvidia.com/dynamo/llms-full.txt.
Flash Indexer: История межгалактической KV-маршрутизации
Flash Indexer в Dynamo отслеживает каждый кэшированный KV-блок во всех inference worker'ах со скоростью 170M ops/s. К этому привели шесть итераций проектирования структур данных.
Flash Indexer - это конкурентный глобальный индекс каждого кэшированного KV-блока на каждом inference worker'е, обеспечивающий более 100 миллионов операций в секунду. Он прошел шесть итераций - от Python dictionary до пространственного индекса с оптимизацией прыжков - и дошел до состояния, когда узкими местами стали задержка сети, токенизация и хеширование. Мы поставляем его как индексатор по умолчанию в Dynamo v1.0.0.
Чтобы интуитивно оценить масштаб: при 100M+ index ops/sec система может поддерживать примерно $$N \approx 10^8 / r$$ одновременных workloads, где $$r$$ - это устойчивое число index ops/sec для workload (inserts + lookups) при реальном трафике, включая bursty prefill, что намного превышает текущий спрос на inference планетарного масштаба.
В этой статье мы пройдем по этим итерациям - как каждое перепроектирование давало новый порядок улучшения, и какое именно решение в области структуры данных или concurrency стояло за ним.
1. Контекст
1.1 Идентичность KV-блока
У каждого кэшированного блока есть три идентификатора:
-
Local block hash (
u64): хеш содержимого токенов внутри одного блока. Не зависит от позиции - два блока с одинаковыми токенами дают одинаковый хеш. И frontend, и publisher используют один и тот же алгоритм. -
Sequence block hash (
u64): скользящий хеш всего префикса до этого блока. Зависит от позиции - идентичные токены в разных позициях дают разные хеши.
seq_hash[0] = local_hash[0]
seq_hash[i] = hash(seq_hash[i-1] || local_hash[i])
- Worker ID: какой worker хранит блок.
Local hash'и намеренно являются chunk hash (без контекста префикса), чтобы frontend мог дешево и параллельно хешировать блоки запроса. Компромисс в том, что chunk hash не различает позицию. "Predict the next token | Learn from the error | Predict the next token." дает одинаковые хеши у блоков 0 и 2. Именно эта проблема коллизий определяет все решения по структурам данных ниже.
1.2 События и запросы
Indexer обрабатывает два типа трафика:
KV Events (записи): publisher, расположенный рядом с каждым engine, отправляет Store(worker_id, local_hash, seq_hash), когда блок кэшируется, и Remove(worker_id, seq_hash), когда он удаляется. Нам нужны явные события, потому что engines кэшируют блоки дольше жизни запроса, а их политики eviction (LRU sweep, pressure по памяти, preemption) скрыты - по одним циклам запрос-ответ нельзя восстановить состояние cache. Поток bursty: prefills создают десятки store одновременно; eviction sweep'ы создают всплески remove.
Тепловая карта плотности KV cache-событий по worker'ам и в сумме, полученная из 5% трассы Mooncake FAST'25, воспроизведенной на 16 worker'ах Mocker с 2,048 GPU blocks на каждом. Зеленые ячейки показывают интервалы, в которых доминируют Store (всплески prefill); янтарные ячейки показывают интервалы, где доминируют Remove (eviction sweep'ы). Дивергентная цветовая шкала ограничена значениями ±10 событий на worker и ±100 событий в сумме, что подчеркивает bursty и временно коррелированный характер KV cache-трафика, который Flash Indexer должен выдерживать на полной скорости линии.
Requests (чтения): на каждый inference request frontend отправляет последовательность chunk hash'ей [local_hash_0, ..., local_hash_D]. Indexer возвращает оценки (worker_id, match_depth), чтобы router мог выбрать worker с самым глубоким кэшированным префиксом.
Каждому engine соответствует publisher, который обогащает сырые KV-события идентичностью worker'а и хешами блоков, а затем рассылает их через pub/sub. Router запрашивает у indexer'а lookup по store, а тот вычисляет оценки перекрытия префикса, используемые для принятия решений по маршрутизации.
Оба пути горячие. Медленные события означают устаревшие решения по маршрутизации. Медленные запросы к indexer'у означают пользовательскую задержку. Цель дизайна - держать оба пути быстрыми без взаимной конкуренции.
2. Вложенный словарь → Rust Actor
2.1 Python Dictionary
Самый простой возможный индекс - это вложенный словарь. Для каждого worker'а храните отображение от local hash блока к множеству внешних sequence hash'ей, которые разделяют этот chunk hash. Поскольку local hash - это chunk hash, одни и те же токены могут появляться в разных позициях в разных последовательностях, и один local hash может соответствовать нескольким sequence hash'ам на одном worker'е. Чтобы найти совпадения, нужно пройти по каждому worker'у и пройти по последовательности запроса, проверяя попадания.
class KvIndex:
# worker_id -> { local_hash -> set of seq_hashes }
index: dict[int, dict[int, set[int]]] = {}
def store(self, worker_id: int, blocks: list[tuple[int, int]]):
if worker_id not in self.index:
self.index[worker_id] = {}
for local_hash, seq_hash in blocks:
if local_hash not in self.index[worker_id]:
self.index[worker_id][local_hash] = set()
self.index[worker_id][local_hash].add(seq_hash)
def remove(self, worker_id: int, seq_hashes: list[int]):
if worker_id not in self.index:
return
for seq_hash in seq_hashes:
for local_hash, hashes in self.index[worker_id].items():
hashes.discard(seq_hash)
def find_matches(self, query: list[int]) -> dict[int, int]:
scores = {}
for worker_id, blocks in self.index.items():
depth = 0
for local_hash in query:
if local_hash in blocks and blocks[local_hash]:
depth += 1
else:
break
if depth > 0:
scores[worker_id] = depth
return scores
У этого подхода есть проблема корректности. local_hash in blocks говорит нам, что у worker'а есть какой-то блок с этими токенами, но не какой именно - разные последовательности, разделяющие один chunk hash, смешиваются. Именно эта проблема коллизий формирует все последующие решения по структурам данных. На один query это O(W × D) (W worker'ов, D глубина запроса).
При сотнях worker'ов и последовательностях длиной в тысячи блоков это неприемлемо.
2.2 Rust Actor
Перенос на Rust (HashMap<WorkerId, HashMap<LocalHash, HashSet<ExternalHash>>>) убирает накладные расходы интерпретатора. Однопоточный actor полностью владеет индексом и общается через каналы - это корректно и без lock'ов, но все чтения сериализуются за всеми записями. Один поток и есть потолок пропускной способности.
3. Инвертированный индекс
worker -> { hash -> ... } заставляет find_matches проходить по каждому worker'у. Но вопрос звучит иначе: "у каких worker'ов есть этот блок?" - ключ должен быть не worker, а блок. Вместо прохода по worker'ам и проверки блоков нужно построить прямой индекс по LocalHash, который сопоставляет последовательности хешей и их множества worker'ов.
// local_hash -> (seq_hash -> set of workers)
index: HashMap<LocalHash, HashMap<ExternalHash, HashSet<WorkerId>>>
Теперь find_matches проходит по запросу один раз. В каждой позиции берется объединение множеств worker'ов. Worker'ы только выпадают по мере углубления - каждый удаляется максимум один раз, - что дает O(D + W) вместо O(W × D).
Инвертированный индекс - это большой выигрыш для чтения, но любой выбор структуры данных - это компромисс между производительностью запроса и стоимостью обновлений.
На стороне чтения снова возникает проблема коллизий из раздела 2.1, но в другой форме. Когда мы объединяем множества worker'ов по sequence hash'ам для данного local hash, мы смешиваем worker'ов, кэшировавших разные последовательности с одинаковым chunk. Данные seq hash есть в индексе, но find_matches не может использовать их без вычисления собственных seq hash'ей запроса - а это снова вводит rolling hash в read-path, именно то, чего chunk hash должны были избежать.
На стороне записи удаления тоже дороги: без обратного поиска по worker'у удаление блока по seq hash требует сканирования всего индекса. Можно добавить таблицу обратного поиска, но это добавит больше bookkeeping на каждую store-операцию.
Обе проблемы решает radix tree.
4. Radix Tree
У каждого узла есть небольшая карта children, ключом в которой служит LocalHash, а также множество worker'ов. Отношения parent-child ограничивают риск коллизий: два блока с одинаковым chunk hash сталкиваются только если у них общий parent, а значит и общий префикс. Разные префиксы ведут к разным parent. Для этого в KV-события нужен один новый field: parent hash, чтобы tree мог связывать child с parent по мере поступления событий.
Prefix-aware radix tree индексирует кэшированные блоки по local hash. Общие префиксы ветвятся там, где последовательности расходятся; каждый узел хранит, какие worker'ы владеют этим блоком.
type SharedRadixBlock = Rc<RefCell<RadixBlock>>;
struct RadixBlock {
children: HashMap<LocalHash, SharedRadixBlock>,
workers: HashSet<WorkerWithDpRank>,
block_hash: Option<ExternalHash>,
}
struct RadixTree {
root: SharedRadixBlock,
lookup: HashMap<WorkerWithDpRank, HashMap<ExternalHash, SharedRadixBlock>>,
}
Каждый узел также несет sequence hash. Per-worker lookup table (worker -> { seq_hash -> node }) обеспечивает доступ O(1) для обработки событий: store прикрепляет children через seq hash parent'а; remove находит узел напрямую. Два ключа под два шаблона доступа - local hash для обхода, sequence hash для событий.
И дерево, и lookup table указывают на одни и те же узлы через Rc<RefCell<T>> (разделяемое владение с внутренней изменяемостью, однопоточно). Карты children в каждом узле небольшие - их размер ограничен коэффициентом ветвления, а не общим числом блоков.
Этот подход по-прежнему остается однопоточным за actor'ом, с сериализованными чтениями и записями.
5. Конкурентный Radix Tree
Чтения не конфликтуют друг с другом. Мы заменяем Rc<RefCell<T>> на Arc<RwLock<T>> (атомарный подсчет ссылок + reader-writer lock). Теперь find_matches берет только read locks и выполняется inline в потоке вызывающего - без канала, без actor'а, без очереди.
Записи используют sticky routing: ThreadPoolIndexer детерминированно назначает каждый WorkerId одному потоку. События для одного и того же worker'а всегда попадают в один и тот же поток, поэтому нет write-write contention на поддереве какого-либо worker'а.
События записи по worker ID sticky-routed в thread pool, что гарантирует последовательный порядок. Конкурентный radix tree с Arc<RwLock> позволяет параллельные чтения find_matches(), обеспечивая одновременные обходы.
type SharedBlock = Arc<RwLock<Block>>;
struct ConcurrentRadixTree {
root: SharedBlock,
lookup: DashMap<WorkerWithDpRank, RwLock<HashMap<ExternalHash, SharedBlock>>>,
}
DashMap шардирует внешнюю map, чтобы чтения и записи по разным worker'ам не упирались в один и тот же lock. parking_lot::RwLock избегает системного вызова ОС на неконфликтных путях (в 2-3 раза быстрее, чем std::sync::RwLock). FxHashMap заменяет SipHash одним шагом multiply-xor - здесь это безопасно, потому что ключи - это u64 hash'и, а не пользовательский ввод.
parking_lot::RwLock по умолчанию task-fair: он обслуживает ожидающих в порядке прихода, а не безусловно отдает приоритет читателям или писателям. В сочетании с гарантией sticky routing, что записи каждого worker'а сериализованы в одном потоке, конкуренция на запись минимальна, и не голодают ни чтения, ни записи.
Для чтений actor исчезает. Несколько вызовов find_matches выполняются одновременно с записями на разных worker'ах.
6. Positional Indexer с jump search
Radix tree обходит узлы по одному, следуя указателям от parent к child, - это плохо для cache и по сути последовательно. Нельзя проверить позицию 128, не посетив 0-127.
Замените tree на Vec<DashMap<LocalHash, SeqEntry>>, индексируемый по позиции. index[position] - это конкурентная map от local hash к sequence entry. Любая позиция получает доступ O(1) - обход не нужен.
enum SeqEntry {
Single(ExternalHash, HashSet<WorkerWithDpRank>),
Multi(HashMap<ExternalHash, HashSet<WorkerWithDpRank>>),
}
struct PositionalIndexer {
// index[position] -> { local_hash -> SeqEntry }
index: Vec<DashMap<LocalHash, SeqEntry>>,
worker_blocks: DashMap<WorkerWithDpRank, LevelIndex>,
jump_size: usize,
}
Перечисление SeqEntry обрабатывает коллизии: в обычном случае слот (position, local_hash) содержит ровно один sequence hash, который хранится inline без выделения HashMap. Только когда несколько префиксов порождают один и тот же chunk hash в одной позиции, запись повышается до Multi.
Разделение Single/Multi также позволяет ленивое вычисление hash: когда lookup находит Single, совпадение однозначно и без вычисления sequence hash запроса. Дорогой rolling hash нужен только для редких Multi-записей, где коллизии chunk hash требуют disambiguation.
Но главное преимущество positional indexer - не layout данных, а то, что делает возможным random access.
Random access позволяет jump search:
- Инициализировать активное множество worker'ов от позиции 0.
- Прыгнуть вперед на
jump_sizeпозиций (например, 64) к следующей контрольной точке. - В контрольной точке подсчитать, сколько активных worker'ов все еще совпадают (проверка мощности множества - без копирования set'ов).
- Если совпадают все: весь пропущенный диапазон подтвержден. Продолжить прыжки.
- Если совпадает меньше: в пропущенном диапазоне некоторые worker'ы выпали. Просканировать вперед позиции
[previous_checkpoint + 1 .. current_checkpoint], чтобы найти точную точку выпадения каждого потерянного worker'а. - Возобновить прыжки от текущей контрольной точки.
Если позиция - ключ первого класса, indexer прыгает вперед фиксированным шагом. При частичном совпадении lookback от предыдущей контрольной точки находит точные точки выпадения, после чего прыжки возобновляются от текущей контрольной точки.
Лучший случай: D / J lookup'ов вместо D.
Худший случай (worker'ы выпадают на каждом прыжке): деградирует в линейное сканирование с overhead от прыжков.
Positional indexer выигрывает на длинных последовательностях с высокой долей общего префикса; radix tree выигрывает на коротких или сильно расходящихся последовательностях.
Layout Vec также улучшает локальность cache: ранние позиции (общие системные prompt'ы, типовые preamble) находятся на горячем пути, скапливаются в начале массива и остаются теплыми в cache.
При размере прыжка J (= jump_size, по умолчанию 64) усредненная стоимость снижается до O(D/J + W). Поскольку J — настраиваемая константа, сложность остается линейной по D; практическая польза в том, что при высокой доле общего префикса можно пропустить подавляющее большинство позиций.
7. Бенчмарки
Все бенчмарки запускаются на 24-ядерном десктопе Arrow Lake (285K), воспроизводя общедоступные production traces Mooncake через mock engine с 16,384 GPU blocks и включенным prefix caching. Harness тестирует все пять backend'ов с 24 параллельными потоками обработки событий.
Ops throughput - это суммарная скорость KV-событий и запросов find_matches в секунду. Мы меняем offered load, сжимая одну и ту же трассу в более короткие интервалы, и сравниваем achieved throughput с offered throughput. Threshold throughput - это точка, где achieved throughput перестает следовать за offered, то есть точка насыщения indexer'а.
Достигнутая и предлагаемая пропускная способность блоков для пяти backend'ов indexer'а, измеренная с помощью mooncake_bench на реальных данных трассы. Flash Indexer выдерживает 170M ops/s - в 42 раза быстрее, чем Radix Tree, поставлявшийся в Dynamo v0.1.0 (4M ops/s), и в 440 раз быстрее наивных реализаций (385K ops/s).
8. Дальнейшие направления
После поставки Flash Indexer в Dynamo v1.0.0 следующая волна оптимизаций нацелена на оставшиеся постоянные множители:
- Бинарный поиск внутри прыжков. Заменить линейный обратный проход после неудачного прыжка на бинарный поиск:
O(log J)вместоO(J)на каждый неудачный прыжок. - Иерархическая маршрутизация. Разреженный верхнеуровневый indexer для грубого покрытия префиксов между deployment groups, с полными indexer'ами на листьях.
- Inline bitset'ы для множеств worker'ов. Заменить
HashSetна фиксированные bitset'ы, хранящиеся inline в каждом узле, чтобы проверки принадлежности сводились к одной битовой операции и без pointer chasing.
9. Заключение
Путь от Python dictionary до Flash Indexer включает шесть итераций, каждая из которых была вызвана конкретным узким местом предыдущего дизайна:
- Наивный вложенный dict — простой, но
O(W × D)на каждый запрос. - Rust + паттерн actor — быстрый язык, корректная concurrency, но узкое место в виде одного потока.
- Инвертированный индекс —
O(D + W)на запрос за счет переворота структуры ключей; дополнительный слойseq_hashдля защиты от коллизий chunk-hash. - Radix Tree — tree-структура заменяет гигантскую плоскую map; карты children в каждом узле остаются небольшими; двухключевой дизайн (local hash для обхода, seq hash для обработки событий);
Rc<RefCell<>>для однопоточного разделяемого владения. - Конкурентный Radix Tree —
Arc<parking_lot::RwLock<>>заменяетRc<RefCell<>>;DashMapс внутреннимRwLockдля lookup table на уровне каждого worker'а (shard-level locking для редких модификаций, дешевые общие чтения на горячем пути); чтения полностью обходят actor; sticky routing сериализует записи по каждому worker'у без contention. - Конкурентный positional indexer через jump search (Flash Indexer) — альтернатива radix tree для long-sequence workloads;
Vec<DashMap<>>, индексируемый по позиции, заменяет pointer chasing на random access O(1), позволяя jump search пропускать большую часть глубины;DashMapс внутреннимRwLockна уровне каждого worker'а для обратного поиска; горячие позиции префикса скапливаются в началеVecи остаются теплыми в cache.
Итог: устойчивая ops throughput на уровне 170 миллионов операций в секунду - с учетом и событий, и запросов - при том что achieved throughput следует за offered throughput вплоть до предела.