cache-policy-comparison

# Overview An eviction policy decides which resident entry a cache removes when a new entry is admitted beyond capacity. Four policies cover almost every replay-and-measure task: | Policy | Data structure | On hit | On admit | Eviction choice | |----------|---------------------------------|------------------------------|--------------------------------------|---------------------------------------------------| | LRU | OrderedDict | Move to tail | Append at tail | Pop head | | LFU | `{key: freq}` + insertion order | `freq[k] += 1` | `freq[k] = 1` | Min `freq`, tiebreak by insertion order | | FIFO | OrderedDict | Nothing | Append at tail | Pop head | | S3FIFO | Three FIFO queues + `freq[k]` | `freq[k] = min(freq+1, cap)` | Admit to small; ghost-hit admits to main | Second-chance on main; small drains to main/ghost | Each has subtleties that trip naive implementations. # LRU Use an `OrderedDict` where the tail is the most-recently-accessed key. On hit, `move_to_end`. On miss + insert, append; pop from head if over capacity. Most common bug: **forgetting to update recency on a hit**. Without the refresh, LRU degenerates to FIFO — hit rate drops substantially on any workload with recency structure. ```python from collections import OrderedDict class LRU: def __init__(self, capacity): self.capacity = capacity self._d = OrderedDict() def contains(self, k): return k in self._d def access(self, k): if k in self._d: self._d.move_to_end(k) else: self._d[k] = None if len(self._d) > self.capacity: self._d.popitem(last=False) ``` # LFU Keep `freq: dict[key, int]` and a tie-breaker — an insertion counter is simplest and deterministic. On hit, increment `freq[k]`. On miss at capacity, evict `min(freq)` with ties broken by insertion order (oldest first). Typical bugs: - **No tie-breaker.** `min(freq.items(), key=lambda x: x[1])[0]` has implementation-defined behaviour across interpreters and distributions. Always include a secondary key. - **Frequency pollution.** A block that was hot once and then went cold can linger forever because its freq is permanently above newcomers. Production systems add aging (periodic decay of freq) or combine with a recency signal (W-TinyLFU). Pure LFU is correct for the task as specified but fragile in practice. # FIFO One queue, insertion order, no hit-time update. Useful as a lower-bound baseline. Do NOT call it "LRU without hit update" — conceptually different even when implementations overlap. Hit on a FIFO cache is still a hit for accounting; the block just does not change rank. # S3FIFO A modern FIFO-family policy (Yang et al., SOSP 2023) that matches or beats LRU on typical web and LLM workloads with a fraction of the bookkeeping cost — which is why recent production systems (Twitter, Google) have been switching to it. The full algorithm — three queues, saturating frequency counter, second-chance eviction on the main queue — is implemented in the `prefix-cache-replay` skill. Consult that skill if your task uses S3FIFO. # Workload implications - Strong **recency** → LRU wins slightly. - Stable **hot set** with long tail (Zipf) → LFU or S3FIFO. - Nearly uniform random → all converge toward `capacity / working_set` hit rate. - **Prefix-shared LLM workloads** are mixed — shared prefixes are both recent and frequent, so LRU/LFU/S3FIFO typically sit within a few percent of each other at the same capacity, but they differ in which blocks remain resident at end-of-trace, and their miss-handling costs diverge. Measure, don't assume. # Comparing hit rates on a trace Replay the same trace through each policy at identical capacity, record `total_hit_tokens / total_prompt_tokens` and the final resident set. Do not compare hit rate alone — also compare: - Final residency — how many unique blocks are resident at the end. Under S3FIFO this is often strictly less than capacity because ghost entries absorb the admission pressure. - Per-request hit-token distribution — two policies can have similar overall hit rate but very different per-request variance. - Admission effort — under policies with ghost structures, the bookkeeping cost per access is non-trivial. # Common mistakes - Reusing an LRU implementation when the task specifies S3FIFO (or vice versa). The final hit rate and residency will both differ; no partial credit for "close enough". - Making ghost count as resident, or treating a ghost hit as a hit for token accounting. - Forgetting to saturate `freq` — unbounded counters turn the main-queue second-chance loop into a spin. - Under LFU, using Python `min(d.items(), key=d.get)` without an explicit insertion-order tiebreaker. - Misordering admission and residency check. Always check `h ∈ cache` BEFORE applying the admission side effects of the current request, otherwise every request self-hits. - Final cache size off by small constants because you forgot to exclude ghost or you forgot to subtract the S-cap vs M-cap split.