Quantitative analysis of consistency in NoSQL key-value stores

Si Liu, Son Nguyen, Jatin Ganhotra, Muntasir Raihan Rahman, Indranil Gupta, José Meseguer

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

Abstract

The promise of high scalability and availability has prompted many companies to replace traditional relational database management systems (RDBMS) with NoSQL key-value stores. This comes at the cost of relaxed consistency guarantees: key-value stores only guarantee eventual consistency in principle. In practice, however, many key-value stores seem to offer stronger consistency. Quantifying how well consistency properties are met is a non-trivial problem. We address this problem by formally modeling key-value stores as probabilistic systems and quantitatively analyzing their consistency properties by statistical model checking. We present for the first time a formal probabilistic model of Apache Cassandra, a popular NoSQL key-value store, and quantify how much Cassandra achieves various consistency guarantees under various conditions. To validate our model, we evaluate multiple consistency properties using two methods and compare them against each other. The two methods are: (1) an implementation-based evaluation of the source code; and (2) a statistical model checking analysis of our probabilistic model.

Original languageEnglish (US)
Title of host publicationQuantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings
EditorsJavier Campos, Boudewijn R. Haverkort
PublisherSpringer-Verlag
Pages228-243
Number of pages16
ISBN (Print)9783319222639
DOIs
StatePublished - Jan 1 2015
Event12th International Conference on Quantitative Evaluation of Systems, QEST 2015 - Madrid, Spain
Duration: Sep 1 2015Sep 3 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9259
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Quantitative Evaluation of Systems, QEST 2015
CountrySpain
CityMadrid
Period9/1/159/3/15

Fingerprint

Quantitative Analysis
Model checking
Chemical analysis
Probabilistic Model
Model Checking
Statistical Model
Scalability
Strong Consistency
Availability
Formal Model
Relational Database
Statistical Models
Quantify
Industry
Evaluate
Evaluation
Modeling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Liu, S., Nguyen, S., Ganhotra, J., Rahman, M. R., Gupta, I., & Meseguer, J. (2015). Quantitative analysis of consistency in NoSQL key-value stores. In J. Campos, & B. R. Haverkort (Eds.), Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings (pp. 228-243). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9259). Springer-Verlag. https://doi.org/10.1007/978-3-319-22264-6_15

Quantitative analysis of consistency in NoSQL key-value stores. / Liu, Si; Nguyen, Son; Ganhotra, Jatin; Rahman, Muntasir Raihan; Gupta, Indranil; Meseguer, José.

Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings. ed. / Javier Campos; Boudewijn R. Haverkort. Springer-Verlag, 2015. p. 228-243 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9259).

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

Liu, S, Nguyen, S, Ganhotra, J, Rahman, MR, Gupta, I & Meseguer, J 2015, Quantitative analysis of consistency in NoSQL key-value stores. in J Campos & BR Haverkort (eds), Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9259, Springer-Verlag, pp. 228-243, 12th International Conference on Quantitative Evaluation of Systems, QEST 2015, Madrid, Spain, 9/1/15. https://doi.org/10.1007/978-3-319-22264-6_15
Liu S, Nguyen S, Ganhotra J, Rahman MR, Gupta I, Meseguer J. Quantitative analysis of consistency in NoSQL key-value stores. In Campos J, Haverkort BR, editors, Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings. Springer-Verlag. 2015. p. 228-243. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-22264-6_15
Liu, Si ; Nguyen, Son ; Ganhotra, Jatin ; Rahman, Muntasir Raihan ; Gupta, Indranil ; Meseguer, José. / Quantitative analysis of consistency in NoSQL key-value stores. Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings. editor / Javier Campos ; Boudewijn R. Haverkort. Springer-Verlag, 2015. pp. 228-243 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{33cf120eb965438582c70db7487119b3,
title = "Quantitative analysis of consistency in NoSQL key-value stores",
abstract = "The promise of high scalability and availability has prompted many companies to replace traditional relational database management systems (RDBMS) with NoSQL key-value stores. This comes at the cost of relaxed consistency guarantees: key-value stores only guarantee eventual consistency in principle. In practice, however, many key-value stores seem to offer stronger consistency. Quantifying how well consistency properties are met is a non-trivial problem. We address this problem by formally modeling key-value stores as probabilistic systems and quantitatively analyzing their consistency properties by statistical model checking. We present for the first time a formal probabilistic model of Apache Cassandra, a popular NoSQL key-value store, and quantify how much Cassandra achieves various consistency guarantees under various conditions. To validate our model, we evaluate multiple consistency properties using two methods and compare them against each other. The two methods are: (1) an implementation-based evaluation of the source code; and (2) a statistical model checking analysis of our probabilistic model.",
author = "Si Liu and Son Nguyen and Jatin Ganhotra and Rahman, {Muntasir Raihan} and Indranil Gupta and Jos{\'e} Meseguer",
year = "2015",
month = "1",
day = "1",
doi = "10.1007/978-3-319-22264-6_15",
language = "English (US)",
isbn = "9783319222639",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "228--243",
editor = "Javier Campos and Haverkort, {Boudewijn R.}",
booktitle = "Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings",

}

TY - GEN

T1 - Quantitative analysis of consistency in NoSQL key-value stores

AU - Liu, Si

AU - Nguyen, Son

AU - Ganhotra, Jatin

AU - Rahman, Muntasir Raihan

AU - Gupta, Indranil

AU - Meseguer, José

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The promise of high scalability and availability has prompted many companies to replace traditional relational database management systems (RDBMS) with NoSQL key-value stores. This comes at the cost of relaxed consistency guarantees: key-value stores only guarantee eventual consistency in principle. In practice, however, many key-value stores seem to offer stronger consistency. Quantifying how well consistency properties are met is a non-trivial problem. We address this problem by formally modeling key-value stores as probabilistic systems and quantitatively analyzing their consistency properties by statistical model checking. We present for the first time a formal probabilistic model of Apache Cassandra, a popular NoSQL key-value store, and quantify how much Cassandra achieves various consistency guarantees under various conditions. To validate our model, we evaluate multiple consistency properties using two methods and compare them against each other. The two methods are: (1) an implementation-based evaluation of the source code; and (2) a statistical model checking analysis of our probabilistic model.

AB - The promise of high scalability and availability has prompted many companies to replace traditional relational database management systems (RDBMS) with NoSQL key-value stores. This comes at the cost of relaxed consistency guarantees: key-value stores only guarantee eventual consistency in principle. In practice, however, many key-value stores seem to offer stronger consistency. Quantifying how well consistency properties are met is a non-trivial problem. We address this problem by formally modeling key-value stores as probabilistic systems and quantitatively analyzing their consistency properties by statistical model checking. We present for the first time a formal probabilistic model of Apache Cassandra, a popular NoSQL key-value store, and quantify how much Cassandra achieves various consistency guarantees under various conditions. To validate our model, we evaluate multiple consistency properties using two methods and compare them against each other. The two methods are: (1) an implementation-based evaluation of the source code; and (2) a statistical model checking analysis of our probabilistic model.

UR - http://www.scopus.com/inward/record.url?scp=84944717924&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944717924&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-22264-6_15

DO - 10.1007/978-3-319-22264-6_15

M3 - Conference contribution

AN - SCOPUS:84944717924

SN - 9783319222639

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 228

EP - 243

BT - Quantitative Evaluation of Systems - 12th International Conference, QEST 2015, Proceedings

A2 - Campos, Javier

A2 - Haverkort, Boudewijn R.

PB - Springer-Verlag

ER -