Scan-resistant cache gadgets improve storage performance and reliability
SR-Gadgets: Make Scan-Resistant Caching Practical
Performance
Summary
Cache systems store data temporarily to speed up computers, but data 'scans' can cause sudden drops or unexpected increases in cache misses, hurting performance. The authors studied these problems and found that a popular algorithm called LIRS avoids them well—not because of earlier assumed reasons, but because it manages its data queues smartly. Using this insight, they created small add-ons called Gadgets that make other cache algorithms handle scans better without changing their core methods. Testing these Gadgets on thousands of real data traces showed they reduce missed data fetches and avoid weird caching problems.
What this means in practice
- •For storage system engineers: Improve caching in storage systems by integrating Gadgets to reduce cache misses and avoid performance anomalies during repeated data scans.
- •For database system developers: Enhance database buffer cache performance on scan-heavy query workloads by applying Gadgets to existing caching algorithms without redesigning eviction logic.
Authors
Yunjia Zheng, Juncheng Yang
Abstract
Block caches commonly serve scan-heavy I/O workloads, motivating extensive studies on scan-resistant eviction algorithms. Many of these algorithms adopt a multi-queue structure. However, they focus primarily on one-time scans and do not handle repeated scans well. Two important challenges from repeated scans are miss-ratio cliffs, where a small increase in cache size sharply reduces the miss ratio, and Belady's anomalies, where increasing the cache size increases the miss ratio. In this paper, we first develop two quantitative metrics to measure these behaviors. With these metrics, we find that LIRS is the only multi-queue algorithm that is scan-resistant (almost cliff- and anomaly-free). Contrary to conventional wisdom, we show that stack distance is not the secret sauce that makes LIRS scan-resistant. Instead, regulating the queues are the key to its scan resistance. Based on these insights, we design the \gadgetprefix Gadgets, easy-to-integrate augmentations that make existing algorithms scan-resistant without changing their eviction heuristics or queue structures. We implement the \gadgetprefix Gadgets in five algorithms: S3-FIFO, SIEVE, ARC, 2Q, and TinyLFU, and make them scan-resistant. Evaluated on 5,538 production traces, all augmented algorithms outperform their base versions, reducing miss ratios by up to 23.1% while consistently reducing cliffs and Belady's anomalies across the production traces.