Your LRU cache is working too hard

Least Recently Used has a simple rule: whenever an object is hit, move it to the front of the queue. That rule sounds cheap. In a concurrent cache, it is not. Moving an object in a linked list requires synchronization, so a popular object can turn every hit into a lock acquisition, a list mutation, and cross-core coherence traffic.

The surprising part is not that promotions cost something. It is how rarely they earn their cost.

In our new paper, Demystifying and Improving Lazy Promotion in Cache Eviction, we evaluated five promotion strategies over 6,357 production traces containing 346 billion requests. With an oracle that knows the future, LRU needs only about 10% of its promotions on average. The other 90% can disappear without increasing the miss ratio.

That result changes the design question. Instead of asking how to make every LRU promotion cheaper, we should ask:

How late can the cache wait before deciding that an object deserves to be promoted?

Why promotion is the scalability bottleneck#

LRU keeps objects in order of their most recent access. A hit moves an object to the head; an eviction removes one from the tail. The ordering is useful, but maintaining it exactly requires a global data structure that many threads modify.

As cores issue hits concurrently, they contend on the same lock. Popular objects are especially troublesome: they are promoted repeatedly even though they are already far from eviction. Those promotions do not change what the cache will keep, but the implementation still pays for them.

FIFO sits at the opposite extreme. It never changes the queue on a hit, so it scales well, but it can evict a frequently used object simply because the object is old. Production systems therefore use several approximations between exact LRU and pure FIFO. We call this family Lazy Promotion.

The key idea is temporal: a decision made closer to eviction has more information. Immediately after a hit, we know only that the object was useful once. At eviction time, we know whether it accumulated more hits, how long ago it was last accessed, and whether it is actually in danger of leaving.

Five ways production systems relax LRU#

We implemented and compared five strategies used in real systems:

Strategy	What it changes	The intuition
Probabilistic-LRU	Promote a hit with some probability	Fewer promotions mean less contention
Batch-LRU	Collect hits and promote them together	Amortize the lock and merge duplicate work
Delay-LRU	Do not re-promote a recently promoted object	A popular object is already safe
FIFO-reinsertion	Record hits, then reinsert at eviction	Make the decision only when it matters
Random-LRU	Sample candidates and evict the least recent	Avoid a globally ordered list

They all reduce coordination, but they do not reduce the right work equally well.

Probabilistic-LRU is simple, but it skips useful and useless promotions with the same probability. A configuration that kept only 5% of promotions raised the average miss ratio by 6%. More conservative settings preserved more of LRU's cache efficiency, but did not remove enough contention to deliver a large throughput gain.

Batch-LRU does better because repeated hits to a popular object can collapse into one update. Its benefit, however, depends heavily on workload skew. Some traces contain many duplicates per batch; others do not.

Delay-LRU is much more consistent. It asks whether enough time has passed since the object's last promotion. With a delay equal to 20% of the cache size, it removed more than 82% of promotions, increased throughput by 7x at 16 threads, and increased miss ratio by no more than 0.1%.

FIFO-reinsertion shifts the decision further to the right. A hit increments a small frequency counter without moving the object. When the object reaches the eviction point, the cache either evicts it or gives it another turn. With a one- or two-bit counter, this approach reduces coordination and can even beat LRU's miss ratio. More counter bits are not necessarily better: a large counter can trap yesterday's popular objects after the hot set has changed.

Count the value of a promotion, not just the promotions#

Simply counting promotions is not enough. An algorithm can eliminate nearly all of them by becoming FIFO, but a lower miss ratio is the reason we promote objects in the first place.

We therefore measure promotion efficiency:

$$\text{promotion efficiency} = \frac{\text{FIFO misses} - \text{algorithm misses}} {\text{algorithm promotions}}$$

The numerator is the miss reduction relative to FIFO. Dividing it by the number of promotions asks how much useful cache behavior each mutation buys.

LRU's average promotion efficiency is only 0.037: each promotion prevents 0.037 misses relative to FIFO. Among configurations whose miss ratio stays within 1% of LRU, Delay-LRU reaches about 0.4, and FIFO-reinsertion reaches about 0.3. They deliver roughly an order of magnitude more value per promotion because they suppress repeated updates to objects that are already safe.

The same pattern appears when Lazy Promotion is added to ARC and 2Q. Delay and reinsertion remain effective; random skipping and batching remain weaker or more workload-dependent. This is not an artifact of one particular queue policy. It comes from filtering low-value work that many LRU-based algorithms share.

The oracle experiment: ranking is mostly unnecessary#

To understand how much room remained, we gave the cache future knowledge. Belady's optimal algorithm normally uses the next access time to rank every object. We asked a simpler, binary question: will this object be accessed again before a typical eviction would reach it?

When the answer is no, the object can be removed early. Once these obviously cold objects are filtered out, the choice among the remaining eviction candidates matters surprisingly little. Random eviction and sampled LRU produce nearly the same miss ratio. The expensive work of keeping every object in a perfect order is not the important part; identifying objects that have no near-term reuse is.

We then applied future knowledge to FIFO-reinsertion. An oracle suppressed a reinsertion whenever the object would not be accessed again soon enough. This cut promotions by more than 90% on average while slightly reducing miss ratio.

The oracle is not a deployable algorithm, but it reveals two useful design principles:

1. Do not reward multiple hits that arrive in one short burst.
2. If a reward is necessary, decide at eviction time, when the cache has the most evidence.

D-FR: do not count clustered hits twice#

Delayed FIFO-reinsertion, or D-FR, combines Delay-LRU's suppression rule with FIFO-reinsertion's eviction-time decision.

Each object records its last counted access. A new hit increments the frequency counter only if enough time has passed. A burst of ten nearby requests therefore contributes one unit of evidence rather than ten. At eviction, the ordinary reinsertion rule uses that filtered counter.

The change needs one four-byte timestamp per object. In our implementation, the saved metadata writes outweighed the extra timestamp check: D-FR improved throughput by 5% over FIFO-reinsertion. For the median trace, it removed a further 60% of reinsertion operations, while achieving a lower miss ratio than LRU.

AGE: do not rescue an object whose evidence is stale#

D-FR filters how quickly frequency accumulates. Age-Guided Eviction (AGE) adds a recency check at the other end.

When FIFO-reinsertion encounters an object with a positive counter, AGE asks how long it has been since the object's last access. If that age exceeds a threshold, the old frequency evidence is treated as stale and the object is evicted instead of reinserted.

AGE removes more promotions than D-FR, but accepts a slightly larger miss-ratio tradeoff on some traces. The useful part is that the parameter behaves predictably: a smaller age threshold filters more aggressively; a sufficiently large threshold becomes ordinary FIFO-reinsertion. Both AGE and D-FR avoid about 0.48 misses per promotion in our evaluation, compared with roughly 0.24 for FIFO-reinsertion.

What I would change in a real cache#

The results suggest a practical order of operations:

1. Measure promotions alongside miss ratio. A policy can look efficient while burning CPU on queue maintenance.
2. Add a delay before replacing the algorithm. Delay-LRU preserves LRU's semantics and produced the most consistent improvement across workloads.
3. Prefer small counters. For FIFO-reinsertion, one or two bits are usually enough. More frequency history can make adaptation worse.
4. Make the final decision at eviction. D-FR and AGE show how extra context can filter work that looked useful at hit time.
5. Validate throughput separately from trace simulation. Our miss-ratio results use the 6,357 production traces, while scalability was measured on a controlled Zipfian workload so that policies could be compared at the same miss ratio.

Exact recency feels principled, but it is an expensive answer to a question the cache rarely needs to ask. A scalable cache does not have to remember every hit. It has to remember enough to make the next eviction a good one.

---

This post is based on the PVLDB paper Demystifying and Improving Lazy Promotion in Cache Eviction by Qinghan Chen, Muhammad Haekal Muhyidin Al-Araby, Ziyue Qiu, Zhuofan Chen, Rashmi Vinayak, and Juncheng Yang. The implementation and trace tools are open source.