Shahram Ghandeharizadeh
ABSTRACT
Query intensive applications augment a Relational Database Management System (RDBMS) with a middle-tier cache to enhance performance. An example is memcached in use by very large well known sites such as Facebook. In the presence of updates to the normalized tables of the RDBMS, invalidation based consistency techniques delete the impacted key-value pairs residing in the cache. A subsequent reference for these key-value pairs observes a cache miss, recomputes the new values from the RDBMS, and inserts the new key-value pairs in the cache. These techniques suffer from race conditions that result in cache states that produce stale data. The Gumball Technique (GT) addresses this limitation by preventing race conditions. Experimental results show GT enhances the accuracy of an application hundreds of folds and, in some cases, may reduce system performance slightly.
- C. Amza, A. Chanda, A. Cox, S. Elnikety, R. Gil, K. Rajamani, W. Zwaenepoel, E. Cecchet, and J. Marguerite. Specification and Implementation of Dynamic Web Site Benchmarks. In Workshop on Workload Characterization, 2002.Google Scholar
- C. Amza, A. L. Cox, and W. Zwaenepoel. A comparative evaluation of transparent scaling techniques for dynamic content servers. In ICDE, 2005. Google ScholarDigital Library
- C. Amza, G. Soundararajan, and E. Cecchet. Transparent Caching with Strong Consistency in Dynamic Content Web Sites. In Supercomputing, ICS '05, pages 264--273, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- F. Benevenuto, T. Rodrigues, M. Cha, and V. A. F. Almeida. Characterizing user behavior in online social networks. In Internet Measurement Conference, 2009. Google ScholarDigital Library
- P. Bernstein and N. Goodman. Multiversion Concurrency Control - Theory and Algorithms. ACM Transactions on Database Systems, 8:465--483, February 1983. Google ScholarDigital Library
- K. S. Candan, W. Li, Q. Luo, W. Hsiung, and D. Agrawal. Enabling dynamic content caching for database-driven web sites. In SIGMOD Conference, pages 532--543, 2001. Google ScholarDigital Library
- R. Cattell. Scalable SQL and NoSQL Data Stores. SIGMOD Rec., 39:12--27, May 2011. Google ScholarDigital Library
- J. Challenger, P. Dantzig, and A. Iyengar. A Scalable System for Consistently Caching Dynamic Web Data. In Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies, 1999.Google ScholarCross Ref
- B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking Cloud Serving Systems with YCSB. In Cloud Computing, 2010. Google ScholarDigital Library
- C. D. Cuong. YouTube Scalability. Google Seattle Conference on Scalability, June 2007.Google Scholar
- A. Datta, K. Dutta, H. Thomas, D. VanderMeer, D. VanderMeer, K. Ramamritham, and D. Fishman. A Comparative Study of Alternative Middle Tier Caching Solutions to Support Dynamic Web Content Acceleration. In VLDB, pages 667--670, 2001. Google ScholarDigital Library
- A. Datta, K. Dutta, H. Thomas, D. VanderMeer, D. VanderMeer, Suresha, and K. Ramamritham. Proxy-Based Acceleration of Dynamically Generated Content on the World Wide Web: An Approach and Implementation. In SIGMOD, pages 97--108, 2002. Google ScholarDigital Library
- A. Datta, K. Dutta, H. M. Thomas, D. E. VanderMeer, and K. Ramamritham. Proxy-based Acceleration of Dynamically Generated Content on the World Wide Web: An Approach and Implementation. ACM Transactions on Database Systems, pages 403--443, 2004. Google ScholarDigital Library
- L. Degenaro, A. Iyengar, I. Lipkind, and I. Rouvellou. A Middleware System Which Intelligently Caches Query Results. In IFIP/ACM International Conference on Distributed systems platforms, 2000. Google ScholarDigital Library
- S. Ghandeharizadeh, S. Barahmand, A. Ojha, and J. Yap. Recall All You See, http://rays.shorturl.com, 2010.Google Scholar
- S. Ghandeharizadeh and J. Yap. Gumball: A Race Condition Prevention Technique for Cache Augmented SQL Database Management Systems, USC Database Laboratory, Tech Report 2012-01, 2012.Google Scholar
- S. Ghandeharizadeh and J. Yap. SQL Query To Trigger Translation: A Novel Consistency Technique for Cache Augmented DBMSs. In Submitted for Publication, 2012.Google Scholar
- P. Gupta, N. Zeldovich, and S. Madden. A Trigger-Based Middleware Cache for ORMs. In Middleware, 2011. Google ScholarDigital Library
- V. Holmedahl, B. Smith, and T. Yang. Cooperative Caching of Dynamic Content on a Distributed Web Server. In HPDC, pages 243--250, 1998. Google ScholarDigital Library
- A. Iyengar and J. Challenger. Improving Web Server Performance by Caching Dynamic Data. In In Proceedings of the USENIX Symposium on Internet Technologies and Systems, pages 49--60, 1997. Google ScholarDigital Library
- A. Labrinidis and N. Roussopoulos. Exploring the Tradeoff Between Performance and Data Freshness in Database-Driven Web Servers. The VLDB Journal, 2004. Google ScholarDigital Library
- S. Patil, M. Polte, K. Ren, W. Tantisiriroj, L. Xiao, J. López, G. Gibson, A. Fuchs, and B. Rinaldi. YCSB++: Benchmarking and Performance Debugging Advanced Features in Scalable Table Stores. In Cloud Computing, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- D. R. K. Ports, A. T. Clements, I. Zhang, S. Madden, and B. Liskov. Transactional consistency and automatic management in an application data cache. In OSDI. USENIX, October 2010. Google ScholarDigital Library
- P. Saab. Scaling memcached at Facebook, http://www.facebook.com/note.php?note_id=39391378919, Dec. 2008.Google Scholar
- M. I. Seltzer. Beyond Relational Databases. Commun. ACM, 51(7):52--58, 2008. Google ScholarDigital Library
- K. Yagoub, D. Florescu, V. Issarny, and P. Valduriez. Caching Strategies for Data-Intensive Web Sites. In VLDB, pages 188--199, 2000. Google ScholarDigital Library
Index Terms
- Gumball: a race condition prevention technique for cache augmented SQL database management systems
Recommendations
Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer ArchitectureOn-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
Modeling LRU cache with invalidation
Least Recently Used (LRU) is a very popular caching replacement policy. It is very easy to implement and offers good performance, especially when data requests are temporally correlated, as in the case of web traffic.When the data content can change ...
The evicted-address filter: a unified mechanism to address both cache pollution and thrashing
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniquesOff-chip main memory has long been a bottleneck for system performance. With increasing memory pressure due to multiple on-chip cores, effective cache utilization is important. In a system with limited cache space, we would ideally like to prevent 1) ...
Comments