One-sentence Summary

Carnegie Mellon University, Al-Araby Sepuluh Nopember Institute of Technology, and Harvard University benchmark five Lazy Promotion strategies on production traces, introduce a promotion efficiency metric measuring hits per promotion, and propose two novel enhancements, Delayed FIFO-reinsertion and Age-Guided Eviction, that reduce cache promotions by $20\text{--}60\%$20–60% while maintaining comparable miss ratios.

Key Contributions

• Benchmarks Probabilistic-LRU, Batch-LRU, Delay-LRU, FIFO-reinsertion, and Random-LRU on 6357 production traces using miss ratio, scalability, promotion count, and promotion efficiency. Delay-LRU and FIFO-reinsertion improve promotion efficiency more than Batch-LRU and Probabilistic-LRU, and a similar observation extends to ARC and 2Q.

• Oracle-knowledge analysis identifies that most cache promotions are unnecessary, revealing an opportunity to reduce promotion operations while preserving miss ratio.

• Introduces Delayed FIFO-reinsertion and Age-Guided Eviction for LRU, reducing promotions by 20-60% while achieving similar or lower miss ratios.

Introduction

Caching is central to databases, operating systems, and content delivery networks because keeping popular data close to users reduces latency and backend load. However, the most efficient common eviction algorithm, LRU, relies on promotions that require locks, creating scalability bottlenecks on multicore servers. Production systems have adopted lazy promotion variants to reduce lock contention, but these techniques have lacked a systematic evaluation of whether they preserve miss ratio and which are actually useful. The authors leverage thousands of production traces to benchmark five real-world lazy promotion strategies, introduce a promotion efficiency metric, and show that Delay-LRU and FIFO-reinsertion can preserve near LRU miss ratios while greatly reducing promotions. They also discover that most LRU promotions are unnecessary and propose two lightweight methods, D-FR and AGE, that remove many low value promotions without worsening cache efficiency.

Dataset

• The authors use a large, real-world cache trace dataset to evaluate lazy promotion techniques. The trace data and source code are released through the paper artifact at https://github.com/cacheMon/Lazy-Promotions.

• The dataset is assembled from traces collected between 2007 and 2023 across several public and private production environments, including Alibaba, CloudPhysics, FIU, Meta, Tencent, Wikipedia, and two private CDN service companies.

• The traces cover multiple cache workloads, including key-value caches, block caches, and object caches. In total, the dataset contains 6,357 traces, 346 billion requests, 25 billion unique objects, 16,625 TB of traffic, and 2,818 TB of data.

• The provided text does not give per-source details such as individual trace counts, request volumes, traffic sizes, or time ranges for every subset. Those detailed subset-level statistics are summarized in Table 2 of the paper.

• The authors do not use the traces as supervised training data or split them into train and test partitions. Instead, the traces are replayed as evaluation workloads through libCacheSim to measure miss ratio behavior for different lazy promotion policies.

• For miss ratio evaluation, the authors replay real-world traces across cache-size settings equal to 0.1%, 1%, and 10% of the trace working set size, where the working set size is the total number of unique objects in the trace.

• Because the real-world traces have very different access patterns, miss ratios at the same cache-size percentage vary widely, ranging from below 1% to above 80%. The authors use LRU as the baseline and report relative miss ratios as miss_A / miss_LRU for the technique being evaluated.

• For miss ratio reporting, the authors aggregate results across the trace collection using box plots. The box shows the 25th and 75th percentiles, while the whiskers show the 10th and 90th percentiles.

• For throughput and scalability analysis, the authors do not replay all 6,357 real-world traces because that would require more than a year and parallel measurements can introduce interference. They instead construct a synthetic Zipfian trace with 10 million requests over 1 million unique objects and skewness parameter 1.0.

• The synthetic Zipfian subset is used as a controlled performance benchmark intended to approximate the access skew observed in real cache workloads. The authors adjust cache sizes across techniques so that all evaluated methods reach comparable miss ratios before comparing throughput.

• The paper does not describe trace cropping, deduplication, filtering based on object metadata, or construction of new metadata fields beyond the workload attributes already present in the traces. The only processing details shown are trace replay, cache-size normalization to working set size, baseline-relative miss ratio calculation, and replacement of full real-world replay with a synthetic trace for scalability measurement.

Method

The authors design a promotion-aware caching architecture that separates object access bookkeeping from expensive rank updates. The core problem they address is that traditional LRU-style promotion modifies shared metadata on every cache hit, which creates locking overhead and limits scalability under concurrent workloads. To mitigate this, the system replaces immediate per-hit promotion with deferred promotion, eviction-time reinsertion, or filtered reinsertion, while preserving enough recency and frequency information to maintain a low miss ratio.

At a high level, the method can be viewed as a set of interchangeable modules that control when and whether an accessed object is rewarded in the cache replacement order. Batch-LRU buffers requested object identifiers and performs promotions periodically. If the requested object identifier is 8 bytes, a batch of 128 identifiers uses only about 1 KB of additional memory. The frequency of batched promotion is controlled by a batch ratio, defined relative to cache size. A batch ratio of $0.1$0.1 means that a batched promotion occurs after approximately $0.1$0.1 times the cache size in insertions. This mechanism coalesces multiple accesses to popular objects into fewer promotion operations, reducing contention more effectively on skewed workloads where many accesses concentrate on a small set of hot objects.

Delay-LRU takes a different path by suppressing promotions that occur too soon after a previous promotion. Each object stores a small timestamp, and a cache hit causes promotion only if enough insertions have elapsed since the object’s last promotion. The delay is parameterized as a delay ratio, defined as the delay interval divided by cache size. Because many promotions occur shortly after a prior request to the same object, delaying them can remove redundant promotion traffic while adding little miss penalty. This approach is especially effective when promotions provide only small ordering benefits for already popular objects.

FIFO-reinsertion shifts the promotion decision from cache-hit time to cache-eviction time. Objects remain in a FIFO queue without order changes on hits. Each object maintains a capped frequency counter. On a hit, the counter increments by one up to a cap determined by the number of counter bits. During eviction, if the counter is greater than zero, the object is reinserted into the cache and its counter is decremented by one. If the counter is zero, the object is evicted. This design counts reinsertions as promotions and tends to reduce promotion overhead most when the frequency cap is small. The method also improves cache efficiency relative to LRU in many cases because it avoids immediately discarding objects that have shown some popularity, while still keeping the queue simple and avoiding expensive promotion on every hit.

Random-LRU is considered as a related scalability-oriented alternative rather than a lazy promotion technique. It samples objects during eviction and evicts the least recently used sample. Because it does not maintain a global linked list or require locking on cache hits, it improves concurrency. However, it can damage cache efficiency if the sample size is too small. Using one sample degenerates into random eviction, while increasing the sample size reduces throughput. A moderate number of samples provides a tradeoff between scalability and miss ratio.

The authors then use future information as an analytical tool to determine how much promotion is fundamentally necessary. They define the reuse distance of an object $o$o as $R(o)$R(o), the number of requests until its next access. The average eviction age is approximated as

With oracle knowledge, an object can be evicted early if

where $\alpha$α is a tolerance factor. The key insight is that ranking cached objects for eviction is often unnecessary. If a binary signal can determine whether an object will be requested before it would naturally be evicted, the system can proactively remove cold objects without maintaining a precise LRU order. This suggests that strong future predictions can support even lazier promotion policies.

Building on this oracle analysis, the authors design an offline version of FIFO-reinsertion. It runs multiple iterations over a trace. In the first iteration, it behaves like standard FIFO-reinsertion and marks reinsertions that do not lead to future cache hits. In later iterations, those marked promotions are omitted. This oracle-guided filtering removes promotions that do not contribute to cache hits, showing that many promotions can be eliminated without hurting, and sometimes improving, cache efficiency.

The practical method derived from these insights is Delayed FIFO-reinsertion, or D-FR. D-FR combines delay-based filtering with eviction-time reinsertion. It tracks the last access time and insertion time of each object using a small timestamp, typically 4 bytes per object. On a cache hit, if the current access falls within a delay-time threshold, the frequency counter is not incremented. The delay ratio controls this threshold. By suppressing frequency increments for clustered hits, D-FR prevents the cache from over-rewarding objects that are accessed repeatedly in a short window. At eviction time, D-FR still uses the frequency counter to decide whether to reinsert or evict the object. Because the decision happens at eviction, where more information is available, and because many metadata updates are avoided, D-FR can reduce promotion count while improving throughput relative to FIFO-reinsertion.

Age-Guided Eviction, or AGE, is a complementary filtering mechanism built on FIFO-reinsertion. Instead of relying only on frequency, AGE considers object age. If the time since an object’s last access exceeds a threshold, the object is treated as unlikely to receive a future request, and it is not promoted during eviction. The threshold is derived from the same approximate eviction-age estimator:

where $C$C is cache size and $m$m is miss ratio. Given a tolerance factor $\alpha$α, AGE may skip promotion when the object age $t(o)$t(o) satisfies

This module reduces promotions by filtering out reinsertions for objects that are infrequent or stale, although it can increase miss ratio compared with D-FR depending on the workload.

When D-FR and AGE are compared with earlier promotion-reduction designs, both can substantially reduce promotion volume while preserving competitive miss ratios. The relative effectiveness of each technique depends on how aggressively promotions are filtered and how the workload distributes accesses across hot and cold objects. As shown in the figure below:

The parameter sensitivity of D-FR is also important to the design. D-FR is relatively robust to changes in delay ratio across a practical range. Increasing the delay ratio tends to reduce promotions further, with only modest impact on miss ratio. This behavior contrasts with simpler delayed promotion schemes, where larger delays can degrade efficiency more noticeably. The stability of D-FR under different delay ratios supports its use as a practical lazy promotion mechanism. The sensitivity to the delay ratio is shown in the figure below:

Experiment

The evaluation replays diverse real-world cache traces and uses controlled synthetic workloads to compare LRU and several lazy promotion variants, measuring miss ratio, scalability, promotion count, and promotion efficiency. These experiments show that random and batched promotions either degrade miss ratio or depend heavily on workload skew, while delay-based and reinsertion-based methods better avoid low-value promotions and preserve cache efficiency. Additional tests on advanced eviction policies show the same promotion bottlenecks, and oracle-guided analysis indicates that eviction-time decisions can make traditional ranking-based promotions largely unnecessary.

The listed lazy promotion techniques relax strict LRU promotion to reduce lock contention and improve scalability while keeping miss ratios competitive. They differ by skipping recent or probabilistic promotions, batching updates, deferring promotion decisions to eviction, or using random sampling instead of maintaining a fully ordered list. Delay-LRU skips recent promotions to avoid promoting objects that are hit multiple times in a short window. Probabilistic-LRU bypasses promotions when locks are unavailable, reducing contention under heavy concurrency. Batch-LRU groups promotions over fixed intervals to reduce the number of expensive lock operations. FIFO-reinsertion postpones promotion decisions until eviction, making the replacement decision more informed. Random-LRU samples eviction candidates and uses last access times, avoiding hit-time list maintenance.

The dataset collection includes a wide range of real-world block and object cache traces from public and private sources across multiple years. It covers workloads from databases, CDNs, photo services, and other production systems, with a scale sufficient to evaluate cache behavior over very different working sets. The dataset description also notes that older traces are filtered to keep only workloads with at least one million requests. The benchmark relies on a diverse mix of block and object cache traces from many real-world sources. The trace collection spans older and newer production environments, with very large numbers of requests and TB-scale traffic.

Experiments evaluate lazy LRU promotion techniques on a large and diverse collection of real-world block and object cache traces from databases, CDNs, photo services, and other production systems. They examine whether relaxed promotion can reduce lock contention and improve scalability while preserving competitive miss ratios. The results support a qualitative conclusion that different lazy promotion strategies, such as skipping recent hits, bypassing unavailable locks, batching updates, deferring decisions to eviction, or sampling candidates, can achieve favorable performance tradeoffs across realistic cache workloads.