, 5 min read, caching, databases, performance
LRU promotes under a lock on every hit. A VLDB 2026 paper ran 6,357 production traces and found most of that work is wasted, with numbers to back a default.
LRU has one habit that costs more than it looks like it should. Every time you hit an object, LRU moves it to the head of a doubly linked list. You can't splice a node out of the middle of a list atomically, so in a multithreaded cache that move happens under a lock, and every hit on every core queues up for it. FIFO never touches the list on a hit, so it scales fine. The folk wisdom is that it misses more, so people keep reaching for LRU anyway.
A VLDB 2026 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, puts real numbers on that tradeoff. It got a Best Research Paper Honorable Mention at the conference in Boston (August 31 to September 4). The authors replayed 6,357 production traces from nine companies (346 billion requests, 2,818 TB of data) through five relaxed versions of LRU. My takeaway after reading it: for a new cache, FIFO-reinsertion should be the default, and LRU is now the one that has to justify itself.
The framing I liked most is that LRU and FIFO aren't rivals. They're the two extremes of one setting: LRU promotes on every hit, FIFO promotes never. Production systems already live somewhere in between. The paper lists Meta's CacheLib (Delay-LRU), Meta's HHVM (promote only if a try-lock succeeds), Twitter's Segcache and Google's CliqueMap (batching), and RocksDB and PostgreSQL (FIFO-reinsertion). It calls the whole family lazy promotion.
FIFO-reinsertion is the one worth remembering. Depending on who built it, you'll see it called CLOCK or Second Chance. With a 1-bit counter it works like this:
Hit
set the object's visited bit. Nothing moves.
Miss
look at the object at the front of the queue.
Visited
clear its bit and move it to the back instead of evicting it. This is the only promotion there is.
Not visited
evict it, then insert the new object at the back.
So promotion happens lazily, at eviction time, and only for objects that were touched since they last reached the front. Delay-LRU gets there differently. It keeps LRU's move-to-head, but skips the move if the object was promoted recently, where "recently" is a delay ratio times the cache size, counted in insertions. A popular object gets hit again long before it drifts to the tail, so re-ranking it on every single hit is wasted work.
The paper's new metric is promotion efficiency: how many misses each promotion saves compared to plain FIFO, which never promotes. In formula terms, FIFO's misses minus the policy's misses, divided by the policy's promotions1. A promotion that never prevents a miss is just lock traffic.
LRU's mean across the traces is 0.037. Put another way, it takes about 27 LRU promotions to save one miss. When the authors keep Delay-LRU and FIFO-reinsertion within 1% of LRU's miss ratio, those two reach efficiencies as high as 0.4 and 0.3. FIFO-reinsertion is also the only lazy technique in the study that lowers LRU's miss ratio, by almost 2% on average with a 2-bit counter. With a 1-bit counter it cuts promotions by 80%.
The oracle experiment is where it gets a little embarrassing for LRU. Using Belady's MIN as the reference (the optimal policy if you know every future request), they find only about 10% of LRU's promotions are needed on average. Most of the locking LRU does buys nothing. They also build an offline FIFO-reinsertion that skips the reinsertions it knows won't lead to a hit, and it gets promotions down to 6% of LRU's while lowering the miss ratio by more than 1%. That one needs to see the future, so treat it as a bound, not a design.
What you can actually ship are their two new tweaks, both built on FIFO-reinsertion:
The paper reports they cut promotions a further 20 to 60% and raise promotion efficiency by more than 80% on average. They aren't identical, though. D-FR also nudges the miss ratio down, while AGE removes more promotions and pays for it with a similar or slightly higher miss ratio than plain FIFO-reinsertion on some traces.
I don't have the production traces, and the paper's repo points to a public dataset server instead of shipping a sample, so I settled for a simulator, to check whether the shape survives a synthetic workload. It uses 50,000 objects, 1,000,000 requests drawn from a Zipf distribution, a 2,500-slot cache (5% of the objects), and a skew alpha from 0.8 to 1.1. The policies are LRU, FIFO, FIFO-reinsertion with one visited bit, and Delay-LRU at delay ratios of 0.1 and 0.5. The FIFO-reinsertion part is short:
def run_fifo_reinsertion(trace, cache_size):
cache = OrderedDict() # obj -> visited bit
for obj in trace:
if obj in cache:
cache[obj] = True # hit: set the bit, nothing moves
else:
if len(cache) >= cache_size:
while True:
victim, visited = next(iter(cache.items()))
if visited:
cache.move_to_end(victim)
cache[victim] = False # the promotion
else:
del cache[victim]
break
cache[obj] = FalseHere's alpha 1.0, the same skew the paper used for its throughput tests:
FIFO-reinsertion beat LRU's miss ratio at every skew I ran, on 13% to 42% of LRU's promotions. Delay-LRU at 0.1 stayed within a hair of LRU; at 0.5 it promoted even less but missed noticeably more. LRU's own efficiency fell from 0.101 at alpha 0.8 to 0.044 at alpha 1.1, which makes sense: the more skewed the workload, the more of LRU's promotions go to hot objects that were never in danger of being evicted.
The whole run takes about two seconds. It's also one synthetic distribution in single-threaded Python with no lock anywhere, so promotions are standing in for lock cost (the paper uses promotion count the same way, as a cost metric that doesn't depend on hardware). It checks the direction. It doesn't reproduce the paper.
It isn't free of tradeoffs. The paper finds FIFO-reinsertion's throughput ceiling is lower than Delay-LRU's: Delay-LRU at a 0.1 delay ratio gets about 5x LRU's throughput at 16 threads with almost the same miss ratio, and more than 12x at 0.9, though that setting raises the miss ratio by 6% on average. So if you've profiled and the lock really is the bottleneck, Delay-LRU is worth a look. If promotions still show up after that, D-FR is the cheap next step.
And if your cache is single-threaded, or so small nobody contends for it, LRU is fine. The point isn't that LRU is wrong. It's that LRU pays for precision it rarely needs, and 0.037 is a good number to remember the next time someone says FIFO can't be trusted.
No requests yet. Play or step the stream; object 1 is the most popular.
visited bit set clear
Comments