website statistics
Skip to content

Performance

FIFO queues are all you need for cache eviction

TL;DR

In this blog, I will describe a simple, scalable FIFO-based eviction 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 12 state-of-the-art algorithms. Moreover, S3-FIFO’s efficiency is robust — it has the lowest mean miss ratio on 10 of the 14 datasets. The use of FIFO queues enables S3-FIFO to achieve good scalability with 6× higher throughput compared to optimized LRU at 16 threads.

FIFO is Better than LRU: the Power of Lazy Promotion and Quick Demotion

TL;DR

Historically FIFO-based algorithms are thought to be less efficient (having higher miss ratios) than LRU-based algorithms. In this blog, we introduce two techniques, lazy promotion, which promotes objects only at eviction time, and quick demotion, which removes most new objects quickly. We will show that

  • Conventional-wisdom-suggested "weak LRUs", e.g., FIFO-Reinsertion, is actually more efficient (having lower miss ratios) than LRU;
  • Simply evicting most new objects can improve state-of-the-art algorithm's efficiency.
  • Eviction algorithms can be designed like building LEGOs by adding lazy promotion and quick demotion on top of FIFO.