Cache Eviction Policies
Eviction policies decide which entries to discard when the cache is full — LRU, LFU, ARC, FIFO, random — trading scan resistance and recency versus frequency against implementation cost.
Definition
When capacity is reached, an eviction policy selects victims. LRU evicts least recently used, capturing recency; LFU evicts least frequently used, capturing popularity; ARC and LFRU adapt between them; random eviction resists scans; FIFO is nearly free. Policy choice interacts with access pattern: scans poison LRU, one-off bursts poison LFU.
Context and scope
Configured on Redis maxmemory-policy, CDNs, browser caches, and in-process LRU implementations. Approximated policies (Redis LFU, segmented LRU) trade precision for memory.
Common misconceptions
- LRU is the best default — scans and large working sets evict everything useful from pure LRU; segmented or random variants resist scans
- Eviction policy affects correctness — it affects hit ratio; correctness comes from TTL and invalidation, which are separate axes
- LFU handles every pattern better — LFU holds stale popular entries and forgets recent shifts; adaptive policies exist precisely because neither dominates
Anti-patterns
- Using LRU for a scan-dominated workload that flushes the entire useful set each pass
- Configuring maxmemory without an eviction policy and getting OOM or random rejects instead of graceful degradation
- Blindly raising cache size instead of fixing the eviction policy mismatch and paying memory cost forever
Related concepts
Related examples
Authoritative source
What it is
Capacity is finite, so the cache must choose whom to forget. The policy encodes a theory of future access: recency theory backs LRU, frequency theory backs LFU, and adaptive theories blend both.
How it works
LRU keeps a recency-ordered list; approximate LRU samples N keys and evicts the oldest sampled, avoiding exact-list contention. LFU tracks counters with decay so popularity fades. Segmented LRU splits into probation and protected segments: a key must be hit twice to be protected, absorbing scans.
When to tune
Scan-heavy background jobs over shared caches, cyclic access patterns larger than cache size, and workloads with popularity shifts. Measure hit ratio before and after policy changes per key class.
Pitfalls
Policies compose with TTL: expired entries should purge before eviction pressure, or capacity serves dead weight. allkeys-lru versus volatile-lru in Redis changes semantics silently — evict-only-expiring versus evict-everything. Very small caches show policy noise; compare at realistic sizes.