Competitive Consistent Caching for Transactions
This paper delves into creating a consistent cache policy tailored for transaction handling in modern applications, addressing existing flaws and limitations in handling transactional reads and writes. It explores definitions, cache policy differences, and introduces innovative consistent cache schemes like PCC, ACC, and LCC.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Competitive Consistent Caching for Transactions Authors: Shuai An, Yang Cao, and Wenyue Zhao
Outline Introduction Definitions & Consistent vs Conventional Cache Policies Limitations of Related Work Consistent Cache Schemes TCache OFF & ReO Results
Introduction Motivation: Transactional reads are becoming increasingly more popular in modern-day applications Online retailers, social networks, etc. Existing solutions that handle transactions are inherently flawed Objective: To create a consistent cache policy tailored towards handling transactions
Definitions Read Transactions & Write Transactions: Groupings of either read or write operations Transaction Commit Protocols: Ensures that transactions are only committed to the cache when they are consistent Transactional Cache: Serves read transactions that require consistency Transaction Database: A database whose data requires consistency
Consistent vs. Conventional Cache Policies Cache Policy: Determine what cached data to evict Consistent Cache Policy: Augment data caches to handle both read and write transactions Conventional Cache Policy: Always used for data caches but were designed only with read operations in mind
Limitations of Existing Works Conventional cache policies (e.g., LRU, LFU, etc.) disregard write operations, which in turn, fails to satisfy consistency for transactions. Transactional commit protocols satisfies consistency for transactions but are held back by conventional cache policies.
Consistent Cache Schemes Scheme Action Upon a Database Update Cache Invalidation Protocol Consistency Pessimistic Consistent Cache (PCC) Send a PURGE message to the cache to evict all the referenced items. PURGE: Remove referenced items in the cache. Always Active Consistent Cache (ACC) Send a REFRESH message to the cache to update the referenced items by refetching from the database. REFRESH: Update referenced items in the cache. Always Locally Consistent Cache (LCC) Send a BAN message to the cache, simply containing a list of items that were updated. BAN: Mark referenced items in the cache and re-fetch them from the database when needed. Sometimes
Obsolete First then First-in-the-furthest (OFF) Policy Obsolete Reads: An item that is cached but stale, so it is of no use OFF Algorithm: Classify each read operation in the transactions of the sequence by their size Inconsistent Cache Hit or Cache Miss Process each read transaction Refresh stale reads in the cache 2 3 Was a Cache Miss? 1 Evict 2 cached items from each class whose next appearance in the sequence is furthest in the future Fetch missing items and answer the read transaction Cache Overflow? 5 4
ReO Staleness Bound s: a user-specified number that ensures the read transaction will access the value that is s versions away ReO Algorithm: uses a bipartite graph and matching to return a reordered sequence of transactions that satisfies the staleness bound.
TCache A prototype that builds upon Memcached for caching transactions Uses the OFF policy, ReO, and batching of transactions as sequences
