Cache Eviction Policies - LRU, LFU, ARC

By the end of this lesson, you will be able to...

• Trace the victim chosen by recency- and frequency-based policies under a fixed cache budget.

• Predict how scans and popularity shifts break different reuse assumptions.

• Explain what ARC learns from ghost entries and when extra policy machinery is justified.

Idea in one sentence: An eviction policy uses incomplete history to predict which cached entry will be least valuable next.

Core Insight

A product cache has room for three entries. The normal hot set is A, B, and C. Then an export job reads thousands of products exactly once.

Nothing is wrong with the cache capacity. Nothing is wrong with the keys. Yet interactive requests begin missing.

The simple model says:

When the cache is full, remove the oldest entry.

That rule sounds neutral. It is not. “Oldest” is one prediction about future reuse. A scan makes each one-time object look recent, so a recency-only cache may discard the older objects that users will request again.

Eviction is the moment where finite capacity becomes a forecast.

The Moving Parts

Keep four pieces separate:

• capacity: how many entries or bytes may remain;
• admission: whether a newly seen object enters the cache;
• history: which access evidence the policy records;
• victim selection: which resident entry leaves when space is needed.

This lesson uses equal-sized entries to make the policy visible. Real caches may evict by byte pressure, approximate metadata, TTL eligibility, or implementation-specific rules. The traces are teaching models, not claims about every Redis, database, or hardware cache.

LRU Bets on Recency

LRU means Least Recently Used. On a miss, it evicts the resident entry whose last access is furthest in the past.

Use a cache with capacity three and this access sequence:

A, B, C, A, D, E, A

Represent the cache from least recent to most recent:

LRU succeeds here because the second access to A moves it away from the eviction end before D and E arrive.

Now change the order slightly:

A, B, C, D, E, F, A

The one-time scan through D, E, and F evicts A, B, and C. The final A misses. LRU interpreted “recently scanned” as “likely to be reused.”

That is not an implementation bug. It is the policy's assumption becoming false.

LRU is a good fit when temporal locality dominates: an entry touched recently is likely to be touched again soon. It adapts quickly when the active set moves. Its weakness is that recency cannot distinguish a new hot set from a one-time sweep.

Check: Why does doubling capacity sometimes fail to repair scan pollution?

Think first, then reveal.

Answer: A scan larger than the new capacity can still fill the recency history with one-time objects and evict the reusable set. Capacity changes when failure occurs; it does not change LRU's prediction.

LFU Bets on Frequency

LFU means Least Frequently Used. It keeps an access count or approximation and evicts an entry with the weakest frequency evidence.

Suppose the cache has learned this resident state:

Now the scan accesses D, E, and F once each. In a simplified LFU model that admits the new entry before choosing the lowest-frequency victim, each scan entry has frequency one and is the weakest candidate. The established hot set survives.

This is the behavior LFU is trying to buy: protect durable popularity from short recency noise.

But history can become inertia. Imagine that yesterday's hot keys have high counts and today's users move to a new catalog. New entries begin with low counts, so the policy may keep yesterday's winners long after their value disappears.

Practical LFU designs therefore need forgetting:

• decay old counts;
• age them over time;
• use approximate logarithmic counters;
• combine frequency with recency for tie-breaking or admission.

The exact mechanism varies. The principle does not: frequency without a time boundary can confuse past popularity with future value.

ARC Learns Which History It Regrets

ARC, the Adaptive Replacement Cache, addresses workloads where recency and frequency take turns being useful.

Its key idea is not simply “mix LRU and LFU.” ARC keeps evidence about both live entries and recently evicted entries.

A simplified view contains:

• a live recency list for entries seen once recently;
• a live frequency list for entries that have been reused;
• two ghost lists that remember only the identities of recently evicted entries from each side;
• a target that shifts capacity between recency and frequency.

Ghost entries do not hold cached values. They hold evidence about mistakes.

If a request returns for an identity in the recency ghost list, the cache learns that it evicted recent material too aggressively. It gives more space to recency. If requests return through the frequency ghost history, it shifts the other way.

request misses resident cache
  -> identity appears in a ghost history
  -> policy observes which kind of victim was regretted
  -> recency/frequency balance changes
  -> future victim selection uses the new balance

This feedback makes ARC adaptive and scan-resistant under the workload model studied in its original paper. It does not create infinite capacity or guarantee the best result for every implementation and workload.

The cost is extra metadata, more state transitions, and a harder operational story. A simpler approximate LRU may be better when misses are cheap, concurrency overhead dominates, or the workload is already well understood.

A Worked Policy Comparison

Consider two workload phases with a three-entry cache:

Phase 1: A, B, A, C, A, B
Phase 2: D, E, F          # one-time scan
Phase 3: A, B, A

The exact result depends on implementation details, especially LFU aging and admission. The useful prediction is qualitative:

Before choosing, state what you expect the phases to do. Then measure by phase. A single daily hit-rate average can hide a disastrous ten-minute catalog scan or a slow evening popularity shift.

Check: An LFU cache performs well all day but misses heavily after the nightly hot set changes. What evidence would support adding decay?

Think first, then reveal.

Answer: Old high-frequency entries remain resident while newly popular keys repeatedly miss. Compare resident frequency age, post-shift hit rate, miss latency, and evictions before and after a bounded decay experiment.

Trace the Boundary, Not Just the Steady State

Policy failures often occur at a transition. Looking only after the cache has settled hides the mechanism.

Suppose a four-entry cache begins with a reusable working set:

warm phase: A, B, C, D, A, B, C, D
scan phase: E, F, G, H
return:     A, B, C, D

Immediately before the scan, both a recency policy and a frequency policy may report an excellent hit rate. During the scan, all four new keys miss under either policy. The interesting difference appears on the return.

In textbook LRU, E, F, G, and H are now the four most recent residents. The returning A, B, C, and D all miss. The scan caused eight expensive misses: four unavoidable first accesses and four avoidable losses of the previous working set.

In the simplified LFU model, the established keys have repeated-use evidence while each scan key has count one. The scan entries compete among themselves and the hot set can survive. The return hits.

That comparison does not prove LFU is universally better. Add a fourth phase in which E, F, G, and H become the new working set. A frequency policy with no aging may continue protecting the old set and resist the real change. LRU will adapt after enough accesses because the new keys stay recent.

The diagnostic habit is to label workload phases and ask where regret appears:

• misses during first access may be unavoidable;
• misses after a scan reveal pollution;
• misses after a genuine hot-set change reveal slow adaptation;
• high hit rate with expensive remaining misses may reveal the wrong objective.

This is why one aggregate hit-rate number cannot tell you which policy assumption failed.

Admission and Eviction Are Different Decisions

The worked traces admit every missed object and then choose a victim. A production cache can instead decide that some objects should not enter.

Imagine a 20 MB report that will be downloaded once. If it enters a size-bounded cache, it may evict hundreds of small objects with repeated demand. No victim-selection algorithm can recover those objects before the admission decision has already spent the capacity.

An admission rule can use evidence such as estimated frequency, object size, request class, or a comparison between the candidate and a likely victim. Rejecting the report preserves the resident set, but it also creates a new risk: the policy may reject an object just before it becomes popular.

Keep the two questions explicit:

admission: does this miss deserve cache space?
eviction:  if it enters, which resident should pay for it?

This separation also prevents a common debugging error. If large one-time objects cause churn, switching from LRU to ARC may help less than changing admission or isolating those objects in a different cache. Measure entry sizes and reuse after admission before blaming victim selection alone.

Cost, Limits, and Signals

Policy quality is only one cost.

Every policy is a trade-off between prediction quality and the memory, CPU, synchronization, and explanation cost required to maintain its history.

Exact recency order can require metadata updates on hits. Frequency needs counters and aging. Adaptive policies need more bookkeeping. Concurrent caches may approximate these ideas to reduce lock contention or CPU cost. Redis, for example, documents an approximated LRU implementation rather than a textbook exact list.

Watch signals that connect policy to system behavior:

• hit and miss rate by workload phase;
• miss latency and downstream load;
• evictions and expirations;
• cache occupancy and entry-size distribution;
• metadata or CPU overhead of the policy;
• time needed to recover after a scan or popularity shift.

A policy is successful when its prediction improves the whole path at acceptable cost. A fashionable algorithm with a slightly higher hit rate can still lose if its synchronization or metadata overhead dominates.

Practice: Choose the Bet

A news cache has a stable set of popular home-page objects, a crawler that scans every article once per hour, and a breaking-news event that replaces the hot set within minutes.

Choose a starting policy and define a test that could change your mind.

Model answer: Start with an adaptive or admission-aware policy because the workload contains stable popularity, scans, and abrupt phase changes. Compare it with approximate LRU under a replay containing all three phases. Measure hit rate by phase, miss latency, origin load, recovery time after the scan, and policy CPU overhead. If simple LRU performs similarly without origin pressure, keep the simpler policy.

Resources

• [PAPER] ARC: A Self-Tuning, Low Overhead Replacement Cache — Focus: Read how ghost histories adapt the recency/frequency balance and why scan resistance matters.
• [DOC] Redis: Key Eviction — Focus: Compare textbook policy names with approximate production behavior and runtime signals.
• [DOC] Caffeine: Eviction — Focus: See how a modern application cache combines capacity policy with practical implementation constraints.

Key Takeaways

• LRU, LFU, and ARC encode different predictions about future reuse.
• Scans break recency; unaged history breaks frequency.
• ARC uses ghost misses as evidence about which kind of entry it evicted too aggressively.
• Choose with phased workload evidence and include the policy's own CPU and metadata cost.