Abstract
- Caching is used in almost every component of today's storage systems to speed up data access and reduce data movement. The most important component of a cache is the eviction algorithm that decides which objects to keep in the very limited cache space. While Least-Recently-Used (LRU) is the most common eviction algorithm, it suffers from many problems.
- First, LRU is not scalable. LRU maintains objects in last-access order, which requires a doubly-linked list. Each data read request requires moving the requested object to the head of the linked list under locking. Therefore, LRU's throughput cannot scale with the number of cores and cannot benefit from modern multi-core CPUs.
- Second, existing state-of-the-art eviction algorithms are mostly built upon LRU, using one or multiple LRUs with complicated adaptive algorithms. As a result, they are not scalable and are often complex and hard to debug.
- As a cache eviction algorithm, FIFO has many attractive properties, such as simplicity, speed, scalability, and flash-friendliness. However, its most prominent criticism is its low efficiency (high miss ratio).
- In this talk, I will introduce a simple, scalable FIFO-based algorithm with three static queues (S3-FIFO). Evaluated on 6594 cache traces from 14 datasets, I will 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.
- The insight is that most objects in today's storage 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.
