Bibliographic Information

• Title: 3L-Cache: Low Overhead and Precise Learning-based Eviction Policy for Caches
• Authors: Wenbin Zhou, Zhixiong Niu, Yongqiang Xiong, Juan Fang, Qian Wang
• Affiliations: The authors are affiliated with Beijing University of Technology and Microsoft Research.
• Journal/Conference: The paper was published in the Proceedings of the 23rd USENIX Conference on File and Storage Technologies (FAST '25). The FAST conference is a premier academic venue for research in storage systems, widely recognized for its high quality and impact in the field.
• Publication Year: 2025. (Note: The paper is for a conference scheduled in February 2025, indicating it was likely accepted for publication in late 2024.)
• Abstract: The paper addresses the high computational overhead of learning-based cache eviction policies, which limits their practical deployment. It introduces 3L-Cache, a novel object-level learning policy designed for Low overhead, the Lowest object miss ratio, and the Lowest byte miss ratio. To achieve low overhead, 3L-Cache incorporates two key innovations: 1) an efficient training data collection scheme that filters unnecessary data and dynamically adjusts training frequency, and 2) a low-overhead eviction method using bidirectional sampling and an efficient eviction strategy. The policy also includes a parameter auto-tuning method for adaptability. Evaluated on 4,855 traces, 3L-Cache is shown to reduce average CPU overhead by 60.9% compared to HALP and 94.9% compared to LRB, while outperforming twelve state-of-the-art policies in either byte or object miss ratio.
• Original Source Link: The full paper is available at: https://www.usenix.org/system/files/fast25-zhou-wenbin.pdf. It is an accepted paper for a future conference.

Executive Summary

Background & Motivation (Why)

• Core Problem: Caching is essential for reducing latency and network traffic in modern systems. While advanced learning-based eviction policies have been developed that significantly improve cache performance (i.e., lower miss ratios) compared to traditional heuristic policies like LRU, they come at a cost: prohibitively high computational overhead. This overhead, sometimes over 100 times that of LRU, makes deploying these policies in large-scale production environments, like Content Delivery Networks (CDNs), economically unfeasible.
• Existing Gaps: The paper's analysis shows that existing learning-based policies fall into a few categories, none of which are ideal. Object-level learning policies (e.g., LRB, HALP) offer the best miss ratios by predicting the reuse distance of individual objects, but they also suffer from the highest CPU overhead due to fine-grained training and prediction. Other categories like policy-level and group-level learning have lower overhead but compromise on miss ratios. The central challenge is to create a policy that achieves the superior miss ratios of object-level learning without its crippling overhead.
• Novel Approach: This paper introduces 3L-Cache, an object-level learning policy specifically engineered to minimize computational overhead while maintaining or even improving miss ratios. The core innovation lies in methodically identifying and eliminating computational waste in the two most expensive components: model training and prediction. It does this through an efficient data collection scheme, a novel bidirectional sampling policy for eviction candidates, and an auto-tuning mechanism to ensure robust performance across diverse workloads.

Main Contributions / Findings (What)

The paper makes the following primary contributions:

1. Comprehensive Evaluation Framework: It is the first work to evaluate a wide range of representative cache eviction policies (both heuristic and learning-based) across three critical metrics simultaneously: byte miss ratio, object miss ratio, and computation overhead.
2. Overhead Reduction in Object-Level Learning: It identifies and quantifies the significant potential for reducing CPU overhead in the training and prediction phases of object-level learning policies without negatively impacting accuracy.
3. Design and Implementation of 3L-Cache: It proposes 3L-Cache, a novel policy that achieves low overhead and state-of-the-art miss ratios. Its key components include:
   • An efficient online training scheme that reduces training frequency without losing model accuracy.
   • A low-overhead eviction mechanism that uses a bidirectional sampling policy to find unpopular objects and an efficient strategy to select victims.
   • An auto-tuning module that adapts policy parameters to different workloads with low overhead.
4. Extensive Experimental Validation: The authors evaluate 3L-Cache against eleven other policies on a massive and diverse collection of 4,855 production traces. The results show 3L-Cache reduces CPU overhead by up to 94.9% compared to LRB and achieves the best miss ratios on a majority of the traces.
5. Generalizability of Techniques: The paper demonstrates that the core overhead-reduction techniques of 3L-Cache can be applied to other object-level policies, successfully reducing LRB's CPU overhead by 80%.

Prerequisite Knowledge & Related Work

Foundational Concepts

• Cache: A smaller, faster memory layer that stores copies of frequently or recently accessed data items (called "objects") from a larger, slower main data store (the "origin server"). When a requested object is found in the cache (a "cache hit"), it can be served quickly, reducing latency. If it's not found (a "cache miss"), it must be fetched from the origin, which is slower.
• Eviction Policy: The algorithm that decides which object(s) to remove ("evict") from the cache when it is full and a new object needs to be stored. The effectiveness of the eviction policy is the primary determinant of the cache's performance.
• Miss Ratios:
  • Object Miss Ratio (OMR): The fraction of total requests that result in a cache miss. A lower OMR means faster average response times.
  • Byte Miss Ratio (BMR): The fraction of total requested bytes that result in a cache miss. This is important for systems like CDNs, where the goal is to reduce network traffic to the origin server. A lower BMR means less data is transferred over the network.
• Least Recently Used (LRU): A simple and widely used heuristic eviction policy. It evicts the object that has not been accessed for the longest period. It works well for workloads with good temporal locality (recently used items are likely to be used again soon) but performs poorly on other access patterns. It serves as a common baseline for comparison.
• Belady's MIN Algorithm: The theoretically optimal offline eviction algorithm. It evicts the object that will be requested again furthest in the future. Since this requires future knowledge, it is impossible to implement in a real online system but serves as an ideal benchmark that learning-based policies aim to approximate.
• Gradient Boosting Machine (GBM): A powerful machine learning ensemble technique that builds a prediction model in the form of a collection of weak prediction models, typically decision trees. It builds the model in a stage-wise fashion, where each new tree corrects the errors of the previous ones. It is known for its high accuracy and efficiency.

Previous Works & Technological Evolution

The paper categorizes cache eviction policies into two main eras: heuristic and learning-based.

• Heuristic Policies: These policies use simple, hand-crafted rules based on object features like recency, frequency, and size.

  • Examples: LRU (recency), LFU (frequency), ARC (adapts between recency and frequency), GDSF (considers size and frequency), and recent high-performance heuristics like S3-FIFO and SIEVE.
  • Limitation: While often efficient, their performance is unstable and can vary dramatically across different workload patterns. No single heuristic performs best everywhere.

• Learning-based Policies: These policies use machine learning models to predict the future utility of an object and make more intelligent eviction decisions. The paper divides them into three sub-categories:

  1. Policy-level Learning: These policies use reinforcement learning (RL) to dynamically choose the best eviction policy from a small set of predefined heuristics (e.g., LRU and LFU).
     • Examples: LeCaR, CACHEUS.
     • Limitation: They suffer from delayed adaptation. When the workload pattern changes, the RL agent takes time to learn the new optimal strategy, leading to suboptimal performance during the transition.
  2. Group-level Learning: This approach clusters similar objects into groups and performs learning and eviction at the group level to reduce overhead.
     • Example: GL-Cache.
     • Limitation: Its performance is highly dependent on the grouping strategy (e.g., GL-Cache's grouping by arrival time) and the definition of group utility, which may not be effective for all workloads. The paper notes it performs well only on a limited number of traces.
  3. Object-level Learning: This is the most precise but also most expensive approach. It trains a model to make a prediction for each individual object, often aiming to predict its next reuse time to mimic Belady's MIN algorithm.
     • Examples: LRB, HALP, Raven, Parrot.
     • Limitation: The fine-grained nature of per-object prediction and training leads to extremely high CPU overhead, making them impractical for production deployment.

Differentiation

3L-Cache belongs to the object-level learning category but directly confronts its primary weakness: high overhead. While previous policies like LRB and HALP focused almost exclusively on maximizing miss ratio reduction, 3L-Cache is designed from the ground up to achieve a three-way balance between byte miss ratio, object miss ratio, and CPU overhead. Its key differentiators from other object-level policies are its pragmatic engineering solutions to reduce computational waste:

• Instead of naive random sampling for eviction candidates (LRB, HALP), 3L-Cache uses a targeted bidirectional sampling policy to find unpopular objects more efficiently.
• Instead of fixed, high-frequency training, 3L-Cache uses an adaptive training data collection scheme to reduce training overhead without compromising accuracy.
• It introduces an auto-tuning module to adapt its internal parameters to diverse workloads, improving generalizability.

Methodology (Core Technology & Implementation Details)

3L-Cache is designed to reduce the high CPU overhead of object-level learning policies by optimizing the two most expensive components: online training and object eviction. Figure 4 provides a high-level overview of its architecture.

该图像是论文中图4的示意图，展示了3L-Cache的整体架构，包括训练数据收集、双向采样策略、效率对象驱逐和参数自动调节四个核心模块，反映了各模块间的数据流和交互关系。

Online Training

The goal of the online training module is to maintain an accurate prediction model with minimal computational cost. This is achieved through an efficient training data collection scheme and the use of a GBM model.

Training Data Collection

This scheme addresses two problems: determining the right amount of historical data to keep and filtering unnecessary requests to reduce training frequency.

• Sliding Window Size: The policy maintains a sliding window of historical requests. The size of this window is critical; too small, and the model lacks information; too large, and it includes outdated patterns. Instead of expensive trial-and-error, 3L-Cache uses a coarse-grained dynamic adjustment. The window size is set to contain a number of unique objects equal to $h_{sw}$ times the number of objects currently in the cache, where $h_{sw}$ is a tunable integer. This allows the window to adapt quickly to changes in cache size and workload.
• Sampling and Labeling: To avoid training data being dominated by very popular objects, 3L-Cache samples objects, not requests. When a request arrives, one object within the sliding window is randomly sampled. To filter redundant information, if a previously sampled object is chosen again before its next request, it is not recorded a second time.
  • Labeling: When a sampled object is requested again, the time interval until this new request is used as the training label (the ground truth value for the "next-arrival-time"). If a sampled object is evicted from the sliding window without being re-requested, it is labeled with a very large value to teach the model to distinguish it from objects that are eventually reused.
• Training Trigger: The GBM model is retrained after a fixed number of labeled entries, $M$, are collected. The paper sets $M = 64,000$, finding this value provides a good balance between model freshness and training overhead.

GBM Model

• Model Choice: 3L-Cache uses a Gradient Boosting Machine (GBM) to predict the log(next-arrival-time-interval) for an object. GBM is chosen for its ability to handle missing features gracefully (e.g., when an object has fewer than three past requests) and its proven high performance in similar prediction tasks.
• Input Features: The model uses six simple yet effective features for each object:
  1. age: Time elapsed since the object's last request.
  2. size: The size of the object in bytes.
  3. frequency: The number of times the object was requested within the sliding window.
  4. inter-arrival times (x3): The time intervals between the three most recent requests for the object.

Cached Object Eviction

This is the second major area of innovation, designed to reduce the prediction overhead associated with finding victim objects.

Bidirectional Sampling Policy

Instead of randomly sampling candidates from the entire cache, 3L-Cache uses a two-pronged approach to find unpopular objects more efficiently.

该图像是图5，展示了双向采样策略的示意图，描述了在缓存队列中从头部和尾部采样以选择待驱逐对象的过程，体现了缓存中插入、移动和驱逐操作的流程。

• Sampling from the tail: Based on the observation that unpopular objects tend to accumulate at the tail of an LRU-like queue, this method samples from the end of the cache. It samples all objects in the last $x\%$ of the queue and conditionally samples objects with a low access frequency ($f$) from the rest of the queue. This is designed to capture "one-hit wonders" and stale objects.
• Sampling from the head: To handle newly arrived objects that may be unpopular, this method samples from the head of the queue. It uses a separate recorded queue to track newly arrived objects. When the space occupied by these new objects exceeds a threshold $Q\%$, it samples the oldest ones (those that have resided in the cache the longest among the new arrivals) as eviction candidates.

Object Eviction

Once a pool of eviction candidates is sampled, this component decides how many to evict and which ones.

• Eviction Ratio: 3L-Cache sets a fixed eviction ratio of 1/2. This means for every two candidates sampled and predicted, one will eventually be evicted. This high ratio dramatically reduces the number of predictions needed per eviction compared to LRB (1/64) and HALP (1/4). The paper justifies this by noting that the two sampling methods generate a balanced number of candidates, and this ratio effectively minimizes CPU overhead without a sharp increase in miss ratio.
• Efficient Management of Candidates: To efficiently manage a large pool of eviction candidates and always evict the one with the worst predicted score (furthest next request time), 3L-Cache uses a combination of a max heap and a hash table.
  • The max heap stores the prediction scores, allowing for O(1) access to the top candidate (the worst object).
  • The hash table maps an object ID to its latest valid prediction score.
  • Workflow: When an object is evicted, the top element is popped from the heap. A crucial validation step checks if the score from the heap matches the score in the hash table. If not, it means the heap entry was stale (e.g., the object was re-accessed, or a newer prediction was made), and the process repeats. This ensures that only valid candidates are evicted while keeping operations efficient.

Auto-tuning Parameter

To ensure good performance across diverse traces, 3L-Cache includes a low-overhead module to automatically tune its key parameters ($h_{sw}, f, x, Q, n$). The rules are triggered by events like model updates or the end of a sampling round and adjust the parameters based on simple heuristics. For instance:

• The sliding window parameter $h_{sw}$ is adjusted based on the hit ratios inside the window versus the cache queue, using the formulas: $$\frac { p _ { s } - p _ { q } } { ( h _ { s w } - 1 ) } > 0 . 0 1 \cdot p _ { q }$$ $$( h _ { s w } - 1 ) \cdot ( p _ { s } - p _ { q } ) < 1 - p _ { q }$$

  • $p_s$: Hit ratio within the sliding window.
  • $p_q$: Hit ratio of the cache queue.

• The sampling range $x$ is adjusted by comparing the eviction probability of candidates from the first part of the tail scan versus the second part.

• The new object threshold $Q$ is adjusted by comparing the number of objects evicted from the tail versus the number of new objects arriving.

  This auto-tuning mechanism (detailed in Table 2) allows 3L-Cache to adapt its behavior without requiring manual configuration for each workload.

This is a manually transcribed table from the paper.

Experimental Setup

Datasets

The evaluation was conducted on 8 public production datasets, comprising 4,855 traces with a total of 266.95 billion requests. The datasets are highly diverse, covering block storage, object storage, and key-value (KV) cache workloads from major companies like Tencent, Twitter, Alibaba, and Meta. This diversity ensures the evaluation is comprehensive and the results are generalizable.

This is a manually transcribed table from the paper.

Evaluation Metrics

The performance of each policy was measured using three key metrics, evaluated at two representative cache sizes: small (0.1% of footprint) and large (10% of footprint).

1. Object Miss Ratio (OMR)

   • Conceptual Definition: The percentage of requested objects that are not found in the cache. This metric is critical for latency-sensitive applications.
   • Mathematical Formula: $$OMR = \frac{\text{Number of Cache Misses}}{\text{Total Number of Requests}}$$

2. Byte Miss Ratio (BMR)

   • Conceptual Definition: The percentage of requested bytes that are not found in the cache. This metric is crucial for measuring network traffic reduction.
   • Mathematical Formula: $$BMR = \frac{\sum_{\text{missed request } i} \text{size}(\text{object}_i)}{\sum_{\text{all requests } j} \text{size}(\text{object}_j)}$$
   • The paper reports miss ratio results as a reduction relative to LRU: $1 - \frac{r_{alg}}{r_{LRU}}$, where $r$ is the miss ratio. A positive value indicates an improvement over LRU.

3. CPU Overhead

   • Conceptual Definition: The computational cost required to execute the eviction policy.
   • Mathematical Formula: The paper reports this as a ratio relative to LRU's CPU overhead: $$\text{CPU Overhead Ratio} = \frac{CPU_{alg}}{CPU_{LRU}}$$
   • A value of 5x means the policy uses five times the CPU resources of LRU.

Baselines

3L-Cache was compared against a comprehensive set of eleven state-of-the-art policies, including:

• 6 Heuristic Policies: LHD, GDSF, ARC, SIEVE, S3-FIFO, TinyLFU. These represent modern, high-performance heuristic approaches.
• 5 Learning-based Policies:
  • Policy-level: LeCaR, CACHEUS
  • Group-level: GL-Cache
  • Object-level: LRB, HALP (the most direct competitors)

Results & Analysis

The evaluation demonstrates that 3L-Cache successfully achieves its goal of providing low miss ratios with low computational overhead.

Core Results: Miss Ratios

This is a manually transcribed table from the paper.

*(Note: The table in the paper does not include `3L-Cache`'s aggregated results, but they are presented throughout the figures and text.)*

Byte Miss Ratio (BMR)

As shown in Figures 6 and 7, 3L-Cache consistently achieves the best or near-best BMR across the vast majority of traces.

• On large datasets (Figure 6), 3L-Cache shows the most significant reduction in BMR at nearly all percentiles, outperforming the next-best policy, LRB. For instance, on the Tencent CBS dataset with small caches, 3L-Cache reduces BMR by an average of 11.6% compared to LRU, while LRB only achieves 8.6%.

• Overall, 3L-Cache achieves the lowest BMR on 69.8% of traces for small caches and 41.2% for large caches, far surpassing any other policy.

  该图像是图表，展示了在不同工作负载和缓存大小下，3L-Cache及其它十二种缓存驱逐策略相较于LRU的字节缺失率降低情况，涵盖CloudPhysics、Tencent CBS、Twitter和Alibaba数据集，分为小缓存和大缓存两组。

  该图像是图表，展示了不同缓存替换策略在小缓存大小(a)和大缓存大小(b)条件下相对于LRU的字节未命中率下降比例，使用了不同数据集标识不同颜色。颜色透明度变化表示同一数据集的多个追踪。

Object Miss Ratio (OMR)

When configured to optimize for OMR, 3L-Cache again demonstrates superior performance (Figures 8 and 9).

• Policies that consider object size in their eviction logic (LHD, GDSF, GL-Cache, LRB, 3L-Cache) generally perform better.

• On large datasets (Figure 8), 3L-Cache shows the greatest reduction for small cache sizes. On Tencent CBS, it achieves a mean reduction of 23.4% over LRU.

• Overall, 3L-Cache achieves the lowest OMR on 66.3% of traces for small caches and 29.3% for large caches.

  该图像是图表，展示了3L-Cache与多种缓存策略在不同大型数据集上、小与大型缓存尺寸条件下，相对于LRU的对象缺失率减少情况。图中通过8个子图比较了不同策略的效果，3L-Cache普遍表现优越。

  该图像是图表，展示了论文中图9关于小数据集上不同缓存大小下多种缓存策略相较于LRU的对象未命中率降低情况。图中分别为(a)小缓存大小和(b)大缓存大小，横轴为数据集，纵轴为相较LRU的对象未命中率降低比例。

Core Results: CPU Overhead

This is where 3L-Cache's primary innovation shines. Figure 10 shows that 3L-Cache dramatically reduces the overhead of object-level learning.

• Compared to other object-level policies, 3L-Cache reduces average CPU overhead by 60.9% vs. HALP and a staggering 94.9% vs. LRB.

• Compared to the lightweight LRU baseline, 3L-Cache's overhead is only 6.4x higher for small caches and 3.4x for large caches. This brings it into a range comparable to heuristic policies, making it economically viable for production.

  该图像是图表，展示了在4855个追踪样本中不同缓存策略在（a）小缓存和（b）大缓存场景下相对于LRU的CPU开销百分位数。较低值表示性能更优，3L-Cache在两种缓存大小下的CPU开销远低于其他学习型策略。

The source of this reduction is confirmed in Tables 4 and 5. The overhead from training and prediction, which consumes over 90% of CPU time in LRB, is reduced to just 37.3% in 3L-Cache for large caches.

This is a manually transcribed table from the paper.

This is a manually transcribed table from the paper.

Ablations / Parameter Sensitivity

• Parameter Auto-tuning: Figure 11 demonstrates the effectiveness of the auto-tuning module. Compared to using fixed default parameters or a random adjustment strategy, the proposed auto-tuning method achieves significantly better byte miss ratios across the tested datasets. It finds the best performance on 81.6% of traces for small caches.

  该图像是图表，展示了不同参数调整策略对3L-Cache字节未命中率的影响，分别针对小缓存尺寸(a)和大缓存尺寸(b)下的腾讯CBS和阿里巴巴数据。图中通过箱线图比较了默认、随机和自动三种参数调整策略的效果。

• Accelerating LRB: To test the generalizability of its methods, the authors applied 3L-Cache's sampling and eviction strategy to LRB. Figure 12 shows this "accelerated LRB" reduces the original LRB's CPU overhead by 80% and even slightly improves its byte miss ratio by 0.6%. This confirms that the overhead-reduction techniques are not specific to 3L-Cache's model but are broadly applicable.

  该图像是图表，展示了图12中在Tencent CBS和CloudPhysics数据集上，3L-Cache设计应用于LRB时对字节未命中率和CPU开销的影响，分别以箱线图形式比较了LRB、modified-LRB和3L-Cache的性能差异。

• Prototype Validation: Figure 13 shows that the performance of a real prototype implementation of 3L-Cache closely matches the simulation results in terms of both hit ratio and CPU overhead. This validates the simulator's accuracy and confirms the policy's real-world practicality.

  该图像是图表，展示了图13中腾讯CBS轨迹上的原型评估结果。左图(a)显示不同缓存大小下三种策略的字节命中率，右图(b)展示对应的CPU开销。图中对比了LRU、LRB和3L-Cache三种缓存替换策略的性能表现。

Conclusion & Personal Thoughts

Conclusion Summary

This paper presents 3L-Cache, a novel learning-based cache eviction policy that, for the first time, successfully combines the high precision of object-level learning with low computational overhead. By systematically targeting and reducing computational waste in model training and prediction, 3L-Cache makes the deployment of high-performance learning-based caching economically feasible. Its core innovations—an efficient training data collection scheme, a bidirectional sampling policy for eviction, and a parameter auto-tuning module—allow it to achieve state-of-the-art byte and object miss ratios while keeping its CPU overhead only a small multiple of the simple LRU policy. The extensive evaluation on thousands of production traces and a prototype implementation provide compelling evidence of its effectiveness and practicality.

Limitations & Future Work

The authors identify one primary limitation: 3L-Cache's sampling strategy is optimized for workloads that exhibit Zipf-like access patterns, where a small number of objects are very popular. If a workload has a more uniform popularity distribution, the bidirectional sampling may become less effective at identifying unpopular objects, potentially degrading to the level of random sampling. As future work, the authors plan to analyze a wider variety of access patterns and design an eviction policy that can adapt to more diverse workloads.

Personal Insights & Critique

• Pragmatism over Purity: The standout quality of this paper is its focus on pragmatism. While much research in ML-based systems focuses on novel models for marginal accuracy gains, this work tackles the far more critical and practical problem of deployment cost. The solutions are not necessarily deep theoretical breakthroughs but are clever, effective engineering designs that make a powerful but expensive technology viable. This focus on bridging the gap between research and production is highly valuable.
• Strong and Convincing Evaluation: The scale of the evaluation is a major strength. Testing on 4,855 traces from 8 different production environments provides very strong evidence for the generalizability and robustness of 3L-Cache. The inclusion of a prototype further bolsters the claims, moving the work beyond pure simulation.
• Generalizability of Ideas: The demonstration that 3L-Cache's techniques can accelerate LRB is a powerful point. It suggests that the paper's contributions are not just a single new algorithm, but a set of principles (e.g., smart sampling for inference, adaptive training frequency) that can be applied to a whole class of online learning systems where computational overhead is a concern.
• Potential Weaknesses and Open Questions:

  • Complexity of Auto-Tuning: The auto-tuning module, while effective, introduces its own set of rules and hardcoded thresholds (e.g., the 0.01 factor in Eq. 1). The sensitivity to these "meta-parameters" is not deeply explored, and in a real-world deployment, their stability would be a key concern.

  • Storage Overhead: The paper notes a storage overhead of 67 bytes per object to store the features. While framed as a small percentage of the cache size, this could become significant in caches that store a very large number of small objects, a common pattern in key-value stores. This trade-off could have been explored in more detail.

  • Applicability to Non-Zipfian Workloads: The authors' acknowledged limitation is important. The reliance on LRU-like queue properties for tail sampling means performance could indeed suffer on scan-heavy or uniform-random workloads. A more adaptive sampling strategy that can detect the workload pattern could be a valuable extension.

    Overall, 3L-Cache is an excellent piece of systems research that provides a well-engineered, thoroughly-evaluated, and practical solution to a significant real-world problem. It sets a new standard for what should be expected from learning-based caching policies: not just high performance, but deployable performance.