ARC (Adaptive Replacement Cache) splits the cache into two LRU lists: T1 for items seen once recently (recency) and T2 for items seen at least twice (frequency). It also keeps two "ghost" lists B1 and B2 of recently-evicted keys (metadata only). When a miss hits a ghost entry, ARC learns which kind of item it evicted too eagerly and adjusts a target size p that shifts capacity between T1 and T2. This self-tuning gives it LRU’s adaptivity and LFU’s scan-resistance without manual parameters.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Systems · Caching

Who to Evict?

Q: What is a cache eviction policy?

When a fixed-size cache is full and a new item needs to be stored, the eviction policy decides which existing item to remove. Common policies are FIFO (evict the oldest inserted), LRU (evict the least recently used), LFU (evict the least frequently used), and adaptive schemes like ARC. The right choice depends on the access pattern: recency-heavy workloads favor LRU, stable-frequency workloads favor LFU.

Q: When is LRU better than LFU, and vice versa?

LRU is better for recency-dominated access, where recently used items are most likely to be used again soon, and it adapts quickly to shifting working sets. LFU is better when some items are persistently popular and you want to protect them from temporary bursts or scans — but naive LFU can be slow to evict items that were popular long ago (cache pollution), which is why LFU variants add aging. In practice ARC or LRU-K style policies aim to get the benefits of both.

Q: What is scan resistance?

Scan resistance is a cache’s ability to keep its useful hot items when a large one-time sequential scan of many distinct keys passes through. Plain LRU is not scan-resistant: a scan touches many keys once and evicts the genuinely hot items. LFU and adaptive policies like ARC are scan-resistant because they weigh frequency, so a single pass of scan keys can’t displace items with a long history of accesses.

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.

FIFO hits

LRU hits

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 keeps A — 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.

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.

On a miss with room, insert

If the key isn’t cached and there’s free space, insert it. No eviction is needed yet.

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 interface def access(key): if key in cache: on_hit(key) # LRU: mark recent; LFU: freq += 1 return 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?

2. Why does LFU beat LRU on a hot-key-plus-scan workload?

3. What does ARC (Adaptive Replacement Cache) do?

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.