FIFO queues are all you need for cache eviction
FIFO queues are all you need for cache eviction
复制标题
DOI：
10.1145/3600006.3613147
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Juncheng Yang;Yazhuo Zhang;Ziyue Qiu;Yao Yue;Rashmi Vinayak
中科院分区：
文献类型：
--
作者：
Juncheng Yang;Yazhuo Zhang;Ziyue Qiu;Yao Yue;Rashmi Vinayak
作为一种缓存逐出算法，FIFO具有简单、快速、可扩展性和闪存友好性等特点。对FIFO最突出的批评是它的低效率(高错失率)。在这项工作中，我们展示了一个简单的，可扩展的基于三个静态队列的FIFO算法(S3-FIFO)。在对来自14个数据集的6594个缓存轨迹进行评估后，我们发现S3-FIFO在各个轨迹上的错失率低于最先进的算法。此外，S3-FIFO的效率是稳健的-它在14个数据集中的10个上具有最低的平均错失率。FIFO队列使S3-FIFO能够实现良好的可扩展性，与16个线程的优化LRU相比，吞吐量提高了6倍。我们的见解是，在不对称的工作负载中，大多数对象只能在短时间内访问一次，因此尽早将它们逐出(也称为快速降级)至关重要。S3-FIFO的关键是一个小的FIFO队列，它过滤掉大多数对象进入主高速缓存，从而提供了保证的降级速度和高的降级精度。
As a cache eviction algorithm, FIFO has a lot of attractive properties, such as simplicity, speed, scalability, and flash-friendliness. The most prominent criticism of FIFO is its low efficiency (high miss ratio). In this work, we demonstrate a simple, scalable FIFO-based algorithm with three static queues (S3-FIFO). Evaluated on 6594 cache traces from 14 datasets, we show that S3-FIFO has lower miss ratios than state-of-the-art algorithms across traces. Moreover, S3-FIFO's efficiency is robust --- it has the lowest mean miss ratio on 10 of the 14 datasets. FIFO queues enable S3-FIFO to achieve good scalability with 6× higher throughput compared to optimized LRU at 16 threads. Our insight is that most objects in skewed workloads will only be accessed once in a short window, so it is critical to evict them early (also called quick demotion). The key of S3-FIFO is a small FIFO queue that filters out most objects from entering the main cache, which provides a guaranteed demotion speed and high demotion precision.