Caching with Monotonicity and Consistency

Abstract

We propose monotonic consistent caching (MCC), a cache scheme for applications that demand transactional guarantees. MCC warrants that a transaction-like request always sees a consistent view of the backend database and that observed writes over the cache will not be lost, even if it operates on conventional cache systems, e.g., Memcached or Redis, that come without such guarantees. Unlike traditional caching which is trivially in Ptime under the offline (batch) model where requests are known in advance, we show that the complexity of MCC ranges from Ptime to Np-Complete, depending on the version selection strategy in case of cache hits that violate transactional guarantees. 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 optimal and approximate MCC policies 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. We further implement a pluggable system that supports all proposed MCC policies. Using benchmark and real-life traces, we show that MCC policies reduce 34.9% of database reads for Redis atop HBase and improve their throughput by 59.1%.