Paper Details

Reference:

Kia Shakiba and Michael Stumm,
"PaperCache: In-Memory Caching with Dynamic Eviction Policies",
In Proceedings 17th ACM Workshop on Hot Topics in Storage and File Systems (HotStorage'25), Boston, MA, USA, ACM, July, 2025, pp. 107–113.
(Also published at https://www.growkudos.com/publications/10.1145%25252F3736548.3737836/reader. Code available: https://papercache.io)

Download:

PDF ; Talk Slides

Abstract:

In-memory caches play a critical role in storage environments by reducing data access latencies and loads on backend data stores. A cache's eviction policy significantly impacts its attained miss ratio, and recent modeling techniques allow for efficient evaluation of different eviction policies at runtime. However, modern in-memory caches lack the ability to switch between eviction policies at runtime, except for Redis that can only switch between LRU and LFU. We present PaperCache, an in-memory cache capable of switching between multiple different eviction policies at runtime. Our evaluation shows that immediately after an eviction policy switch, PaperCache's behavior closely mirrors that of a cache implementing the target policy exactly (with a miss ratio typically within 1%) for a short period of time, after which PaperCache's behavior is fully inline with an exact policy implementation. Further, PaperCache is able to periodically and automatically switch to the policy exhibiting the lowest miss ratio, reducing the overall miss ratio by up to 48.5%.

Keywords:

In-memory Caches, Dynamic eviction policy switching, Key-Value Stores, Miss rate curve (MRC) generation, Eviction policies, LFU, LRU, FIFO, LRFU, 2Q, S3-FIFO, MRU, Clock, Sieve

Reference Info:

DOI: 10.1145/3736548
ISBN: 9798400719479

BibTeX:

@inproceedings(Shakiba-HotStorage25,
    author = {Kia Shakiba and Michael Stumm},
    title = {PaperCache: In-Memory Caching with Dynamic Eviction Policies},
    booktitle = {Proceedings 17th ACM Workshop on Hot Topics in Storage and File Systems (HotStorage'25)},
    location = {Boston, MA, USA},
    publisher = {ACM},
    month = {July},
    year = {2025},
    pages = {107--113},
    doi = {10.1145/3736548},
    isbn = {9798400719479},
    keywords = {In-memory Caches, Dynamic eviction policy switching, Key-Value Stores, Miss rate curve (MRC) generation, Eviction policies, LFU, LRU, FIFO, LRFU, 2Q, S3-FIFO, MRU, Clock, Sieve}
)