A cache that’s full has to throw something out to make room — and which thing it evicts is the whole game. Race three classic policies on the exact same access stream, same size: FIFO evicts whatever was inserted longest ago (ignoring how it’s used), LRU evicts the item that hasn’t been touched for the longest time (recency), and LFU evicts the item accessed the fewest times (frequency). On a workload with one hot key surrounded by a rotating scan, LFU protects the hot key while LRU and FIFO keep evicting it during each scan — so their hit rates pull apart. Step the stream and watch three caches disagree.
FIFO (oldest) · LRU (least recently used) · LFU (least frequently used) — same stream, different evictions
capacity
How many items the cache can hold. When full, an access to a new key forces an eviction.
FIFO
Evict the item inserted longest ago — ignores whether it’s still being used.
LRU
Evict the least-recently-used item — recency-aware; the classic default.
LFU
Evict the least-frequently-used item — frequency-aware; protects hot keys from scans.
eviction.js — three policies, one stream
Ready
Same access stream, three caches of size 3: FIFO, LRU, LFU. Each step feeds the next key to all three; they hit or evict differently. Watch the hit counts diverge on this hot-key-plus-scan workload. Step to race.
0
FIFO hits
0
LRU hits
0
LFU hits
How it works
The three policies differ only in what they call “least valuable,” and that choice interacts with the workload. This stream is a hot key A accessed repeatedly, interleaved with a rotating scan B, C, D that alone would fill the cache. FIFO and LRU both let the scan push A out: FIFO because A was inserted early, LRU because during a scan A becomes the least-recently-touched. So every time the scan comes around, they’ve evicted A and miss on the next A. LFU instead remembers that A has been accessed far more often than any scan key, so it evicts a scan key and keepsA — turning those repeated A accesses into hits. This is exactly the “scan-resistance” problem, and it’s why real systems reach for ARC (Adaptive Replacement Cache): ARC keeps two lists — one for recency (LRU-like) and one for frequency (LFU-like) — plus “ghost” entries of recently-evicted keys, and adaptively shifts the balance between them based on which kind of miss it’s seeing. It gets LRU’s responsiveness and LFU’s scan-resistance without you tuning anything.
1
On a hit, just record it
If the accessed key is already in the cache, it’s a hit. LRU also marks it most-recently-used; LFU bumps its frequency count. FIFO leaves its insertion order untouched.
2
On a miss with room, insert
If the key isn’t cached and there’s free space, insert it. No eviction is needed yet.
3
On a miss when full, evict by policy
FIFO drops the oldest-inserted key; LRU drops the least-recently-used; LFU drops the least-frequently-used (ties broken by age). This is where the policies diverge.
✓
Match the policy to the workload
LRU suits recency-heavy access; LFU suits stable frequency and resists scans; FIFO is simplest but ignores usage. ARC adapts between recency and frequency automatically, capturing the best of both.
FIFO
oldest out
LRU
least recent out
LFU
least frequent out
ARC
adapts LRU↔LFU
The code
# three eviction policies, same interfacedef access(key):
if key in cache:
on_hit(key) # LRU: mark recent; LFU: freq += 1return HIT
if full():
victim = choose_victim() # the policy's whole identity:
evict(victim) # FIFO -> oldest inserted# LRU -> least recently used# LFU -> least frequently used
insert(key)
return MISS
Quick check
1. Which item does LRU evict when the cache is full?
LRU (least recently used) evicts the item that hasn’t been touched for the longest time — a recency judgment. FIFO evicts by insertion age, and LFU evicts by access frequency; each is a different notion of "least valuable".
2. Why does LFU beat LRU on a hot-key-plus-scan workload?
During a scan, the hot key temporarily becomes the least-recently-touched, so LRU throws it out and misses on the next hot access. LFU remembers the hot key has far more accesses than any scan key, keeps it, and turns those accesses into hits.
3. What does ARC (Adaptive Replacement Cache) do?
ARC keeps an LRU-like recency list and an LFU-like frequency list, tracks recently-evicted "ghost" keys, and shifts the balance between the two lists based on the misses it observes — getting LRU’s responsiveness and LFU’s scan-resistance automatically.
FAQ
What is a cache eviction policy?
When a full cache must store a new item, the eviction policy decides which existing item to remove. Common ones: FIFO (oldest inserted), LRU (least recently used), LFU (least frequently used), and adaptive schemes like ARC. The best choice depends on the access pattern — recency-heavy favors LRU, stable-frequency favors LFU.
When is LRU better than LFU, and vice versa?
LRU wins on recency-dominated access and shifting working sets. LFU wins when some items are persistently popular and must survive bursts/scans — but naive LFU can cling to once-popular items (needs aging). ARC and LRU-K aim to capture both.
What is scan resistance?
A cache’s ability to keep its hot items when a big one-time scan of many distinct keys passes through. Plain LRU isn’t scan-resistant (a scan evicts hot items); LFU and ARC are, because they weigh frequency, so a single scan pass can’t displace long-accessed items.
How does ARC work?
ARC splits the cache into two LRU lists — T1 (seen once, recency) and T2 (seen ≥ twice, frequency) — plus ghost lists B1/B2 of recently-evicted keys. A miss on a ghost entry tells ARC it evicted too eagerly, so it adjusts a target size p that shifts capacity between T1 and T2 — self-tuning between recency and frequency with no manual parameters.