A cache miss is easy to blame on size.

Make the cache bigger. Buy memory. Increase the Redis tier. Add another page to the buffer pool. Raise the CDN budget. Sometimes that is exactly right.

But a cache is not merely a small box in front of a large box. It is an online decision system. On every miss, it decides whether the incoming object deserves space, and if so, which resident object should lose its place.

That decision contains a forecast:

which object will be reused soon enough to justify keeping it?

Cache replacement is prediction under memory pressure.

The Future Is the Perfect Policy

Belady’s 1966 study of virtual-storage replacement algorithms gave the clean reference point: evict the page whose next use is farthest in the future.1 This is often called MIN or the clairvoyant policy. It is optimal for a fixed request sequence and fixed cache size.

It is also impossible online. The operating system, database, CDN, or application cache does not know the future request stream.

That impossibility is useful. Belady is not a product design. It is a regret meter. If your real policy is far from Belady, the trace is telling you there was predictable reuse you failed to exploit. If your real policy is close to Belady, the misses are mostly capacity or cold-start reality.

Every practical policy is a way to approximate next use from the past.

Recency Is a Story About Tomorrow

Least recently used replacement says:

the object touched most recently is likely to be touched again soon

That guess is often good because programs and users have locality. Loops revisit the same pages. Product sessions revisit the same entities. Databases touch neighboring index and data pages. Denning’s working-set model formalized a version of this idea: the active pages of a computation are the recently used pages over a window, and managing that working set helps prevent thrashing.2

LRU is beautiful because it is simple, adaptive, and hard to embarrass on many ordinary traces.

But LRU has a specific failure mode: scans.

A one-time scan through objects larger than the cache looks recent while it is happening. LRU admits the stream and evicts the hot set. By the time the scan ends, the cache is full of objects that will never be used again.

The cache did not run out of memory. It believed the wrong story about recency.

A Tiny Cache War

The lab below generates a trace with a hot working set and occasional one-hit scans. It compares four policies:

  • Belady, the offline oracle that evicts the item used farthest in the future;
  • LRU, pure recency;
  • LFU, frequency with recency tie-breaking;
  • frequency gate, an LRU cache with a TinyLFU-style admission rule: on a miss, the incoming object must have more recent frequency evidence than the LRU victim before it is admitted.

The gate is intentionally simplified. It uses exact decayed counts instead of a compact sketch. The point is the admission idea, not the production data structure.

The Audit tile is generated by the same JavaScript as the chart. Its exported runAudit() runs 20 deterministic checks: bad-control recovery, trace determinism, one-hit scan construction, hit/miss ledger conservation, Belady as an upper bound, Belady matching a brute-force optimum on a tiny trace, the classic FIFO anomaly fixture, LRU’s stack monotonicity, reuse-distance accounting, and a 36-scenario grid over cache size, hot-set size, scans, and phase shifts. The audit is deliberately about invariants, not vibes. It checks that the toy world behaves like the theory it is trying to explain.

Belady LRU LFU Frequency gate Cold scan

Deterministic synthetic trace. Hot objects repeat with a skewed distribution; scans are one-hit objects. Belady uses the full future trace and is an upper bound, not an implementable policy. The frequency gate uses exact decayed counts to illustrate TinyLFU-style admission without sketching details. The audit counter is produced by the simulation code, not hand-entered.

At the default setting, LRU admits every scan object. That is locally reasonable: the scan object was just requested. But each one-hit admission pushes out something from the hot set. When the scan ends, LRU has to relearn pages it already knew.

The frequency gate refuses almost all scan objects. It asks a separate question before admission:

does the incoming object have more evidence of reuse than the victim?

For one-hit scans, the answer is usually no. The gate lets the miss happen without poisoning the resident set.

Now set Scan length to zero. LRU improves. Without scan pollution, recency is a good enough forecast. Then set Hot-set shift to 50%. Halfway through the trace, the hot objects change. Frequency becomes sticky, and the gate can lag behind recency. The policy that resisted noise also resists change.

That is the whole game:

recency adapts quickly, frequency forgets slowly

Admission Is Its Own Decision

Many cache discussions jump straight to eviction: if the cache is full, which resident object should leave?

But admission is a separate decision. On a miss, the cache can choose not to store the incoming object at all. That sounds strange only if “requested once” is treated as sufficient evidence of future value.

TinyLFU makes this explicit. Einziger, Friedman, and Manes propose a compact frequency-based admission policy: compare the estimated recent frequency of the incoming object with the estimated frequency of the eviction candidate, and admit only when the newcomer looks more valuable.3 The production trick is that approximate counting can be compact enough to sit on the hot path.

This is why a cache is two systems:

  • an eviction policy, deciding which resident object is weakest;
  • an admission policy, deciding whether the new object should enter.

LRU has an implicit admission policy: admit everything. Scan-resistant caches often separate the two.

Miss-Ratio Curves Beat Vibes

The cache-size slider in the lab changes hit rates, but a single size is not the whole story. Mattson, Gecsei, Slutz, and Traiger’s storage-hierarchy paper gave methods for evaluating cache behavior across sizes, including the stack-distance view behind miss-ratio curves.4

The idea is wonderfully operational. For each access, ask how many distinct objects were referenced since the previous access to the same object. That is a reuse distance. If the reuse distance is larger than the cache, an LRU-like stack cache will miss. Cold references have no previous access and miss for every finite cache.

The lab’s reuse-distance panel is a small version of that measurement. It tells you whether misses are mostly:

  • very short reuses that your policy somehow failed to keep;
  • medium reuses that need more capacity;
  • long reuses that may not be worth storing;
  • cold one-hit objects.

Those categories imply different actions. “Increase cache size” is sensible for medium-distance reuse. It does not fix a stream of cold one-hit scan objects.

Regret Has a Ghost List

ARC, the Adaptive Replacement Cache of Megiddo and Modha, was designed to balance recency and frequency without manual tuning.5 It keeps track of recently evicted items as well as resident ones, using that ghost history to adapt how much cache to allocate to recency versus frequency.

That ghost idea is profound. A miss to a recently evicted object is feedback:

you threw this away too early

The cache is not just storing data. It is learning from regret.

But adaptivity is not free. A policy that reacts aggressively to recent misses can chase scans. A policy that trusts frequency can be slow after a phase change. A policy that needs many counters can burn memory, CPU, lock time, or tail latency. A policy that improves average hit rate can still harm important requests if the wrong objects are protected.

This is why production cache design is not a leaderboard of replacement algorithms. It is a workload diagnosis.

Before You Change the Cache

Before changing a cache policy, I want a trace-backed ledger:

  • hit rate by request class, not only total hit rate;
  • object size distribution if values are not uniform;
  • reuse-distance or stack-distance histogram;
  • one-hit object fraction;
  • scan or batch-job contribution to evictions;
  • hot-set churn rate after deploys, releases, or market opens;
  • admission rate for cold objects;
  • evictions of objects that are reused soon afterward;
  • latency and CPU cost of the policy itself;
  • miss penalty distribution, not just miss count.

The most useful metric is often “evicted and reused soon.” That is regret in the language of a cache. Belady would not have made that eviction.

The Sentence to Keep

An eviction is a prediction. An admission is a prediction too.

LRU predicts from recency. LFU predicts from frequency. Belady predicts from the future. ARC learns from ghost misses. TinyLFU-style admission asks whether a new object has earned the right to displace an old one.

None of these policies is morally correct. Each embeds a belief about the workload.

do not ask whether the cache is big enough until you know what it keeps

The cache is not a drawer. It is a memory policy.

Reading Trail

  1. Laszlo A. Belady, “A Study of Replacement Algorithms for a Virtual-Storage Computer”, IBM Systems Journal, 1966. ↩

  2. Peter J. Denning, “The Working Set Model for Program Behavior”, Communications of the ACM, 1968. A copy is also available from the Denning Institute. ↩

  3. Gil Einziger, Roy Friedman, and Ben Manes, “TinyLFU: A Highly Efficient Cache Admission Policy”, 2015; published in ACM Transactions on Storage, 2017. DOI: 10.1145/3149371. ↩

  4. Ronald L. Mattson, Jan Gecsei, Donald R. Slutz, and Irving L. Traiger, “Evaluation Techniques for Storage Hierarchies”, IBM Systems Journal, 1970. ↩

  5. Nimrod Megiddo and Dharmendra S. Modha, “ARC: A Self-Tuning, Low Overhead Replacement Cache”, FAST 2003. PDF: CMU mirror. ↩