Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01vx021f18v
Title: Stronger Consistency and Semantics for Low-Latency Geo-Replicated Storage
Authors: Lloyd, Wyatt
Advisors: Freedman, Michael J
Contributors: Computer Science Department
Keywords: Causal Consistency
Distributed Systems
Geo-Replicated Storage
Scalable Storage
Subjects: Computer science
Issue Date: 2013
Publisher: Princeton, NJ : Princeton University
Abstract: Geo-replicated, distributed data stores that support complex online applications, such as social networks, strive to provide an always-on experience where operations always successfully complete with low latency. Today's systems sacrifice strong consistency and expressive semantics to achieve these goals, exposing inconsistencies to their clients and necessitating complex application logic. In this work, we identify and define a consistency model--causal consistency with convergent conflict handling, or causal+--that is the strongest achieved under these constraints. We explore the ramifications of and implementation techniques for causal+ consistency through the design and implementation of two storage systems, COPS and Eiger. COPS is a key-value store that provides causal+ consistency. 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. Eiger is a system that provides causal+ consistency for the rich column-family data model. The central approach in COPS and Eiger is tracking and explicitly checking that causal dependencies between keys are satisfied in the local cluster before exposing writes. Our work also provides stronger semantics, in the form of read- and write-only transac- tions, that allow programmers to consistently interact with data spread across many servers. COPS includes the first scalable read-only transactions that can optimistically complete in one round of local reads and take at most two non-blocking rounds of local reads. Eiger includes read-only transactions with the same properties that are more general--they are applicable to non-causal systems--and more fault-tolerant. Eiger also includes scalable write-only transactions that take three rounds of local non-blocking communication and do not block concurrent read-only transactions. We implemented COPS and Eiger and demonstrate their performance experimentally. The later of these systems, Eiger, achieves low latency, has throughput competitive with an eventually-consistent and non-transactional production system, and scales to large clusters almost linearly.
URI: http://arks.princeton.edu/ark:/88435/dsp01vx021f18v
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Lloyd_princeton_0181D_10586.pdf1.17 MBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.