Rethinking Cache Eviction: Low-Overhead and Precise Learning-based Design

Abstract

Caches reduce latency and network traffic, and cache performance largely depends on the eviction policy. Eviction effectiveness is typically measured by byte and object miss ratios. Although learning-based eviction policies can reduce misses, their high computational overhead limits practical deployment. This work presents 3L-Cache+, an extended and refined version of 3L-Cache. 3L-Cache+ is an object-level learning-based eviction policy that achieves low computational overhead while delivering strong overall miss-ratio performance. To reduce overhead, we introduce two key techniques. First, we design an efficient training-data collection scheme that filters redundant requests and dynamically adjusts the training frequency. Second, we propose a lightweight eviction method that combines bidirectional sampling, which prioritizes unpopular objects, with an efficient eviction-candidate selection strategy. In addition, an auto-tuning mechanism improves adaptability across traces. We evaluate 3L-Cache+ in a testbed using 4,855 traces. The results show that 3L-Cache+ reduces average CPU overhead by 74.7% and 95.5% compared with HALP and LRB, respectively, and by 22.7% compared with the prior 3L-Cache baseline. 3L-Cache+ incurs only 4.8× LRU overhead under small cache sizes and 3.1× under large cache sizes, while achieving the best byte- or object-miss-ratio performance among 11 state-of-the-art policies.