KC Sivaramakrishnan
Gowtham Kaki
Skip Abstract Section
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.
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. doi: 10. 1145/2463676.2465279. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 2237.Google Scholar
- 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. doi: 10.1145/2517349.2522732. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. doi: 10.1145/223784.223785. Google ScholarDigital Library
- E. Brewer. Towards Robust Distributed Systems (Invited Talk), 2000.Google Scholar
- 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. doi: 10.1007/978-3-642-28869-2_4. Google ScholarDigital Library
- 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. doi: 10.1145/ 2535838.2535848. Google ScholarDigital Library
- 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.Google Scholar
- 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. doi: 10.1145/1807128.1807152. Google ScholarDigital Library
- 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. doi: 10.1145/1294261.1294281. Google ScholarDigital Library
- 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. doi: 10.1145/564585. Google ScholarDigital Library
- 564601.Google Scholar
- 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. Google ScholarDigital Library
- doi: 10.1145/78969.78972.Google Scholar
- 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/.Google Scholar
- A. Lakshman and P. Malik. Cassandra: A Decentralized Structured Storage System. SIGOPS Operating Systems Review, 44(2):35–40, Apr. 2010. ISSN 0163-5980. doi: 10.1145/1773912.1773922. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. doi: 10.1145/ 2043556.2043593. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- USENIX Association. URL http://dl.acm.org/citation. cfm?id=2482626.2482657.Google Scholar
- C. H. Papadimitriou. The Serializability of Concurrent Database Updates. Journal of the ACM, 26(4):631–653, Oct. 1979. ISSN 0004- 5411. doi: 10.1145/322154.322158. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- ACM. ISBN 0-89791-916-5. doi: 10.1145/268998.266711.Google Scholar
- RUBiS. Rice University Bidding System, 2014. URL http:// rubis.ow2.org/. Accessed: 2014-11-4 13:21:00.Google Scholar
- 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. doi: 10.1007/978-3-642-24550-3_29. Google ScholarDigital Library
- 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. doi: 10.1145/2213836.2213945. Google ScholarDigital Library
- 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. doi: 10.1145/2043556.2043592. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. doi: 10.1145/ 2517349.2522731. Google ScholarDigital Library
- Twissandra. Twitter clone on Cassandra, 2014. URL http:// twissandra.com/. Accessed: 2014-11-4 13:21:00.Google Scholar
- 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 ConclusionsGoogle Scholar
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 ImplementationUser-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 ComputingModern 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 GoodDecentralized, 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