← System Design Playbook Cache eviction playground

LRU vs LFU

Both caches receive the same stream of requests. When a cache is full, LRU evicts the key used longest ago and LFU evicts the key used least often. Step through a scenario and watch which one keeps the right keys.

Request stream hit miss Left mark = LRU, right mark = LFU
Or request a key yourself

LRU

Evicts the least recently used key
most recentleast recent
Waiting for the first request.

LFU

Evicts the least frequently used key
most usedleast used
Waiting for the first request.

How LRU works

A hash map plus a doubly linked list ordered by recency. A hit moves the key to the front; a miss inserts at the front and drops the tail when full. Both are O(1).

  • Good when recent use predicts the next use: sessions, recently opened files, page caches.
  • Weak spot: a one-off scan of many keys pushes out the keys you actually reuse.
get(k):  if k in map: move k to front; return hit
put(k):  if full: remove tail
         insert k at front

How LFU works

Each key keeps a use count. When full, the key with the lowest count is evicted; ties go to the one used longest ago. O(1) versions keep a list of keys per count.

  • Good when popularity is stable: CDN assets, best-selling products, config keys.
  • Weak spot: keys that were popular in the past keep high counts and block new favorites. Real systems decay counts over time.
get(k):  if k in map: count[k] += 1; return hit
put(k):  if full: remove key with min (count, last_used)
         insert k with count 1