More Web Proxy on the site http://driver.im/

Article

What consistency does your key-value store actually provide?

Authors:

Jay J. WylieAuthors Info & Claims

HotDep'10: Proceedings of the Sixth international conference on Hot topics in system dependability

Pages 1 - 16

Published: 03 October 2010 Publication History

Abstract

Many key-value stores have recently been proposed as platforms for always-on, globally-distributed, Internet-scale applications. To meet their needs, these stores often sacrifice consistency for availability. Yet, few tools exist that can verify the consistency actually provided by a key-value store, and quantify the violations if any. How can a user check if a storage system meets its promise of consistency? If a system only promises eventual consistency, how bad is it really? In this paper, we present efficient algorithms that help answer these questions. 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. We run these algorithms on traces of our eventually consistent key-value store called Pahoehoe and find few or no violations, thus showing that it often behaves like a strongly consistent system during our tests.

References

[1]

A. Aiyer, L. Alvisi, and R. A. Bazzi. On the availability of non-strict quorum systems. In Proc. 19th DISC, pages 48-62, September 2005.

Digital Library

[2]

A. S. Aiyer, E. Anderson, X. Li, M. A. Shah, and J. J. Wylie. Consistability: Describing usually consistent systems. In HotDep. USENIX Association, 2008.

Digital Library

[3]

E. Anderson, C. Hoover, X. Li, and J. Tucek. Efficient Tracing and Performance Analysis for Large Distributed Systems. In MASCOTS '09: Proceedings of the 17th IEEE International Symposium on Modeling, Analysis, and Simulation, September 2009.

[4]

E. Anderson, X. Li, A. Merchant, M. A. Shah, K. Smathers, J. Tucek, M. Uysal, and J. J. Wylie. Efficient eventual consistency in Pahoehoe, an erasure-coded key-blob archive. In DSN'10, pages 181-190, June 2010.

[5]

E. Anderson, X. Li, M. Shah, J. Tucek, and J. J. Wylie. What consistency does your key-value store actually provide? Technical Report HPL-2010-98, Hewlett-Packard Laboratories, 2010.

[6]

E. Brewer. Towards robust distributed systems, 2000. Available at http://www.cs.berkeley.edu/ ~brewer/cs262b-2004/PODC-keynote.pdf. Accessed May 2010.

Digital Library

[7]

Cassandra. Available at http://incubator. apache.org/cassandra/. Accessed December 2009.

[8]

F. Chang, J. Dean, S. Ghemawhat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A distributed storage system for structured data. In OSDI'06, pages 205-218, November 2006.

Digital Library

[9]

B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. In Proceedings of the 34th International Conference on Very Large Data Bases (VLDB'08), pages 1277-1288, August 2008.

Digital Library

[10]

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In ACM Symposium on Cloud Computing (SoCC), pages 143-154, 2010.

Digital Library

[11]

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 SOSP'07, pages 205-220, October 2007.

Digital Library

[12]

S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant Web services. ACM SIGACT News, 33(2):51-59, June 2002.

Digital Library

[13]

Google Storage for Developers. Available at http: //code.google.com/apis/storage. Accessed May 2010.

[14]

L. Lamport. On interprocess communication, Part I: Basic formalism and Part II: Algorithms. Distributed Computing, 1(2):77-101, June 1986.

[15]

J. Misra. Axioms for memory access in asynchronous hardware systems. ACM Transactions on Programming Languages and Systems, 8(1):142-153, January 1986.

Digital Library

[16]

E. Pierce and L. Alvisi. A recipe for atomic semantics for Byzantine quorum systems. Technical report, University of Texas at Austin, 2000.

[17]

Amazon's Simple Storage Service. Available at http: //aws.amazon.com/s3. Accessed May 2010.

[18]

K. Simon. An improved algorithm for transitive closure on acyclic digraphs. Theoretical Computer Science, 58(1-3):325-346, 1988.

Digital Library

[19]

W. Vogels. Eventually consistent. Communications of the ACM, 52(1):40-44, 2009.

Digital Library

[20]

Voldemort. Available at http:// project-voldemort.com/. Accessed March 2010.

Cited By

Tzialla IWang JZhu JPanda AWalfish M(2024)Efficient Auditing of Event-driven Web ApplicationsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650089(1208-1224)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650089
Mansouri YToosi ABuyya R(2017)Data Storage Management in Cloud EnvironmentsACM Computing Surveys10.1145/313662350:6(1-51)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1145/3136623
Tan CYu LLeners JWalfish M(2017)The Efficient Server Audit Problem, Deduplicated Re-execution, and the WebProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132760(546-564)Online publication date: 14-Oct-2017
https://dl.acm.org/doi/10.1145/3132747.3132760
Show More Cited By

What consistency does your key-value store actually provide?
1. Computer systems organization

Recommendations

LSM-tree managed storage for large-scale key-value store
SoCC '17: Proceedings of the 2017 Symposium on Cloud Computing

Key-value stores are increasingly adopting LSM-trees as their enabling data structure in the backend storage, and persisting their clustered data through a file system. A file system is expected to not only provide file/directory abstraction to organize ...
LSM-Tree Managed Storage for Large-Scale Key-Value Store

Key-value stores are increasingly adopting LSM-trees as their enabling data structure in the backend block storage, and persisting their clustered data through a block manager, usually a file system. In general, a file system is expected to not only ...
Squirrel: an extensible distributed key-value store
META 2019: Proceedings of the 4th ACM SIGPLAN International Workshop on Meta-Programming Techniques and Reflection

Distributed key-value (KV) stores are a rising alternative to traditional relational databases since they provide a flexible yet simple data model. Recent KV stores use eventual consistency to ensure fast reads and writes as well as high availability. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

HotDep'10: Proceedings of the Sixth international conference on Hot topics in system dependability

October 2010

67 pages

Program Chairs:
Paulo Verissimo
University of Lisbon
,
Hakim Weatherspoon
Cornell University

Publisher

USENIX Association

United States

Publication History

Published: 03 October 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tzialla IWang JZhu JPanda AWalfish M(2024)Efficient Auditing of Event-driven Web ApplicationsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650089(1208-1224)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650089
Mansouri YToosi ABuyya R(2017)Data Storage Management in Cloud EnvironmentsACM Computing Surveys10.1145/313662350:6(1-51)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1145/3136623
Tan CYu LLeners JWalfish M(2017)The Efficient Server Audit Problem, Deduplicated Re-execution, and the WebProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132760(546-564)Online publication date: 14-Oct-2017
https://dl.acm.org/doi/10.1145/3132747.3132760
Viotti PVukolić M(2016)Consistency in Non-Transactional Distributed Storage SystemsACM Computing Surveys10.1145/292696549:1(1-34)Online publication date: 29-Jun-2016
https://dl.acm.org/doi/10.1145/2926965
Viotti PMeiklejohn CVukolić MAlvaro PBessani A(2016)Towards property-based consistency verificationProceedings of the 2nd Workshop on the Principles and Practice of Consistency for Distributed Data10.1145/2911151.2911162(1-4)Online publication date: 18-Apr-2016
https://dl.acm.org/doi/10.1145/2911151.2911162
Lu HVeeraraghavan KAjoux PHunt JSong YTobagus WKumar SLloyd WMiller EHand S(2015)Existential consistencyProceedings of the 25th Symposium on Operating Systems Principles10.1145/2815400.2815426(295-310)Online publication date: 4-Oct-2015
https://dl.acm.org/doi/10.1145/2815400.2815426
Golab WRahman MAuYoung AKeeton KLi X(2014)Eventually Consistent: Not What You Were Expecting?Queue10.1145/2576966.258299412:1(30-40)Online publication date: 15-Jan-2014
https://dl.acm.org/doi/10.1145/2576966.2582994
Golab WRahman MAuYoung AKeeton KLi X(2014)Eventually consistentCommunications of the ACM10.1145/257679457:3(38-44)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1145/2576794
Terry DPrabhakaran VKotla RBalakrishnan MAguilera MAbu-Libdeh HKaminsky MDahlin M(2013)Consistency-based service level agreements for cloud storageProceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles10.1145/2517349.2522731(309-324)Online publication date: 3-Nov-2013
https://dl.acm.org/doi/10.1145/2517349.2522731
Bouchenak SChockler GChockler HGheorghe GSantos NShraer A(2013)Verifying cloud servicesACM SIGOPS Operating Systems Review10.1145/2506164.250616747:2(6-19)Online publication date: 23-Jul-2013
https://dl.acm.org/doi/10.1145/2506164.2506167
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents