FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion

This repo contains code for HotOS'23 paper: FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion

Abstract

LRU has been the basis of cache eviction algorithms for decades, with a plethora of innovations on improving LRU’s miss ratio and throughput. While it is well-known that FIFO- based eviction algorithms provide significantly better throughput and scalability, they lag behind LRU on miss ratio, thus, space efficiency.

We performed a large-scale simulation study using 6587 block and web cache workloads collected in the past two decades. We find that contrary to what common wisdom suggests, some FIFO-based algorithms, such as FIFO-Reinsertion (or CLOCK), are, in fact, more efficient than LRU. Moreover, we find that quick demotion — evicting most new objects very quickly — is critical for space efficiency. We show that when enhanced by quick demotion, not only can state-of-the-art algorithms be more efficient, a simple FIFO-based algorithm can outperform five complex state-of-the-art in terms of miss ratio.

Repo structure

The repo is a snapshot of libCacheSim, which contains the implementation of the algorithms compared in the paper.

How to use libCacheSim

You can compile libCacheSim, which will provide a cachesim binary, then you can run simulations with

# ./cachesim DATAPATH TRACE_FORMAT EVICTION_ALGO CACHE_SIZE [OPTION...]
./cachesim DATA oracleGeneral lru,arc,lecar,qdlp 0 --ignore-obj-size 1

Detailed instructions can be found at libCacheSim.

Traces

The traces we used can be downloaded here

The traces are zstd compressed and have the following format:

struct {
    uint32_t timestamp;
    uint64_t obj_id;
    uint32_t obj_size;
    int64_t next_access_vtime;  // -1 if no next access
}

The compressed traces can be used with libCacheSim without decompression.

License

Copyright 2023, Carnegie Mellon University

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

Acknowledgement

We greatly thank the following people and organizations that made this work possible.

Testbed

We greatly appreciate the resources and support provided by Cloudlab and PDL for performing large-scale evaluations.

Open source cache traces and the people behind it

• Twitter
• Tencent Block (Download)
• Tencent Photo (Download)
• Wikimedia CDN
• Alibaba Block
• MSR
• FIU
• CloudPhysics

Funding

This work was supported in part by Meta Fellowship, NSF grants CNS 1901410 and 1956271, and an AWS grant.

Citation

@inproceedings{yang2023qd,
  title={FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion},
  author={Yang, Juncheng and Qiu, Ziyue and Zhang, Yazhuo and Yue, Yao and Rashmi, K.V.},
  booktitle={The 19th Workshop on Hot Topics in Operating Systems (HotOS 23)},
  year={2023}
}