Consistency-based service level agreements for cloud storage
Published 8 October 2013Open access
Douglas B. Terry, Vijayan Prabhakaran, Ramakrishna Kotla, Mahesh Balakrishnan, Marcos K. Aguilera, Hussam Abu-Libdeh
Citations220
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Evaluations running on a worldwide test bed with geo-replicated data show that the Pileus system adapts to varying client-server latencies to provide service that matches or exceeds the best static consistency choice and server selection scheme.
Abstract
Choosing a cloud storage system and specific operations for reading and writing data requires developers to make decisions that trade off consistency for availability and performance. Applications may be locked into a choice that is not ideal for all clients and changing conditions. Pileus is a replicated key-value store that allows applications to declare their consistency and latency priorities via consistency-based service level agreements (SLAs). It dynamically selects which servers to access in order to deliver the best service given the current configuration and system conditions. In application-specific SLAs, developers can request both strong and eventual consistency as well as intermediate guarantees such as read-my-writes. Evaluations running on a worldwide test bed with geo-replicated data show that the system adapts to varying client-server latencies to provide service that matches or exceeds the best static consistency choice and server selection scheme.
Keywords
Computer Science
Communications of the ACMTime, clocks, and the ordering of events in a distributed system
8,437 Citations1978Leslie Lamport
A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events, and a bound is derived on how far out of synchrony the clocks can become.
Benchmarking cloud serving systems with YCSB
3,632 Citations2010Brian F. Cooper, Adam Silberstein +3 more
This work presents the "Yahoo! Cloud Serving Benchmark" (YCSB) framework, with the goal of facilitating performance comparisons of the new generation of cloud data serving systems, and defines a core set of benchmarks and reports results for four widely used systems.
Dynamo
3,454 Citations2007Giuseppe DeCandia, Deniz Hastorun +7 more
D Dynamo is presented, a highly available key-value storage system that some of Amazon's core services use to provide an "always-on" experience and makes extensive use of object versioning and application-assisted conflict resolution in a manner that provides a novel interface for developers to use.
ACM Transactions on Computer SystemsBigtable
3,432 Citations2008Fay W. Chang, Jay B. Dean +7 more
The simple data model provided by Bigtable is described, which gives clients dynamic control over data layout and format, and the design and implementation of Bigtable are described.
ACM SIGOPS Operating Systems ReviewCassandra
2,630 Citations2010Avinash Lakshman, Prashant Malik
Cassandra is a distributed storage system for managing very large amounts of structured data spread out across many commodity servers, while providing highly available service with no single point of failure.
ACM SIGMOD RecordScalable SQL and NoSQL data stores
1,345 Citations2011R. G. G. Cattell
This paper examines a number of SQL and socalled "NoSQL" data stores designed to scale simple OLTP-style application loads over many servers, and contrasts the new systems on their data model, consistency mechanisms, storage mechanisms, durability guarantees, availability, query support, and other dimensions.
Communications of the ACMEventually consistent
1,005 Citations2008Werner Vogels
Building reliable distributed systems at a worldwide scale demands trade-offs between consistency and availability.
Proceedings of the VLDB EndowmentPNUTS
960 Citations2008Brian F. Cooper, Raghu Ramakrishnan +7 more
PNUTS provides data storage organized as hashed or ordered tables, low latency for large numbers of concurrent requests including updates and queries, and novel per-record consistency guarantees and utilizes automated load-balancing and failover to reduce operational complexity.
Spanner: Google's globally-distributed database
827 Citations2012James C. Corbett, Jay B. Dean +24 more
Managing update conflicts in Bayou, a weakly connected replicated storage system
814 Citations1995Doug Terry, Marvin Theimer +4 more
The motivation for and design of these mechanisms for conflict detection and per -write conflict resolution based on client-provid ed procedures are presented and the experiences gained with an initial implementation of the system are described.
Windows Azure Storage
799 Citations2011Brad Calder, Wang Ju +25 more
The WAS architecture, global namespace, and data model is described, as well as its resource provisioning, load balancing, and replication systems.
Megastore: Providing Scalable, Highly Available Storage for Interactive Services
654 Citations2011Jason D. Baker, Chris T. Bond +8 more
Megastore provides fully serializable ACID semantics within ne-grained partitions of data, which allows us to synchronously replicate each write across a wide area network with reasonable latency and support seamless failover between datacenters.
Don't settle for eventual
569 Citations2011Wyatt Lloyd, Michael J. Freedman +2 more
This paper identifies and defines a consistency model---causal consistency with convergent conflict handling, or causal+---that is the strongest achieved under these constraints and presents the design and implementation of COPS, a key-value store that delivers this consistency model across the wide-area.
ComputerCAP twelve years later: How the "rules" have changed
562 Citations2012Kyle Palos
The featured Web extra is a podcast from Software Engineering Radio, in which the host interviews Dwight Merriman about the emerging NoSQL movement, the three types of nonrelational data stores, Brewer's CAP theorem, and much more.
Session guarantees for weakly consistent replicated data
411 Citations2002Doug Terry, Alan Demers +4 more
Four per-session guarantees are proposed to aid users and applications of weakly consistent replicated data: "read your writes", "monotonic reads", "writes follow reads", and " monotonic writes".
Chain replication for supporting high throughput and availability
374 Citations2004Robbert van Renesse, Fred B. Schneider
Besides outlining the chain replication protocols themselves, simulation experiments explore the performance characteristics of a prototype implementation and several object-placement strategies (including schemes based on distributed hash table routing) are discussed.
ACM SIGOPS Operating Systems ReviewManaging update conflicts in Bayou, a weakly connected replicated storage system
335 Citations1995Doug Terry, Marvin Theimer +4 more
Networked Systems Design and ImplementationVolley: automated data placement for geo-distributed cloud services
327 Citations2010Sharad Agarwal, John Dunagan +4 more
Volley is evaluated on the month-long Live Mesh trace, and it is found that, compared to a state-of-the-art heuristic, Volley simultaneously reduces datacenter capacity skew, reduces inter-datacenter traffic by over 1.8× and reduces 75th percentile user-latency by over 30%.
ACM Transactions on Database SystemsData caching issues in an information retrieval system
323 Citations1990Rafael Alonso, Daniel Barbará +1 more
Using a user's local storage capabilities to cache data at the user's site would improve the response time of user queries albeit at the cost ofurring the overhead required in maintaining multiple copies.
ACM Transactions on Computer SystemsDesign and evaluation of a conit-based continuous consistency model for replicated services
291 Citations2002Haifeng Yu, Amin Vahdat
It is argued that the TACT consistency model can simultaneously achieve the often conflicting goals of generality and practicality by describing how a broad range of applications can express their consistency semantics using TACT and by demonstrating that application-independent algorithms can efficiently enforce target consistency levels.
Proceedings of the VLDB EndowmentConsistency rationing in the cloud
205 Citations2009Tim Kraska, Martin Hentschel +2 more
A new transaction paradigm is presented, that not only allows designers to define the consistency guarantees on the data instead at the transaction level, but also allows to automatically switch consistency guarantees at runtime.
Data Consistency Properties and the Trade-offs in Commercial Cloud Storages: the Consumers' Perspective
149 Citations2011Hiroshi Wada, Alan Fekete +3 more
It is found that many platforms seem in practice to offer more consistency than they promise; there are also cases where the platform offers consumers a choice between stronger and weaker consistency, but there is no observed benefit from accepting weaker consistency properties.
Communications of the ACMReplicated data consistency explained through baseball
133 Citations2013Doug Terry
A broader class of consistency guarantees can, and perhaps should, be offered to clients that read shared data.
A self-organized, fault-tolerant and scalable replication scheme for cloud storage
126 Citations2010Nicolas Bonvin, Thanasis G. Papaioannou +1 more
A self-managed key-value store that dynamically allocates the resources of a data cloud to several applications in a cost-efficient and fair way and dynamically maintains multiple differentiated availability guarantees to each different application despite failures is proposed.
Eventual consistency
113 Citations2011David Bermbach, Stefan Tai
A novel approach to benchmark staleness in distributed datastores is presented and the approach is used to evaluate Amazon's Simple Storage Service (S3) and unexpected findings are reported.
Networked Systems Design and ImplementationPRACTI replication
108 Citations2006Nalini Belaramani, Mike Dahlin +5 more
Analyzing consistency properties for fun and profit
93 Citations2011Wojciech Golab, Xiaozhou Li +1 more
This work addresses two important problems related to the consistency properties in a history of operations on a read/write register, and investigates two quantities: one is the staleness of the reads and the commonality of violations.
Relaxed currency and consistency
86 Citations2004Hongfei Guo, Per-Åke Larson +2 more
This paper explains how C&C constraints are enforced in MTCache, the prototype mid-tier database cache, including how constraints and replica update policies are elegantly integrated into the cost-based query optimizer.
Hot Topics in System DependabilityWhat consistency does your key-value store actually provide?
72 Citations2010Eric Anderson, Xiaozhou Li +3 more
By analyzing the trace of interactions between the client machines and a key-value store, the algorithms can report whether the trace is safe, regular, or atomic, and if not, how many violations there are in the trace.
ACM Transactions on Computer SystemsSinfonia
65 Citations2009Marcos K. Aguilera, Arif Merchant +3 more
At the core of Sinfonia is a new minitransaction primitive that enables efficient and consistent access to data, while hiding the complexities that arise from concurrency and failures.
The VLDB JournalThe demarcation protocol: A technique for maintaining constraints in distributed database systems
64 Citations1994Daniel Barbar�-Mill�, Héctor García-Molina
The demarcation protocol is presented; it overcomes problems by using explicit consistency constraints as the correctness criteria, and is shown how this technique can be applied to linear arithmetic, existential, key, and approximate copy constraints.
arXiv (Cornell University)SCADS: Scale-Independent Storage for Social Computing Applications
49 Citations2009Michael Armbrust, Armando Fox +5 more
A new architecture, SCADS, is proposed that allows the developer to declaratively state application specific consistency requirements, takes advantage of utility computing to provide cost effective scale-up and scale-down, and will use machine learning models to introspectively anticipate performance problems and predict the resource requirements of new queries before execution.
Proceedings of the VLDB EndowmentWhere in the world is my data?
32 Citations2011Sudarshan Kadambi, Jianjun Chen +6 more
This paper introduces a flexible constraint language to specify replication policy constraints, and presents an adaptive scheme for replicating data to where it is most frequently accessed, while respecting policy constraints and using minimal bookkeeping.
An Application-Based Adaptive Replica Consistency for Cloud Storage
26 Citations2010Ximei Wang, Shoubao Yang +3 more
An application-based adaptive mechanism of replica consistency is proposed in this paper, dividing the consistency of applications into four categories according to their read frequencies and update frequencies, and then design corresponding consistency strategies.
Flex-KV
16 Citations2012Amar Phanishayee, David G. Andersen +3 more
The case is made for a flexible key-value storage system (Flex-KV) that can support both DRAM and disk-based storage, can act as an unreliable cache or a durable store, and operate consistently or inconsistently.
Transactions with Consistency Choices on Geo-Replicated Cloud Storage
13 Citations2013Ramakrishna Kotla, Mahesh Balakrishnan +2 more
Pileus is a replicated and scalable key-value storage system that features geo-replicated transactions with varying degrees of consistency chosen by applications.
A batch of PNUTS
13 Citations2011Adam Silberstein, Russell Sears +2 more
This paper discusses the experience of running batch-oriented Hadoop on top of Yahoo's serving-oriented PNUTS system instead of the standard HDFS file system, and introduces a batch write path to improve latency-insensitive write throughput to PnUTS.
Weak consistency as a last resort
5 Citations2010Marco Serafini, Flavio Junqueira
This paper shows how Eventual Linearizability can be used to support master-worker schemes such as workload sharding in Web applications and shows that it can significantly reduce the time to completion of the workload in some settings.