Distributed KV caches for LLM serving are built on the observation that prefixes repeat. Shared system prompts, multi-turn conversations, and RAG over a common corpus all let a cache turn repeated prefixes into avoided prefill.
That makes this optimization look obvious: when several concurrent requests need the same cold KV block, let one request fetch it and make the others wait. In Go this pattern is called single-flight. In a KV connector it could avoid duplicate external lookups, duplicate reads, and duplicate GPU block allocations.
The code path is real. The workload case is not automatic.
I first measured a historical Mooncake trace and found almost no coalescable work. Then I noticed that Mooncake's current FAST'25 README labels that file as historical and tells new experiments to use three newer traces. I reran the entire experiment. The two real traces largely preserved the negative result at short load windows. The synthetic trace did not: under larger effective windows, an ideal single-flight could remove as much as 8.8% of cold load attempts in the most favorable configuration.
That split is more useful than a clean negative. It shows why cache hit rate is not enough, why one trace is not a conclusion, and which workload statistic actually decides whether coalescing is worth building.
In vLLM's MooncakeStoreConnector
, a request that finds an external KV prefix allocates destination GPU blocks and starts an asynchronous load. Those blocks do not become ordinary local prefix-cache hits until the load completes. A second request arriving in that interval cannot simply reuse the first request's destination. It can perform its own lookup, allocate different GPU blocks, create its own load metadata, enter the receive queue independently, and submit another external Get for the same logical content.
I verified that behavior with a deterministic probe through the real control path:
Scheduler
-> MooncakeStoreConnector
-> MooncakeStoreWorker
-> batch_get_into_multi_buffers
The first Get was held at a barrier while seven other requests sharing the same cold block progressed. The result was eight lookups, eight load specifications, eight receive-queue entries, eight Get submissions, and eight distinct CUDA destination addresses for one block hash. Every request completed once and the barrier did not time out. The probe established duplicated submitted work; it did not claim eight completed NIC transfers or an end-to-end latency loss.
That distinction matters. A deterministic reproducer proves possibility: the system can take the path. It does not prove prevalence: that production requests often create the necessary overlap. And neither proves importance: that eliminating the work beats the synchronization, bookkeeping, failure propagation, and head-of-line blocking introduced by the fix.
The probe and the trace experiment are documented on vLLM issue #50433.
Ordinary prefix caching needs the same content to appear again before it is evicted. Single-flight needs a much narrower event: the same content must appear again on the same instance before the first load finishes.
Those are different distributions.
A workload can have a high cache hit rate because prefixes return after seconds or minutes. That does not help a mechanism whose opportunity window is milliseconds. Conversely, a workload with only moderate reuse can benefit if the reuse arrives in bursts.
The quantity to measure is therefore not appearances per hash. It is the fan-in of same-instance, same-hash cold requests inside one load window.
The model is small, but two plausible implementation mistakes force the answer before the trace is read.
The first is inserting a block into the cache when a load starts. That makes the next request a cache hit and guarantees fan-in one. The block must remain absent until completion:
t first miss; load starts
[t, t+W) later requests still see a cold block
t+W load completes; block enters the cache
I added a reverse test: deliberately switch to insert-on-miss and assert that the redundancy rate becomes identically zero. Negative-result work needs this kind of test because a silently broken model often produces the cleanest possible negative.
The second mistake is using a sliding window. Suppose requests for one block arrive at 0, 9, and 18 ms and a load takes 10 ms. The first two overlap. The third arrives after the leader has completed, so it sees a cached block. A sliding-window clustering algorithm can chain the three together because each neighboring pair is close. That inflates fan-in.
Instead, the first miss opens an anchored cohort. Later misses join only until the leader's fixed completion time. At that time the cohort closes and the block is inserted. Requests arriving exactly at completion are processed after the completion event and count as hits.
Eleven unit tests cover these semantics, stable ordering of timestamp ties, cross-instance isolation, LRU eviction, accounting identities, and the reverse insert-on-miss assertion.
It is tempting to sweep both offered-load scaling and physical fetch latency. For count-valued outcomes in this model, they collapse into one parameter.
If trace time is compressed by a factor s
, an arrival at t
becomes t/s
.
Two requests overlap when their original separation is less than W * s
,
where W
is physical load latency. Uniform time scaling preserves event and LRU access order. The model therefore depends on:
W_eff = W * s
A 10 ms fetch under 100x offered-load compression is the same counting point as a 100 ms fetch under 10x compression. Rates can be derived afterward, but they are not independent experiments.
I swept W_eff
over 10, 30, 100, 300, 1,000, 3,000, and 10,000 ms; instance counts from 1 to 16; three per-instance LRU capacities; round-robin and a first-block-affinity routing proxy; and two prefix-lookup interpretations. That is 420 configurations and 840 warmup/steady rows per trace.
Routing, cache capacity, and instance count are model parameters. The traces contain no production instance labels.
Mooncake's current trace README publishes three JSONL files with the same schema as the historical release: arrival timestamp, input and output token lengths, and cumulative prefix hashes over 512-token blocks.
| Trace | Requests | Block lookups | Distinct timestamps | Arrival model |
|---|---|---|---|---|
| Conversation | 12,031 | 288,500 | 1,180 | timestamped real trace |
| Tool/agent | 23,608 | 409,616 | 1,180 | timestamped real trace |
| Synthetic | 3,993 | 121,877 | 3,982 | Poisson-generated |
Every one of the 39,632 records parsed with exactly the documented fields and
types. For every record, the number of hashes equalled
ceil(input_length / 512)
. The current tool/agent file is not byte-identical to the historical single-file trace.
The arrival timelines are very different. Conversation and tool/agent have a median positive timestamp gap of about 3,000 ms, with medians of 10 and 20 requests sharing a timestamp. Synthetic has almost one timestamp per request and a median positive arrival gap of 175 ms.
The public README documents relative arrival timestamps but does not establish whether ties in the real traces are true batches or timestamp buckets. I treat ties as simultaneous. If they are buckets for arrivals spread through the interval, that choice biases the model toward finding within-tick fan-in; it is not evidence that they actually arrived together.
The steady-state results below report the fraction of cold block-load attempts an ideal same-hash single-flight could remove.
| Trace / effective window | Median redundancy | Maximum redundancy | Maximum fan-in | Rows with p99 fan-in > 1 |
|---|---|---|---|---|
Conversation, W_eff <= 1 s |
||||
| 0.000493% | 0.006068% | 15 | 0 | |
Conversation, W_eff = 3 s |
||||
| 0.000493% | 0.025903% | 22 | 0 | |
Conversation, W_eff = 10 s |
||||
| 0.055459% | 0.108998% | 49 | 0 | |
Tool/agent, W_eff <= 1 s |
||||
| 0.000921% | 0.002890% | 2 | 0 | |
Tool/agent, W_eff = 3 s |
||||
| 0.001024% | 0.078805% | 16 | 0 | |
Tool/agent, W_eff = 10 s |
||||
| 0.057785% | 0.211872% | 16 | 0 | |
Synthetic, W_eff = 1 s |
||||
| 0.100243% | 0.655305% | 3 | 0 | |
Synthetic, W_eff = 3 s |
||||
| 0.584295% | 2.812072% | 3 | 16 / 60 | |
Synthetic, W_eff = 10 s |
||||
| 2.534440% | 8.816033% | 4 | 60 / 60 |
The two real traces support a scoped negative. Through one second of effective window, their median avoidable work is around one hundred-thousandth of cold loads, and the worst grid point remains below 0.007%. At three seconds, a few configurations pick up more overlap around the roughly three-second timestamp cadence, but the worst result is still below 0.08%. The 99th-percentile fan-in is one in every summary row.
The high maximum fan-in in the conversation trace does not contradict the tiny fraction. A small number of cohorts, including heavily shared early hashes inside timestamp ties, can have many members while almost every cohort still has one. Maximum fan-in is a failure-mode signal, not a prevalence measure.
Synthetic changes the conclusion. Its median redundancy reaches 0.10% at one second, 0.58% at three seconds, and 2.53% at ten seconds. At the ten-second point, every grid row has p99 fan-in above one, and the maximum avoidable share is 8.82%. That is large enough that the cost per load and absolute load rate become operational questions rather than rounding errors.
This is not evidence that Mooncake production traffic behaves like the synthetic trace. It is evidence against a workload-independent negative claim.
I modeled prefix lookup in two ways. contiguous_prefix
walks from the first
block and treats the suffix after the first unavailable block as needed.
independent_blocks
tests every hash separately. They are not two independent experiments; they are sensitivity bounds around prefix-walk behavior.
On the two real traces, the largest absolute difference in redundancy ratio
between the modes was 4.48e-6
and 4.11e-6
respectively: less than 0.00045
percentage points. On synthetic it grew to 0.001269
, or about 0.127 percentage points. That is visible, but still much smaller than the gap between the real and synthetic workloads. The main split is coming from arrivals and reuse, not from choosing the more favorable lookup interpretation.
Routing provides a useful warning about seductive secondary findings. On both real traces, first-block affinity produced a higher redundancy ratio than round-robin at 168 of 210 paired steady-state grid points and tied at the other 42. That sounds like evidence that affinity routing makes duplicate loads worse. I do not think it supports that claim. The routing proxy sent every request with the same first hash to one instance, producing maximum request-imbalance ratios of 16.0 for conversation and 7.41 for tool/agent. Prefix concentration and load concentration are inseparable in those numbers.
Synthetic is a useful check: its maximum imbalance was only 1.19, and affinity was higher at 92 pairs, equal at 106, and lower at 12. The clean directional story disappeared with the hotspot. Routing effects need a design that holds per-instance offered load constant; this sweep reports imbalance but does not control it.
The median positive same-hash reuse gaps are about 132 seconds for conversation, 93 seconds for tool/agent, and 59 seconds for synthetic. Looking only at those medians would predict that all three should be negative. The synthetic result shows why that shortcut fails.
Single-flight opportunities live in the lower tail: the small fraction of keys whose repeated accesses land inside the load window. A long global median can coexist with enough short-gap events to matter, especially after offered-load scaling. The useful diagnostic is a distribution or direct cohort count, not a single reuse-distance statistic.
A better decision sequence is:
- Measure same-key overlap inside the intended fetch-latency window.
- Separate the fraction of duplicate cohorts, duplicate attempts, and removable attempts; they answer different questions.
- Convert the removable fraction to an absolute rate and cost.
- Compare that saving with coordination paid on every lookup, including timeout and owner-failure paths.
In symbols:
avoidable cost rate
= cold-load rate * redundancy ratio * cost per load
Only then is it useful to debate the implementation.
The location matters. A Get-layer single-flight could merge external reads but still leave duplicate scheduler lookups, GPU allocations, and copies. A scheduler or pending-block design can avoid more work, but it also owns deadlines, cancellation, reference counts, readiness, and fallback.
LMCache illustrates the difference between layers. In LMCache v0.3.9 and v0.5.1, I found no content-keyed cross-request single-flight for in-progress retrievals in the async lookup client or the storage retrieval path. Its vLLM wrapper nevertheless reports connector-level as synchronous. With default prefix caching and eligible full blocks, vLLM can publish an allocated block into its local hash cache immediately, allowing a later request to reuse the same GPU block. That is partial deduplication at the GPU-allocation layer; it does not guarantee that request-specific LMCache lookup, prefetch, or external-read work is coalesced.
The engineering question is therefore not simply "does this connector have single-flight?" It is "which duplicated resources does the chosen ownership point actually eliminate?"
The deterministic Mooncake probe should remain available because it pins a real behavior and can test any future ownership design. But the two real FAST'25 traces do not justify adding scheduler-hot-path coordination on their own. Their short-window opportunity rate is too small.
The synthetic trace prevents the opposite overreach. It says not to close the design question forever. A deployment with denser arrivals, bursty shared prefixes, slower remote fetches, or much higher offered load can cross the threshold. Agentic workloads with large shared prompts are plausible candidates, but the trace must show it.
This experiment also does not measure TTFT, completed NIC bytes, network contention, or end-to-end speedup. It models submitted cold-load attempts under explicit cache and routing assumptions. A positive trace result is a reason to run a system benchmark, not a substitute for one.
Each full run completed 420 configurations and produced 840 phase rows and 5,208 per-instance rows. The three cohort files contain about 230 million rows in total. Output SHA-256 values matched their manifests, every gzip stream decompressed successfully, instance totals reconciled to every summary row, and cohort line counts matched aggregate cohort counts exactly.
The important lesson is not that single-flight wins or loses. It is that prefix reuse and concurrent prefix reuse are different workload properties. A high hit rate establishes the value of caching. It says almost nothing about the value of coordinating in-progress misses.
Measure the overlap window before building the ownership machinery. Then keep the conclusion scoped to the workload that produced it.