HotStorage’18 Paper: ML-based Cache Replacement

Driving Cache Replacement with ML-based LeCaR, Giuseppe Vietri, Liana V. Rodriguez, Wendy A. Martinez, Steven Lyons, Jason Liu, Raju Rangaswami, Giri Narasimhan, and Ming Zhao. In Proceedings of the 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage’18), July 2018. [to appear]

Abstract

Can machine learning (ML) be used to improve on existing cache replacement strategies? We propose a general framework called LeCar that uses the ML technique of regret minimization to answer the question in the affirmative. Surprisingly, we show that the LeCar framework outperforms ARC using only two fundamental eviction policies — LRU and LFU. We also show that the performance gap increases when the size of the available cache gets smaller relative to the size of the working set.

Bibtex

@inproceedings{hotstorage18-lecar,
title = {Driving Cache Replacement with ML-based {LeCaR}},
author = {Giuseppe Vietri and Liana V. Rodriguez and Wendy A. Martinez and Steven Lyons and Jason Liu and Raju Rangaswami and Giri Narasimhan and Ming Zhao},
booktitle = {Proceedings of the 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage’18)},
month = {July},
year = {2018}
}

HotStorage’15 Paper: To ARC or Not to ARC

To ARC or Not to ARC, Ricardo Santana, Steven Lyons, Ricardo Koller, Raju Rangaswami, and Jason Liu. In Proceedings of the 7th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 2015), July 2015. [paper]

abstractbibtex
Cache replacement algorithms have focused on managing caches that are in the datapath. In datapath caches, every cache miss results in a cache update. Cache updates are expensive because they induce cache insertion and cache eviction overheads which can be detrimental to both cache performance and cache device lifetime. Nondatapath caches, such as host-side flash caches, allow the flexibility of not having to update the cache on each miss. We propose the multi-modal adaptive replacement cache (mARC), a new cache replacement algorithm that extends the adaptive replacement cache (ARC) algorithm for non-datapath caches. Our initial trace-driven simulation experiments suggest that mARC improves the cache performance over ARC while significantly reducing the number of cache updates for two sets of storage I/O workloads from MSR Cambridge and FIU.
@inproceedings {Santana2015:MARC,
author = {Ricardo Santana and Steven Lyons and Ricardo Koller and Raju Rangaswami and Jason Liu},
title = {To ARC or Not to ARC},
booktitle = {7th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 15)},
year = {2015},
address = {Santa Clara, CA},
url = {https://www.usenix.org/conference/hotstorage15/workshop-program/presentation/santana},
publisher = {USENIX Association},
}