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 language | English |
---|---|
Title of host publication | Proceedings of the 49th International Conference on Very Large Data Bases |
Number of pages | 14 |
Publication status | Accepted/In press - 18 Nov 2022 |
Event | The 49th International Conference on Very Large Data Bases, 2023 - Vancouver, Canada Duration: 28 Aug 2023 → 1 Sep 2023 Conference number: 49 https://vldb.org/2023/ |
Conference
Conference | The 49th International Conference on Very Large Data Bases, 2023 |
---|---|
Abbreviated title | VLDB 2023 |
Country/Territory | Canada |
City | Vancouver |
Period | 28/08/23 → 1/09/23 |
Internet address |