Consistency-based service level agreements for cloud storage
Open accessThe DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Time, clocks, and the ordering of events in a distributed system
Lamport, L. (1978) · Communications of the ACM · doi:10.1145/359545.359563 · Cited by 8,488 · cited 1×
“Our definition of causal consistency resembles that used in other systems [28][30] but includes the notion of sessions.”
Benchmarking cloud serving systems with YCSB
Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., & Sears, R. (2010) · Proceedings of the 1st ACM symposium on Cloud computing · doi:10.1145/1807128.1807152 · Cited by 3,716 · cited 1×
“The widely used YCSB benchmark [18], which was developed for evaluating the performance of cloudbased key-value stores, provided the workload that we”
MethodBigtable: A Distributed Storage System for Structured Data
Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., & Gruber, R. E. (2008) · ACM Transactions on Computer Systems · doi:10.1145/1365815.1365816 · Cited by 3,460
(2007) · doi:10.1145/1294261.1294281 · Cited by 3,447 · cited 1×
“Such storage services invariably replicate application data on multiple machines to make it highly available.”
BackgroundCassandra: a decentralized structured storage system
Lakshman, A., & Malik, P. (2010) · ACM SIGOPS Operating Systems Review · doi:10.1145/1773912.1773922 · Cited by 2,664 · cited 2×
“These include Dynamo [20], SimpleDB [5], BigTable [16], PNUTS [17][35], Cassandra [27], Windows Azure [14], Spanner [19], and many more [15].”
Scalable SQL and NoSQL data stores
Cattell, R. (2011) · ACM SIGMOD Record · doi:10.1145/1978915.1978919 · Cited by 1,358 · cited 1×
“These include Dynamo [20], SimpleDB [5], BigTable [16], PNUTS [17][35], Cassandra [27], Windows Azure [14], Spanner [19], and many more [15].”
Vogels, W. (2009) · Communications of the ACM · doi:10.1145/1435417.1435432 · Cited by 1,013 · cited 1×
“Such storage services invariably replicate application data on multiple machines to make it highly available.”
BackgroundPNUTS: Yahoo!'s hosted data serving platform
Cooper, B. F., Ramakrishnan, R., Srivastava, U., Silberstein, A., Bohannon, P., Jacobsen, H.-A., Puz, N., Weaver, D., & Yerneni, R. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454167 · Cited by 958 · cited 9×
“These include Dynamo [20], SimpleDB [5], BigTable [16], PNUTS [17][35], Cassandra [27], Windows Azure [14], Spanner [19], and many more [15].”
BackgroundMethodInfluentialManaging update conflicts in Bayou, a weakly connected replicated storage system
Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., & Hauser, C. H. (1995) · Proceedings of the fifteenth ACM symposium on Operating systems principles - SOSP '95 · doi:10.1145/224056.224070 · Cited by 815 · cited 1×
“Pileus actually provides a stronger form of eventual consistency than many systems, a guarantee that has been called prefix consistency [37] or timeline consistency [17].”
BackgroundSelf-citationSpanner: Google's globally-distributed database
Corbett, J. C., Dean, J. B., Epstein, M., Fikes, A., Frost, C., Furman, J. J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., et al. (2012) · doi:10.5555/2387880.2387905 · Cited by 807
Windows Azure Storage: a highly available cloud storage service with strong consistency
Calder, B., Wang, J., Ogus, A., Nilakantan, N., Skjolsvold, A., McKelvie, S., Xu, Y., Srivastav, S., Wu, J., Simitci, H., et al. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043571 · Cited by 796
Megastore: Providing Scalable, Highly Available Storage for Interactive Services
Baker, J. D., Bond, C. T., Corbett, J. C., Furman, J. J., Khorlin, A., Larson, J. A., Leon, J.-M., Li, Y., Lloyd, A., & Yushprakh, V. (2011) · Cited by 645
CAP twelve years later: How the "rules" have changed
Brewer, E. (2012) · Computer · doi:10.1109/mc.2012.37 · Cited by 614 · cited 1×
“Recognizing these fundamental trade-offs [12], storage systems like Amazon’s SimpleDB and DynamoDB [43], Google’s AppEngine data store [22],”
BackgroundDon't settle for eventual: scalable causal consistency for wide-area storage with COPS
Lloyd, W., Freedman, M. J., Kaminsky, M., & Andersen, D. G. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043593 · Cited by 565 · cited 2×
“Researchers have proposed consistency models with guarantees that lie between these two extremes, such as session guarantees [36], continuous consistency [3][9][46], RedBlue consistency [29], and causal consistency [30], and many have been shown to be useful in diverse applications [10][36][42][23][34].”
BackgroundChain replication for supporting high throughput and availability
van Renesse, R., & Schneider, F. B. (2004) · Operating Systems Design and Implementation · Cited by 495
Session guarantees for weakly consistent replicated data
Terry, D., Demers, A. J., Petersen, K., Spreitzer, M., Theimer, M. M., & Welch, B. B. (2002) · International Conference on Parallel and Distributed Information Systems · doi:10.1109/pdis.1994.331722 · Cited by 430 · cited 4×
“demonstrated that a variety of consistency guarantees are useful including monotonic reads, read-my-writes, and bounded staleness [36][39][42][46].”
BackgroundInfluentialSelf-citationMaking Geo-Replicated Systems Fast as Possible, Consistent when Necessary
Li, C., Porto, D., Clement, A., Gehrke, J. E., Preguiça, N., & Rodrigues, R. (2012) · Max Planck Digital Library · Cited by 381
Managing update conflicts in Bayou, a weakly connected replicated storage system
Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., & Hauser, C. H. (1995) · ACM SIGOPS Operating Systems Review · doi:10.1145/224057.224070 · Cited by 339
Self-citationVolley: automated data placement for geo-distributed cloud services
Agarwal, S., Dunagan, J., Jain, N., Saroiu, S., Wolman, A., & Bhogan, H. (2010) · doi:10.5555/1855711.1855713 · Cited by 324
Data caching issues in an information retrieval system
Alonso, R. D. H., Barbará, D., & García-Molina, H. (1990) · ACM Transactions on Database Systems · doi:10.1145/88636.87848 · Cited by 319 · cited 1×
“Researchers have proposed consistency models with guarantees that lie between these two extremes, such as session guarantees [36], continuous consistency [3][9][46], RedBlue consistency [29], and causal consistency [30], and many have been shown to be useful in diverse applications [10][36][42][23][34].”
BackgroundDesign and evaluation of a conit-based continuous consistency model for replicated services
Yu, H., & Vahdat, A. (2002) · ACM Transactions on Computer Systems · doi:10.1145/566340.566342 · Cited by 289 · cited 3×
“demonstrated that a variety of consistency guarantees are useful including monotonic reads, read-my-writes, and bounded staleness [36][39][42][46].”
BackgroundConsistency rationing in the cloud: pay only when it matters
Kraska, T., Hentschel, M., Alonso, G., & Kossmann, D. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687657 · Cited by 207 · cited 2×
“Even within a datacenter, the latency of strongly consistent reads has been measured as eight times that of reads with weaker session guarantees [26].”
BackgroundA self-organized, fault-tolerant and scalable replication scheme for cloud storage
Bonvin, N., Papaioannou, T. G., & Aberer, K. (2010) · ACM Symposium on Cloud Computing (SoCC) · doi:10.1145/1807128.1807162 · Cited by 151 · cited 1×
“Other work has shown how to provide more dynamic reconfiguration [1][13][25], and we could adopt such mechanisms in the future as they are largely orthogonal to our new contributions.”
BackgroundWada, H., Fekete, A. D., Zhao, L., Lee, K., & Liu, A. (2011) · Cited by 149
Replicated data consistency explained through baseball
Terry, D. (2013) · Communications of the ACM · doi:10.1145/2500500 · Cited by 134 · cited 2×
“demonstrated that a variety of consistency guarantees are useful including monotonic reads, read-my-writes, and bounded staleness [36][39][42][46].”
BackgroundResultSelf-citationEventual consistency: How soon is eventual? An evaluation of Amazon S3's consistency behavior
Bermbach, D., & Tai, S. (2011) · Middleware for Service Oriented Computing · doi:10.1145/2093185.2093186 · Cited by 118 · cited 1×
“Studies have shown that even eventually consistent systems frequently deliver strongly consistent data [11][44].”
BackgroundAnalyzing consistency properties for fun and profit
Golab, W., Li, X., & Shah, M. A. (2011) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1993806.1993834 · Cited by 98
Sinfonia: A new paradigm for building scalable distributed systems
Aguilera, M. K., Merchant, A., Shah, M. A., Veitch, A., & Karamanolis, C. (2009) · ACM Transactions on Computer Systems · doi:10.1145/1629087.1629088 · Cited by 82
Self-citationSCADS: Scale-Independent Storage for Social Computing ApplicationsPreprint
Armbrust, M., Fox, A., Patterson, D. A., Lanham, N., Trushkowsky, B., Trutna, J., & Oh, H. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0909.1775 · Cited by 76
What consistency does your key-value store actually provide?
Anderson, E. J., Li, X., Shah, M. A., Tucek, J. A., & Wylie, J. J. (2010) · Hot Topics in System Dependability · Cited by 70
Where in the world is my data?
Kadambi, S., Chen, J., Cooper, B. F., Lomax, D., Ramakrishnan, R., Silberstein, A., Tam, E., & García-Molina, H. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402707.3402740 · Cited by 32
Flex-KV: enabling high-performance and flexible KV systems
Phanishayee, A., Andersen, D. G., Pucha, H., Повзнер, А. А., & Belluomini, W. (2012) · doi:10.1145/2378356.2378361 · Cited by 21 · cited 1×
“Researchers have observed the need for more flexible storage designs that permit tradeoffs between consistency and availability [33].”
Background
Cited by
Big Data and cloud computing: innovation opportunities and challenges
Yang, C., Huang, Q., Li, Z., Liu, K., & Hu, F. (2017) · International Journal of Digital Earth · doi:10.1080/17538947.2016.1239771 · Cited by 838
Davoudian, A., Chen, L., & Liu, M. (2019) · ACM Computing Surveys · doi:10.1145/3158661 · Cited by 207
“Recently, there have been some studies on relieving the application programmer of the manual and error-prone selection of the correct level of consistency, whereby the decision process is automatically performed by the application (Li et al. 2014; Liu et al. 2014; Terry et al. 2013).”
Background
Metadata
- Authors
- Terry, D. B., Prabhakaran, V., Kotla, R., Balakrishnan, M., Aguilera, M. K., & Abu-Libdeh, H.
- Venue
- Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles
- Publisher
- ACM
- Published
- 2013-11-03
- Pages
- 309-324
- OpenAlex
- W2078432474
- Cited by
- 221
- References
- 32
- FWCI
- 19.24
- Type
- conference paper
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.