Systems employing technics of distributing data across multiple machines are widespread nowadays and demand significant expertise from operators. Oftentimes requirement of strong consistency from the data store is too expensive and unafordable in practical systems. One of the approaches is an application of partial quorum systems with weaker consistency guarantees. Probabilistically Bounded Staleness (PBS) [1] was introduced together with -visibility. WARS model which is based on mentioned above theory is deliberated to give a tool to reason about datastore consistency by bounding a staleness of data. Further studying of PBS approach is a step towards better understanding and providing tools for reasoning about consistency in distributed systems with partial quorums. The work presented in this paper is a proposition of an enhanced WARS model backed by experimental data to get a more precise view of a system.
Modern datastore systems are obliged with numerous requirements such as scalability,
availability, suficient level of consistency per an organization’s need. Systems operating with significant
volumes of data are using diferent techniques of distributing and replicating data across
numerous physical machines satisfy the demands for data quality. With the ability of employing strong
consistency guarantees most of the time practitioners are not able to trade of availability [
Quorum systems giving a lot of benefits in current datastore architecture and used inside
well-known database management systems, such as Cassandra, DynamoDB. The simplified
logic of this kind of datastores — is when the write operation arrives at one of the member of
the datastore system, the response returned back to the client only after a particular number of
members acknowledged this operation, typically called write quorum — . The same logic
applies to read operation with a possible diferent number of members required to return
data, called read quorum — . In quorum systems, strong consistency is guaranteed when
+ > , where is the number of replicas storing a data item. Partial quorums, where
+ ⩽ are used in practice to elevate availability of the system and got proven to be good
enough to be widely employed [
PBS - models the probability of stale data item being return from the read operation
which is initiated after time units passed since write request is complete. Definition 3 from [
The motivation and impact of the two refinements proposed to the WARS model are described in this section below. In the last paragraph of this section, the complete model is expounded.
Cassandra database management system employs query-model first approach as per "Instead
of modeling the data first and then writing queries, with Cassandra you model the queries
and let the data be organized around them.", taken from [
The result of the provided reasoning above is the inclusion of the write and read request processing time into WARS model.
Authors of the original PBS paper made a straight point that the client delays has to be taken
into account while considering practical scenarios [
As per the original definition, - is calculated starting from the point after the write request was committed. However, the client is acquainted with the knowledge of the write request being successfully committed only after the response from the coordinator is received. The revised definition of - with delineation of client viewpoint is presented below. Definition 1. A quorum system obeys PBS - from client viewpoint if, with probability 1 − , any client request started at least units of time after a write response received by a client, returns to a client at least one value that is at least as recent as that write.
The next parameters are included in the original WARS model: distribution of write request processing time; distribution of read request processing time; distribution of client request latency; distribution of client acknowledgment latency;
Client 1
Coordinator
Replica Client 2
Coordinator
Replica
CR CA
CR CA
W to N replicas
A respWonses
DW t seconds after
R to N replicas S respRonses
DR
Time
The entire data flow starting from the client initiating a request can be seen on a space-time diagram shown in Figure 1. The process starts from the client sends a request to the coordinator with the delay drawn from distribution — . The coordinator sends requests to datastore nodes, where is the amount of replicas. Every request to a datastore instance completes in time composed of value drawn from , , and . After the coordinator receives W responses, the response from the coordinator is transmitted back to the client, taking the time of value drawn from . The read part is much alike to the writing part with the diference in the distribution of request delay and datastore processing time values are drawn from. Thus each request out of from coordinator to instances storing replicas consists of time drawn from , , and . The coordinator waits for responses and then send a response to the client with the latency drawn from
The condition for the client to see a stale data is when read requests from coordinator will
be processed faster than write requests on the step before. Deriving from the logic originated
in the original paper dedicated to PBS consistency theory [
This section will cover a comparison of Monte Carlo simulation of the original WARS model and
enhanced model with relation to the performance of Cassandra cluster in the multi data-center
environment. A synthetic run of the primary model was done according to the simulation
described in the original PBS paper in section 5.2 [
For the synthetic execution of enhanced model, multiple variations of exponential distribution were taken. The parameters — ∈ {0.05, 0.1, 0.2, 0.4, 0.5} were used for the network delays from coordinator to replica nodes inside one datastore. For the cases where the data is stored on replicas located in multiple locations exponential distribution with the next parameters was used — ∈ {0.007, 0.01}. For client delays, with consideration of data being stored in multiple locations, it is assumed that distributions for diferent locations from the client’s perspective are not the same. It is considered that one location is closer than the other. First distribution for client delay is ∈ {0.015} and the second – ∈ {0.006}. The data is taken from measuring network latency to a data center in Frankfurt and Singapore during the actual Cassandra cluster test. The write and read request processing time are considered to be small for simulation described in this paper, hence the distribution are taken with the next parameter for both, read and write request processing time, = 1.
Experiments were conducted with diferent settings of the amount of replicas — N and read and write consistency — R, W : • = 3, = = 1 • = 4, = = 1 • = 4, = = 2, cross data-center environment • = 6, = = 2, cross data-center environment • = 6, = 2, = 1, cross data-center environment • = 6, = 1, = 2, cross data-center environment The cases for the client to read and write operation from the same data center and diferent were spread evenly. For the determination of -, the condition described in section 3.3 is used after the parameters were drawn from the respected distributions.
For measuring -, Cassandra cluster was prepared using service from cloud vendor — Digital Ocean. All operations were conducted using one process to update a key and multiple processes to read this key from diferent data centers. Cluster setup consisted of a total of 20 nodes split evenly in Frankfurt and Singapore locations. For every new version update, the diference was measured between events of write request completes and read request obtain the same data.
Density plots of time diference for write operation and then read the corresponding version of data with the respect to geographical locations are shown on Figures 2, 3, 4, 5.
As can be noticed, cases where the diference in time of mentioned earlier events is negative. The aforementioned can happen due to numerous anomalies in the network such as delays, packet reordering considering a significant variability in distance between client and datastore locations. From - prospective negative diference corresponds to state where data is available immediately after the client gets a response from the coordinator. After calculating RMSE for Monte Carlo simulation and actual run of the system, the next results were obtained: The noticeable diference for the original model simulation is explained by not counting client request delays in a geographically distributed environment. The impact of a client delay can be seen on provided graphics. The results are suficient to conclude that the enhanced model gives a better result for estimation - from client side perspective.
This section is dedicated to showing the work based on PBS ideas as well as ideas PBS theory is based on together with alternative approaches in order to achieve the best balance between consistency and availability.
Adaptive consistency model currently gets enough interests and application [
Closed-form expression of PBS t-visibility was proposed as an alternative approach to use event-based Monte Carlo simulator in [12]. It is said by the author that the original WARS model simulation was unable to provide precision given by the proposed expression. The direction of comparing the enhanced WARS model to the provided expression together with studying client viewpoint and its relation to the equation is a promising research step.
Optimizing network topology: As an updated model takes into account message reordering and delays in both network connection to datastore and inside datastore instances. The network topology might be optimized per the required need of every organization. A study of the relationship between network topology and consistency was conducted in [13] based on datastore model introduced in [14] and obtained results can be used together with -visibility approach to improving the balance between performance and consistency of the datastore.
Cost optimization of cloud providers: With the rise of cloud computing services and increasing adoption from the business. Customers of the mentioned services are facing numerous challenges and issues such as vendor locks, capitally studied in [15, 16] and cost optimization challenges [17, 18]. To tackle such formidable tasks organizations are obliged to experiment with diferent infrastructure setups which are time and resource-consuming actions. The experimentation are required due to the unique needs of every organization. By using an analytical model of the desired system, currently speaking, of the desired datastore, with organization-specific requirements and the SLA from cloud vendors the decision might be less expensive. However, further detailed studying is required in this direction.
Further model development: As request processing time was introduced in an updated version of the model. The model can be developed further by study a dependency between system load and data store request processing time. Resources that can be encountered are the next: • CPUs: sockets, cores, hardware threads (virtual CPUs) • Memory: capacity • Storage devices: I/O, capacity • Interconnects: CPUs, memory, I/O.
Exploring the influence of the mentioned parameters to the consistency from -visibility prospective and further embedding into analytical reasoning can be done by using the USE method introduced by Brendan Gregg in [19].
During work on this paper, PBS -consistency analysis from the client perspective was conducted by using data centers located in multiple geographical regions for Cassandra datastore cluster. Definition of - with consideration of a client view-point was proposed. The carried experiments allowed us to afirm a suficiency of the enhanced version of WARS model with a consideration of client delays and data processing time. The new model has been studied by using Monte Carlo simulation and was compared to the measurements procured from the Cassandra cluster execution. The enhanced model gives a more precise picture of data store consistency from client perspective by relying on - as a key metric, with consideration of auxiliary parameters. The next actions towards improving and employing the proposed model were defined. Moreover, obtained results can be fitted into the observability and monitoring practices of organization [20] by engaging approaches mentioned in section 5.
The author thanks to Prof. Grygoriy Zholtkevych for his supervision and support. [8] H.-E. Chihoub, S. Ibrahim, G. Antoniu, M. S. Pérez, Harmony: Towards automated selfadaptive consistency in cloud storage, in: 2012 IEEE International Conference on Cluster Computing, 2012, pp. 293–301. doi:10.1109/CLUSTER.2012.56. [9] X. Yao, C.-L. Wang, Probabilistic consistency guarantee in partial quorum-based data store, IEEE Transactions on Parallel and Distributed Systems 31 (2020) 1815–1827. doi:10. 1109/TPDS.2020.2973619. [10] H. Yu, A. Vahdat, Design and evaluation of a conit-based continuous consistency model for replicated services, ACM Trans. Comput. Syst. 20 (2002) 239–282. URL: https://doi.org/ 10.1145/566340.566342. doi:10.1145/566340.566342. [11] S. Sidhanta, W. Golab, S. Mukhopadhyay, S. Basu, Adaptable sla-aware consistency tuning for quorum-replicated datastores, IEEE Transactions on Big Data 3 (2017) 248–261. doi:10.1109/TBDATA.2017.2656121. [12] R. Ali, Consistency analysis of replication-based probabilistic key-value stores, ArXiv abs/2002.06098 (2020). [13] V. Sobol, Simplifying simulation of distributed datastores based on statistical estimating cap-constraint violation, in: Proceedings of the PhD Symposium at ICT in Education, Research, and Industrial Applications co-located with 16th International Conference "ICT in Education, Research, and Industrial Applications 2020 (ICTERI 2020)", volume 2791, CEUR Workshop Proceedings, 2020. URL: http://ceur-ws.org/Vol-2791/2020200042.pdf. [14] K. Rukkas, G. Zholtkevych, Distributed datastores: Towards probabilistic approach for estimation of reliability., in: Proceedings of the 11th International Conference on ICT in Education, Research and Industrial Applications: Integration, Harmonization and Knowledge Transfer, volume 1356, CEUR Workshop Proceedings, 2015. URL: http://ceur-ws.org/Vol-1356/paper_51.pdf. [15] P. S. Justin Lerma, Cloud cost optimization: principles for lasting success, 2020. URL: https:// cloud.google.com/blog/topics/cost-management/principles-of-cloud-cost-optimization. [16] J. Opara-Martins, R. Sahandi, F. Tian, Critical analysis of vendor lock-in and its impact on cloud computing migration: A business perspective, J. Cloud Comput. 5 (2016). URL: https://doi.org/10.1186/s13677-016-0054-z. doi:10.1186/s13677-016-0054-z. [17] E. Weintraub, Y. Cohen, Cost optimization of cloud computing services in a networked environment, International Journal of Advanced Computer Science and Applications 6 (2015) pp. 148–157. doi:10.14569/IJACSA.2015.060420. [18] E. Weintraub, Y. Cohen, Optimizing Cloud Computing Costs of Services for Consumers, 2019, pp. 83–96. doi:10.4018/978-1-5225-7766-9.ch007. [19] B. Gregg, Thinking methodically about performance: The use method addresses shortcomings in other commonly used methodologies., Queue 10 (2012) 40–51. URL: https: //doi.org/10.1145/2405116.2413037. doi:10.1145/2405116.2413037. [20] B. Beyer, C. Jones, J. Petof, N. R. Murphy, Site Reliability Engineering: How Google Runs Production Systems, 1st ed., O’Reilly Media, Inc., 2016.