# From the engine to the cluster

Lecture 19 · Serving models · Distributed Systems I
Paper: Mooncake (FAST 2025)
The page also has slides and an interactive simulator: https://alfonsocampodonico.com/classes/distributed-systems/del-motor-al-cluster?lang=en
Code: https://github.com/AlfonsoCampodonico/ta050-sistemas-distribuidos/tree/main/repos/servir-tokens (`gh repo clone AlfonsoCampodonico/ta050-sistemas-distribuidos`)

> Storing, finding, splitting and scaling the KV cache: from one replica to a service, with Mooncake.

## 1. From one replica to a service

In Lecture 18 we looked inside vLLM: how a GPU builds batches with continuous batching and manages the KV cache of in-flight requests with PagedAttention. Since 2024, almost everything new in serving happens **outside** that replica. The engine is still inside each one; what changes is what surrounds it.

Today's paper is **Mooncake** (Qin et al., FAST 2025, best paper), the system that serves Kimi, Moonshot AI's chatbot. It's no accident that it won at a storage conference: its central idea is trading compute for storage.

The lecture has four parts:

| Part | What changes | Systems question |
| --- | --- | --- |
| Store | the KV cache isn't thrown away when the request ends: it's kept in GPU, cluster DRAM or disk | distributed cache |
| Find | the router sends each request to where its prefix already is, without overloading anyone | content-based routing |
| Split | prefill and decode have opposite needs, and are separated in time or in space | sizing pools |
| Scale | frontier models are mixtures of experts, and serving them is a parallelism problem | Lecture 17, again |

This is the last of the four lectures: 16 and 17 on training, 18 and 19 on serving. In all four, the state that matters is large and lives on the GPU; in serving, that state is the KV cache.

## 2. The workload: how much repeats

Mooncake published a one-hour trace of real Kimi requests. The average prompt has **7,590 tokens** and the response **182**: about 42 times more input tokens than output (Mooncake, arXiv version, §4.2). In Lecture 18 we were thinking of prompts of hundreds of tokens; in a real chatbot, prefill dominates.

Why so long? The model has no memory between requests: each turn sends the system prompt, the whole history and the new message, plus documents, tools or an agent's context. And **each turn is the prefix of the next one**.

In production, roughly half of the prefill doesn't need to be computed:

- **DeepSeek**, in the stats for one day of service (February 27 to 28, 2025): 608 billion input tokens, of which 342 billion, **56.3%**, came out of their on-disk KV cache.
- **Mooncake**, on the Kimi trace: with infinite capacity, at most about 50% of the KV cache could be reused. Popularity is very uneven: more than half of the blocks are never used again, and some (system prompts, popular documents) are used tens of thousands of times. With 1,000 cache blocks the hit rate is 30%; with 50,000, 50%.

The demos' workload (`engine.Chat`) mimics this: 1,000 conversations of about 4.5 turns on average (4,539 requests), 4 apps with a 2,000-token system prompt each. The average prompt comes out at about 3,900 tokens and the response at about 178.

**Connection to the course.** This is Lecture 12, cache consistency, with two friendly differences: the content is immutable (the KV cache for a given prefix is always the same, there's no invalidation) and a miss is cheap (you recompute). The hard part is where to put it and how to find it.

## 3. The prefix cache

**Why prefixes.** A token's KV cache depends on all the previous tokens. A block can only be reused if everything that came before it is the same: the same text at a different position doesn't help.

**Chained hashes.** The prompt is split into blocks of tokens (Mooncake uses 512; the repository, 64). Each block's identifier is the hash of its tokens **and of the previous block's identifier**:

> h₀ = hash(block₀), hᵢ = hash(hᵢ₋₁, blockᵢ)

If two prompts have the same h₃, they have the same tokens in blocks 0 through 3. Two conversations in the same app share the system prompt blocks; from the first differing block on, the hashes diverge and never match again.

**Lookup and eviction.** For a new prompt, you walk its hashes in order and stop at the first one that's missing: it's walking a prefix tree, and SGLang literally implements it as a radix tree (RadixAttention). For eviction, LRU: system prompt blocks are touched all the time and stay; those of abandoned conversations go. It's the same trick as PagedAttention's blocks from Lecture 18, but across different requests.

In the repository, the `prefix` package is exactly that in about 80 lines: `Hash(prev, content)`, and a `Cache` with `Match` (how many blocks of the prompt are already there), `Insert` and LRU.

**Tiers.** Mooncake's subtitle is literal: *trading more storage for less computation*. GPU memory is enough for the current batch, but the machines have lots of CPU DRAM and nearly idle SSDs.

| Tier | What it is | Who uses it |
| --- | --- | --- |
| GPU HBM | the current batch and hot prefixes | everyone |
| Cluster DRAM | a distributed pool, accessible over RDMA | Mooncake, LMCache |
| SSD / file system | large, cheap capacity | DeepSeek (3FS), Dynamo |

The math that justifies it, with the repository's cost model: computing a prefill token costs 0.05 ms and fetching it from the pool 0.005 ms, ten times less. As long as fetching is cheaper than recomputing, it pays to store.

## 4. The router

With a prefix cache, picking a replica is a trade-off between **going where the prefix is** and **not overloading anyone**. The repository's four policies (`cluster` package):

- **Round robin.** Spreads load evenly, but each turn of a conversation lands on a different replica: it only benefits from the system prompt.
- **Least loaded.** Balances well and also doesn't know where each conversation is.
- **Per session (sticky).** A hash of the session always picks the same replica: it uses the cache but ignores load. It's hash-mod-N: if a replica is added or lost, almost every session moves and loses its cache. Consistent hashing would move only a 1/N fraction.
- **Prefix-aware.** The one from Mooncake's Conductor (§6.1): for each replica it estimates the time to first token as the wait for what it already has queued plus the prefill for the part of the prompt it's missing, and picks the lowest. The real Conductor also adds the cost of fetching the prefix from another machine and rejects (429) if no replica meets the SLO; in the repository that is exercise 5.

**The demo** (`go run ./cmd/sim router`): 1,000 conversations, 4,539 requests, four replicas.

| Router | Cache hits | TTFT p50 | TTFT p99 | Imbalance |
| --- | --- | --- | --- | --- |
| Round robin, no cache | 0% | 19 s | 63 s |  |
| Round robin | 56% | 119 ms | 790 ms |  |
| Least loaded | 57% |  | 512 ms |  |
| Per session | 73% |  | 4.1 s | 1.24 |
| Prefix-aware | 73% | 79 ms | 456 ms | 1.07 |
| Prefix-aware + pool | 88% |  | 142 ms |  |

Without a cache, 18.3 million prefill tokens have to be computed and the cluster saturates. Sticky and prefix-aware get the same reuse; the difference is in the tail: sticky lets a replica with long conversations saturate. The shared pool lets you fetch a prefix computed on another replica at a tenth of the cost.

**With little cache** (`-cache 256`, a quarter per replica) the gap widens: round robin 40% (p99 7.2 s), sticky 44% (p99 26 s), prefix-aware 52% (p99 3.0 s), and with the pool 88% (155 ms).

**A real case.** The postmortem Anthropic published in September 2025 explains that its routing is sticky, and that a routing bug sent some short-context requests to servers configured for a million tokens, and a load-balancing change on August 29 multiplied that share; because routing was sticky, later requests from those conversations also landed there. The router doesn't just decide latency: it decides which hardware and configuration each request lands on.

**In Kubernetes.** A regular HTTP load balancer picks by connections or round robin, which is the worst row in the table. The **Gateway API Inference Extension** lets the gateway pick the pod by looking at the model's state: the queue, KV cache usage, which prefixes it holds. **llm-d**, in the CNCF sandbox since March 2026, is built on vLLM and that extension and brings the pieces from this lecture: a scheduler that routes by prefix, prefill and decode as separate services, tiered KV cache offloading and autoscaling. NVIDIA Dynamo does something similar. The Endpoint becomes a stateful object, and the scheduler needs fresh information from each replica: the classic problem of load information in a distributed load balancer.

## 5. Prefill and decode

**Interference.** With continuous batching (Orca, Lecture 18), prefill and decode share iterations. With 8,000-token prompts, the prefill of a single one costs, with the repository's cost model, 20 ms to read the weights plus 0.05 ms per token: about 420 ms. Decode iterations take about 30 ms; in the one where that prefill gets in, every user who was reading sees the text stall for almost half a second.

Two metrics in tension: **time to first token** (TTFT), which the new user sees, and **time between tokens** (TBT or TPOT), which the user already reading sees.

**Chunking the prefill (Sarathi-Serve, OSDI 2024).** The prompt is processed in fixed-size chunks, for example 512 tokens per iteration, alongside the batch's decodes (*stall-free scheduling*). No iteration blows up; the long prompt takes a bit longer to finish its prefill. Against vLLM they report up to 2.6 times the capacity with Mistral-7B on one A100, up to 3.7 with Yi-34B on two and up to 5.6 with Falcon-180B in a pipeline. Today it's on by default in the major servers.

**Separating the machines (DistServe, OSDI 2024).** One pool of GPUs only does prefill: it computes the prompt, produces the first token and sends the KV cache. Another pool only does decode. Advantages: no interference, each pool uses the parallelism that suits it and scales with its own demand. The metric is **goodput**: requests per second that meet both the TTFT SLO and the TBT SLO at the same time. They report up to 7.4 times more requests or an SLO 12.6 times tighter. According to its own authors' retrospective, in 2025 disaggregation became the standard in production.

**What it costs to move the KV.** Llama 3 70B takes 320 KiB per token; an 8,000-token prompt is about 2.6 GB. With 800 Gb/s of RDMA (about 100 GB/s), that's 26 ms, against about 400 ms to compute that prefill: on the order of 6%. And Mooncake sends each layer's KV as soon as it's done, overlapped with the following layers, the same trick as DualPipe in Lecture 17.

**The demo** (`go run ./cmd/sim desagregado`), same workload, four replicas:

| Configuration | Meets the SLO | Why |
| --- | --- | --- |
| Colocated | 25% | TBT p99 of 194 ms because of long prefills |
| Colocated, prefill in 512 chunks | 100% | TBT p99 of 60 ms, goodput 7.90 |
| 1 prefill + 3 decode | 25% | prefill can't keep up: TTFT p50 of 22 s |
| 2 prefill + 2 decode | 62% |  |
| 3 prefill + 1 decode | 8% | decode saturates: TBT p99 of 244 ms |

**The honest part.** With this cost model and four replicas, chunked prefill wins. What the model doesn't capture is DistServe's advantage at scale: each pool with its own parallelism and hardware, scaling separately. Disaggregating trades an interference problem for a **sizing** problem, and that sizing has to be dynamic: with agents and documents, prompts grow; with reasoning models, decode grows. In Kubernetes it's one HorizontalPodAutoscaler per pool, with the prefill queue or KV cache usage as the metric instead of CPU.

## 6. Mooncake

Mooncake brings together the lecture's two ideas, a shared prefix cache and disaggregation, around a distributed KV cache pool (figure 1 and §3).

**The pieces.**

- **Conductor:** the global scheduler. For each request it picks a prefill instance and a decode instance by looking at where the KV cache is and how loaded each one is.
- **Prefill and decode pools:** separate groups of GPU machines.
- **KV cache pool:** not separate machines, but the DRAM and SSDs of the same GPU machines, organized in blocks.
- **Messenger:** a component on each node that moves the KV cache with GPUDirect RDMA.

**The flow of a request.**

1. The chosen prefill instance fetches from the pool the KV cache for the prefix that already exists.
2. It computes only the rest, in chunks and pipelined if it's long.
3. It sends the resulting KV cache to the decode node layer by layer, while it computes.
4. The request enters decode's continuous batching, which can still reject it if it wouldn't meet the TBT SLO.

**Very long prompts: chunked pipeline parallelism (CPP).** With hundreds of thousands of tokens, a prefill on a single machine breaks the TTFT SLO. Mooncake groups X prefill nodes and splits the prompt into chunks; each chunk runs on a different stage at the same time, in a pipeline. Tensor parallelism across nodes would do two all-reduces per layer over RDMA, and sequence parallelism would communicate at least once per layer; the pipeline only communicates at stage boundaries. It's the reasoning from Lecture 17: whatever communicates least is what crosses the network.

**Overload: whom not to serve.** Kimi had more demand than GPUs. If a request is going to finish outside the SLO, the compute spent on it is wasted; the worst case is doing the prefill and having decode reject it. With **early rejection**, the Conductor rejects on arrival if the load can't take it. But decode only gets loaded once prefill finishes, so the rejection looks at stale load, and prefill and decode oscillate out of phase (figure 9). The fix is to **predict** decode load: with the trace at double speed on 8 + 8 machines, rejections drop from 4,183 to 3,589. It's control with delayed feedback, like TCP congestion control.

**Results** (FAST version). In Kimi's real deployment, Mooncake serves 115% more requests on the A800 clusters and 107% more on the H800 clusters than the previous system. In experiments, effective capacity (requests that meet the SLO) goes up between 59% and 498% depending on the scenario. It runs on thousands of nodes and processes more than 100 billion tokens per day. The production and capacity results are from the FAST version; the overload section, the trace and the cache statistics are only in the extended arXiv version (v4), and we cite them with its numbering (§6.1, §7, figure 9).

## 7. The frontier

**Serving a mixture-of-experts model: DeepSeek.** In February 2025 DeepSeek published its inference system for V3 and R1. Prefill and decode are separate: in prefill each unit is 4 nodes (32 GPUs) with **EP32**; in decode, 18 nodes (144 GPUs) with **EP144**, 2 routed experts and one shared expert per GPU. Why so large? Each token activates 8 of 256 experts; for each expert to multiply efficiently it needs many tokens, meaning a huge global batch, and spreading the experts over more GPUs means each one reads fewer weights, which is what limits decode. As with DualPipe in training, they overlap communication and compute: two alternating microbatches in prefill, attention split into a 5-stage pipeline in decode.

**One day at DeepSeek** (February 27 to 28, 2025):

| Metric | Value |
| --- | --- |
| Nodes of 8 H800s | 226.75 on average, peak of 278 |
| Input tokens | 608 billion, 56.3% from the on-disk cache |
| Output tokens | 168 billion |
| Per prefill node | \~73,700 tokens/s (with cache hits) |
| Per decode node | \~14,800 tokens/s |
| Per user | 20 to 22 tokens/s |

The back-of-the-envelope math: 14,800 / 21 ≈ 700 users generating at once per decode node. The report computes a theoretical margin of 545% if everything were billed at R1's rate, and clarifies that actual revenue is much lower.

**Speculative decoding** (Leviathan et al., ICML 2023). A small model proposes k tokens; the large one verifies all k in a single pass, accepts the first ones that match and puts its own at the first one that doesn't. The result has exactly the same distribution as the large model alone (with greedy decoding, the same text). It pays off because decode is bound by reading the weights: a pass over k+1 tokens costs almost the same as one over a single token. If each token is accepted with probability α:

> tokens per pass = (1 − α^(k+1)) / (1 − α), cost = k·c + 1

where c is the cost of the draft relative to one pass of the large model. With α = 0.8, k = 4 and c = 0.05: 3.36 tokens per 1.2 passes, about 2.8 times faster (`go run ./cmd/sim especulativo`). With low α, proposing 8 is worse than 4. Today the draft is usually a small head on top of the same model (EAGLE), and DeepSeek-V3 trains a multi-token prediction (MTP) module that serves this purpose.

**A smaller KV cache.** Since the KV cache decides almost everything, architectures changed so it takes less space:

- **Grouped-query attention:** Llama 3 70B has 64 query heads and only 8 key and value heads: 320 KiB per token instead of 2.5 MiB.
- **Multi-head latent attention (MLA):** stores a compressed latent vector and reconstructs keys and values at compute time. DeepSeek-V2 reports 93.3% less KV cache than its 67B dense model.
- **Quantizing the KV cache** to 8 bits or fewer.

Every byte saved per token is multiplied three times: more sequences in the batch, more prefixes in each cache tier, less to transfer from prefill to decode. It's the same argument as FP8 in training.

**What about the labs?** DeepSeek published its full system and Moonshot published Mooncake. From Anthropic, what's public is the September 2025 postmortem: they serve Claude on Trainium, NVIDIA GPUs and TPUs, with pools separated by context length and sticky routing. Google and OpenAI have published little about how they serve. Everything in this lecture is open source: vLLM and SGLang have prefix caching, chunked prefill and disaggregation; llm-d and Dynamo orchestrate them in a cluster.

## 8. Demo, questions and readings

**The repository.** `servir-tokens` is the same engine from Lecture 18, now with a prefix cache, chunked prefill and several replicas behind a router, all in virtual time. New packages: `prefix` (chained hashes and LRU) and `cluster` (routers and disaggregation).

| Command | What it shows |
| --- | --- |
| `go run ./cmd/sim router` | the router and the prefix cache |
| `go run ./cmd/sim desagregado` | colocated, chunked or separated |
| `go run ./cmd/sim especulativo` | speculative decoding |
| `go test ./...` | the tests for what the lecture claims |

The tests check that the prefix-aware router reuses more and has a better p99 than round robin, that sticky has a worse tail, that the shared pool increases reuse, that chunked prefill keeps TBT under the SLO and that the disaggregated setup delivers all tokens with lower TBT than the colocated one. The *Inference cluster* simulator lets you change the router, the cache and the number of prefill replicas in the browser.

Exercises from the README: sharing physical blocks between sequences with the same prefix, early rejection, hot-spot replication like Mooncake's, and an adaptive prefill-to-decode ratio.

**Review questions.**

1. Why can a block only be reused if everything before it is the same? How does the chained hash guarantee it? *A token's keys and values depend on all the previous ones. Block i's hash includes block i−1's, so if it matches at i, the whole prefix matches.*
2. What does the prefix-aware router have that round robin and sticky don't? *It estimates TTFT on each replica by combining cache and queue: it goes where the prefix is unless that replica is loaded. Round robin ignores the cache; sticky ignores load.*
3. An 8,000-token prompt in a batch of decodes: what does the user who was already reading see? *The text stalls for about 400 ms. Sarathi splits the prefill into fixed chunks per iteration.*
4. Why, with prefill and decode separated, does the ratio have to track the load? *Each pool has fixed capacity: if there's more prefill than it can handle, TTFT blows up even if decode is idle, and vice versa.*
5. Why does verifying k proposed tokens cost almost the same as generating one? *Decode is bound by reading the weights: a pass over k+1 tokens reads them only once.*

**Readings.**

- Qin et al., [Mooncake: Trading More Storage for Less Computation — A KVCache-centric Architecture for Serving LLM Chatbot](https://www.usenix.org/conference/fast25/presentation/qin), FAST 2025. This is the lecture's paper.
- Zhong et al., [DistServe](https://arxiv.org/abs/2401.09670), OSDI 2024.
- Agrawal et al., [Sarathi-Serve](https://arxiv.org/abs/2403.02310), OSDI 2024.
- DeepSeek, [Day 6: One More Thing, DeepSeek-V3/R1 Inference System Overview](https://github.com/deepseek-ai/open-infra-index), 2025.
- Leviathan et al., [Fast Inference from Transformers via Speculative Decoding](https://arxiv.org/abs/2211.17192), ICML 2023.
- Zheng et al., [SGLang](https://arxiv.org/abs/2312.07104) (RadixAttention), 2024.
- DeepSeek-AI, [DeepSeek-V2](https://arxiv.org/abs/2405.04434) (MLA), 2024.
- Anthropic, [A postmortem of three recent issues](https://www.anthropic.com/engineering/a-postmortem-of-three-recent-issues), September 2025.
- [Gateway API Inference Extension](https://gateway-api-inference-extension.sigs.k8s.io/) and [llm-d](https://llm-d.ai/).

**Wrapping up the four lectures.** In 16 and 17 the state was the model, and it was split along dimensions; in 18 and 19 the state is the KV cache, and it gets paged, shared, cached and transferred. The questions are the same: what gets split, what gets communicated, what happens when it fails.

## Run the examples

With Go installed and no dependencies, from the repository root:

```sh
cd repos/servir-tokens
go run ./cmd/sim router
go run ./cmd/sim desagregado
go run ./cmd/sim especulativo
```
