research-article

Strong consistency in cache augmented SQL systems

Authors:

Shahram Ghandeharizadeh,

Hieu NguyenAuthors Info & Claims

Middleware '14: Proceedings of the 15th International Middleware Conference

Pages 181 - 192

https://doi.org/10.1145/2663165.2663318

Published: 08 December 2014 Publication History

Abstract

Cache augmented SQL, CASQL, systems enhance the performance of simple operations that read and write a small amount of data from big data. They do so by looking up the results of computations that query the database in a key-value store (KVS) instead of processing them using a relational database management system (RDBMS). These systems incur undesirable race conditions that cause the KVS to produce stale data. This paper presents the IQ framework that provides strong consistency with no modification to the RDBMS. It consists of two non-blocking leases, Inhibit (I) and Quarantine (Q). Ratings obtained from a social networking benchmark named BG show the proposed framework has minimal impact on system performance while providing strong consistency guarantees.

References

[1]

M. Altinel, C. Bornhövd, S. Krishnamurthy, C. Mohan, H. Pirahesh, and B. Reinwald. Cache Tables: Paving the Way for an Adaptive Database Cache. In VLDB, 2003.

Digital Library

[2]

K. Amiri, S. Park, and R. Tewari. DBProxy: A dynamic data cache for Web applications. In ICDE, 2003.

[3]

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.

[4]

T. Armstrong, V. Ponnekanti, D. Borthakur, and M. Callaghan. LinkBench: A Database Benchmark Based on the Facebook Social Graph. ACM SIGMOD, June 2013.

Digital Library

[5]

D. Badal. Correctness of Concurrency Control and Implications in Distributed Databases. In COMPSAC Conference, November 1979.

[6]

S. Barahmand and S. Ghandeharizadeh. BG: A Benchmark to Evaluate Interactive Social Networking Actions. CIDR, January 2013.

[7]

S. Barahmand, S. Ghandeharizadeh, and D. Montauk. Extensions of BG for Testing and Benchmarking Alternative Implementatios of Feed Following. ACM SIGMOD Workshop on Reliable Data Services and Systems (RDSS), 2014.

[8]

S. Barahmand, S. Ghandeharizadeh, and J. Yap. A Comparison of Two Physical Data Designs for Interactive Social Networking Actions. CIKM, 2013.

Digital Library

[9]

P. Bernstein and M. Goodman. Concurrency Control in Distributed Database Systems. ACM Computing Surveys, 13(2), June 1981.

Digital Library

[10]

P. Bernstein and N. Goodman. Multiversion Concurrency Control - Theory and Algorithms. ACM Transactions on Database Systems, 8:465--483, February 1983.

Digital Library

[11]

C. Bornhovdd, M. Altinel, C. Mohan, H. Pirahesh, and B. Reinwald. Adaptive Database Caching with DBCache. IEEE Data Engineering Bull., pages 11--18, 2004.

[12]

S. Ceri and S. Owicki. On the Use of Optimistic Methods for Concurrency Control in Distributed Databases. In Sixth Berkeley Workshop on Distributed Data Management and Computer Networks, February 1982.

[13]

B. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. VLDB, 1(2), Aug. 2008.

Digital Library

[14]

S. Ghandeharizadeh, S. Irani, J. Lam, and J. Yap. CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores. ACM/IFIP/USENIX Middleware, December 2014.

Digital Library

[15]

S. Ghandeharizadeh and J. Yap. Cache Augmented Database Management Systems. In ACM SIGMOD DBSocial Workshop, June 2013.

Digital Library

[16]

S. Ghandeharizadeh and J. Yap. SQL Query To Trigger Translation: A Novel Consistency Technique for Cache Augmented DBMSs. In USC DBLAB Technical Report 2014-07, http://dblab.usc.edu/users/papers/sqltrig.pdf, Submitted for Publication, 2014.

[17]

S. Ghandeharizadeh, J. Yap, and S. Barahmand. COSAR-CQN: An Application Transparent Approach to Cache Consistency. In International Conference On Software Engineering and Data Engineering, 2012.

[18]

S. Ghandeharizadeh, J. Yap, and H. Nguyen. Strong Consistency in Cache Augmented SQL Systems, http://dblab.usc.edu/Users/papers/IQTechReport.pdf. In USC Database Laboratory Technical Report Number 2014-06, 2014.

Digital Library

[19]

J. Gray. Notes on Database Operating Systems. In Operating Systems: An Advanced Course. Sprinter-Verlag, 1979.

Digital Library

[20]

P. Gupta, N. Zeldovich, and S. Madden. A Trigger-Based Middleware Cache for ORMs. In Middleware, 2011.

Digital Library

[21]

S. Harizopoulos, D. J. Abadi, S. Madden, and M. Stonebraker. OLTP Through the Looking Glass, and What We Found There. In SIGMOD, 2008.

Digital Library

[22]

H. Kung and J. Robinson. On Optimistic Methods for Concurrency Control. ACM Transactions on Database Systems, 6, June 1981.

Digital Library

[23]

P. Larson, J. Goldstein, and J. Zhou. MTCache: Transparent Mid-Tier Database Caching in SQL Server. In ICDE, pages 177--189, 2004.

Digital Library

[24]

W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. In SOSP, 2011.

Digital Library

[25]

Q. Luo, S. Krishnamurthy, C. Mohan, H. Pirahesh, H. Woo, B. G. Lindsay, and J. F. Naughton. Middle-Tier Database Caching for e-Business. In SIGMOD, 2002.

Digital Library

[26]

D. Menasce and R. Muntz. Locking and Deadlock Detection in Distributed Databases. In Third Berkeley Workshop on Distributed Database Management and Computer Networks, 1978.

[27]

R. Nishtala et. al. Scaling Memcache at Facebook. NSDI, 2013.

Digital Library

[28]

F. Perez-Sorrosal, M. Patino-Martinez, R. Jimenez-Peris, and B. Kemme. Elastic SI-Cache: Consistent and Scalable Caching in Multi-Tier Architectures. VLDB Journal, 2011.

Digital Library

[29]

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.

Digital Library

[30]

M. Rajashekhar and Y. Yue. Twitter memcached (Twemcache) is version 2.5.3, https://github.com/twitter/twemcache/releases/tag/v2.5.3.

[31]

D. Reed. Naming and Synchronization in a Decentralized Computer System, Ph.D. thesis, Department of Electrical Engineering and Computer Science, MIT, 1978.

[32]

D. Rosenkrantz, R. Stearns, and P. Lewis. System Level Concurrency Control for Distributed Database Systems. ACM Transactions on Database Systems, 3, June 1978.

Digital Library

[33]

A. Silberstein, A. Machanavajjhala, and R. Ramakrishnan. Feed Following: The Big Data Challenge in Social Applications. In DBSocial, 2011.

Digital Library

[34]

Y. Sovran, R. Power, M. K. Aguilera, and J. Li. Transactional Storage for Geo-Replicated Systems. In SOSP, 2011.

Digital Library

[35]

T. T. Team. Mid-Tier Caching: The TimesTen Approach. In Proceedings of the SIGMOD, 2002.

Digital Library

[36]

R. Thomas. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Transactions on Database Systems, 4, June 1979.

Digital Library

[37]

W. Vogels. Eventually Consistent. Communications of the ACM, Vol. 52, No. 1, January 2009.

Digital Library

[38]

G. Whalin, X. Wang, and M. Li. Whalin memcached Client Version 2.6.1, http://github.com/gwhalin/Memcached-Java-Client/releases/tag/release_2.6.1.

[39]

J. Yap, S. Ghandeharizadeh, and S. Barahmand. An Analysis of BG's Implementation of the Zipfian Distribution, USC Database Laboratory Technical Report Number 2013-02.

Cited By

Nguyen HLi JGhandeharizadeh S(2024)Graph Stores with Application-Level Query Result CachesPerformance Evaluation and Benchmarking10.1007/978-3-031-68031-1_4(44-58)Online publication date: 22-Sep-2024
https://doi.org/10.1007/978-3-031-68031-1_4
An SCao YZhao W(2022)Competitive Consistent Caching for Transactions2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00207(2154-2167)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00207
Ghandeharizadeh SHuang HNguyen H(2021)Boosting OLTP Performance Using Write-Back Client-Side CachesTransactions on Large-Scale Data- and Knowledge-Centered Systems XLVIII10.1007/978-3-662-63519-3_2(16-44)Online publication date: 18-May-2021
https://doi.org/10.1007/978-3-662-63519-3_2
Show More Cited By

Index Terms

Strong consistency in cache augmented SQL systems

Recommendations

System level concurrency control for distributed database systems

A distributed database system is one in which the database is spread among several sites and application programs “move” from site to site to access and update the data they need. The concurrency control is that portion of the system that responds to ...
Virtual world consistency: A condition for STM systems (with a versatile protocol with invisible read operations)

The aim of a Software Transactional Memory (STM) is to discharge the programmers from the management of synchronization in multiprocess programs that access concurrent objects. To that end, an STM system provides the programmer with the concept of a ...
The notions of consistency and predicate locks in a database system

In database systems, users access shared data under the assumption that the data satisfies certain consistency constraints. This paper defines the concepts of transaction, consistency and schedule and shows that consistency requires that a transaction ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Middleware '14: Proceedings of the 15th International Middleware Conference

December 2014

334 pages

ISBN:9781450327855

DOI:10.1145/2663165

General Chair:
Laurent Réveillère
LaBRI, University of Bordeaux, France
,
Program Chairs:
Lucy Cherkasova
HP Labs, USA
,
François Taïani
Université de Rennes 1 / IRISA, France

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Orange
Conseil Régional d'Aquitaine
LaBRI: LaBRI
Raytheon BBN Technologies: Raytheon BBN Technologies
ACM: Association for Computing Machinery
Red Hat JBoss Middleware: Red Hat JBoss Middleware
Bordeaux: City of Bordeaux
USENIX Assoc: USENIX Assoc
GDR ASR: GDR Architecture, Systèmes et Réseaux
IBM: IBM
HP: HP
IFIP

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 December 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Middleware '14

Sponsor:

LaBRI
Raytheon BBN Technologies
ACM
Red Hat JBoss Middleware
Bordeaux
USENIX Assoc
GDR ASR
IBM
HP

Middleware '14: 15th International Middleware Conference

December 8 - 12, 2014

Bordeaux, France

Acceptance Rates

Middleware '14 Paper Acceptance Rate 27 of 144 submissions, 19%;

Overall Acceptance Rate 203 of 948 submissions, 21%

Upcoming Conference

MIDDLEWARE '24

25th International Middleware Conference

December 2 - 6, 2024

Hong Kong , Hong Kong

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
277
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 19 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nguyen HLi JGhandeharizadeh S(2024)Graph Stores with Application-Level Query Result CachesPerformance Evaluation and Benchmarking10.1007/978-3-031-68031-1_4(44-58)Online publication date: 22-Sep-2024
https://doi.org/10.1007/978-3-031-68031-1_4
An SCao YZhao W(2022)Competitive Consistent Caching for Transactions2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00207(2154-2167)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00207
Ghandeharizadeh SHuang HNguyen H(2021)Boosting OLTP Performance Using Write-Back Client-Side CachesTransactions on Large-Scale Data- and Knowledge-Centered Systems XLVIII10.1007/978-3-662-63519-3_2(16-44)Online publication date: 18-May-2021
https://doi.org/10.1007/978-3-662-63519-3_2
Alabdulkarim YAlmaymoni MGhandeharizadeh S(2019)Polygraph: A Plug-n-Play Framework to Quantify Application AnomaliesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.2939520(1-1)Online publication date: 2019
https://doi.org/10.1109/TKDE.2019.2939520
Ermakov NMolodyakov S(2019)Development and implementation of accelerated methods of data accessJournal of Physics: Conference Series10.1088/1742-6596/1326/1/0120251326(012025)Online publication date: 25-Oct-2019
https://doi.org/10.1088/1742-6596/1326/1/012025
Ghandeharizadeh SAlmaymoni MHuang H(2019)Rejig: A Scalable Online Algorithm for Cache Server Configuration ChangesTransactions on Large-Scale Data- and Knowledge-Centered Systems XLII10.1007/978-3-662-60531-8_5(111-134)Online publication date: 18-Oct-2019
https://doi.org/10.1007/978-3-662-60531-8_5
Ghandeharizadeh SAlabdulkarim YNguyen H(2019)CPR: Client-Side Processing of Range PredicatesCloud Computing – CLOUD 201910.1007/978-3-030-23502-4_24(340-354)Online publication date: 14-Jun-2019
https://doi.org/10.1007/978-3-030-23502-4_24
Ghandeharizadeh SHuang HNguyen H(2019)Nova: Diffused Database Processing Using Clouds of Components [Vision Paper]Beyond Databases, Architectures and Structures. Paving the Road to Smart Data Processing and Analysis10.1007/978-3-030-19093-4_1(3-14)Online publication date: 27-Apr-2019
https://doi.org/10.1007/978-3-030-19093-4_1
Ghandeharizadeh SNguyen HMoon C(2019)A Comparison of Two Cache Augmented SQL ArchitecturesMolecular Orientation and Emission Characteristics of Ir Complexes and Exciplex in Organic Thin Films10.1007/978-3-030-11404-6_8(94-109)Online publication date: 30-Jan-2019
https://doi.org/10.1007/978-3-030-11404-6_8
Alabdulkarim YAlmaymoni MGhandeharizadeh SHuang HNguyen H(2018)Testing Database Applications with PolygraphProceedings of the 20th International Conference on Information Integration and Web-based Applications & Services10.1145/3282373.3282378(200-206)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3282373.3282378
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents