Quantitative Analysis of Consistency in NoSQL Key-Value Stores
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....
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
2017-02-01
|
| Series: | Leibniz Transactions on Embedded Systems |
| Subjects: | |
| Online Access: | https://drops.dagstuhl.de/storage/07lites/lites_vol004/lites_vol003_issue001/LITES-v004-i001-a003/LITES-v004-i001-a003.pdf |
| _version_ | 1797208369067458560 |
|---|---|
| author | Liu, Si Ganhotra, Jatin Rahman, Muntasir Raihan Nguyen, Son Gupta, Indranil Meseguer, José |
| author_facet | Liu, Si Ganhotra, Jatin Rahman, Muntasir Raihan Nguyen, Son Gupta, Indranil Meseguer, José |
| author_sort | Liu, Si |
| collection | DOAJ |
| description | 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 both statistical model checking and implementation evaluation. 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. |
| first_indexed | 2024-04-24T09:37:42Z |
| format | Article |
| id | doaj.art-7d16402990b14d9d88cdebda4ebc7fe8 |
| institution | Directory Open Access Journal |
| issn | 2199-2002 |
| language | English |
| last_indexed | 2024-04-24T09:37:42Z |
| publishDate | 2017-02-01 |
| publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| record_format | Article |
| series | Leibniz Transactions on Embedded Systems |
| spelling | doaj.art-7d16402990b14d9d88cdebda4ebc7fe82024-04-15T07:53:08ZengSchloss Dagstuhl -- Leibniz-Zentrum fuer InformatikLeibniz Transactions on Embedded Systems2199-20022017-02-014103:103:2610.4230/LITES-v004-i001-a003Quantitative Analysis of Consistency in NoSQL Key-Value StoresLiu, Si0Ganhotra, Jatin1Rahman, Muntasir Raihan2Nguyen, Son3Gupta, Indranil4Meseguer, José5Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USADepartment of Computer Science, University of Illinois at Urbana-Champaign, IL, USAMicrosoft, Redmond, WA, USAAddepar Inc., Sunnyvale, CA, USADepartment of Computer Science, University of Illinois at Urbana-Champaign, IL, USADepartment of Computer Science, University of Illinois at Urbana-Champaign, IL, USAThe 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 both statistical model checking and implementation evaluation. 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.https://drops.dagstuhl.de/storage/07lites/lites_vol004/lites_vol003_issue001/LITES-v004-i001-a003/LITES-v004-i001-a003.pdfnosql key-value storeconsistencystatistical model checkingrewriting logicmaude |
| spellingShingle | Liu, Si Ganhotra, Jatin Rahman, Muntasir Raihan Nguyen, Son Gupta, Indranil Meseguer, José Quantitative Analysis of Consistency in NoSQL Key-Value Stores Leibniz Transactions on Embedded Systems nosql key-value store consistency statistical model checking rewriting logic maude |
| title | Quantitative Analysis of Consistency in NoSQL Key-Value Stores |
| title_full | Quantitative Analysis of Consistency in NoSQL Key-Value Stores |
| title_fullStr | Quantitative Analysis of Consistency in NoSQL Key-Value Stores |
| title_full_unstemmed | Quantitative Analysis of Consistency in NoSQL Key-Value Stores |
| title_short | Quantitative Analysis of Consistency in NoSQL Key-Value Stores |
| title_sort | quantitative analysis of consistency in nosql key value stores |
| topic | nosql key-value store consistency statistical model checking rewriting logic maude |
| url | https://drops.dagstuhl.de/storage/07lites/lites_vol004/lites_vol003_issue001/LITES-v004-i001-a003/LITES-v004-i001-a003.pdf |
| work_keys_str_mv | AT liusi quantitativeanalysisofconsistencyinnosqlkeyvaluestores AT ganhotrajatin quantitativeanalysisofconsistencyinnosqlkeyvaluestores AT rahmanmuntasirraihan quantitativeanalysisofconsistencyinnosqlkeyvaluestores AT nguyenson quantitativeanalysisofconsistencyinnosqlkeyvaluestores AT guptaindranil quantitativeanalysisofconsistencyinnosqlkeyvaluestores AT meseguerjose quantitativeanalysisofconsistencyinnosqlkeyvaluestores |