Fast on-ssd index speeds key-value cache recovery and matching
SARP: An On-SSD Index for KVCache with Fast Prefix Matching and Recovery
Databases
Summary
Large language models use many small cache blocks to answer questions faster by reusing past information. When the system crashes, recovering these cache blocks is slow and costly. The authors have created SARP, a new way to store an index on solid-state drives that speeds up finding cache blocks and recovering after crashes. SARP uses a clever mix of a small in-memory guide and grouped data on SSD to balance speed and recovery time better than past methods.
What this means in practice
- •For llm infrastructure teams: Improve the speed of recovering and querying key-value caches after crashes in distributed large language model systems.
- •For storage system engineers: Design SSD-based indexing methods that balance fast prefix matching with low recovery times for large-scale caching.
Authors
Jun Kong, Qi Lin, Zhichao Cao
Abstract
Distributed LLM serving relies on a global index to locate reusable key-value cache (KVCache) blocks through prefix matching. Losing the index after a crash or restart forces affected requests to recompute existing KVCache on GPUs. Persisting the index restores access after a failure. Existing persistent indexes face a tension between prefix-matching performance and recovery time. A snapshot-backed in-memory index supports fast prefix matching, but rebuilding the full index delays recovery. An on-SSD index avoids this rebuild, but adds storage accesses to prefix matching. Our core insight is that extending a matched prefix over a short span typically requires distinguishing only a few token sequences, suggesting that sparse in-memory routing state may suffice. Prefix matching also accesses block metadata in sequence order, allowing metadata for consecutive blocks to be retrieved together. We present SARP (Sparse Adaptive Routing and Packing), an on-SSD KVCache index for fast recovery and prefix matching. SARP groups consecutive block IDs and metadata into segments to amortize storage accesses across multiple blocks. A compact in-memory routing directory identifies candidate segments using entries at selected block positions. SARP limits segment retrievals and uses compact filters to prioritize candidates with longer potential matches. After retrieval, SARP verifies block IDs against the query and reuses only KVCache blocks covered by the verified prefix. After a restart, SARP restores the sparse routing directory from a snapshot. Across four multi-turn chat and agentic workloads, SARP recovers 8.0x to 77.5x faster than the in-memory index baselines and delivers 1.15x to 66.6x the request throughput of the on-SSD index baselines, while reusing only 0.0030% to 0.029% fewer tokens than exact prefix matching.