研究者がシンプルで高性能なキャッシュ消去アルゴリズムを設計(Researchers Design Simple, High-Performing Cache Eviction Algorithm)

ad

2023-12-05 カーネギーメロン大学

研究者がシンプルで高性能なキャッシュ消去アルゴリズムを設計(Researchers Design Simple, High-Performing Cache Eviction Algorithm)Computer Science Department researchers have designed a method to more efficiently and effectively kick unnecessary items out of the cache, improving the performance of software, servers and websites that rely on cached items.

◆カーネギーメロン大学の研究者は、S3-FIFOアルゴリズムを開発し、キャッシュから不要なアイテムを効率的かつ効果的に排除する方法を提案しました。
◆このアルゴリズムは、実世界の大規模データで他の最新アルゴリズムを凌駕し、シンプルでスケーラブルなキャッシングを実現します。S3-FIFOは、一回のみ使用されるアイテムを素早く排除することで特に優れており、多くのデータセットで低いミス率を達成し、スループットが優れたスケーラビリティを実現しました。

<関連情報>

キャッシュ消去に必要なのはFIFOキューだけ FIFO queues are all you need for cache eviction

Juncheng Yang,Yazhuo Zhang,Ziyue Qiu,Yao Yue,Rashmi Vinayak
SOSP ’23: Proceedings of the 29th Symposium on Operating Systems Principles  Published:23 October 2023
DOI:https://doi.org/10.1145/3600006.3613147

ABSTRACT

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.

1602ソフトウェア工学
ad
ad
Follow
ad
タイトルとURLをコピーしました