LFU Eviction

The Idea

 LFU evicts by ACCESS COUNT, not recency:

 key      accesses   verdict
 hot_a    10,000     keep forever (until decay)
 warm_b       900    keep
 cold_c         2    evict first — even if accessed a moment ago

 bet: POPULARITY persists. things read often will keep being read.
 LRU's bet: RECENT use predicts future use. different physics.

Where Frequency Wins

 stable skewed workloads:
 - product catalogs with fixed bestsellers
 - library/dataset lookups (papers, packages, docs)
 - config/metadata that a few thousand keys serve constantly

 the LRU killer scenario LFU survives:
   periodic bulk scan touches EVERY key once
   → LRU flushes entire hot set (scan looks "recent"!)
   → LFU shrugs: one access doesn't outrank 10,000

 if batch jobs or crawlers walk your cache,
 LRU alone is quietly destroying your hit rate.

The Relic Problem and Decay

 pure counters never forget:
   item popular LAST YEAR still holds top counts
   → blocks genuinely hot newcomers → hit rate rots silently

 fixes:
 - PERIODIC HALVING: every N minutes, count /= 2
   (logarithmic aging; old popularity fades in ~hours)
 - WINDOWED counting: track per-time-bucket, sum recent windows
 - Redis LFU: probabilistic counter with configurable decay
   via lfu-log-factor + lfu-decay-time
 
 frequency without decay is worse than recency. always pair them.

Counting Cheaply

 exact per-key counters cost memory at scale:

 approximations used in production:
 - COUNT-MIN SKETCH: tiny fixed memory, occasional overcount,
   never undercount → safe for eviction decisions
 - PROBABILISTIC counters: increment with probability 1/2^n
   once count is large (saturating ~log growth) — Redis style
 - CUCKOO/TinyLFU filters: admission control before full tracking

 W-TinyLFU (Caffeine's default): admission window + sketch-based
 frequency test beats plain LRU on skewed traces significantly —
 the state of the art for in-process caches.

Choosing: LRU vs LFU vs Hybrid

Signal	Lean
Session-y traffic, temporal bursts	LRU
Stable catalog popularity	LFU
Bulk scans / crawlers present	LFU or segmented LRU
Mixed reality	TinyLFU-style hybrid

 practical default ladder:
   start allkeys-lru (simple, decent)
   hit rate disappointing? check scan patterns first
   then try allkeys-lfu (redis) or W-TinyLFU (in-process)
   measure hit rate delta — let data pick, not fashion

Interview Framing

LFU answers score on three beats: where it beats LRU (stable skew + scan immunity), its failure mode WITHOUT decay (relics), and one cheap-approximation mention (count-min sketch or Redis’s probabilistic counters). Closing with “measure both on real traces; hybrids usually win” converts theory into engineering judgment.