SNIA Developer Conference September 15-17, 2025 | Santa Clara, CA
Juncheng Yang
Ph.D. Student
Carnegie Mellon University
"Juncheng Yang (https://junchengyang.com) is a 5th-year Ph.D. student from Carnegie Mellon University. His research interests broadly cover the efficiency, performance, and sustainability of large-scale cache and storage systems. In collaboration with Twitter, Meta, Google, and Akamai, his works are published at OSDI, NSDI, SOSP, FAST, Eurosys, and SOCC, with multiple best paper awards at SOSP, NSDI, and SYSTOR. One of his works, Segcache, has been in production at Twitter and a startup. Besides, he worked at Twitter and Cloudflare, improving the efficiency of the cache infrastructure. His research is sponsored by a Meta fellowship, and he is a Google Cloud Innovator. And he was an invited QConSF speaker and SNIA 2020 keynote speaker."
Related Sessions
No More LRU: Simple Scalable Caching with Only FIFO Queues
- 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.