Running software in a distributed manner is a common practice nowadays. This approach produces a lot of new challenges which should be thought in advance. This paper is the next step on understanding systems such as distributed datastores by using statistical estimation for violation of guarantees from Brewer's Conjecture. The paper focuses on finding ways for simplification of theoretical and practical modelling of a system of a distributed datastore. Considering that real-world distributed datastore consists of nodes with a different distribution of fail and recovery time it is proposed to substitute every node of distributed datastore with nodes with one common distribution of fail and one common distribution of recovery time. The verification of the approach is done by modelling systems and statistically comparing their violation of guarantees from Brewer's Conjecture. The results allow us to define cases where we can substitute one system with another without losing perception of its behaviour.
Modern databases store data with multiple copies and often replicate it to different geographical regions to support the efficient decision-making process. However, processing and storing data in a distributed environment produce a lot of new challenges and limitations which didn’t exist in a single-computer world.
Some of those limitations were formalized as Brewer’s Conjecture [
Paper [
Obviously links that bind nodes may fail too but this is outside of the scope of the next analysis and it is assumed that every link if always works correctly. 2
To conduct a simulation mathematical model of a distributed datastore defined
in [
Experiments in this paper focus on estimation of the third guarantee from
Brewer’s Conjecture — partition tolerance. The metric used to estimate partition
tolerance is based on Definition 4 in [
Figure 1 is an example of ζt = 1 as clearly every alive node is able to reach any other alive node (a non-alive node is represented by a red-filled circle). Figure 2 is an example of ζt = 0. As node 1 is not able to reach any other alive node.
It is assumed that the distribution of fail and recovery time for every node obeys Poisson distribution. As we can treat time in our experiments as a discrete quantity, events — failure and recovery as a series of events with the known average time but the exact time is random. From practical examples, it may be the hardware failures, periodic releases of newer versions of software, etc. Saying that some node has a different distribution comparing with some other node it is understood as both of them are having Poisson distribution but parameters of Poisson distribution are different.
In order, to simplify future simulating of a distributed datastore and theoretical reasoning it is proposed to substitute probabilistic distribution of every node with one common distribution. Empirical results to answer a question — when ζt for a model of distributed datastore with every node having a different probabilistic distribution of fail and recovery time is not statistically different from the model with nodes having the same distribution are presented below. 3
As was mentioned above in the set of experiments, time is considered as a discrete quantity.
Required steps before every experiment run: – Generation of graph (N, L) which corresponds to nodes and links of a distributed datastore: – Generation of parameters for Poisson distribution of fail and recovery time for every node from graph (N, L) for system having different parameters of distribution — Soriginal – Generation of parameters for Poisson distribution of fail and recovery time for every node from graph (N, L) for system having different parameters of distribution — Sideal – Define discrete time series — T
To generate a graph, WattsStrogatz model [
The next steps are taken to define parameters for both systems — Soriginal and Sideal: – define E(f ail) and E(recovery) for Sideal. Mentioned values are the input data of an experiment; – for every node from Soriginal calculate random values — deviationrecovery and deviationfail based on normal distribution N (0, E(recovery)/2) and N (0, E(f ail) ∗ (deviation) respectively. Define E(f ail − deviationfail) and E(recovery − deviationrecovery) for Soriginal. Where deviation is an input parameter of an experiment;
During experiment run for every t ∈ T the value for ζ is recorded based on
Definition 4 from [
The process is repeated for different randomly generated network structures with the same parameters and then values for random variable ζ is aggregated by the number of times when the system had ζ = 1 and frequency of this systems. The mentioned aggregations are stored separately for Soriginal and Sideal. Pearson test(χ2) with p − value > 0.05 is applied to obtained data to get a conclusion about the statistical difference in systems behaviour. Every aggregated result is stored in a bucket of size — S based on a number of times. Bucketing is done in order to eliminate inaccuracies in cases when time series is long enough and the difference between two values is small enough to be treated as one value for χ2 test. 4
In total 5000 different systems were generated and run. Below are the results of the most notable cases. 4.1
Parameters used in this experiment are shown in Table 1.
Distributions of a results are shown in Figure 3 and Figure 4. Shapiro-Wilk
Test [
Parameters for experiment 2 are presented in Table 3. Distributions of tested systems are shown in Figure 5 and Figure 6. Positive outcome is received on Shapiro-Wilk test. χ2 test results are presented in Table 3. In this case it is possible to conclude that big E(f ail) in comparison to E(recovery) highly contributes to χ2 test results.
Parameters
Name Value
P r 0.5
K 5
E(f ail) 300
E(recovery) 30
deviation 0.5
The parameters used in experiment 3 are shown in Table 5. Distribution results
for this experiment are shown in Figure 7 and Figure 8. Shapiro-Wilk Test [
Based on experiment results, it is possible to specify the next parameters which
results of χ2 test depends on hence answer to a question — are the system
statistically equal based on Definition 4 from [
– The ratio of expected values of fail and recovery time: – The average deviations of all components considering that ν(N, L) - is a number of vertices in graph (N, L):
AR =
E(recovery)
E(f ail)
Experiments showed that the result of χ2 test has an inverse relation to the specified above parameters. The bucket size — S has a direct relation to χ2 test, as we treat close to each other values as one value for χ2 test.
Based on relation each parameter has to the end result it is possible to define one proportion that represents the influence of each parameter.
S
AR ∗ AD ∗ C′(β) 6
The study described in the paper was focused on improving and simplifying
tackling challenges set up in [
The proposed in the paper relation (4) based on empirical data gives a practically useful tool concerning to model a real-world system (referred in this paper as Soriginal) as a system with nodes having the same distribution (referred in the paper as Sideal. (3) (4)
This relation is grounded by a big set of experiments was conducted however it can be improved using coefficients in order to make the influence of each of the parameters more explicit.
We plan to use relation (4) for studying different mechanisms to estimate the
degree of ensuring each CAP-guarantee applying metrics specified in [
The author thanks to Prof. Grygoriy Zholtkevych for his supervision and support.