Cache Eviction Policies Lab (Interactive)

Replay accesses and batch-scan bursts against LRU, LFU, FIFO, and TTL on a capacity-limited cache and compare hit ratios. Step through eviction decisions: which key each algorithm sacrifices when RAM fills, and how scan traffic or viral bias defeats it.

Eviction Policy Replay: LRU vs LFU vs FIFO vs TTL

Replay a request trace against a full cache and watch which key each algorithm sacrifices.

maxmemory-policy

Cache capacity (slots)4 keys

Request a key (GET)

Hits

Misses

Hit ratio

—

Evictions

RAM contents · clock t=44/4 full

A3 hits

inserted t0age 4 · idle 1

B1 hits

inserted t1age 3 · idle 2

C5 hits

inserted t2age 2 · idle 3

D2 hits

inserted t3age 1 · idle 4

Decision trace

› Loaded A–D. Policy: LRU. Access keys or fire a scan burst, then watch whom each policy sacrifices.

LRU (HashMap + doubly linked list, O(1)): assumes temporal locality. A batch scan of never-repeated keys flushes the hot set — Redis approximates it by sampling 5–10 keys to skip pointer overhead.

How It Works Under the Hood

DRAM is finite: when Redis hits maxmemory, an eviction policy decides which key dies to make room while protecting the hit ratio. LRU (hash map + doubly linked list, O(1)) assumes temporal locality but a one-shot batch scan flushes the hot set; LFU keeps frequency leaders but historical viral keys squat forever without logarithmic decay; FIFO evicts by insertion order; TTL expires on schedule via passive checks plus an active sampler sweeping 20 keys every 100ms. Production Redis uses approximated LRU — sampling 5–10 random keys — to dodge pointer overhead at near-ideal accuracy.

Core Architectural Principles

True LRU is HashMap + Doubly Linked List giving O(1) get/put; Redis approximates it by random sampling.
LFU needs decay counters or old viral keys never leave RAM; scan bursts poison plain LRU.
Redis policies differ: allkeys-lru evicts anything, volatile-lru only TTL-tagged keys, noeviction errors on write.

Interview Round Script

Expect the O(1) LRU data-structure question in both design and coding rounds: HashMap for lookup, doubly linked list for recency moves. Then show production depth: "Redis approximates LRU by sampling 5–10 keys to avoid pointer memory," and pick allkeys-lru versus allkeys-lfu based on whether popularity is sticky or transient — warning that one-off scans pollute LRU.

Key Trade-Offs

Recency-based eviction fits most web traffic but must be hardened against scan pollution, while frequency-based fits static popularity at the cost of stale-favorite bias.

Related Curriculum Chapter