It's Time to Revisit LRU vs. FIFO

Authors: 

Ohad Eytan, Danny Harnik, and Effi Ofer, IBM Research; Roy Friedman, Technion; Ronen Kat, IBM Research

Abstract: 

We revisit the question of the effectiveness of the popular LRU cache eviction policy versus the FIFO heuristic which attempts to give an LRU like behavior. Several past works have considered this question and commonly stipulated that while FIFO is much easier to implement, the improved hit ratio of LRU outweighs this. We claim that two main trends call for a reevaluation: new caches such as front-ends to cloud storage have very large scales and this makes managing cache metadata in RAM no longer feasible; and new workloads have emerged that possess different characteristics.

We model the overall cost of running LRU and FIFO in a very large scale cache and evaluate this cost using a number of publicly available traces. Our main evaluation workload is a new set of traces that we collected from a large public cloud object storage service and on this new trace FIFO exhibits better overall cost than LRU. We hope that these observations reignite the evaluation of cache eviction policies under new circumstances and that the new traces, that we intend to make public, serve as a testing ground for such work.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {254276,
author = {Ohad Eytan and Danny Harnik and Effi Ofer and Roy Friedman and Ronen Kat},
title = {It{\textquoteright}s Time to Revisit {LRU} vs. {FIFO}},
booktitle = {12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20)},
year = {2020},
url = {https://www.usenix.org/conference/hotstorage20/presentation/eytan},
publisher = {USENIX Association},
month = jul
}

Presentation Video