The cache sketch: revisiting expiration-based caching in the age of cloud data management
Abstract
The expiration-based caching model of the web is generally considered irreconcilable with the dynamic workloads of cloud database services, where expiration dates are not known in advance. In this paper, we present the Cache Sketch data structure which makes expiration-based caching of database records feasible with rich tunable consistency guarantees. The Cache Sketch enables database services to leverage the large existing caching infrastructure of content delivery networks, browser caches and web caches to provide low latency and high scalability. The Cache Sketch employs Bloom filters to create compact representations of potentially stale records to transfer the task of cache coherence to clients. Furthermore, it also minimizes the number of invalidations the service has to perform on caches that support them (e.g., CDNs). With different age-control policies the Cache Sketch achieves very high cache hit ratios with arbitrarily low stale read probabilities. We present the Constrained Adaptive TTL Es- timator to provide cache expiration dates that optimize the performance of the Cache Sketch and invalidations. To quantify the performance gains and to derive workloadoptimal Cache Sketch parameters, we introduce the YCSB Monte-Carlo Caching Simulator (YMCA), a generic framework for simulating the performance and consistency characteristics of any caching and replication topology. We also provide empirical evidence for the efficiency of the Cache Sketch construction and the real-world latency reductions of database workloads under CDN-caching.
- Citation
- BibTeX
Gessert, F., Schaarschmidt, M., Wingerath, W., Friedrich, S. & Ritter, N.,
(2015).
The cache sketch: revisiting expiration-based caching in the age of cloud data management.
In:
Seidl, T., Ritter, N., Schöning, H., Sattler, K.-U., Härder, T., Friedrich, S. & Wingerath, W.
(Hrsg.),
Datenbanksysteme für Business, Technologie und Web (BTW 2015).
Bonn:
Gesellschaft für Informatik e.V..
(S. 53-72).
@inproceedings{mci/Gessert2015,
author = {Gessert, Felix AND Schaarschmidt, Michael AND Wingerath, Wolfram AND Friedrich, Steffen AND Ritter, Norbert},
title = {The cache sketch: revisiting expiration-based caching in the age of cloud data management},
booktitle = {Datenbanksysteme für Business, Technologie und Web (BTW 2015)},
year = {2015},
editor = {Seidl, Thomas AND Ritter, Norbert AND Schöning, Harald AND Sattler, Kai-Uwe AND Härder, Theo AND Friedrich, Steffen AND Wingerath, Wolfram} ,
pages = { 53-72 },
publisher = {Gesellschaft für Informatik e.V.},
address = {Bonn}
}
author = {Gessert, Felix AND Schaarschmidt, Michael AND Wingerath, Wolfram AND Friedrich, Steffen AND Ritter, Norbert},
title = {The cache sketch: revisiting expiration-based caching in the age of cloud data management},
booktitle = {Datenbanksysteme für Business, Technologie und Web (BTW 2015)},
year = {2015},
editor = {Seidl, Thomas AND Ritter, Norbert AND Schöning, Harald AND Sattler, Kai-Uwe AND Härder, Theo AND Friedrich, Steffen AND Wingerath, Wolfram} ,
pages = { 53-72 },
publisher = {Gesellschaft für Informatik e.V.},
address = {Bonn}
}
Haben Sie fehlerhafte Angaben entdeckt? Sagen Sie uns Bescheid: Send Feedback
More Info
ISBN: 978-3-88579-635-0
ISSN: 1617-5468
xmlui.MetaDataDisplay.field.date: 2015
Language:
(en)

Content Type: Text/Conference Paper