Making Cache Monotonic and Consistent

Shuai An, Yang Cao

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

Abstract / Description of output

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
PublisherVLDB Endowment
Number of pages14
Publication statusPublished - 1 Dec 2022
EventThe 49th International Conference on Very Large Data Bases, 2023 - Vancouver, Canada
Duration: 28 Aug 20231 Sept 2023
Conference number: 49

Publication series

NameProceedings of the VLDB Endowment
PublisherVLDB Endowment
ISSN (Electronic)2150-8097


ConferenceThe 49th International Conference on Very Large Data Bases, 2023
Abbreviated titleVLDB 2023
Internet address


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

Cite this