Don't settle for eventual: Scalable causal consistency for wide-area storage with COPS

Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, David G. Andersen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

319 Scopus citations

Abstract

Geo-replicated, distributed data stores that support complex online applications, such as social networks, must provide an "always-on" experience where operations always complete with low latency. Today's systems often sacrifice strong consistency to achieve these goals, exposing inconsistencies to their clients and necessitating complex application logic. In this paper, we identify and define a consistency model - causal consistency with convergent conflict handling, or causal+ - that is the strongest achieved under these constraints. We present the design and implementation of COPS, a key-value store that delivers this consistency model across the wide-area. A key contribution of COPS is its scalability, which can enforce causal dependencies between keys stored across an entire cluster, rather than a single server like previous systems. The central approach in COPS is tracking and explicitly checking whether causal dependencies between keys are satisfied in the local cluster before exposing writes. Further, in COPS-GT, we introduce get transactions in order to obtain a consistent view of multiple keys without locking or blocking. Our evaluation shows that COPS completes operations in less than a millisecond, provides throughput similar to previous systems when using one server per cluster, and scales well as we increase the number of servers in each cluster. It also shows that COPS-GT provides similar latency, throughput, and scaling to COPS for common workloads.

Original languageEnglish (US)
Title of host publicationSOSP'11 - Proceedings of the 23rd ACM Symposium on Operating Systems Principles
Pages401-416
Number of pages16
DOIs
StatePublished - Dec 7 2011
Event23rd ACM Symposium on Operating Systems Principles, SOSP 2011 - Cascais, Portugal
Duration: Oct 23 2011Oct 26 2011

Publication series

NameSOSP'11 - Proceedings of the 23rd ACM Symposium on Operating Systems Principles

Other

Other23rd ACM Symposium on Operating Systems Principles, SOSP 2011
CountryPortugal
CityCascais
Period10/23/1110/26/11

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • ALPS systems
  • causal + consistency
  • key-value storage
  • read transactions
  • scalable wide-area replication

Fingerprint Dive into the research topics of 'Don't settle for eventual: Scalable causal consistency for wide-area storage with COPS'. Together they form a unique fingerprint.

Cite this