2026-07-15 · KV cache · 6 min

What your router actually knows about the KV cache

vLLM’s KV-event stream never fires on a cache hit. The single most common thing a prefix cache does — reuse a block that’s already resident — puts nothing on the wire. If you’re building a cache-aware router on top of that stream, that’s the first thing to know, because it bounds what your router can know.

vLLM emits exactly three events (vllm/distributed/kv_events.py): BlockStored, BlockRemoved, AllBlocksCleared. BlockStored fires once, in cache_full_blocks(), the first time a full block is hashed and inserted. Eviction fires BlockRemoved. A full reset_prefix_cache() fires AllBlocksCleared. That’s the entire vocabulary.

The hit path is touch(). It runs when a request reuses blocks already in the cache: it bumps the ref count, pulls the block off the free list if it was idle, records a metric. It does not append to the event queue — there is no emit anywhere in the function. It’s called from allocate_new_computed_blocks() to touch the blocks a request just matched in the prefix cache, so they aren’t evicted.

So a block announces itself once, when it’s first computed. Every reuse after that — the same request’s next segment, or a different request sharing the prefix — is invisible. A consumer building a global index from these events learns which blocks exist and on which pod. It learns nothing about how recently any of them was touched. That’s fine if all you want is “who has this prefix.” It’s a hole the moment you want to reason about staleness: the schema carries no recency signal, and the hit that would carry it never fires.

SGLang has the same gap, in the same place — and that’s not convergence. Its match_prefix() → _match_prefix_helper() updates last_access_time on every node it walks, and emits nothing. SGLang’s kv_events code is a credited, near-verbatim port of vLLM’s: PR #6098’s own description says “Event classes and publisher code borrowed from vllm-project/vllm#16750.” Same class names, same fields, same buffer_steps=10_000, same hwm=100_000, same port 5557. The blind spot isn’t a vLLM oversight you switch engines to escape. It’s a property of the shared design. Both engines model the stream as births and deaths of blocks, never traffic on blocks.

One more thing the stream won’t hand you: recovery has a floor. It isn’t pure fire-and-forget — the publisher pairs a zmq.PUB socket with a zmq.ROUTER for replay, stamps each batch with a sequence number, and keeps the last 10,000 batches in a ring buffer, so a subscriber that sees a gap can request a replay from its last sequence. But if the gap is older than that window, there’s no snapshot to fall back on — NVIDIA’s own Dynamo-vs-vLLM replay comparison says vLLM’s consumer has “no built-in initial state sync” and “must rebuild state through other means.” Dynamo’s own indexer has that fallback: ask for a range that’s too old and you get a TreeDump, the full RadixTree as synthetic events. vLLM and SGLang have no TreeDump. That was deliberate — PR #16750 existed specifically to avoid pulling Dynamo’s Rust/NATS publisher into vLLM as a dependency — but it means the two ecosystems give you different reliability guarantees, not just different transports. No recency on hits, and no full resync past the buffer window. Build your index to tolerate both.

The structure under it isn’t a radix trie with RCU

Ask how these caches are built and you’ll hear “radix trie with RCU” — a prefix tree, lock-free reads racing a writer that publishes new versions. Clean mental model. It’s wrong for two of the three canonical open-source implementations, and the third doesn’t use RCU.

SGLang is the only one that’s actually a radix tree (radix_cache.py). And it has no locks — not lock-free-as-in-RCU, no concurrency primitives at all. Grep radix_cache.py and the C++ port (tree_v2.{h,cpp}) for mutex|lock|rcu|atomic and the only hit is lock_ref, which is a reference count for eviction, not a mutex. It gets away with that because the tree is never shared across threads: SGLang’s scheduler owns it and drives match, insert, and evict from a single loop. There’s no reader/writer race to solve, so there’s no lock.

vLLM v1 isn’t a tree at all. Its prefix cache is a flat dict — BlockHashToBlockMap, hash → block, degrading to a nested dict only on hash collision. Same single-writer story: one EngineCore process, one scheduling loop, no lock.

The one component that genuinely has a concurrency problem is llm-d’s cross-pod indexer (llm-d/llm-d-kv-cache) — because that’s where many pods’ event streams write while many routing decisions read. It’s not a tree, and it’s not RCU. It’s a two-level LRU hash map with sharded locks: InMemoryIndex scopes each mutex to a single key, Lookup takes no global lock, and the write path runs FNV-1a-sharded workqueues so events for one pod stay ordered while different pods parallelize. Textbook sharded-lock table, not a versioned structure with grace-period reclamation. Nobody solved lock-free concurrent tree reads here. They sidestepped the problem three different ways: single writer thread, SPMD replication, per-key locks.

What actually makes it interoperate is the hash, not the tree

The thing that lets a router index another engine’s cache isn’t the data structure — it’s the block hash. vLLM keys each block by a chained hash over (parent_block_hash, token_chunk, extra_keys), sha256_cbor or xxhash_cbor, seeded off PYTHONHASHSEED. llm-d’s indexer recomputes the same shape — FNV-64a over the CBOR encoding of (parent, chunk, extra), block size 16 — and its config explicitly aligns the seed to vLLM’s PYTHONHASHSEED. That wire-compatibility is the load-bearing part. The index is a map of hash → pod, and it works only because two separate codebases agree, byte for byte, on how to hash a block.

I came at this from the metrics side. My merged PR to llm-d-inference-sim (#358) adds vllm:prefix_cache_hits and vllm:prefix_cache_queries counters, so rate(hits) / rate(queries) reproduces vLLM’s token-level cache-hit rate in Prometheus. The simulator’s synthetic cache doesn’t model a radix tree — it calls llm-d’s own chunked-hash token processor (TokensToKVBlockKeys) to turn tokens into block keys. Even the simulator is built on hash-chain block indexing. Once you leave SGLang, the trie is the exception, not the rule.

Two corrections to carry if you’re building on this stack. The event stream tells you a block was born and when it died, never that it was used, and it won’t resync you past its buffer — so hold recency and staleness in your own logic, not the stream’s. And the structure underneath is probably a sharded hash map, not a radix trie — the interop that lets your router index another engine’s cache lives in the block hash.