Skip to content

multi-user-cache-lifecycle.md

Latest commit

 

History

History
108 lines (85 loc) · 5.68 KB

multi-user-cache-lifecycle.md

File metadata and controls

108 lines (85 loc) · 5.68 KB
Raw

Multi-User KV Cache: Sharing, Isolation, and the Life of a Block

Fifth doc in the set — edf-floor → prefix-cache → prefill-chunk → decode-step traced ONE request; this one zooms out to many users hitting the assistant at the same time.

The distinction everything hangs on

  • A running sequence's KV state is private — its block table (a list of pointers) belongs to that request alone.
  • The physical block pool + prefix-cache index are worker-global — shared by every user on that GPU. Whether two users share a block is decided purely by bytes: shared iff their token prefixes are byte-identical from position 0.

Result: memory is a tree. One trunk of system-prompt blocks (refcount = number of live conversations), branching into per-conversation chains. Each user pays only for their divergence, never for the trunk.

Content Actually shared with
System prompt / product preamble Everyone on the worker (demo: seq a hit 400 tokens of turn 1's blocks from a different conversation)
A conversation's own history That conversation's future turns only (turn 2 hit 448 of turn 1) — effectively per-session
Unique user content Nobody (demo: seq b, 0 hits)

The state diagram — life of one physical block

stateDiagram-v2
    [*] --> Free: pool initialized

    Free --> Private: allocate()<br/>a growing sequence page-faults<br/>past a block boundary (ref = 1)

    Private --> Cached: sequence retires →<br/>cache.insert() hashes the FULL block,<br/>cache takes its own ref;<br/>sequence releases (ref = 1, cache-owned)
    Private --> Free: partial tail block —<br/>no complete identity, never cached;<br/>release → ref 0

    Cached --> Shared: another request's match()<br/>finds the hash → retain<br/>(ref = 2, 3, ... one per reader)<br/>every hit re-stamps LRU
    Shared --> Cached: readers finish and release<br/>(back to ref = 1)

    Cached --> Evicted_HBM: pool pressure →<br/>evict_lru() picks oldest UNPINNED,<br/>drops the cache's ref only
    Shared --> Evicted_HBM: eviction while still read:<br/>unmapped from the index, but memory<br/>survives until the last reader releases

    state "Demoted (production tiers)" as Demoted {
        DRAM --> NVMe: idle longer /<br/>free tier demotes first
        NVMe --> DRAM: promoted on access
    }

    Evicted_HBM --> Demoted: LMCache tier ladder —<br/>users think for 30s–minutes;<br/>HBM's LRU horizon is SHORTER than<br/>a human's typing pause
    Evicted_HBM --> Free: mini-engine (no tiers):<br/>last ref released → block recycled

    Demoted --> Cached: user's next turn —<br/>match hits, blocks RELOAD to HBM<br/>(bandwidth cost ≪ recompute cost)
    Demoted --> [*]: cold too long → dropped;<br/>next turn pays a cold prefill

    note right of Cached
        PINNED blocks (enterprise / hot
        system prompts) refuse the
        eviction edge entirely —
        a cache miss is a contractual
        risk once TTFT depends on hits
    end note
Loading

Reading the diagram as replenishment policy

  1. Allocate on demand — blocks enter use one page-fault at a time; nothing is reserved for tokens never generated (that headroom is what lets MORE users batch concurrently: max_concurrent ≈ free_HBM / (KV/token × seq_len)).
  2. Every finished request replenishes the cache — retirement is a donation, not a free. Turn N's compute becomes turn N+1's discount.
  3. Active users defend their own blocks — every hit re-stamps LRU, so the conversations being used stay hot without any explicit policy. Idle users' history is exactly what ages out. Self-tuning by construction.
  4. Eviction unmaps; refcounts free — a block being read by a running sequence survives eviction from the index. No user is ever yanked mid-read.
  5. Demotion beats destruction — the HBM→DRAM→NVMe ladder exists because human think-time outlives HBM residency. Reloading 7k tokens of KV is a bandwidth cost; recomputing them is a compute cost. Bandwidth is far cheaper.
  6. Pinning is the SLA hook — enterprise blocks never take the eviction edge for free-tier benefit; free tier demotes to NVMe first (tiering.py).

Isolation — what sharing does and doesn't leak

  • Content: safe by construction. Shared blocks are immutable (decode writes land only in the sequence's OWN tail block), and match() can only return blocks whose exact prefix the requester already sent — you cannot retrieve bytes you couldn't have typed.
  • Timing: the honest caveat. A suspiciously fast prefill reveals that someone previously submitted your exact prefix — a real side-channel class for prefix caches. Mitigation: namespace the cache per tenant with cache_salt (vLLM), trading cross-tenant system-prompt sharing for isolation. This repo's cache_correctness.py uses the same mechanism to force guaranteed-cold comparison runs.

The multi-worker dimension

Everything above is per GPU — worker 0's pool knows nothing of worker 1's. A conversation benefits from its history only by returning to the worker that holds it: that is the session-affinity hash ring's entire job (serving/cache/affinity.py), and the load override is the explicit trade — if the affinity worker is drowning, eat ONE deliberate cold prefill elsewhere, because queueing destroys p99 while a miss merely costs money.

One line to keep

Per-request state is private; physical memory is shared by byte-identical prefix; active users keep their blocks warm by using them; idle users' history slides down the HBM→DRAM→NVMe ladder and climbs back on their next message.