Wait, What?
A cache miss does not only ask “what should we load?” It may also force a harder question: “what should we throw away?”
Cache-replacement algorithms decide which resident item should be evicted when space is limited. The problem appears in operating systems, databases, storage systems, processors, web caches and distributed services. It looks simple until the future matters: the perfect decision depends on what will be accessed next, which an online algorithm does not know.
That makes cache replacement an excellent learning topic because it connects data structures, online algorithms, locality, workload distributions, adversarial traces, approximation, hardware constraints and systems measurement.
Quick Answer
Learn cache replacement through the route hits and misses → finite capacity → FIFO → optimal offline replacement → recency → LRU → implementation cost → second chance → CLOCK → frequency and scan resistance → working sets → ARC → multi-generation reclaim → trace simulation → miss-ratio curves → production measurement. A beginner should be able to simulate a short reference string by hand. A professional should be able to explain why a policy performs well or badly on a workload, estimate its metadata and runtime cost, recognise pathological traces and validate claims with representative measurements.
1. Define the Cache Before the Policy
A cache stores a limited subset of a larger addressable universe because the cached location is faster or cheaper to access. Replacement becomes necessary when a new item must enter a full cache.
Before comparing policies, state the unit being cached, the cache capacity, what counts as an access, whether writes matter and what a miss costs. Otherwise two experiments may be measuring different systems.
2. Start With a Reference String
Use a tiny cache of three frames and an access sequence such as A, B, C, A, D, B, E. For every access, record hit or miss, cache contents and the eviction decision. This trace is the equivalent of a worked example for replacement policy.
3. FIFO Is Simple Because It Ignores Usage
First-In, First-Out evicts the item that entered earliest. It needs queue order but does not care whether an old item was accessed one microsecond ago. Its simplicity makes it useful pedagogically, even though age-of-entry is often a weak predictor of future reuse.
4. Belady’s Optimal Policy Gives an Unreachable Benchmark
The optimal offline replacement policy evicts the item whose next use is furthest in the future. It cannot be implemented online without knowing future accesses, but it gives a lower bound on misses for a known trace.
This teaches an important analytical distinction: an algorithm can be impossible to deploy and still be extremely useful as a benchmark.
5. Locality Explains Why Recency Can Work
Programs and workloads often show temporal locality: recently accessed items are more likely to be accessed again soon. LRU converts that empirical regularity into a policy—evict the least recently used item.
6. LRU Needs More Than a Definition
Exact LRU requires maintaining access order. In a software cache this may mean a hash table plus a doubly linked list, or another structure that supports lookup and recency updates. In virtual-memory systems, exact recency tracking can be too expensive, motivating approximations.
The existing How to Learn Hash Tables article owns generic constant-time lookup reasoning. Cache replacement adds per-access metadata maintenance and eviction order.
7. A Better Hit Ratio Can Still Lose Overall
A replacement policy with fewer misses may perform worse if it requires much more CPU time, locking, metadata memory or write traffic. Professional evaluation therefore measures total cost, not miss ratio in isolation.
8. Second-Chance Policies Approximate Recency
Second-chance algorithms keep a simple order but give recently referenced items another opportunity before eviction. A reference bit records whether an item has been used since the policy last inspected it.
9. CLOCK Makes Second Chance Efficient
CLOCK arranges frames conceptually in a ring. A moving hand inspects reference bits: if a candidate has been used, clear its bit and advance; if not, choose it for eviction. This avoids maintaining a perfectly ordered LRU list while still approximating recency.
Operating Systems: Three Easy Pieces — Beyond Physical Memory: Policies provides a clear treatment of optimal replacement, FIFO, LRU approximations and CLOCK-style policies.
10. The Working Set Is More Important Than the Cache Size Alone
If the actively reused set of pages exceeds available memory, replacement can become constant churn. Adding clever eviction logic cannot fully repair a capacity mismatch between the working set and the cache.
11. Thrashing Is a Systems Failure, Not Just a Bad Eviction
When the system repeatedly evicts pages that are needed again almost immediately, useful work is overwhelmed by misses, faults and data movement. The algorithm has entered a workload regime where replacement decisions dominate execution.
12. Sequential Scans Can Pollute Recency-Based Caches
A one-time scan through a dataset larger than the cache can push genuinely hot items out of a naïve recency list. When the scan finishes, the cache may contain mostly items that will never be touched again.
This motivates scan-resistant policies and is a good counterexample to the rule “recently used always means likely to be useful again.”
13. Frequency and Recency Capture Different Signals
Recency asks how long since the last access. Frequency asks how often an item has been used. Some workloads reward one signal more than the other. A robust policy may need to adapt rather than commit permanently to a fixed balance.
14. ARC Adapts Between Recency and Frequency
Adaptive Replacement Cache maintains information about recently and frequently used items and adapts the balance between them as the workload changes. Its design was motivated partly by the weakness of fixed policies under changing traces and scans.
The original IBM Research paper describes ARC as self-tuning, scan-resistant and constant-time per request in its design. See ARC: A self-tuning, low overhead replacement cache.
15. Ghost History Can Be Useful Even After Data Is Gone
Adaptive policies may remember metadata about recently evicted items without retaining their full contents. If an evicted key is requested again quickly, that history provides evidence that the policy may have allocated too little space to one behaviour class.
16. Page Replacement Is an Online-Algorithm Problem
The policy must act before the future reference sequence is known. This connects directly to the existing How to Learn Online Algorithms article. Cache replacement supplies a concrete systems setting where uncertainty about the future is unavoidable.
17. More Cache Does Not Make Every Policy Monotonically Better
Some replacement algorithms can exhibit anomalies where increasing the number of frames increases misses for a particular reference string. FIFO’s classic Belady anomaly is valuable because it destroys the intuition that “more memory must always reduce misses” for every policy.
18. Stack Algorithms Have a Useful Inclusion Property
For stack algorithms such as idealised LRU, the set of items held with capacity k is contained within the set held with capacity k+1 for the same trace. This structural property prevents Belady’s anomaly and gives a deeper reason than empirical observation.
19. Modern Operating Systems Use Richer Reclaim Machinery
Production kernels must balance anonymous memory, file-backed pages, cgroups, aging cost, reclaim cost and latency under pressure. Linux’s Multi-Gen LRU, for example, organises pages into generations and uses access recency information for reclaim and working-set estimation.
See the current Linux Multi-Gen LRU documentation for a real modern page-reclaim design rather than a classroom-only policy.
20. A Cache Policy Should Be Tested on Traces With Different Shapes
Useful traces include looping working sets, one-time scans, bursts, phase changes, Zipf-like popularity, mixed hot/cold items and adversarial sequences. A policy that wins one trace can lose badly on another.
21. Miss-Ratio Curves Reveal More Than One Cache Size
A miss-ratio curve plots miss rate against cache capacity. It helps distinguish a genuinely strong policy from one that happened to look good at a single arbitrary size. It also helps capacity planning: sometimes doubling cache size barely changes misses; sometimes a small increase crosses the working-set knee.
22. Tail Latency Can Matter More Than Average Hit Rate
In storage or service caches, misses may trigger expensive remote or disk operations. A small change in miss behaviour can create large changes in high-percentile latency. Benchmarking should therefore track latency distribution as well as aggregate hit ratio.
23. Concurrency Changes the Implementation Cost
A global LRU list updated on every access can become a contention point. Sharding, approximate recency, batched updates or lock-free metadata can trade policy precision for throughput. The best theoretical replacement rule may be the wrong production design if maintaining it serialises the system.
24. Common Learning Failure States
- Comparing policies without fixing the cache capacity and reference trace.
- Confusing insertion age with recency of use.
- Assuming LRU is always optimal because locality often exists.
- Ignoring the metadata and CPU cost of exact recency tracking.
- Using hit ratio as the only performance metric.
- Testing only random accesses and missing scan pollution.
- Assuming more cache frames reduce misses for every policy.
- Forgetting dirty-page writeback cost.
- Ignoring multi-tenant or cgroup pressure in real operating systems.
- Calling a policy “adaptive” without specifying what signal changes its behaviour.
25. A Beginner-to-Professional Learning Ladder
- Level 1: simulate FIFO on a seven-access trace.
- Level 2: compare FIFO with optimal offline replacement.
- Level 3: hand-trace LRU and explain the locality assumption.
- Level 4: implement an LRU cache with bounded capacity.
- Level 5: implement CLOCK and compare metadata cost.
- Level 6: construct traces that defeat naïve recency.
- Level 7: study ARC and scan resistance.
- Level 8: generate miss-ratio curves across multiple capacities.
- Level 9: inspect a modern OS reclaim design such as Multi-Gen LRU.
- Level 10: evaluate a production cache using hit rate, latency, metadata overhead, contention, write cost and workload phase changes.
26. Teach With Competing Traces, Not One Definition at a Time
Give two policies the same trace and ask learners to predict which will miss next. Then alter the trace: add a scan, repeat a hot pair, enlarge the working set. The purpose is to make the policy assumption visible through counterexamples.
This predict-run-investigate cycle follows the spirit of PRIMM. See Using PRIMM to teach programming.
27. Fade Worked Trace Tables Into Independent Simulation
Begin with every hit, miss, reference bit and eviction annotated. Next hide the eviction column. Then hide cache contents after each step. Finally give only the policy and trace. Worked-example research supports high guidance for novices when many interacting elements are new, followed by fading as schemas strengthen.
See When Instructional Guidance is Needed.
28. Immediate, Delayed and Transfer Checks
- Immediate: simulate FIFO, LRU and CLOCK for ten accesses.
- Counterexample: create a scan that pollutes LRU.
- Anomaly: explain why “more cache is always better” is not valid for every policy.
- Delayed: explain CLOCK without drawing the ring.
- Transfer: choose a replacement strategy for a tiny embedded cache, a database buffer and OS page reclaim.
- Professional: design a trace suite and metrics that could falsify your preferred policy.
Metacognitive questions should stay attached to the actual trace: What assumption am I using about future reuse? What evidence would disprove it? What cost am I ignoring? Current EEF guidance recommends explicit planning, monitoring and evaluation within subject tasks. See Metacognition and Self-Regulated Learning.
29. AI Assistance Boundary
AI can generate reference strings, simulate policies, suggest adversarial traces and help analyse benchmark logs. The learner should still be able to hand-trace the policy, state the locality assumption, identify implementation overhead and independently verify the measurements.
Professional Direction
Advanced study includes 2Q, LIRS, ARC, TinyLFU, segmented LRU, admission versus eviction policies, reuse-distance analysis, miss-ratio curves, hardware cache replacement, database buffer management, CDN caching, learned caching, multi-tenant isolation, flash-aware policies and kernel page reclaim.
Algorithm-learning rule: when a cache performs well, do not ask only for its hit rate. Ask what future-use assumption the policy is making, what trace shape rewards that assumption, what trace breaks it, what the policy costs to maintain, and whether the misses that remain are the ones your system can afford.
eduKate Sengkang 