Eviction Policies

In a Nutshell

A cache has limited memory, so when it fills up and a new item needs to go in, something has to come out. An eviction policy is the rule that decides which item to remove. The goal is to keep the items most likely to be requested again and discard the ones least likely — maximizing the hit ratio. The classic policies are LRU (evict least-recently-used), LFU (evict least-frequently-used), and FIFO (evict oldest), each betting on a different theory of what "likely to be needed again" means. Choosing the right one, and setting the right memory limit, directly determines how effective your cache is.

How It Actually Works

The Core Policies

Policy	Evicts	Bets That	Weakness
LRU (Least Recently Used)	Item untouched longest	Recently used → soon reused (temporal locality)	A one-time scan of many items pollutes the cache
LFU (Least Frequently Used)	Item with fewest accesses	Popular items stay popular	Old-but-once-hot items linger; new items disadvantaged
FIFO (First In First Out)	Oldest inserted	Insertion order ≈ usefulness	Ignores actual access patterns
Random	A random item	Simplicity; surprisingly OK	No intelligence
TTL-based	Whatever expired	Time bounds relevance	Not size-driven

LRU is the default choice for most caches because temporal locality (recently accessed data tends to be accessed again soon) holds in the vast majority of real workloads.

LRU vs LFU: The Key Distinction

Access sequence: A A A A B C D E  (A is hit 4x, then a burst of new items)

LRU after B,C,D,E fill the cache:
  → A is now "least recently used" and gets EVICTED
  → but A was clearly the most popular! LRU is fooled by the recent burst.

LFU:
  → A has 4 accesses vs 1 each for B,C,D,E
  → A is KEPT (correctly); a one-time scan doesn't evict the hot item.

LFU resists "cache pollution" from scans, but struggles when popularity
shifts over time (a formerly-hot item won't leave).

Modern systems often use hybrids: LRU-K, Segmented LRU, or TinyLFU / W-TinyLFU (used by Caffeine and others) combine frequency and recency to get the best of both.

Redis Eviction Policies (Concrete Example)

Redis exposes a maxmemory-policy — a great illustration of the real options:

Policy	Behavior
noeviction	Reject writes when full (return errors)
allkeys-lru	Evict least-recently-used across all keys
allkeys-lfu	Evict least-frequently-used across all keys
allkeys-random	Evict a random key
volatile-lru	LRU, but only among keys with a TTL set
volatile-ttl	Evict the key with the shortest remaining TTL

allkeys-lru is a common general-purpose choice; volatile-* variants let you protect persistent keys and only evict explicitly-expirable ones.

Eviction vs Expiration — Not the Same Thing

Expiration (TTL):  time-driven — an item is removed because its TTL elapsed
Eviction (policy): space-driven — an item is removed because the cache is FULL

Both can apply: an item may expire before it's ever evicted, or be evicted
while still "fresh" simply because memory ran out.

Sizing the Cache

Eviction policy only matters because memory is bounded. Two failure modes:

• Too small → high eviction rate → low hit ratio → cache barely helps (churns constantly).
• Too large → wasted expensive memory; and beware unbounded local caches causing OOM crashes.

The right size is where the hit ratio curve flattens — the point of diminishing returns. Monitor eviction rate and hit ratio together: a rising eviction rate with a falling hit ratio means the cache is too small for its working set.

Seeing It in Action

Scenario: Tuning eviction for different cache workloads.

Workload 1 — User session cache (Redis):
  Access pattern: sessions accessed repeatedly during activity, then idle.
  Policy: volatile-lru with per-session TTL.
  Why: recency matters (active users' sessions stay hot), and expired
       sessions should go first. Protects any non-session persistent keys.

Workload 2 — Product catalog cache:
  Access pattern: a small set of popular products dominate traffic (long tail).
  Policy: allkeys-lfu.
  Why: the bestsellers are hit constantly; frequency captures this better
       than recency, and a crawler scanning all products won't evict the
       hot bestsellers (scan resistance).

Workload 3 — Analytics scan / batch job:
  Access pattern: reads each row once, sequentially (no reuse).
  Policy: don't cache, or use a small FIFO/random cache.
  Why: LRU would be polluted by data that's never reused — the classic
       "LRU is terrible for scans" case. Sometimes NOT caching is right.

Sizing: monitored hit ratio vs memory; set maxmemory where the curve
        knees over. Alert if eviction rate spikes (working set grew).

The takeaway: the "best" eviction policy is workload-dependent. LRU is the safe default, but LFU wins when popularity is stable and skewed (catalogs), TTL-aware variants win for session-like data, and scan-heavy workloads may be better served by not caching at all. Always pair policy choice with cache sizing driven by the hit-ratio curve.

Interview Questions

1. Q: What is a cache eviction policy and why is one necessary? Hint: Caches have bounded memory; when full, adding a new item requires removing an existing one. The eviction policy decides which item to remove, aiming to discard the items least likely to be reused so the hit ratio stays high. Without a policy, the cache either can't accept new data or grows unbounded and crashes (OOM).

2. Q: Compare LRU and LFU. When does each fail? Hint: LRU evicts the least-recently-used item (bets on temporal locality) — but a one-time scan of many items can evict genuinely-hot data (cache pollution). LFU evicts the least-frequently-used (bets on stable popularity) — but a formerly-hot item lingers after its popularity fades, and new items are disadvantaged. Hybrids (W-TinyLFU, segmented LRU) combine recency and frequency.

3. Q: What's the difference between eviction and expiration? Hint: Expiration is time-driven — an item is removed because its TTL elapsed (relevance bounded by time). Eviction is space-driven — an item is removed because the cache is full (bounded by memory), chosen by the eviction policy. An item can expire before being evicted, or be evicted while still fresh because memory ran out. Redis volatile-* policies combine the two.

4. Q: How do you decide the right cache size? Hint: Plot/observe hit ratio vs cache size — it rises steeply then flattens. The right size is at the "knee" where returns diminish; larger wastes expensive memory. Monitor eviction rate and hit ratio together: a rising eviction rate with falling hit ratio means the cache is too small for the working set. Also cap local caches to avoid OOM.

5. Q: Why can LRU perform poorly for a large sequential scan, and what do you do about it? Hint: A scan reads many items once with no reuse, filling the cache with data that will never be requested again and evicting genuinely-hot items (pollution). Mitigations: use a scan-resistant policy (LFU / W-TinyLFU / segmented LRU), bypass the cache for scan/batch access, or use a separate small cache for such workloads. Sometimes not caching is the right answer.

References

• Redis: Key eviction policies — the concrete maxmemory-policy options
• Caffeine (W-TinyLFU) design — a modern high-hit-ratio cache
• Designing Data-Intensive Applications by Martin Kleppmann — caching and working sets

Dive Deeper

• TinyLFU: A Highly Efficient Cache Admission Policy — the paper behind modern hybrid eviction
• The LRU-K page replacement algorithm — a classic recency/frequency hybrid
• Cloudflare: how caches decide what to keep — eviction in a global edge cache