LRU Eviction

The Problem Eviction Solves

 caches are FINITE. when full and a new item arrives,
 something must go. the eviction policy chooses what.

 goal: evict the item LEAST likely to be needed again.
 perfectclairvoyance is impossible → use the past as proxy:
   LRU: whatever wasn't used recently probably won't be soon.

The Mechanics

 LRU = recency-ordered structure:

 GET x  ──► move x to front          (recency refreshed)
 PUT y  ──► insert at front
 EVICT  ──► remove from back         (least recently used)

 [ newest ] f, d, a, m, q [ oldest ]
                              ▲ full? q goes first

 O(1) with hashmap + doubly-linked list:
   map: key → node     list: recency order
   every implementation does exactly this under the hood

Why Recency Works: Temporal Locality

 access patterns in real traffic:
 - just-referenced data tends to be referenced again SOON
   (a user's session touches profile, then trips, then payment)
 - scan patterns poison LRU: one bulk job reading everything
   flushes your hot set with never-needed entries
 
 mitigations for scans:
 - LRU-K: require K accesses before entering the main pool
 - segmented LRU: new items prove themselves in a probation zone
 - Redis approximates instead of tracking perfectly (below)

Approximated LRU (Redis-style)

 exact LRU costs memory (pointers per key). Redis samples:

 on eviction need:
   sample N keys (default 5) at random
   evict the LEAST recently used OF THE SAMPLE

 result: near-LRU behavior at fraction of memory cost.
 tunable via maxmemory-samples; good enough in practice —
 a nice example of trading precision for scale deliberately.

LRU vs Alternatives

Policy	Idea	Best against
LRU	Recency	Temporal locality (most web workloads)
LFU	Frequency	Stable popularity skew
FIFO	Insertion order	Nothing much; rarely right
Random	Luck	Baseline; surprisingly OK for uniform access
TTL-first	Age	Freshness-bound data

 LRU failure mode vs LFU: one viral-but-now-dead key keeps
 getting TOUCHED during its decline and blocks the true hot set;
 LFU would have aged it out by frequency decay.
 conversely LFU lets stale-popular relics linger without decay.
 modern answer: LRU+LFU hybrids (W-TinyLFU in Caffeine).

Configuration Reality

 redis:
   maxmemory 8gb
   maxmemory-policy allkeys-lru      ← the common choice
   
 variants worth knowing:
   volatile-lru    only keys WITH ttl evicted (mixing policies)
   noeviction      writes FAIL when full ← correct for locks/sessions?
   allkeys-lfu     frequency-based alternative

 sizing: monitor hit rate as you shrink/grow memory —
 hit-rate-vs-size curve flattens at the right capacity.

Interview Framing

“Cache is full — what happens?” expects: eviction policy exists, LRU named, O(1) mechanics known (hashmap + linked list), scan-poisoning acknowledged with an LRU-K/segmented mention, and Redis approximation cited. That arc takes 60 seconds and covers the entire depth most interviews probe.