Harvard Study Cuts Wasted Cache Promotions 20 to 60 Percent

A Harvard and Carnegie Mellon paper on cache eviction found two techniques that cut promotions by 20 to 60 percent without raising miss ratios. The study received a Best Paper Honorable Mention at the VLDB 2026 conference in Boston, which ran Aug. 31 to Sept. 4.

Assistant Professor Juncheng Yang and colleagues measured how often software caches shuffle data to the front of a queue. Those moves, called promotions, take locks, burn CPU time, and, Yang said, use energy as large caches grow with AI workloads.

Most LRU Promotions Never Earn a Hit

Least Recently Used still sits in Memcached, Nginx, Varnish, and a long list of databases. On every hit it promotes the object to the head of a doubly linked list, and the paper’s new yardstick says that habit buys almost nothing.

THE WASTE INSIDE LRU

• Hits per move: LRU’s mean promotion efficiency is 0.037, so each promotion leads to 0.037 hits.
• Oracle filter: Against Belady’s MIN, only 10 percent of LRU promotions are needed on average.
• Trace load: The comparison used 6,357 traces and 346 billion requests for 2,818 TB of data.
• Date span: The traces were collected from 2007 to 2023 across key-value, block, and object caches.

Promotion efficiency counts the hits a promotion actually produces. Delay-LRU reaches as high as 0.4 hits per promotion, and FIFO-reinsertion reaches 0.3, when the miss ratio stays within 1 percent of LRU. Batch-LRU stays under 0.1. The gap is the point of the paper: most of the moves LRU makes never turn into later hits.

Qinghan Chen of Carnegie Mellon University is the lead author, with Muhammad Haekal Muhyidin Al-Araby of Sepuluh Nopember Institute of Technology, Ziyue Qiu, Zhuofan Chen, and Rashmi Vinayak of Carnegie Mellon, and Yang at Harvard. The work ran on traces from Alibaba, CloudPhysics, Meta, Microsoft, Tencent, Twitter, Wikipedia, and two content delivery networks.

How a Promotion Turns Into a Lock

A promotion is the update that sends an object to the head of an LRU list after a hit. Because that update touches the middle of a linked list, it cannot be done with one atomic instruction, so the cache takes a lock. On a many-core server the lock becomes the bottleneck long before DRAM does.

FIFO never promotes on a hit, which is why it scales and why operators still distrust it. LRU is treated as the efficient choice, FIFO as the simple one, and that split has been in textbooks since Belady’s 1966 work. Production engineers already tried to split the difference. Meta CacheLib delays a second promotion if an object just moved. Meta’s HHVM promotes only if a try-lock succeeds. RocksDB and PostgreSQL wait until eviction and then reinsert a still-hot object. Redis samples a few objects at eviction and drops the least recently used among them.

The paper groups those shortcuts as lazy promotion: fewer list updates, less lock waiting, more requests per second. Engineers often call the same shortcuts weak LRU, on the theory that skipping moves must raise the miss ratio. The measurements say that theory is sloppy. Some of the shortcuts keep the hit rate and waste far fewer moves. Some of them do not.

Caching has been out for more than 60 years and is one of the fundamental ideas of computer science. Our work is rooted in measurement, and in trying to understand how our modern systems work.

Juncheng Yang, Assistant Professor of Computer Science, Harvard SEAS

Delay and FIFO Beat the Weak-LRU Label

The team put five production methods on the same traces, using libCacheSim, at cache sizes equal to 0.1 percent, 1 percent, and 10 percent of the working set. Miss ratios at one size still ranged from under 1 percent to more than 80 percent, because the workloads do not look alike. The ranking below uses the 1 percent size, which the authors say matches the other two.

FIVE LAZY PROMOTION METHODS ON PRODUCTION TRACES

Probabilistic-LRU can drop promotions in line with its probability, including a 90 percent cut at probability 0.1, but throughput barely moves until the probability is tiny. At probability 0.05 the miss ratio rises 6 percent on average across the traces; at 0.5 it still rises 2 percent. Random skips do not protect popular objects, and the same hot item then gets promoted from different cores, which the authors say stirs extra cache-coherence traffic.

Delay-LRU and FIFO-reinsertion are the methods that raise promotion efficiency without a miss-ratio bill. The same pair still works when the authors drop it into ARC and 2Q, two older algorithms that already use LRU queues. Batch-LRU and Probabilistic-LRU often lift misses in those designs. Reinsertion at eviction, the CLOCK or second-chance pattern, beats promotion on every hit. That is the ranking production caches have been missing.

Two Tweaks Cut Promotions Another 20 to 60 Percent

Even FIFO-reinsertion still moves too much. If that method is given future knowledge, it can drop promotions by more than 90 percent on all 6,357 traces and slightly lower the miss ratio. The authors do not ship an oracle. They ship two filters that steal part of that gap.

THE TWO NEW FILTERS

• Delayed FIFO-reinsertion (D-FR): It adds CacheLib-style delay to reinsertion, so a recently rescued object is not immediately rescued again. On a median trace it cuts promotions 60 percent versus plain FIFO-reinsertion, with a miss ratio in line with an offline FIFO-reinsertion pass.
• Age-Guided Eviction (AGE): It uses recency to throw out low-value reinsertions, so the queue does not spend a move on an object that is already old. Together with D-FR it is the source of the 20 to 60 percent cut against LRU-family promoters.

Across the production traces the two methods keep a similar or lower miss ratio and lift promotion efficiency by more than 80 percent on average. Throughput tests used a Zipfian stream of 10 million requests for 1 million objects, because a full concurrent sweep of every method and parameter on 6,357 traces would have taken more than a year. Figure captions in the paper report scaling at 16 threads. The source code and experimental data are on GitHub under cacheMon.

Systems programmers have treated lazy promotion as settled advice since SIEVE, and that is why this paper reads as a ranking rather than a new data structure. The remaining surprise is how many LRU moves still fail the new metric. Popularity is concentrated, so a second promotion of a hot object is often wasted, and a random skip hits the wrong objects. The useful move is the late one, at eviction, with a delay and an age check on top.

SIEVE and S3-FIFO Already Run in Production

Yang joined Harvard SEAS as an assistant professor of computer science in July 2025 after a Carnegie Mellon Ph.D. with Vinayak. The VLDB honorable mention is, Harvard SEAS said, the group’s fifth honored caching paper since 2023. The earlier designs are already in other people’s code, which is why a promotion metric is not an academic toy.

THE CACHING LINE BEHIND THIS PAPER

1. 2020: An OSDI study of hundreds of Twitter in-memory cache clusters maps how those systems actually miss, expire, and fill.
2. 2021: Segcache, with Yao Yue and Vinayak, wins the NSDI Community Award and uses 22 to 60 percent less memory than prior in-memory caches, with up to 40 percent higher single-thread throughput than Memcached and close to an 8x gain at 24 threads. Twitter and Momento put it in production.
3. 2023: S3-FIFO, built from three FIFO queues, beats a long list of eviction algorithms on thousands of traces and, in later talks, shows about 6x the throughput of an optimized LRU at 16 threads. Google, AWS, VMware, and Redpanda have used it.
4. 2024: SIEVE, simpler than LRU, takes the NSDI Community Award. Independent ports exist in more than 18 languages, and Yang’s talks put the count above 60 libraries, with production use at Google, VMware, Redpanda, Android, ImmuDB, and TiDB.
5. 2026: The lazy-promotion paper is presented at VLDB in Boston. A second VLDB 2026 paper from the group, Clock2Q+, targets metadata cache replacement inside VMware vSAN.

SIEVE and S3-FIFO already rest on lazy promotion and quick demotion, the idea that new junk should leave the cache fast and that popular objects should be saved with as little list surgery as possible. The new paper does not replace those designs. It scores the shortcuts already sitting in CacheLib, RocksDB, Redis, and CliqueMap, then adds D-FR and AGE on top of reinsertion. Operators who still ship a locked LRU list can steal the ranking without waiting for a full algorithm swap.

Caches Keep Shuffling Memory While Power Bills Rise

Harvard SEAS framed the award around energy, because data-center caches hold huge DRAM footprints that cost power to run and to manufacture. Yang called the promotion step energy intensive and not scalable, a bottleneck for web and server traffic. The paper itself reports promotions, misses, and thread scaling, not joules, so a 20 to 60 percent cut in moves is not a measured 20 to 60 percent cut in watts.

The room those caches sit in is still getting more expensive. The International Energy Agency puts global data-center electricity at about 415 terawatt hours in 2024, or about 1.5 percent of world electricity, after 12 percent yearly growth over five years. Its base case sends that load to about 945 TWh by 2030, growing about 15 percent a year, more than four times the rest of electricity demand. Servers account for about 60 percent of data-center electricity. Storage is about 5 percent, networking up to 5 percent, and cooling ranges from about 7 percent in efficient hyperscale sites to more than 30 percent in older enterprise rooms.

A cache that serves a hit without taking a lock spends less CPU on the request, which is the part of the stack the IEA counts inside that server share. Caches also run in CPUs, operating systems, databases, cloud services, and edge nodes, so a cheaper promotion policy travels farther than one database. The remaining headroom is still the oracle result: a FIFO-reinsertion pass with future knowledge dropped more than 90 percent of promotions on the same traces. D-FR and AGE take a slice of that. They do not close it.

Harvard SEAS posted the lab note on Sept. 8, 2026, after VLDB closed on Sept. 4 in Boston. The simulator, traces, and figure scripts are in the public cacheMon repository.

Frequently Asked Questions

What Is Lazy Promotion in Cache Eviction?

Lazy promotion delays the move that would send a hot object to the head of the queue, often until eviction time. CLOCK, also called second chance, is the classic form: an object that has been touched gets another pass instead of being copied to the front on every hit. LRU promotes on every hit, and FIFO promotes on none. The VLDB study also tested Redis-style Random-LRU, which the authors say is not technically lazy promotion because it never promotes at all; it samples a few objects at eviction and drops the least recently used among them.

What Does Promotion Efficiency Measure?

It is the extra hits a method wins over FIFO, divided by the number of promotions it performs, written as (FIFO misses minus method misses) divided by that method’s promotion count. FIFO is the baseline because it performs no promotions. A higher number means each remaining move is doing more work. The paper reports that metric at a cache size equal to 1 percent of the working set after checking that 0.1 percent and 10 percent showed the same pattern, and it logged 16,625 TB of request traffic across 25 billion objects.

Who Wrote the VLDB Lazy Promotion Paper?

Qinghan Chen, Ziyue Qiu, Zhuofan Chen, and Rashmi Vinayak at Carnegie Mellon University, Muhammad Haekal Muhyidin Al-Araby at Sepuluh Nopember Institute of Technology in Surabaya, and Juncheng Yang at Harvard University. It appears in Proceedings of the VLDB Endowment volume 19, number 4, pages 549 to 562, issued for the 2026 Boston conference, with a DOI of 10.14778/3785297.3785299, and the arXiv copy was posted Aug. 30, 2026.

How Did the Team Measure Throughput on Thousands of Traces?

Miss-ratio tests used libCacheSim on the full set of 6,357 traces. Concurrent throughput tests could not be run that way, because a full sweep of every method and parameter would have taken more than a year and because parallel throughput runs interfere with one another. They used a synthetic Zipfian trace of 10 million requests for 1 million unique objects, with a skewness parameter of 1.0 chosen to match cache access patterns in the real traces, and they compared methods at the same miss ratio, presenting the 1 percent miss-ratio case.