METRICS FOR EVALUATING CONSISTENCY IN DISTRIBUTED DATASTORES
DOI:
https://doi.org/10.30837/2522-9818.2020.12.040Keywords:
distributed datastore, response time, CAP-theorem, stochastic consistency metric, methods of building distributed networkAbstract
The subject of the paper is metrics for evaluating consistency of distributed datastore as one of main CAP-guarantees, more precisely, criteria for reliable distributed datastore. The goal of the research is investigation of the ability to develop such a program on the earlier stage of building distributed network and build some components of decision-making algorithm, which purpose is to build optimal network topology. This decision-making algorithm should be suitable for any business model and its requirements. To be more detailed, for that purpose the following tasks had been done: mathematical model for stochastic metric for consistency in distributed datastore is built; the conditions of consistency convergence time are investigated in initial perfect datastore environment. Methods used are: theory of number partitions, basics from graph theory and probability theory, computer modeling and program for running sets of experiments. As a result, it is established that in the conditions of data loss absence the consistency convergence after first write request is equal or less than diameter of graph that represents topology of distributed network. Such convergence has the same unit of measure as the link cost of each link in the network; the stochastic model is proposed for metric to evaluate consistency. Making a final conclusion, this will give the opportunity to investigate or monitor the current state of the system in the given time interval. This research is the base to form some elements of decision-making algorithm for building topology in a distributed network and the elements of the algorithm for monitoring such a system. Also, based on trends of requests frequency of data modification and reading, the strategy of nodes allocation in the topology is suggested, which can improve the response time and speed of convergence of the distributed storage to the fully consistent or close to that state. The practical role of the components of the decision-making algorithm is that the network architect could apply the algorithm at the stage of building the network for a distributed database, so that CAP characteristics will be optimized in the context of specific business needs. The mathematical model for the stochastic metric of distributed storage consistency can be applied both at the system design stage, for testing the satisfactory level of consistency, and at the system operation stage, as a component of the network monitoring system.
References
Kuhlenkamp, J., Klems, M., Röss, O. (2014), "Benchmarking Scalability and Elasticity of Distributed Database Systems", PVLDB, No. 7, P. 1219–1230.
Tanenbaum, A. S., Steen, M. V. (2007), Distributed systems - principles and paradigms, 2nd Edition, Upper Sddle River, Prentice-hall, 686 p.
Banothu, N., Bhukya, S. and Sharma, K. (2016), "Big-data: Acid versus base for database transactions", 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), Chennai, P. 3704–3709. DOI: 10.1109/ICEEOT.2016.7755401.
Brewer, E. A. (2000), "Towards robust distributed systems (abstract)", PODC '00: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computingJuly 2000, DOI: https://doi.org/10.1145/343477.343502
Gilbert, S., Lynch, N. A. (2002), "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services", SIGACT News, No. 33, P. 51–59.
Brewer, E. A. (2012), "CAP twelve years later: How the "rules" have changed", Computer, No. 45, P. 23–29.
Bailis, P., Ghodsi, A. (2013), Eventual Consistency Today: Limitations, Extensions, and Beyond, QUEUE, Vol. 11, Issue 3, P. 9–13, available at : https://dl.acm.org/doi/pdf/10.1145/2460276.2462076?download=true
Gilbert, S., Lynch, N. A. (2012), "Perspectives on the CAP Theorem", Computer, No. 45, P. 30–36.
Calder, B., Wang, J., Ogus, A., Nilakantan, N., Skjolsvold, A., et. al. (2011), "Windows Azure Storage: a highly available cloud storage service with strong consistency", SOSP '11, available at : https://azure.microsoft.com/en-us/blog/sosp-paper-windows-azure-storage-a-highly-available-cloud-storage-service-with-strong-consistency/.
Madria, S. K. (1998), "Handling of Mutual Conflicts in Distributed Databases Using Timestamps", Comput. J., No. 41, P. 376–385.
Rukkas, K., Zholtkevych, G. (2015), "Distributed Datastores: Towards Probabilistic Approach for Estimation of Dependability", ICTERI, Computer Science, available at : https://pdfs.semanticscholar.org/5eb0/01632c6cd6da2e4ec92adbc288939de0f4f9.pdf?_ga=2.235973185.1723289165.1592897490-2045290888.1592897490.
Andrews, G. E. (1976), The theory of partitions, Cambridge University Press, 255 p.
Bondy, J. A., Murty, U. S. (1976), Graph Theory with Applications, Elsevier Science Ltd.The Boulevard Langford Lane Kidlington, Oxford OX5 1GBUnited Kingdom, 270 p.
Rukkas, K., Zholtkevych, G. (2020), "Probabilistic model for estimation of cap-guarantees for distributed datastore", Advanced Information Systems, No. 4, P. 47–50. DPI: 10.20998/2522-9052.2020.2.09
Rukkas, K., Zholtkevych, G. (2020), "Load balancing consistency in a distributed datastore", Control, Navigation and Communication Systems, No. 2, P. 95–100. DOI: 10.26906/SUNZ.2020.2.095
Lemeshko, O., Yevdokymenko, M., Yeremenko, O. (2019), "Model of data traffic qos fast rerouting in infocommunication networks", Innovative Technologies and Scientific Solutions for Industries, No. 3 (9), P. 127–134. DOI: https://doi.org/10.30837/2522-9818.2019.9.127
Yeremenko, O., Yevdokymenko, M., Sleiman, B. (2020), "Advanced performance-based fast rerouting model with path protection and its bandwidth in software-defined network", Innovative Technologies and Scientific Solutions for Industries, No. 1 (11), P. 163–171. DOI: https://doi.org/10.30837/2522-9818.2020.11.163.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Galyna Zholtkevych
![Creative Commons License](http://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png)
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Our journal abides by the Creative Commons copyright rights and permissions for open access journals.
Authors who publish with this journal agree to the following terms:
Authors hold the copyright without restrictions and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-commercial and non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
Authors are permitted and encouraged to post their published work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.