PaperlayerView exact revision on arXiv

Source-linked AI summary

Demystifying and Improving Lazy Promotion in Cache Eviction

Qinghan Chen, Muhammad Haekal Muhyidin Al-Araby, Ziyue Qiu, Zhuofan Chen, Rashmi Vinayak, Juncheng Yang

arXiv:2608.29993v1cs.DB

TL;DR

Cache eviction needs to balance LRU’s cache efficiency against the scalability cost of frequent, locked promotions, while the effectiveness of deployed Lazy Promotion techniques remains insufficiently understood. The paper benchmarks five techniques on 6357 production traces, introduces promotion efficiency, and evaluates advanced algorithms. Delay-LRU and FIFO-reinsertion perform best; D-FR and AGE reduce promotions by 20%–60% with a lower or similar miss ratio, while only 10% of LRU promotions are needed on average under oracle knowledge.

  • Problem

    The paper addresses limited understanding of whether Lazy Promotion improves scalability and reduces promotions while maintaining cache miss ratio.

  • Method

    The paper benchmarks five Lazy Promotion techniques on 6357 production traces and integrates them into ARC and 2Q while measuring promotion efficiency.

  • Results

    Delay-LRU and FIFO-reinsertion are most effective, while D-FR and AGE reduce promotions by 20%–60% with a lower or similar miss ratio.

  • Takeaways & Limitations

    Most LRU promotions are unnecessary, and D-FR and AGE provide practical ways to reduce promotions without compromising miss ratios.

  • Takeaways & Limitations

    The evaluation assumes miss ratio is deterministic and independent of the underlying hardware, and production Probabilistic-LRU implementations may vary their probability with contention.

Abstract

from arXiv · show

Cache eviction algorithms play a critical role in the performance of modern data systems, yet their scalability is often limited by the high computational overhead associated with object promotions. Lazy Promotion techniques have emerged as relaxations of traditional Least-Recently-Used (LRU) methods, designed to alleviate lock contention and increase throughput. This work uses production traces from real-world systems to benchmark five Lazy Promotion strategies: Probabilistic-LRU, Batch-LRU, Delay-LRU, FIFO-reinsertion, and Random-LRU. We evaluate these techniques across miss ratio, scalability, promotion count, and a novel metric called promotion efficiency, which measures the number of hits per promotion. Our results reveal that Delay-LRU and FIFO-reinsertion significantly improve promotion efficiency, whereas Batch-LRU and Probabilistic-LRU struggle to reduce promotions without significantly increasing miss ratio. We further explore the impact of lazy promotion in advanced algorithms such as ARC and 2Q and make a similar observation. Moreover, we uncover substantial optimization potential, showing that most cache promotions are unnecessary when equipped with oracle knowledge. To further reduce promotions in LRU, we propose two novel enhancements-Delayed FIFO-reinsertion (D-FR) and Age-Guided Eviction (AGE)-that reduce promotions by 20-60% while achieving a similar or lower miss ratio.

1 INTRODUCTION

Lazy Promotion relaxes LRU promotions to address scalability bottlenecks, but its effectiveness and tradeoffs have been poorly understood. This paper benchmarks five techniques on production traces, identifies the strongest approaches, and introduces methods that reduce promotions while preserving miss ratio.

  • Motivation: LRU’s linked-list promotions require locking, limiting throughput on multicore systems despite its lower miss ratio than FIFO.Each access promotes an object to the list head, while middle-list operations cannot be performed atomically.
  • Motivation: Production systems use Lazy Promotion relaxations to reduce promotions and lock contention, including delayed, probabilistic, batched, and FIFO-based approaches.The paper names Cachelib, HHVM, Segcache, Cliquemap, RocksDB, and PostgreSQL as examples.
  • Evaluation: 6357 production traces totaling 346 billion requests benchmark five Lazy Promotion techniques across miss ratio, scalability, promotion count, and promotion efficiency.The traces cover systems from nine companies and 2,818 TB of data.
  • Findings: Delay-LRU and FIFO-reinsertion are most effective, while Batch-LRU achieves less than 0.1 hits per promotion and Probabilistic-LRU performs worst.Probabilistic-LRU reduces promotions randomly without distinguishing popular from unpopular objects.
  • Optimization opportunity: Only 10% of LRU promotions are needed on average according to Belady’s MIN, revealing substantial opportunity to eliminate unnecessary promotions.With future knowledge, FIFO-reinsertion reduces promotions by over 90% on average while slightly reducing miss ratio.
  • Proposed techniques: D-FR and AGE reduce promotions by 20%–60% while achieving a lower or similar miss ratio and improving average promotion efficiency by more than 80%.D-FR delays FIFO-reinsertion, whereas AGE uses recency information to filter unnecessary reinsertions.

2 BACKGROUND AND MOTIVATION

Caching balances efficiency and scalability through eviction policies that determine which objects remain in a full cache. LRU favors recency but requires promotion-related locking, motivating Lazy Promotion techniques that reduce hit-time promotion overhead.

  • Software cache and eviction algorithm: Caching stores popular objects on fast storage so requests can be served quickly and backend access can be reduced.The paper cites databases, operating systems, and compute-storage disaggregated architectures as caching contexts.
  • Software cache and eviction algorithm: Eviction algorithms determine which objects remain in a full cache and the order in which they are evicted.The choice of eviction algorithm affects cache efficiency and scalability.
  • LRU and FIFO: LRU retains recently accessed objects and usually achieves high efficiency but poor scalability because every hit promotes an object under a global lock.Promotion moves the accessed object to the head of a doubly linked list.
  • LRU and FIFO: FIFO improves scalability by avoiding promotions and hit-time locking, but often has poor efficiency because it ignores access patterns.LRU promotes every object upon a hit, whereas FIFO promotes none.
  • Lazy promotion techniques: Lazy Promotion relaxes LRU by reducing promotion frequency during cache hits while seeking to maintain a low miss ratio.Probabilistic-LRU skips promotions when try-lock fails, while Batch-LRU performs promotions in batches.
  • Lazy promotion techniques: Delay-LRU promotes an object only after a tunable delay since its last promotion, trading fewer promotions against potential miss-ratio increases.The technique relies on popular objects not requiring frequent promotion to remain cached.

3 HOW DO EXISTING LAZY PROMOTION TECHNIQUES PERFORM?

Existing Lazy Promotion techniques trade promotion reduction against throughput, miss ratio, and scalability in markedly different ways. Delay-LRU and FIFO-reinsertion provide the strongest overall benefits, while Probabilistic-LRU and Batch-LRU expose important workload or efficiency trade-offs.

  • Probabilistic-LRU: Probabilistic-LRU reduces promotions without distinguishing popular from unpopular objects, leaving popular-object promotions and coherence overhead that limit throughput gains.Significant throughput increases appear only at very small probabilities, where miss ratio rises substantially.
  • Probabilistic-LRU: A 90% promotion reduction at prob 0.1 does not translate into substantial throughput gains, while prob 0.05 raises miss ratio by 6% on average.At prob 0.5, miss ratio still increases by 2% on average.
  • Batch-LRU: Batch-LRU can reduce promotions and improve throughput while maintaining a miss ratio similar to LRU, but its effectiveness varies heavily across workloads.At batch ratio 0.1, throughput increases by more than 4× at 16 threads, while promotion reduction varies substantially across traces.
  • Delay-LRU: At delay ratio 0.1, Delay-LRU reduces promotions to 24% of LRU on average and delivers 5× higher throughput at 16 threads without visibly increasing miss ratio.The results indicate that approximately 76% of promotions occur soon after the previous request to the same object.
  • Delay-LRU: Delay-LRU maintains consistent benefits across diverse workloads, but larger delay ratios increase throughput further while raising miss ratio by 6% on average at delay ratio 0.9.At delay ratio 0.1, 39.5% of traces show no miss-ratio increase.
  • FIFO-reinsertion: FIFO-reinsertion reduces promotions by up to 80% with one frequency bit and can lower LRU’s miss ratio by almost 2% with a 2-bit counter, but its scalability is below Delay-LRU.Larger frequency caps can retain short-lived popular objects too long, eventually increasing miss ratio.

4 CAN LAZY PROMOTIONS BE LAZIER WITH FUTURE INFORMATION?

Future information shows that cache ranking and many promotions are unnecessary. Offline FIFO-reinsertion filters promotions using future access times, substantially reducing promotions without increasing miss ratio.

  • Belady early eviction uses future reuse distances to remove cold objects before eviction is otherwise required.
  • Belady-Random and Belady-RandomLRU have similar miss ratios, indicating that eviction ranking is largely unimportant with early-eviction signals.
  • At tolerance factor 5, Belady early eviction achieves a 14% average miss-ratio reduction versus LRU.
  • Offline FIFO-reinsertion removes promotions whose next access is too far in the future and reduces promotions from LRU by more than 90%.
  • Offline FIFO-reinsertion achieves promotion efficiency above 0.8, with each promotion reducing 0.8 cache misses.

5 PRACTICAL LAZIER PROMOTION

D-FR and AGE make FIFO-reinsertion lazier without requiring future information. D-FR preserves or improves miss ratio while AGE filters more promotions with a modest miss-ratio trade-off on some traces.

  • 5.1 Delayed FIFO-reinsertion (D-FR): D-FR suppresses clustered hits by delaying frequency updates and makes promotion decisions at eviction time.
  • 5.1 Delayed FIFO-reinsertion (D-FR): Compared with FIFO-reinsertion, D-FR reduces promotions by 60% for a median trace.
  • 5.1 Delayed FIFO-reinsertion (D-FR): D-FR reduces miss ratio similarly to offline FIFO-reinsertion and achieves higher promotion efficiency than existing Lazy Promotion techniques.
  • 5.1 Delayed FIFO-reinsertion (D-FR): Larger D-FR delay ratios reduce more promotions but produce slightly higher miss ratios; D-FR remains below LRU in miss ratio.
  • 5.2 Age guided eviction (AGE): AGE filters FIFO-reinsertions when object age exceeds a threshold estimated with a tolerance factor.
  • 5.2 Age guided eviction (AGE): AGE reduces more promotions than D-FR but has similar or slightly higher miss ratio than FIFO-reinsertion, with promotion efficiency around 48%.
  • 5.2 Age guided eviction (AGE): A smaller AGE factor filters promotions more aggressively while increasing miss ratio; sufficiently large factors reproduce FIFO-reinsertion.

6 RELATED WORK

Prior work established Lazy Promotion as a scalability technique, but this paper addresses the limited evaluation of widely deployed variants. It connects promotion contention with cache throughput and shows that low-value promotions can be suppressed while preserving miss ratio.

  • Lazy Promotion was introduced to improve throughput and scalability, alongside quick demotion to improve cache efficiency.
  • Existing studies often evaluate proposed eviction algorithms without deeply examining alternatives that were not introduced in the paper.
  • Prior work found that aggressively increasing hit ratio can hurt cache throughput because of promotion contention.
  • This work reports that suppressing low-value promotions can preserve miss ratio while significantly improving scalability.
  • The paper presents its study as the first examination of the effectiveness of widely deployed Lazy Promotion techniques.

7 CONCLUSION

The evaluation finds that Delay-LRU and FIFO-reinsertion reduce promotions while maintaining miss ratios, while Probabilistic-LRU and Batch-LRU have important drawbacks. D-FR and AGE further reduce promotions without compromising miss ratios.

  • Delay-LRU and FIFO-reinsertion reduce promotions while maintaining miss ratios.
  • Probabilistic-LRU increases miss ratios, while Batch-LRU is heavily workload-dependent.
  • Most cache promotions are unnecessary, exposing considerable opportunities for optimization.
  • D-FR and AGE reduce promotions without compromising miss ratios.
Loading 2608.29993v1…