Researchers Design Simple, High-Performing Cache Eviction Algorithm

Tuesday, December 5, 2023 - by Aaron Aupperlee

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. (Image created with…

Researchers in Carnegie Mellon University's Computer Science Department (CSD) 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.

The algorithm, S3-FIFO, outperformed other state-of-the-art cache-eviction algorithms when tested on massive amounts of real-world data. S3-FIFO stands for simple and scalable caching with three static (S3) first-in-first-out (FIFO) queues.

"S3-FIFO is the first eviction algorithm of its type that is simpler, more efficient and faster than state-of-the-art methods," said CSD Ph.D. student Juncheng Yang. "Simplicity is critical for caching because it leads to fewer bugs and more reliable service."

The cache is memory space set aside to store items for quick retrieval. Web browsers, for example, store images, code, fonts, icons and other items to help pages load rapidly. This cache space fills up quickly. Eviction algorithms decide which items to keep in the cache and which to evict.

Many caches rely on least recently used (LRU) eviction algorithms, which remove items from the cache that haven't been accessed in some time. For LRU to work properly, the status of each item in the cache must be updated each time the cache is accessed. This method is neither scalable nor efficient, and efforts to improve LRU systems trade efficiency for throughput or vice versa.

FIFO eviction algorithms are alternatives to LRU methods that work as the name suggests. The algorithm considers the oldest items in the cache the first to be evicted. This allows FIFO algorithms to be simpler, faster, scalable and flash-friendly while using fewer computing resources and requiring less metadata. FIFO algorithms, however, have a high miss ratio, meaning that the data the systems seek is often not in the cache for fast access.

As part of its research, the team discovered that most items in the cache are only used once before being evicted, known as one-hit wonders. The team first observed a high one-hit-wonder ratio in only a few datasets. It then built its own distributed computation platform to process and analyze all the open-source datasets and found that one-hit wonders were incredibly common. This analysis was the largest to date and millions of times larger than previous efforts. The team designed S3-FIFO to keep popular items in the cache and rapidly evict potential one-hit wonders.  

"This was an important observation. It enabled us to achieve better than state-of-the-art efficiency without the need for complex designs," said Ziyue Qiu, a Ph.D. student in CSD. "Most objects in the cache are one-hit wonders, and it doesn't make sense to keep them there for a long time."

The team tested S3-FIFO on 6,594 cache traces from 14 datasets and demonstrated that it had lower miss ratios than state-of-the-art algorithms. S3-FIFO also had the lowest mean miss ratio on 10 of the 14 datasets, while the second-best algorithm is the best only on two datasets. Moreover, the eviction algorithm's design allowed it to achieve good scalability with six times higher throughput compared to LRU-based algorithms.

"S3-FIFO leverages unique observations about items in the cache into a top-performing eviction algorithm that has already caught the attention of marque companies," said Rashmi Vinayak, an associate professor in CSD.

 S3-FIFO was developed by Yang, Qiu and Vinayak in CMU's School of Computer Science; Yazhuo Zhang from Emory University; and Yao Yue from the Pelikan Foundation in San Francisco. The team's research, "FIFO Queues Are All You Need for Cache Eviction," was presented at the 29th ACM Symposium on Operating Systems Principles in October in Germany. More information about the team's work is available on the S3-FIFO website.

For more information, Contact:
Aaron Aupperlee | 412-268-9068 | aaupperlee@cmu.edu