Making Cache Monotonic and Consistent

Shuai An, Yang Cao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We propose monotonic consistent caching (MCC), a cache scheme for applications that demand consistency and monotonicity. MCC warrants that a transaction-like request always sees a consistent view of the backend database and observed writes over the cache will not be lost. We show that the complexity of MCC ranges from PTime to Np-Complete. We characterize MCC via a notion of obsolete items, based on which we abstract a principle for designing competitive MCC policies. By applying the principle, we develop an optimal MCC policy for the batch model, where requests in a batch are known in advance. For the online and semi-online models, we develop ML-augmented policies that benefit from blackbox ML models for classifying obsolete items, while being provably competitive even if the ML is arbitrarily bad. Using benchmark and real-life traces, we show that MCC policies reduce 39.09% of database reads for Redis atop HBase and improve their throughput by 77.15%.
Original languageEnglish
Title of host publicationProceedings of the 49th International Conference on Very Large Data Bases
Number of pages14
Publication statusAccepted/In press - 18 Nov 2022
EventThe 49th International Conference on Very Large Data Bases, 2023 - Vancouver, Canada
Duration: 28 Aug 20231 Sep 2023
Conference number: 49
https://vldb.org/2023/

Conference

ConferenceThe 49th International Conference on Very Large Data Bases, 2023
Abbreviated titleVLDB 2023
Country/TerritoryCanada
CityVancouver
Period28/08/231/09/23
Internet address

Fingerprint

Dive into the research topics of 'Making Cache Monotonic and Consistent'. Together they form a unique fingerprint.

Cite this