FIFO queues are all you need for cache eviction (blog.jasony.me)
from tedu to programming on 28 Aug 2023 05:00
https://azorius.net/g/programming/p/Y12g34n1MT839Fww4b-FIFO-queues-are-all-you-need-for-cache-eviction

In this blog, I will describe a Simple, Scalable eviction algorithm with three Static FIFO queues (S3-FIFO). Evaluated on 6594 cache traces from 14 companies, we show that S3-FIFO has lower miss ratios than 12 state-of-the-art algorithms designed in the past decades. 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 in cachelib at 16 threads.

#programming #systems