Distributed KV Cache — infra.bea.ai

At cluster scale with multiple serving instances, each instance maintains its own KV cache — leading to redundant prefill of common prefixes. Distributed KV cache enables cross-instance sharing, turning prefix caching from a per-instance optimization into a cluster-wide one.

1. The Redundancy Problem at Scale

With $N$ independent vLLM instances serving the same model:

Instance 0: caches "System prompt A" → serves users 0-99
Instance 1: caches "System prompt A" → serves users 100-199  (REDUNDANT!)
Instance 2: caches "System prompt A" → serves users 200-299  (REDUNDANT!)
...

Without coordination, every instance independently prefills the same system prompt. With 100 requests/second and 10 instances: 10× redundant prefill of the same tokens.

The fix requires two capabilities:

Shared KV storage: A place where KV cache computed by one instance is accessible to others
Cache-aware routing: Direct requests to the instance most likely to have the relevant KV cached

2. Architecture

┌─────────────────────────────────────────────────┐
│  Router (cache-aware)                           │
│  Maintains: prefix → instance mapping           │
│  Routes: new request → instance with best match │
├─────────────────────────────────────────────────┤
│  Global KV Index                                │
│  Hash table: token_hash → {instance, blocks}    │
│  Updated on: prefill completion, eviction        │
├──────────┬──────────┬──────────┬────────────────┤
│ Instance │ Instance │ Instance │   Shared KV    │
│    0     │    1     │    2     │   Store        │
│ (local)  │ (local)  │ (local)  │ (CPU/disk/     │
│          │          │          │  network)      │
└──────────┴──────────┴──────────┴────────────────┘

3. Cache-Affinity Routing

Distributed KV Routing

The router’s most important job: send requests to the instance that already has their prefix cached.

def route_request(request, instances, kv_index):
    prefix_hash = hash(request.prompt[:system_prompt_length])
    
    # Find instances with this prefix cached
    cached_on = kv_index.lookup(prefix_hash)
    
    if cached_on:
        # Route to least-loaded instance that has the cache
        target = min(cached_on, key=lambda i: i.queue_depth)
    else:
        # No cache hit — route to least-loaded instance
        target = min(instances, key=lambda i: i.queue_depth)
    
    return target

Impact of Cache-Affinity Routing

Routing strategy	Cache hit rate	Throughput relative to random
Random (round-robin)	$1/N$ per instance	1×
Cache-affinity	80-95%	2-3×
Cache-affinity + load-aware	75-90%	2.5-3.5×

llm-d reports 3× higher throughput and 2× faster TTFT with prefix-cache-aware routing vs round-robin on Llama-3.1 70B.

4. Distributed KV Storage Options

Storage	Bandwidth	Latency	Capacity	Use case
GPU HBM (local)	3,350 GB/s	ns	80-192 GB	Hot cache (current requests)
CPU DRAM (local)	64 GB/s	μs	512-2TB	Warm cache (recent evictions)
Remote GPU (RDMA)	50 GB/s	μs	Other instance’s HBM	Cross-instance sharing
Distributed store	10-50 GB/s	ms	Unlimited	Persistent, cluster-wide

LMCache Approach

Tiered storage within each node, with a shared remote tier:

Request arrives → check local GPU cache → check local CPU → check remote store → prefill

Mooncake Approach

Centralized distributed store with RDMA transfer:

Request arrives → router checks global index → if cached on another instance:
  Transfer KV via RDMA (25-50ms for 4K context) vs full prefill (50-100ms)

5. Consistency and Eviction

Consistency Model

KV cache is immutable once written (the same token sequence always produces the same KV). This simplifies consistency — no need for write locks or invalidation. The only operations are:

Write: After prefill, register KV blocks in the global index
Read: On cache hit, read KV blocks (local or remote)
Evict: When memory pressure rises, remove entries from index + storage

Eviction Strategy

# Global LRU eviction
# When any instance runs low on memory:
# 1. Evict least-recently-used entries from local GPU cache → move to CPU
# 2. If CPU full → move to remote store or discard
# 3. Update global index to reflect new location (or removal)

# Eviction priority: unique prefixes > shared prefixes
# (shared prefixes are more likely to be needed again)

6. When Distributed KV Cache Matters

Scenario	Benefit	Why
Many instances, shared system prompts	High	Eliminate $N\times$ redundant prefill
RAG with repeated documents	High	Document KV reused across queries
Multi-turn chat	Medium	Session KV shared across turns (already handled per-instance)
All unique prompts	None	No sharing opportunity
Single instance	None	Already has its own prefix cache

For the systems implementing distributed KV, see LMCache & Mooncake and llm-d.

Self-Check

Explain the redundant prefill problem with multiple independent instances
Describe cache-affinity routing and its throughput impact
Compare distributed KV storage options (local GPU/CPU, remote RDMA, distributed store)
Explain why KV cache immutability simplifies consistency
Design an eviction strategy for a distributed KV store
Identify workloads where distributed KV cache provides the most benefit