Optimizing LMCache's prefix lookup for one-sided RDMA
LMCache decides what to recompute and what to load by asking one question a lot: how much of this prefix do you already have? On a one-sided RDMA backend, that question can answer itself, and the answer is the read.
What an existence check is
LMCache offloads vLLM's KV cache to tiers below the GPU: local CPU, then a remote backend.
A remote backend plugs in as a connector with a small surface: get,
put, close, and an existence check, exists /
contains. The existence check answers a narrow question: does the tier hold
this key, without transferring the value. It is meant to be cheap relative to a
get, because its job is planning, not loading.
Why LMCache asks
vLLM reuses work along a token prefix. A shared system prompt, a long document, a few-shot preamble: if the prefix repeats, its attention KV does not need to be recomputed, only loaded. LMCache splits that prefix into fixed-size chunks, hashes each chunk to a key, and before it loads anything it needs to know the longest run of chunks, starting from the front, that the backend already holds.
Existence therefore comes first. The keys are ordered, and what matters is the contiguous prefix that is present. The first gap ends the usable run: everything up to it is loaded, everything after it is recomputed. So the planning question is not really "is key K here?" It is "how many leading chunks are here?"
The batched existence check
Asking per chunk is one round trip per key, which is wasteful when a prefix is dozens or
hundreds of chunks. LMCache's connector contract has a batched form,
batched_contains(keys) -> int: one call that returns the number of leading
chunks present, the prefix hit length. It collapses many existence round trips into one and
hands back exactly the number LMCache acts on. This is already an optimization in LMCache:
check the whole prefix at once, get back where it stops.
Making it free on one-sided RDMA
On most backends, contains and get are different calls.
contains asks the server "do you have it," get asks "send it,"
and the server does the work both times. A one-sided RDMA backend is not shaped that way.
The data node does nothing per read. The client resolves a key to a descriptor,
a small record holding the remote address, the rkey that authorizes the read,
the length, and the version and checksum to validate. The read itself is then just
fi_read against that address.
Which means existence is not a separate question. A key exists exactly when its descriptor
resolves, and resolving the descriptor is the same metadata lookup the read needs. So
batched_contains was computing every hit's read address and throwing it away,
and the following batched_get resolved it all over again. Two metadata round
trips per hit, for one address.
The optimization is to keep what the existence check already produced.
batched_contains now resolves the prefix once, returns the prefix-hit count,
and prefetches each hit's address into a small per-client cache. The paired
batched_get reads straight from that cache: no second metadata round trip,
just the RDMA read.
The other half is the GIL. Both the metadata resolve and the read block, and a Python binding that holds the GIL across a blocking hop freezes the asyncio event loop. The binding releases the GIL across both, so other work proceeds while the control plane and the NIC do theirs. Net result: LMCache's lookup-then-fetch went from two GIL-holding metadata round trips per hit to one GIL-free batched lookup, with the read served from the prefetched address.
A prefix hit means no write at all
There is a second thing content addressing buys, and it took us a while to notice we had got it for free.
Blocks are keyed by a hash chain, H(prev_block_hash, tokens). That is a
content hash, so identical prefixes across different sessions land on the same key. When a
writer asks to allocate a block whose hash is already in the index, the control plane
increments a retention count and hands back the existing read descriptor. No slot is
granted, no bytes cross the wire, no write happens. Two requests sharing a long system
prompt do not store it twice.
The chaining also means the key space is the prefix tree. We did not build a separate structure for prefix lookup; it falls out of hashing the blocks the way you have to hash them anyway.
The hard part: pointers must stay true
Caching addresses is where it gets subtle, because a descriptor is a capability to read a specific remote slot. The cache must never hand back a pointer that should be gone.
A delete here is a lazy unpublish: it removes the key's descriptor so new lookups miss, but
it leaves the bytes and the rkey live until the slot is rotated and reclaimed.
A cached descriptor would still read those bytes and validate them cleanly, so a read after
a delete could return the just-deleted value. The fix is small: delete and put both drop
the key from the cache, so the next read re-resolves and misses. The cache also keeps only
the leading prefix it reports, so nothing lingers for an unrelated later batch to
pick up.
And the cache is never trusted for correctness. Every read still validates the bytes it lands against the descriptor: magic, key, version, a CRC over the payload, and a check that the descriptor's key matches the key requested. A stale entry can only ever cause a miss and a recompute, never a wrong value. The cache is a speed shortcut, not a source of truth.
This only works on a one-sided design, where the existence check and the read resolve the
same record. So the win is not a faster contains. It is letting
contains do work that get would otherwise repeat: ask once,
prefetch, release the GIL, and drop the answer the moment the key changes.