Lab Lunch: 25 May 2021 - Yang Cao

Title: Consistent Caching for Read-Only Transactions

Abstract:

Transactions and caches have long been two largely separate concepts in database systems. In this talk, we will discuss their connection in the context of client-facing read-only transactions, where we aim to provide transactional guarantees in the presence of possibly inconsistent caches at frontend machines. We focus on snapshot isolation, where a transaction must be answered over a valid logical snapshot of the database. This requires the cache policies to ensure all reads within a transaction are answered consistently over the cache that can be inconsistent w.r.t. database updates. We study three cache schemes that warrant consistent transaction caching, compatible with commonly used cache invalidation protocols. We study the problem of consistent cache policy design under all three schemes.  

While conventional caching is trivially in PTIME, consistent caching for transactions becomes NP-complete. Unique to consistent caching is the existence of obsolete queries, which are cached queries that can never be used for answering transactions due to consistency, no matter what cache policies are used. Obsolete queries are coNP-complete to identify. Nonetheless, we develop OFF, a unified consistent cache policy for all three schemes with performance guarantees. Based on it, we present TCache, a cache proxy for read-only transactions. A preliminary test has found that TCache can effectively reduce database transactional read load via client-side caches.

May 25 2021 -

Lab Lunch: 25 May 2021 - Yang Cao

Speaker: Yang Cao

Blackboard Collaborate
Invitation Only