[RFC]: Explicit Context Caching — Guaranteed KV Cache Eviction Protection

### Changes proposed

# Explicit Context Caching — Guaranteed KV Cache Eviction Protection

## Summary

Introduce a `guaranteed_until` timestamp mechanism in Mooncake Store to implement Explicit Context Caching:

1. **Eviction protection**: Users mark `cache_control: {"type": "ephemeral"}` in `messages`, and the corresponding prefix KV Cache is marked as guaranteed (non-evictable within TTL) in the Store. After expiration, objects automatically degrade to regular objects
2. **Passive expiration**: Uses an absolute `guaranteed_until_` timestamp — BatchEvict naturally skips unexpired objects; expired objects automatically become eviction candidates. Zero new RPCs, crash-safe by design
3. **Zero state on inference engine side**: All guaranteed lifecycle management resides on the Master side. Inference engines (SGLang, vLLM, etc.) do not track or manage guaranteed cache; radix tree nodes require no new fields

## 1. Background and Motivation

### Problem 1: High-Value Prefixes Lack Eviction Protection

Mainstream inference engines (SGLang, vLLM, etc.) reuse KV Cache through prefix matching (RadixAttention / Automatic Prefix Caching). Shared prefixes (system prompts, RAG documents, few-shot examples) are frequently hit. The current eviction strategy in Mooncake Store sorts purely by lease timeout — least recently accessed objects are evicted first. This means:

- Under memory pressure, high-value long prefixes (e.g., a 4K-token system prompt) may be evicted first (because they may not have recent writes)
- After eviction, the next request requires full recomputation, causing P99 latency spikes and GPU compute waste

### Problem 2: OpenAI-Compatible cache_control Semantics Have No Backend Support

The OpenAI API introduced `cache_control: {"type": "ephemeral"}` markers, allowing users to declare "this prefix is important, don't evict it" in message content blocks. Frontend frameworks (e.g., LangChain, VLLM) widely support this semantic, but Mooncake Store has no corresponding eviction protection mechanism, rendering the marker effectively inert.

### Problem 3: Design Gap Between Explicit and Implicit Caching

Alibaba Bailian adopts a standalone CacheIndex + 20-block lookback window approach (multi-tenant cloud service), but this introduces a complex indexing system and inference-engine-side lifecycle management. For single-cluster self-deployment scenarios, we need a lighter approach.

**Goals**: Provide deterministic eviction protection (hard guarantee) for prefixes marked with `cache_control`. After TTL expiry, objects automatically degrade to regular objects. Zero new state on inference engine side. Zero regression risk.

## 2. Core Design

### Tiered Architecture

| Tier | Location | Role in Explicit Caching | Guarantee Level |
|------|----------|-------------------------|-----------------|
| L1 (GPU) | Inference engine Worker (local) | Temporarily held during inference, normal eviction | No guarantee |
| L2 (CPU) | Inference engine Worker (local) | Speedup on same-engine hit (bonus) | No guarantee |
| L3 (Mooncake Store) | Distributed storage | **Deterministic guarantee tier** | Hard guarantee |

L1/L2 do not participate in guarantees: requests may be routed to any engine instance, and L2 is only available on the local instance. Binding guarantees to L2 would require forced routing to a specific instance, breaking load balancing. L3 is shared across all engines, naturally supporting cross-engine reuse.

### Architecture Diagram

```
Client (messages with cache_control markers)
│
▼
┌──────────────────────────────────────┐
│ Inference Engine API Server │
│ - Parse cache_control → token offsets│
└──────────────┬───────────────────────┘
│
▼
┌──────────────────────────────────────┐
│ Inference Engine Worker Instance │
│ ┌──────────────────────────────┐ │
│ │ HiCache Controller (no change)│ │
│ │ - radix tree normal prefix │ │
│ │ matching │ │
│ │ - On write: check cache_ │ │
│ │ control → write_through │ │
│ │ with guaranteed param │ │
│ │ - On read: check cache_ │ │
│ │ control → GetReplicaList │ │
│ │ with guaranteed param │ │
│ └──────────────────────────────┘ │
└──────────┬───────────────────────────┘
│
┌──────────▼───────────────────────────┐
│ Mooncake Store (L3) │
│ - guaranteed_until_ timestamp guard │
│ - BatchEvict skips unexpired objs │
│ - GrantLease auto-renewal │
│ - Guaranteed capacity limit+fallback│
│ - SSD Offload priority protection │
└─────────────────────────────────────┘
```

### Design 1: guaranteed_until_ Timestamp Scheme

Add `guaranteed_until_` (`SteadyClock::time_point`) to `ObjectMetadata`, defaulting to epoch (no guarantee). At PutStart, if `ReplicateConfig.guaranteed_until_ms > 0`, the Master converts it to an absolute timestamp.

**Core semantic**: `guaranteed_until_` unexpired → object is non-evictable (equivalent to hard pinned); expired → automatically degrades to a regular object.

**Why timestamps over reference counting / lease renewal**:

| Approach | New RPCs | Crash recovery | Complexity |
|----------|----------|----------------|------------|
| Reference counting | Requires ReleaseGuaranteed | Must clean residual counts | High |
| Lease renewal | Requires RenewGuaranteed | Depends on TTL patches | Medium |
| **guaranteed_until timestamp** | **Zero** | **Natural expiration, no orphans** | **Low** |

### Design 2: Zero State on Inference Engine Side

Inference engines (SGLang, vLLM, etc.) hold no guaranteed state. All lifecycle management is on the Master side:

- **Write path**: HiCache checks whether the current block falls within `cache_control`-marked token range → if yes, write_through to L3 with `guaranteed_until_ms`
- **Read path**: When a request carries `cache_control`, pass `guaranteed_ttl_ms` in GetReplicaList to renew; when not, don't pass it, and the guaranteed period naturally counts down
- **No new fields on radix tree nodes**

### Design 3: GrantLease Only Renews, Never Creates

`GrantLease` adds a `guaranteed_ttl` parameter, but only renews when the object currently has `guaranteed_until_ > now`. After expiration, even if `guaranteed_ttl > 0` is passed, no new guaranteed period is created. This prevents requests without `cache_control` from accidentally renewing.

### Design 4: Guaranteed Capacity Limit

The Master maintains a `guaranteed_memory_used_` atomic variable. At PutStart, it checks whether `guaranteed_memory_limit_` would be exceeded. If exceeded, returns `GUARANTEED_CAPACITY_EXCEEDED`; the Worker side degrades to a normal PutStart (without guaranteed_until_ms), so writes are never blocked.

### Design 5: SSD Offload Priority Protection

Guaranteed objects have a "must succeed" offload semantic — they cannot be dropped due to a full queue:

| Priority | Object Type | Behavior When Queue Full |
|----------|------------|--------------------------|
| HIGH | guaranteed (`guaranteed_until_ > now`) | Evict LOW objects to make room; must write to SSD |
| NORMAL | soft-pinned | Best-effort, droppable |
| LOW | Regular objects (no pin) | Best-effort, droppable |

### Design 6: BatchExpireGuaranteed for Active Invalidation

Operational scenarios (updated system prompts, incorrect RAG docs) require immediate invalidation without waiting for TTL expiry. A new `BatchExpireGuaranteed` RPC sets `guaranteed_until_` to epoch for all objects matching a `prefix_hash`.

## 3. Backward Compatibility

- `guaranteed_until_ms` defaults to 0 → existing PutStart behavior unchanged
- `guaranteed_until_` defaults to epoch → `IsHardPinned()` returns false → BatchEvict behavior unchanged
- `guaranteed_ttl` defaults to 0 → GrantLease does not modify `guaranteed_until_` → GetReplicaList behavior unchanged

**Zero regression risk.**

## 4. Modified Files Overview

| File | Changes |
|------|---------|
| `mooncake-store/include/replica.h` | Add `guaranteed_until_ms` to `ReplicateConfig` |
| `mooncake-store/include/master_service.h` | Add `guaranteed_until_` to `ObjectMetadata`, timestamp check in `IsHardPinned()`, `guaranteed_ttl` in `GrantLease`, `guaranteed_memory_used_`/`guaranteed_memory_limit_`, `BatchExpireGuaranteed`, `GetOffloadPriority()` |
| `mooncake-store/src/master_service.cpp` | guaranteed_until conversion & capacity check in `AllocateAndInsertMetadata`, guaranteed skip & counter decrement in `BatchEvict`, renew-only logic in `GrantLease`, priority queue in `PushOffloadingQueue`, `BatchExpireGuaranteed` implementation |
| `mooncake-store/include/rpc_types.h` | Add `guaranteed_ttl_ms` to `GetReplicaListRequest`, add `BatchExpireGuaranteedRequest/Response` |
| Inference engine HiCache Controller | Write-back policy awareness of cache_control; pass `guaranteed_ttl_ms` on L3 reads when request has cache_control |
| Inference engine API Server | cache_control parsing → token offsets; `/v1/cache/evict` endpoint |

## 5. Known Limitations and Future Work

| Item | Description |
|------|-------------|
| BatchExpireGuaranteed O(N) scan | Currently scans all shards; can be optimized to O(K) with a prefix index |
| Guaranteed state lost on Master restart | `guaranteed_until_` is not persisted to etcd (consistent with `hard_pinned`); next request rebuilds guaranteed state |
| Guaranteed capacity quota strategy | Currently global total limit; future per-client/namespace quota isolation |

### Before submitting a new issue...

- [ ] Make sure you already searched for relevant issues and read the [documentation](https://kvcache-ai.github.io/Mooncake/)

Start with mooncake-store/include/replica.h, master_service.h, rpc_types.h, and the corresponding master_service.cpp paths listed in the modified-files overview. Trace PutStart, BatchEvict, GrantLease, PushOffloadingQueue, and GetReplicaList before assessing the inference-engine HiCache and API-server integration. Done means the timestamp, renewal, capacity, offload, invalidation, and backward-compatibility semantics work across the proposed interfaces.

Written by the indexing model from the issue text.