More Web Proxy on the site http://driver.im/

research-article

Declarative programming over eventually consistent data stores

Authors:

KC Sivaramakrishnan,

Suresh JagannathanAuthors Info & Claims

ACM SIGPLAN Notices, Volume 50, Issue 6

Pages 413 - 424

https://doi.org/10.1145/2813885.2737981

Published: 03 June 2015 Publication History

Abstract

User-facing online services utilize geo-distributed data stores to minimize latency and tolerate partial failures, with the intention of providing a fast, always-on experience. However, geo-distribution does not come for free; application developers have to contend with weak consistency behaviors, and the lack of abstractions to composably construct high-level replicated data types, necessitating the need for complex application logic and invariably exposing inconsistencies to the user. Some commercial distributed data stores and several academic proposals provide a lattice of consistency levels, with stronger consistency guarantees incurring increased latency and throughput costs. However, correctly assigning the right consistency level for an operation requires subtle reasoning and is often an error-prone task. In this paper, we present QUELEA, a declarative programming model for eventually consistent data stores (ECDS), equipped with a contract language, capable of specifying fine-grained application - level consistency properties. A contract enforcement system analyses contracts, and automatically generates the appropriate consistency protocol for the method protected by the contract. We describe an implementation of QUELEA on top of an off-the-shelf ECDS that provides support for coordination-free transactions. Several benchmarks including two large web applications, illustrate the effectiveness of our approach.

References

[1]

P. Alvaro, N. Conway, J. Hellerstein, and W. R. Marczak. Consistency Analysis in Bloom: a CALM and Collected Approach. In CIDR 2011, Fifth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 9-12, 2011, Online Proceedings, pages 249–260, 2011. URL http://www.cidrdb.org/cidr2011/ Papers/CIDR11_Paper35.pdf.

[2]

P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Highly Available Transactions: Virtues and Limitations. PVLDB, 7(3):181–192, 2013.

Digital Library

[3]

P. Bailis, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Bolt-on Causal Consistency. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, pages 761–772, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2037-5. 1145/2463676.2465279.

Digital Library

[4]

P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Coordination-Avoiding Database Systems. CoRR, abs/1402.2237, 2014. URL http://arxiv.org/abs/1402.

Digital Library

[5]

2237.

[6]

M. Balakrishnan, D. Malkhi, T. Wobber, M. Wu, V. Prabhakaran, M. Wei, J. D. Davis, S. Rao, T. Zou, and A. Zuck. Tango: Distributed Data Structures over a Shared Log. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pages 325–340, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2388-8.

Digital Library

[7]

V. Balegas, N. Preguiça, R. Rodrigues, S. Duarte, C. Ferreira, M. Najafzadeh, and M. Shapiro. Putting the Consistency back into Eventual Consistency. In Proceedings of the Tenth European Conference on Computer System, EuroSys ’15, Bordeaux, France, 2015. URL http://lip6.fr/Marc.Shapiro/papers/ putting-consistency-back-EuroSys-2015.pdf.

Digital Library

[8]

H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, and P. O’Neil. A Critique of ANSI SQL Isolation Levels. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, SIGMOD ’95, pages 1–10, New York, NY, USA, 1995. ACM. ISBN 0-89791-731-6.

Digital Library

[9]

E. Brewer. Towards Robust Distributed Systems (Invited Talk), 2000.

[10]

S. Burckhardt, D. Leijen, M. Fähndrich, and M. Sagiv. Eventually Consistent Transactions. In Proceedings of the 21st European Conference on Programming Languages and Systems, ESOP’12, pages 67–86, Berlin, Heidelberg, 2012. Springer-Verlag. ISBN 978-3-642-28868-5.

Digital Library

[11]

S. Burckhardt, A. Gotsman, H. Yang, and M. Zawirski. Replicated Data Types: Specification, Verification, Optimality. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, pages 271–284, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2544-8. 2535838.2535848.

Digital Library

[12]

S. Burckhardt, D. Leijen, J. Protzenko, and M. Fähndrich. Global Sequence Protocol: A Robust Abstraction for Replicated Shared State. In Proceedings of the 29th European Conference on Object-Oriented Programming, ECOOP ’15, Prague, Czech Republic, 2015. URL http://research.microsoft.com/pubs/ 240462/gsp-tr-2015-2.pdf.

[13]

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing, SoCC ’10, pages 143–154, New York, NY, USA, 2010. ACM. ISBN 978-1-4503-0036-0.

Digital Library

[14]

G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s Highly Available Key-value Store. In Proceedings of Twentyfirst ACM SIGOPS Symposium on Operating Systems Principles, SOSP ’07, pages 205–220, New York, NY, USA, 2007. ACM. ISBN 978-1- 59593-591-5.

Digital Library

[15]

S. Gilbert and N. Lynch. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-tolerant Web Services. SIGACT News, 33(2):51–59, June 2002. ISSN 0163-5700.

Digital Library

[16]

564601.

[17]

M. P. Herlihy and J. M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990. ISSN 0164-0925.

Digital Library

[18]

[19]

KC Sivaramakrishnan, G. Kaki, and S. Jagannathan. Declarative Programming over Eventually Consistent Data Store. Technical Report TR-15-002, Purdue University, 2015. URL http://docs.lib. purdue.edu/cstech/1776/.

[20]

A. Lakshman and P. Malik. Cassandra: A Decentralized Structured Storage System. SIGOPS Operating Systems Review, 44(2):35–40, Apr. 2010. ISSN 0163-5980.

Digital Library

[21]

C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. Making Geo-replicated Systems Fast As Possible, Consistent when Necessary. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, pages 265– 278, Berkeley, CA, USA, 2012. USENIX Association. ISBN 978- 1-931971-96-6. URL http://dl.acm.org/citation.cfm? id=2387880.2387906.

Digital Library

[22]

C. Li, J. a. Leitão, A. Clement, N. Preguiça, R. Rodrigues, and V. Vafeiadis. Automating the Choice of Consistency Levels in Replicated Systems. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC’14, pages 281– 292, Berkeley, CA, USA, 2014. USENIX Association. ISBN 978- 1-931971-10-2. URL http://dl.acm.org/citation.cfm? id=2643634.2643664.

Digital Library

[23]

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 Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP ’11, pages 401–416, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0977-6. 2043556.2043593.

Digital Library

[24]

W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Stronger Semantics for Low-latency Geo-replicated Storage. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, nsdi’13, pages 313–328, Berkeley, CA, USA, 2013.

Digital Library

[25]

USENIX Association. URL http://dl.acm.org/citation. cfm?id=2482626.2482657.

[26]

C. H. Papadimitriou. The Serializability of Concurrent Database Updates. Journal of the ACM, 26(4):631–653, Oct. 1979. ISSN 0004- 5411.

Digital Library

[27]

K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers. Flexible Update Propagation for Weakly Consistent Replication. In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, SOSP ’97, pages 288–301, New York, NY, USA, 1997.

Digital Library

[28]

ACM. ISBN 0-89791-916-5.

[29]

RUBiS. Rice University Bidding System, 2014. URL http:// rubis.ow2.org/. Accessed: 2014-11-4 13:21:00.

[30]

M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-Free Replicated Data Types. In X. Défago, F. Petit, and V. Villain, editors, Stabilization, Safety, and Security of Distributed Systems, volume 6976 of Lecture Notes in Computer Science, pages 386– 400. Springer Berlin Heidelberg, 2011. ISBN 978-3-642-24549-7.

Digital Library

[31]

S. Sivasubramanian. Amazon dynamoDB: A Seamlessly Scalable Nonrelational Database Service. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD ’12, pages 729–730, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1247-9.

Digital Library

[32]

Y. Sovran, R. Power, M. K. Aguilera, and J. Li. Transactional Storage for Geo-replicated Systems. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP ’11, pages 385– 400, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0977-6.

Digital Library

[33]

D. B. Terry, A. J. Demers, K. Petersen, M. Spreitzer, M. Theimer, and B. W. Welch. Session Guarantees for Weakly Consistent Replicated Data. In Proceedings of the Third International Conference on Parallel and Distributed Information Systems, PDIS ’94, pages 140– 149, Washington, DC, USA, 1994. IEEE Computer Society. ISBN 0-8186-6400-2. URL http://dl.acm.org/citation.cfm? id=645792.668302.

Digital Library

[34]

D. B. Terry, V. Prabhakaran, R. Kotla, M. Balakrishnan, M. K. Aguilera, and H. Abu-Libdeh. Consistency-based Service Level Agreements for Cloud Storage. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pages 309–324, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2388-8. 2517349.2522731.

Digital Library

[35]

Twissandra. Twitter clone on Cassandra, 2014. URL http:// twissandra.com/. Accessed: 2014-11-4 13:21:00.

[36]

Z3. High-performance Theorem Prover, 2014. URL http://z3. codeplex.com/. Accessed: 2014-11-4 13:21:00. Introduction System Model Motivation RDT Specification Summarization Anomalies under Eventual Consistency Contracts From Contracts to Implementation Contract Language Syntax Semantics Capturing Store Semantics Contract Classification Generality of Contracts Soundness of Contract Classification Transaction Contracts Syntax and Semantics Extensions Transactional Bank Account Coordination-free Transactions Classification Implementation Operation Consistency Transactions Summarization Evaluation Related Work Conclusions

Cited By

Kallas KNiksic FStanford CAlur RLee JAgrawal KSpear M(2022)Stream processing with dependency-guided synchronizationProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508413(1-16)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508413
Biswas RKakwani DVedurada JEnea CLal A(2021)MonkeyDB: effectively testing correctness under weak isolation levelsProceedings of the ACM on Programming Languages10.1145/34855465:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485546
Gadducci FMelgratti HRoldán CSammartino M(2021)Categorical specification and implementation of Replicated Data TypesTheoretical Computer Science10.1016/j.tcs.2021.12.020Online publication date: Dec-2021
https://doi.org/10.1016/j.tcs.2021.12.020
Show More Cited By

Index Terms

Declarative programming over eventually consistent data stores

Recommendations

Declarative programming over eventually consistent data stores
PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation

User-facing online services utilize geo-distributed data stores to minimize latency and tolerate partial failures, with the intention of providing a fast, always-on experience. However, geo-distribution does not come for free; application developers ...
Limitations of Highly-Available Eventually-Consistent Data Stores
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Modern replicated data stores aim to provide high availability, by immediately responding to client requests, often by implementing objects that expose concurrency. Such objects, for example, multi-valued registers (MVRs), do not have sequential ...
Secure replication for client-centric data stores
DICG '22: Proceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good

Decentralized, peer-to-peer systems using Conflict-free Replicated Data Types (CRDTs) can offer a more privacy-friendly alternative to centralized solutions that are often used by Big Tech. However, traditional CRDTs assume that all replicas are trusted,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 50, Issue 6

PLDI '15

June 2015

630 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2813885

Editor:
Andy Gill
University of Kansas, Lawrence, KS

Issue’s Table of Contents

PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2015
630 pages
ISBN:9781450334686
DOI:10.1145/2737924
General Chair:
David Grove
IBM Research, USA
,
Program Chair:
Steve Blackburn
Australian National University, Australia

Copyright © 2015 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2015

Published in SIGPLAN Volume 50, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
762
Total Downloads

Downloads (Last 12 months)101
Downloads (Last 6 weeks)12

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kallas KNiksic FStanford CAlur RLee JAgrawal KSpear M(2022)Stream processing with dependency-guided synchronizationProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508413(1-16)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508413
Biswas RKakwani DVedurada JEnea CLal A(2021)MonkeyDB: effectively testing correctness under weak isolation levelsProceedings of the ACM on Programming Languages10.1145/34855465:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485546
Gadducci FMelgratti HRoldán CSammartino M(2021)Categorical specification and implementation of Replicated Data TypesTheoretical Computer Science10.1016/j.tcs.2021.12.020Online publication date: Dec-2021
https://doi.org/10.1016/j.tcs.2021.12.020
Zeller PBieniusa APoetzsch-Heffter A(2021)Combining state- and event-based semantics to verify highly available applicationsScience of Computer Programming10.1016/j.scico.2021.102687210(102687)Online publication date: Oct-2021
https://doi.org/10.1016/j.scico.2021.102687
Gadducci FMelgratti HRoldán CSammartino M(2020)Implementation Correctness for Replicated Data Types, CategoricallyTheoretical Aspects of Computing – ICTAC 202010.1007/978-3-030-64276-1_15(283-303)Online publication date: 25-Nov-2020
https://doi.org/10.1007/978-3-030-64276-1_15
Dexter PChiu KSendir B(2019)An Error-Reflective Consistency Model for Distributed Data Stores2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00082(728-737)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00082
Zhao XHaller PDe Koster JBergenti FFranco J(2018)Observable atomic consistency for CvRDTsProceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control10.1145/3281366.3281372(23-32)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3281366.3281372
Mansouri YToosi ABuyya R(2017)Data Storage Management in Cloud EnvironmentsACM Computing Surveys10.1145/313662350:6(1-51)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1145/3136623
Flores PSiqueira F(2017)Invariant Control in Eventually Consistent DatabasesProceedings of the 20th International Workshop on the Web and Databases10.1145/3068839.3068844(13-18)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1145/3068839.3068844
Gadducci FMelgratti HRoldán C(2017)A Denotational View of Replicated Data TypesCoordination Models and Languages10.1007/978-3-319-59746-1_8(138-156)Online publication date: 27-May-2017
https://doi.org/10.1007/978-3-319-59746-1_8
Show More Cited By

View Options

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 Issue’s Table of Contents