Paper Details

Reference:

Sari Sultan, Kia Shakiba, Albert Lee, Paul Chen, and Michael Stumm,
"TTLs matter: Efficient cache sizing with TTL-aware miss ratio curves and working set sizes",
In Proceedings of the 19th European Conference on Computer Systems (EuroSys'24), Athens, Greece, Association for Computing Machinery, 2024, pp. 387 – 404.

Abstract:

In-memory caches play a pivotal role in optimizing distributed systems by significantly reducing query response times. Correctly sizing these caches is critical, especially considering that prominent organizations use terabytes and even petabytes of DRAM for these caches. The Miss Ratio Curve (MRC) and Working Set Size (WSS) are the most widely used tools for sizing these caches.\PARModern cache workloads employ Time-to-Live (TTL) limits to define the lifespan of cached objects, a feature essential for ensuring data freshness and adhering to regulations like GDPR. Surprisingly, none of the existing MRC and WSS tools accommodate TTLs. Based on 28 real-world cache workloads that contain 113 billion accesses, we show that taking TTL limits into consideration allows an average of 69% (and up to 99%) lower memory footprint for in-memory caches without a degradation in the hit rate.\ARThis paper describes how TTLs can be integrated into today's most important MRC generation and WSS estimation algorithms. We also describe how the widely used HyperLogLog (HLL) cardinality estimator can be extended to accommodate TTLs, and show how it can be used to efficiently estimate the WSS. Our extended algorithms maintain comparable performance levels to the original algorithms. All our extended approximate algorithms are efficient, run in constant space, and enable more resource-efficient and cost-effective cache management.

Keywords:

Cache Sizing, HyperLogLog (HLL), In-memory Caches, Key-Value Stores, Miss Ratio Curve (MRC), Time to Live (TTL), Working Set Size (WSS)

Reference Info:

DOI: 10.1145/3627703.3650066
ISBN: 9798400704376

BibTeX:

@inproceedings(Sultan-EuroSys24,
    author = {Sari Sultan and Kia Shakiba and Albert Lee and Paul Chen and Michael Stumm},
    title = {TTLs matter: Efficient cache sizing with TTL-aware miss ratio curves and working set sizes},
    booktitle = {Proceedings of the 19th European Conference on Computer Systems (\textbf{EuroSys'24})},
    location = {Athens, Greece},
    organization = {Association for Computing Machinery},
    year = {2024},
    pages = {387 -- 404},
    doi = {10.1145/3627703.3650066},
    isbn = {9798400704376},
    keywords = {Cache Sizing, HyperLogLog (HLL), In-memory Caches, Key-Value Stores, Miss Ratio Curve (MRC), Time to Live (TTL), Working Set Size (WSS)}
)