# Cache Replacement Policies
This document summarizes common cache replacement (eviction) policies, their tradeoffs, and when to use (or avoid) each. It’s written as a practical companion to `docs/design.md`.
Implementation notes live in `docs/policies/README.md`.
Terminology used below:
- **Admission**: whether an item is allowed into cache at all (some “policies” combine admission + eviction).
- **Eviction**: which resident item to remove when making space.
- **Scan pollution**: one-time accesses (e.g., large scans) pushing out genuinely hot items.
- **Metadata cost**: extra per-entry memory and CPU needed to maintain the policy.
## How To Choose (Quick Guidance)
Pick based on workload first:
- **Strong temporal locality (hot keys repeat quickly)**: `LRU` / `Clock` usually works.
- **One-hit-wonder dominated / scan-heavy**: prefer scan-resistant policies like `LRU-K`, `2Q`, `ARC`.
- **Frequency matters more than recency** (hot keys repeat but with long gaps): `LFU` (with aging) or hybrids.
- **Need low overhead & simple**: `FIFO`, `Random`, `Clock`.
- **Need adaptive across shifting workloads**: `ARC` (or related adaptive policies).
If you can only implement one “general purpose” policy for mixed workloads, `ARC`-style adaptivity or `LRU-K`/`2Q`-style scan resistance usually beats plain `LRU`, at the cost of more metadata and complexity.
## Policy Catalog (Summaries)
### OPT / MIN (Belady’s Optimal)
**Idea**: evict the item whose *next* use is farthest in the future.
- **Pros**: best possible hit rate for a known future; gold-standard for evaluation.
- **Cons**: requires knowing the future; not implementable in real systems (except offline traces/simulators).
- **Use when**: benchmarking and comparing other policies on recorded traces.
- **Avoid when**: building a real cache.
### Random
**Idea**: evict a uniformly random resident item.
- **Pros**: trivial; very low overhead; surprisingly decent under some adversarial patterns.
- **Cons**: ignores locality; unstable hit rate; can evict hot items.
- **Use when**: you need the simplest possible eviction with constant overhead.
- **Avoid when**: locality exists and you can afford minimal tracking.
### FIFO (First-In, First-Out)
**Idea**: evict the oldest inserted item.
- **Pros**: simple; O(1); predictable; low metadata.
- **Cons**: ignores reuse; can be very poor when early inserts stay hot.
- **Use when**: insert order correlates with staleness (e.g., streaming-ish workloads), or you want predictability.
- **Avoid when**: strong temporal locality; “old but hot” keys are common.
### LIFO / FILO (Last-In, First-Out)
**Idea**: evict the most recently inserted item.
- **Pros**: can work for some cyclic/scan-like patterns where newest items are least likely to be reused.
- **Cons**: counterproductive under temporal locality; uncommon in general-purpose caches.
- **Use when**: you have evidence newest items are least reusable.
- **Avoid when**: typical request caches with recency locality.
### LRU (Least Recently Used)
**Idea**: evict the item not accessed for the longest time.
- **Pros**: strong default for temporal locality; intuitive; stable.
- **Cons**: vulnerable to scan pollution; maintaining exact LRU can be costly under high concurrency.
- **Use when**: workloads have strong recency locality; you can tolerate metadata and updates on every access.
- **Avoid when**: large sequential scans are common; cache is highly contended and strict ordering is too expensive.
### MRU (Most Recently Used)
**Idea**: evict the most recently accessed item.
- **Pros**: can outperform LRU for some “looping scan” patterns where the just-touched item won’t be reused soon.
- **Cons**: performs poorly for typical temporal locality.
- **Use when**: known cyclic access where the most-recently-used item is least likely to be reused next.
- **Avoid when**: you’re unsure; MRU is rarely a safe default.
### Second-Chance / Clock
**Idea**: approximate LRU using a circular list and a referenced bit; give items a “second chance”.
- **Pros**: O(1) amortized; lower overhead than strict LRU; good concurrency properties in practice.
- **Cons**: approximation quality depends on implementation; still suffers from scan pollution in many forms.
- **Use when**: you want LRU-like behavior with cheaper metadata and fewer writes.
- **Avoid when**: you specifically need scan resistance or frequency awareness.
### NRU (Not Recently Used)
**Idea**: evict an item whose “referenced” bit is not set; bits are periodically cleared (epochs).
- **Pros**: very low overhead; works well when you can batch/reset reference bits cheaply.
- **Cons**: coarse recency signal; behavior depends heavily on epoch length.
- **Use when**: you already have hardware/software reference bits or can cheaply track “touched this epoch”.
- **Avoid when**: you need tight recency ordering.
### LFU (Least Frequently Used)
**Idea**: evict the item with the smallest access count.
- **Pros**: strong when popularity is stable and skewed; resists scan pollution better than LRU.
- **Cons**: “cache pollution by history” (once-hot items stick around); needs **aging/decay** to adapt; counters add overhead.
- **Use when**: hot items remain hot for long periods; frequency is the primary predictor.
- **Avoid when**: the hot set shifts quickly; you can’t implement decay/aging safely.
### MFU (Most Frequently Used)
**Idea**: evict the most frequently used item.
- **Pros**: can work in specific “burst then never again” patterns (items that were heavily used are now “done”).
- **Cons**: usually the opposite of what you want; not a general-purpose choice.
- **Use when**: you have evidence “most frequent so far” implies “least likely to be reused now”.
- **Avoid when**: almost always.
### Aging / Decayed LFU (LFU with time decay)
**Idea**: combine frequency with time so old counts lose influence (e.g., periodic halving, exponential decay).
- **Pros**: avoids LFU’s “stale hot” problem; adapts to changing popularity.
- **Cons**: more complexity; decay schedule can be tricky; still more metadata than LRU/Clock.
- **Use when**: you want frequency but with adaptivity to phase changes.
- **Avoid when**: extremely latency-sensitive hot paths where counter maintenance dominates.
### LRU-K
**Idea**: evict based on the K-th most recent access time (e.g., `K=2` tracks the 2nd most recent touch).
- **Pros**: filters one-time accesses; much more scan-resistant than LRU.
- **Cons**: more metadata per entry; more expensive updates; needs careful implementation to stay O(1) in practice.
- **Use when**: mixed point-lookups + scans; DB buffer pools; workloads with many one-hit-wonders.
- **Avoid when**: you need the simplest possible policy or can’t afford per-entry history.
### 2Q
**Idea**: use two queues: a short “probation” FIFO for new items and a main LRU for items that are accessed again.
- **Pros**: simple scan resistance; cheaper than LRU-K; widely used pattern.
- **Cons**: requires tuning queue sizes; still mainly recency-based once admitted to main queue.
- **Use when**: you want an easy scan-resistant upgrade over LRU.
- **Avoid when**: you can’t tolerate tuning knobs or workload changes dramatically.
### SLRU (Segmented LRU)
**Idea**: split LRU into segments (e.g., probationary + protected); promotion requires reuse.
- **Pros**: reduces scan pollution; simple; common in practice.
- **Cons**: needs segment sizing; not as adaptive as ARC-style approaches.
- **Use when**: you want low-complexity scan resistance with LRU semantics.
- **Avoid when**: workload shifts require continual retuning.
### ARC (Adaptive Replacement Cache)
**Idea**: adaptively balances recency vs frequency using two LRU lists plus “ghost” history lists to tune itself.
- **Pros**: strong across many workloads; self-tuning between scan resistance and frequency-ish behavior.
- **Cons**: more complex; more metadata (including ghost entries); harder to implement lock-efficiently.
- **Use when**: you need robust performance across shifting patterns and can afford complexity.
- **Avoid when**: memory overhead must be minimal or implementation complexity is a hard constraint.
### CAR (Clock with Adaptive Replacement)
**Idea**: ARC-like adaptivity but with Clock structures to reduce overhead.
- **Pros**: retains ARC’s adaptivity with lower overhead in some implementations.
- **Cons**: still complex; behavior depends on details.
- **Use when**: you want ARC-like behavior but prefer Clock-style mechanics.
- **Avoid when**: you need simplicity or have no room for ghost/history metadata.
### LIRS (Low Inter-reference Recency Set)
**Idea**: use inter-reference recency (distance between repeated touches) to classify and protect frequently reused items.
- **Pros**: excellent scan resistance in many workloads; strong theoretical grounding.
- **Cons**: implementation complexity; metadata overhead; harder to explain/debug than LRU variants.
- **Use when**: you can invest in a high-quality scan-resistant policy for DB-like workloads.
- **Avoid when**: you need a small, simple policy surface.
### CLOCK-Pro
**Idea**: Clock-based policy that differentiates hot/cold pages and tracks recent history to handle scans better than Clock.
- **Pros**: good scan resistance with Clock mechanics; practical for OS/DB buffer caches.
- **Cons**: more complex than Clock; tuning/implementation details matter.
- **Use when**: you want better-than-Clock scan handling without full ARC machinery.
- **Avoid when**: you want the simplest possible eviction logic.
### Size/Cost-Aware Policies (GDS / GDSF family)
**Idea**: evict based on a “value” score that accounts for retrieval cost and/or object size (common in web caches).
- **Pros**: optimizes for byte hit rate or cost-weighted hit rate; better than LRU when object sizes vary widely.
- **Cons**: more bookkeeping; needs cost/size signals; can be less intuitive.
- **Use when**: objects have large size variance; misses have heterogeneous cost (e.g., network fetch cost).
- **Avoid when**: costs are uniform and you only care about request hit rate.
### TTL / Time-Based Expiration (Not a Replacement Policy)
**Idea**: entries expire after a time-to-live, regardless of recency/frequency.
- **Pros**: bounds staleness; essential for correctness in many domains.
- **Cons**: does not optimize hit rate by itself; still needs an eviction policy when full.
- **Use when**: correctness requires freshness bounds (configs, tokens, CDN-like caching).
- **Avoid when**: you treat TTL as a substitute for eviction optimization.
## Practical Tradeoffs (What Changes In Real Systems)
- **Scan resistance**: `LRU`/`Clock` are vulnerable; `LRU-K`/`2Q`/`ARC`/`LIRS` handle scans better.
- **Metadata & CPU**: `Random`/`FIFO` < `Clock` < `LRU` < `2Q`/`SLRU` < `LRU-K`/`ARC`/`LIRS`.
- **Concurrency**: strict global `LRU` lists can contend; `Clock` and sharded designs often scale better.
- **Adaptivity**: `LFU` needs decay to adapt; `ARC`-family adapts via history; static partitions (`2Q`/`SLRU`) need tuning.
- **Predictability**: simpler policies are easier to reason about under tail-latency constraints; complex policies can have more edge cases.
## When To Use / Not Use (Rules Of Thumb)
- Use `LRU` when you have **temporal locality** and can tolerate per-hit metadata updates.
- Prefer `Clock` when you want **LRU-like** behavior with **lower overhead**.
- Avoid plain `LRU` for workloads with **large scans** unless you add scan resistance (e.g., `2Q`, `SLRU`, `LRU-K`).
- Use `LFU` (with aging) when **popularity is stable** and you care about long-term hot items.
- Use `ARC` when workload is **mixed or shifting** and you can afford the complexity and memory overhead.
- Use cost/size-aware policies (GDS/GDSF) when optimizing **byte hit rate** or **miss cost**, not just request count.
## Reference Material
- Wikipedia: Cache replacement policies: https://en.wikipedia.org/wiki/Cache_replacement_policies
- LRU-K: “The LRU-K page replacement algorithm for database disk buffering” (O’Neil, O’Neil, Weikum), 1993.
- 2Q: “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm” (Johnson, Shasha), 1994.
- ARC: “ARC: A Self-Tuning, Low Overhead Replacement Cache” (Megiddo, Modha), 2003.
- LIRS: “LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance” (Jiang, Zhang), 2002.
- OPT (Belady): “A study of replacement algorithms for a virtual-storage computer” (Belady), 1966.
- GDS/GDSF: “GreedyDual-Size: An algorithm for web caching” (Cao, Irani), 1997.