Deciding what to evict: LRU, LFU and friends

In one minute

• When a cache is full, the eviction policy decides which entry to drop. The ideal is Belady's MIN: evict the entry whose next use is farthest away. It needs the future, so it serves as a yardstick, not an implementation.
• Real policies guess the future from two signals: recency (LRU, CLOCK) and frequency (LFU). Recency adapts quickly but is flushed by scans; frequency resists scans but clings to items that used to be popular.
• Modern policies win by treating new items with suspicion: S3-FIFO and SIEVE evict one-hit wonders quickly, and W-TinyLFU only admits a newcomer if it is more frequent than the victim.
• Throughput matters as much as hit ratio. An LRU hit is a write to shared pointers; a CLOCK or SIEVE hit only sets a bit, which scales across cores.
• Choose with a trace. Replay real access logs through candidate policies at your real cache size and compare miss ratios against Belady's bound.

How it works

What the policy is trying to do

Every eviction bets that this entry will be needed later than the others. Belady showed in 1966 that evicting the entry used farthest in the future minimises misses. No online cache knows the future, but simulating MIN on a recorded trace bounds the possible gain: if LRU misses 12% and MIN 9% at the same size, no policy saves more than a quarter of your misses.

Recency: LRU and its weakness

LRU evicts the entry unused for the longest time and adapts instantly when popularity shifts. Its weakness is scans: a one-off pass over many keys (a backup, a crawler, an analytics query) pushes every hot key out for keys that will never be read again. A loop slightly larger than the cache makes it miss on every access. The LLD lesson on designing an LRU cache covers its implementation.

Frequency: LFU and its weakness

LFU evicts the entry with the fewest accesses, so scans barely affect it. But a pure count never forgets: yesterday's viral video keeps its count long after interest moves on, so practical LFU ages counts. Redis's allkeys-lfu keeps an 8-bit logarithmic counter per key that is incremented probabilistically (lfu-log-factor, default 10, saturates around a million hits) and decremented when the key has been idle for lfu-decay-time minutes (default 1) (Redis docs). LFU can be O(1) with a list of frequency buckets, moving a key to the next bucket on each hit (Shah, Mitra and Matani).

Approximations: CLOCK and sampling

CLOCK approximates LRU with a circular buffer and a reference bit per slot. A hit sets the bit; to evict, a hand sweeps the circle, clearing set bits and evicting the first slot whose bit is clear. PostgreSQL's buffer manager uses a generalised version, the clock sweep, with a usage_count per buffer that a hit increments up to 5 and the sweep decrements, so frequently used pages survive several passes. Postgres also fences off scans instead of trusting the policy: a large sequential scan reuses a private 256 KB ring of buffers, and COPY uses a ring of at most 16 MB, so one big query cannot flush shared_buffers (Postgres buffer README). Redis avoids lists entirely: it samples maxmemory-samples keys (default 5) and keeps a small pool of the best candidates across evictions. Redis 8.6 added a third signal, least recently modified (allkeys-lrm, volatile-lrm): the timestamp moves only on writes, so keys that are read constantly but never updated still age out (Redis docs).

Combining both signals

2Q and segmented LRU put new entries on a probationary list and promote them on a second hit, so scans churn only probation. ARC (Megiddo and Modha, 2003) keeps recency and frequency lists plus "ghost" lists of evicted keys, and shifts space towards whichever ghost list gets hits (ARC paper). Linux uses active and inactive lists, and since kernel 6.1 offers the multi-generational LRU (MGLRU).

Suspicion of newcomers: TinyLFU, S3-FIFO and SIEVE

Objects requested once and never again (one-hit wonders) are common, and more so at cache scale. Across 6,594 production traces, the median share of one-hit wonders was 26% over a whole trace but 72% within a slice holding 10% of the trace's objects, which is roughly what a cache sees between evictions (S3-FIFO paper). Recent policies get most of their gain by evicting these fast.

W-TinyLFU, used by Caffeine and adopted by many Java and Go caches, adds an admission step. A small LRU window catches bursts. The paper's Caffeine release fixed it at 1% of capacity (TinyLFU paper); current Caffeine sizes window and main regions at runtime by hill climbing on the hit rate (Caffeine design). When the window evicts a candidate, a compact frequency sketch decides whether it beats the main region's victim; if not, the newcomer is dropped and the established entry stays. The sketch is a Count-Min sketch of 4-bit counters, halved periodically so old popularity fades.

S3-FIFO (SOSP 2023) uses three FIFO queues: a small one (about 10% of the cache) for new objects, a main one, and a ghost queue of recently evicted keys. Objects not re-accessed while in the small queue are evicted quickly; objects found in the ghost queue go straight to main.

SIEVE (NSDI 2024) is simpler still: one FIFO queue with a visited bit per object. A hit sets the bit without moving the object. To evict, a hand walks from tail toward head, clearing bits and evicting the first unvisited object, and stays where it stopped. An object never re-read is evicted on the hand's next pass. On 1,559 traces it had a lower miss ratio than nine other modern policies on over 45% of traces, and adding it to five production cache libraries took fewer than 20 changed lines on average (SIEVE paper).

Expiry comes before eviction

In caches with TTLs, many entries are dead before the policy ever looks at them. Twitter's study of 153 production cache clusters found that TTLs often set the effective working set, so removing expired objects promptly matters more than the choice of eviction policy, and at reasonable sizes FIFO often matched LRU (Twitter OSDI 2020). Redis, for example, deletes expired keys lazily on access and also periodically samples keys with TTLs to delete the dead ones nobody reads (Redis docs).

The same problem shape elsewhere

Eviction is the overload shape applied to memory: when demand exceeds capacity, drop by predicted value. An LLM server dropping KV-cache blocks of idle conversations and a Kubernetes node evicting pods under memory pressure make the same bet, and fail the same way when a burst of low-value work pushes out high-value work.

Down the stack

Diagram

flowchart TD
  M["Miss and cache full"] --> H["Hand at object (start: tail)"]
  H --> V{"Visited bit set?"}
  V -->|yes| C["Clear bit, move hand toward head (wrap at head)"]
  C --> V
  V -->|no| E["Evict object, hand stays at its neighbour"]
  E --> I["Insert new object at head, bit clear"]
  HIT["Hit"] --> S["Set visited bit, do not move"]

Worked example

A product image cache at an edge site holds 2 million objects. Normal traffic is 20,000 requests per second, and a nightly partner sync walks 5 million distinct catalogue images once, at 5,000 requests per second for about 17 minutes.

Replaying a day of logs through a simulator gives these miss ratios (illustrative numbers in the shape such studies usually show). Belady's MIN: 8%. W-TinyLFU: 10%. SIEVE: 10.5%. LRU: 13% for the day, but during the sync window LRU's miss ratio for normal traffic jumps to 40%, because the scan pushes most of the hot set out, and it takes about an hour of normal traffic to refill.

Translate to the origin. LRU at 13% sends 2,600 requests per second to the image origin on average, and the post-sync refill spikes it toward 8,000. W-TinyLFU at 10% sends 2,000, and during the sync it rejects the one-off images at admission, so the hot set barely moves. SIEVE also protects the hot set: hot objects have their visited bit set, so the hand clears it and moves on, while scanned objects are evicted on the hand's next pass.

Both cut origin load by about a quarter versus LRU and remove the nightly spike; SIEVE needs one bit per object, W-TinyLFU gets slightly better ratios. Either beats buying 30% more memory, which the miss-ratio curve says would only bring LRU to about 11.5%.

In the wild

• Discord, 2020: an LRU cache that the garbage collector had to keep scanning. Read States, the service that tracks which messages each user has read, held a large in-memory LRU cache in Go. Latency and CPU spiked about every two minutes, because Go forces a collection at least that often and each one walked the whole cache. Shrinking the cache cut the spikes but raised p99 latency, because more reads fell through to the database. A Rust rewrite with no garbage collector removed the spikes and let them raise the cache to 8 million Read States per server, a reminder that an eviction policy's metadata lives inside a runtime with its own costs (Discord).
• Twitter, 2020: what 153 production cache clusters actually do. Traces from Twitter's Twemcache fleet showed more than 35% of clusters were write-heavy (over 30% writes), popularity was roughly Zipfian with sometimes extreme skew, object sizes shifted daily, and TTL often bounded the working set. In simulation, FIFO frequently matched LRU, and LRU won mainly when the cache was severely undersized. The data fed the later S3-FIFO and SIEVE work (paper).

Trade-offs

Pitfalls in production

• Choosing by reputation. A policy that wins on CDN traces may lose on a buffer pool. Replay your own trace at your real size and compare against MIN.
• Batch jobs flushing the online cache. Backups and re-indexers evict the hot set under LRU. Use a scan-resistant policy, or keep batch traffic out of the cache.
• Frequency that never forgets. LFU without decay keeps last month's hits. Configure aging, such as Redis's lfu-decay-time.
• Counting entries when memory is bytes. A policy limited by entry count lets a few huge values exhaust memory. Weigh entries by size, or use separate pools for large objects.
• Eviction hiding a capacity problem. Evicted keys that are re-read soon mean the working set does not fit. Track them, and grow the cache when the miss-ratio curve says it pays.

Leadership lens

• Ask for a trace-driven comparison before changing a policy or buying memory. A policy change is often cheaper than hardware.
• Treat batch and online traffic as separate tenants of any shared cache, and make that a design review question.
• Prefer proven libraries (Caffeine, Ristretto, Redis's built-in policies) over custom eviction code.
• Monitor the eviction rate and the age of evicted keys, not just the hit ratio, to see pressure before users do.

Check yourself

1. Why can LRU miss on every access when a workload loops over 1,001 keys with a cache of 1,000?

   Show answer

   Each key is the least recently used exactly when it is about to be needed, so it is always evicted just in time to miss. MIN would keep most keys resident.

2. Why does a hit in SIEVE scale better across cores than a hit in LRU?

   Show answer

   A SIEVE hit only sets a visited bit, while an LRU hit relinks list nodes, which needs a lock and writes several shared cache lines.

3. What problem does TinyLFU's admission step solve that eviction alone does not?

   Show answer

   It stops a newcomer from displacing an entry that is accessed more often. A scan can then pass through the small window without evicting the established hot set.

4. Why do LFU caches need aging?

   Show answer

   Without it, items that were popular long ago keep high counts and never leave, so new popular items cannot get in.

Sources and further study

Primary

• Yang, Yue and Rashmi, A large scale analysis of hundreds of in-memory cache clusters at Twitter (OSDI 2020): production evidence on TTLs, skew and when FIFO is enough.
• Einziger, Friedman and Manes, TinyLFU (full paper): the reset-by-halving proof, the 10x sample size and the window experiments.

Systems docs

• PostgreSQL buffer manager README: clock sweep, the background writer and ring buffers for scans, VACUUM and bulk writes.
• Multi-Gen LRU (Linux kernel docs): how to enable and tune the kernel's generational page reclaim.
• Caffeine efficiency: W-TinyLFU against LRU, ARC, LIRS and Belady's bound on several traces.

Books

• Database Internals, Alex Petrov, chapter 5 "Transaction Processing and Recovery": buffer management, page replacement, CLOCK and LFU from the storage engine's side.
• Systems Performance (2nd ed.), Brendan Gregg, chapter 7 "Memory": page scanning, reclaim and how to observe memory pressure.

Other curricula

• donnemartin/system-design-primer: mentions LRU as the way to keep hot data in RAM and stops there; no scan resistance or admission.
• Caching guidance (Azure Architecture Center): lists eviction types (most recently used, first-in-first-out, explicit removal) and warns against pinning items so they never leave.

Watch

• NSDI '24: SIEVE is Simpler than LRU (USENIX): the authors explain SIEVE, lazy promotion and quick demotion, with results on 1,559 traces.

Free resources

• SIEVE is Simpler than LRU (NSDI 2024 paper): the algorithm, its analysis and the trace study.
• FIFO queues are all you need for cache eviction (S3-FIFO, SOSP 2023): why one-hit wonders dominate and how three FIFO queues exploit that.
• TinyLFU: A Highly Efficient Cache Admission Policy (arXiv): the frequency sketch, aging by halving, and W-TinyLFU.
• Caffeine design notes: how a production cache buffers hits and applies W-TinyLFU concurrently.
• ARC: A Self-Tuning, Low Overhead Replacement Cache (FAST 2003): the adaptive recency and frequency policy with ghost lists.
• Key eviction (Redis docs): Redis's sampled LRU and LFU, maxmemory-samples and the LFU tuning knobs.