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 Design overview.

Implementation notes live in the per-policy docs and the policy data structures.

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 This Doc Is Organized

Quick guidance and a simple decision flow
Policy catalog (with implemented vs roadmap separation)
Practical tradeoffs and rules of thumb

How To Choose (Quick Guidance)

These recommendations mirror the latest benchmark guide in Benchmarks. Results depend on workload shape, cache size, and access distribution.

Pick based on workload first:

Strong temporal locality + low latency: LRU or Clock (fastest in benchmarks).
One-hit-wonder dominated / scan-heavy: S3-FIFO or Heap-LFU; LRU-K or 2Q for mixed scans + reuses.
Frequency matters more than recency (hot keys repeat with long gaps): LFU or Heap-LFU; LRU-K for multi-access signals.
Need low overhead & simple: LRU or Clock (fast ops, minimal metadata); FIFO/Random when simplicity trumps hit rate.
Need adaptive across shifting workloads: S3-FIFO or 2Q.

If you can only implement one “general purpose” policy for mixed workloads, S3-FIFO or LRU are the strongest defaults in current benchmarks, with 2Q as a good alternative when scans are common.

Policy Catalog (Summaries)

Implemented Policies (CacheKit)

Policy	Summary	Doc
LRU	Strong default for temporal locality	LRU doc
MRU	Evicts most recent (niche: cyclic patterns)	MRU doc
SLRU	Segmented LRU with probation/protected	SLRU doc
LFU	Frequency-driven, stable hot sets	LFU doc
Heap-LFU	LFU with heap eviction	Heap-LFU doc
MFU	Evicts highest frequency (niche/baseline)	MFU doc
LRU-K	Scan-resistant recency	LRU-K doc
2Q	Probation + protected queues	2Q doc
ARC	Adaptive recency/frequency balance	ARC doc
CAR	ARC-like with Clock (lower hit overhead)	CAR doc
FIFO	Simple insertion-order (oldest first)	FIFO doc
LIFO	Stack-based (newest first)	LIFO doc
Clock	Approximate LRU	Clock doc
Clock-PRO	Scan-resistant Clock variant	Clock-PRO doc
NRU	Coarse recency tracking	NRU doc
S3-FIFO	Scan-resistant FIFO	S3-FIFO doc
Random	Baseline: uniform random eviction	Random doc

Roadmap Policies (Planned)

See Policy roadmap for upcoming policies (LIRS, GDSF, TinyLFU/W-TinyLFU, etc.).

Implemented Policy Summaries (Short)

LRU: Strong default for temporal locality; fast; scan-vulnerable.
MRU: Opposite of LRU; evicts most recent; only for specific cyclic patterns.
SLRU: Segmented LRU; simple scan resistance via probation/protected segments.
Clock: LRU-like with lower overhead; good for low-latency paths.
NRU: Coarse recency tracking with reference bits; simpler than Clock; O(n) worst-case eviction.
S3-FIFO: Scan-resistant FIFO with ghost history; strong general-purpose choice.
LFU / Heap-LFU: Frequency-driven; stable hot sets; slower to adapt.
MFU: Opposite of LFU; evicts highest frequency; burst detection or baseline comparisons.
LRU-K: Good scan resistance; more metadata per entry.
2Q: Simple scan resistance; requires queue sizing.
ARC: Adaptive recency/frequency balance; no manual tuning; more metadata overhead.
CAR: ARC-like adaptivity with Clock; hits set ref bit only; scan-resistant.
FIFO: Predictable insertion order (oldest first); weak under strong locality.
LIFO: Stack order (newest first); niche use for undo buffers.
Clock-PRO: Scan-resistant Clock variant; more complexity.
Random: Baseline; uniform random eviction; minimal overhead; benchmark reference.

For broader policy taxonomy (OPT, ARC, CAR, LIRS, Random, etc.), use the Policy roadmap and reference material below.

Practical Tradeoffs (What Changes In Real Systems)

Scan resistance: LRU/Clock are vulnerable; S3-FIFO, Heap-LFU, LRU-K, 2Q, ARC, and CAR handle scans better.
Metadata & CPU: Random/FIFO < Clock < LRU < 2Q/SLRU < LRU-K/ARC/CAR/LIRS.
Concurrency: strict global LRU lists can contend; Clock and sharded designs often scale better.
Adaptivity: LFU needs decay to adapt; ARC/CAR adapt 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 need low latency; it is consistently fast in benchmarks.
Prefer Clock when you want LRU-like behavior with lower overhead and similar latency.
For scan-heavy workloads, avoid plain LRU; prefer S3-FIFO or Heap-LFU, with 2Q or LRU-K as alternatives.
Use LFU/Heap-LFU when frequency is predictive and the hot set is stable; expect slower adaptation to shifts.
For shifting patterns, S3-FIFO or 2Q adapts better in benchmarks than frequency-only policies.
Use cost/size-aware policies (GDS/GDSF) when optimizing byte hit rate or miss cost, not just request count.

Quick Decision Flow

Need lowest latency? Start with LRU or Clock.
Scan-heavy workloads? Prefer S3-FIFO or Heap-LFU.
Frequency matters? Use LFU/Heap-LFU or LRU-K.
Shifting patterns? Try S3-FIFO or 2Q.

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.

CacheKit Docs