The cache eviction algorithm is the heart of a cache. The effectiveness and performance of the eviction algorithm decide the efficiency, throughput, and scalability of a cache. This project aims to design simple, efficient, and scalable cache eviction algorithms.
A cache can be viewed as a logically ordered queue with four operations — insertion, removal, promotion, and demotion. Among them, promotion and demotion are internal operations used to maintain the ordering of objects in the queue. Through a large-scale workload study and cache simulations on over 6000 traces collected from 2007 to 2023, we make two observations. First, we find that Lazy Promotion — promotion only at eviction, such as reinsertion in FIFO-Reinsertion/CLOCK, not only improves throughput and scalability but also improves efficiency. While conventional wisdom suggests FIFO-Reinsertion/CLOCK is a weak LRU, we find it is more efficient than LRU. Second, we find Quick Demotion — removing most new objects quickly is the key to efficient cache eviction algorithms. The eviction algorithms that can perform quick demotion are often more efficient.
Yazhuo Zhang (Emory University)
Yao Yue (ex-Twitter)
We thank Twitter for allowing us to investigate the performance of production caches and open-source the large cache trace dataset. The project is supported by a Facebook Fellowship, NSF CNS 1901410 and 1956271. The computation was performed on the PDL clusters, the Cloudlab testbed, the Chameleon testbed, and AWS.
We thank the members and companies of the PDL Consortium: Amazon, Google, Hitachi Ltd., Honda, Intel Corporation, IBM, Meta, Microsoft Research, Oracle Corporation, Pure Storage, Salesforce, Samsung Semiconductor Inc., Two Sigma, and Western Digital for their interest, insights, feedback, and support.