Reliability and Fault-tolerance of NoSQL Systems
Reading this posts requires some basic knowledge in probability theory. Consult "Grinstead and Snell's Introduction to Probability" e.g.; it is available online.
Assumptions
We start out by making some assumptions on the reliability of hardware. The given values are examples as I don't have any real values to share. This discussion is about how to arrive at a certain result.
Commodity Hardware | Rackmount Server | SAN | |
---|---|---|---|
expected failure | 1 day in 1 year | 1 day in 5 years | 1 day in 50 years |
probability of failure p_{f} | 0.00273973 | 0.00054794 | 0.00005479 |
reliability p_{r} | 0.99726 | 0.999452 | 0.999945 |
There are two possible outcomes when evaluating one particular day in the lifetime of a unit: it either fails, or it does not. We denote the probability of failure with p_{f}, and the probability that the unit stands with p_{r}. Since we only have these two events, the relation p_{r} = 1 − p_{f} must be true. Think of p_{r} as the probability that the systems runs or equivalently as the reliability.
To given an example we consider the case of one expected failure in one year. We derive p_{f} = 1/365 = 0.00273973 and the remaining numbers follow accordingly.
Fault-tolerance of a traditional system
Our imaginary traditional/vertial system is composed of one SAN, one rackmount database, and one rackmount compute-server. The system as a whole is available if and only if all three components are running. This translates into
p_{r}^{(vertical)} = p_{r}^{(SAN)} ⋅ (p_{r}^{(rackmount)})^{2} = 0.999452 .
Expressed in other terms, the systems fails every 2.38 years in expectation.
Fault-tolerance of a sharted system
Let us consider a sharted system as depicted in the following figure.
We compute the reliability of one shard first. A shard is a system of 3 units of commodity hardware. The shard fails if and only if all three systems fail. Hence, we can compute the reliability by
p_{r}^{(shard)} = 1 − (p_{f}^{(Commodity)})^{3}.
To compute the total reliabilty for n shards we have to employ
p_{r}^{(shard − storage)} = (p_{r}^{(shard)})^{n} .
Even if we assume that there are 100 such shards we arrive with an expected failure only every 1332 years in expectation!
Thus, the weak link in such a composition is not the shards but the server which maintain the data distribution (named sharder in the figure) and the access points (named router in the figure) of the composition. They act as a single point of failure. If one wishes to compute the reliability, we can proceed as with the vertical system by replacing the SAN with our sharded storage. The numbers will be roughly the same as the single points of failure dominate the result. The reliability will improve largely if they are backed up with a fail-over system as indicated in the figure.
Fault-tolerance of a nothing shared architecture
We start out from a different model when considering nothing shared architectures. We assume that there is a number of r systems required to finish the computation in a timely manner. We also assume that once one system fails the data and computation is seamlessly overtaken by another system. This is a reasonable assumption given that the size-distribution of the values behaves well. The question is how many systems n are required to achieve a certain reliability p_{r}^{(total)}. The result is given by the following equation
$$ p_r^{(total)} = \sum_{k=r}^n {n \choose k} \; p^{n-k}_{f} \; p_{r}^k $$
where p_{f} (respectively p_{r}) is the probability of failure (respectively reliability) of a unit.
Let us try to understand the given equation intuitively. The basic idea is to count and add all the cases that yield exactly r running systems. Let us consider the corner case r = n first. Then the equation simplifies to p_{r}^{(total)} = p_{r}^{k} which is obviously correct.
For some k with r ≤ k ≤ n, consider the case that exactly k systems are running. The probability that the first k units are running and the remaining n − k units are not running is exactly p_{r}^{k} ⋅ p_{f}^{n − k}. There are n choose k configurations that yield exactly k running systems. Finally, we sum over all k where r ≤ k ≤ n.
Numbers
Let us consider some numbers. We assume that we need at least 100 commodity type machines. The following table shows the reliability of the corresponding nothing shared architecture.
Number of Units | 100 | 101 | 102 | 103 | 104 | 105 |
---|---|---|---|---|---|---|
Reliability | 0.760067 | 0.968304 | 0.997115 | 0.999799 | 0.999988 | 0.999999 |
expected failure in years | 0.011 | 0.086 | 0.949 | 13.6 | 241 | 5077 |
Exactly 100 machines yield a terrible reliability. However, an overhead of just 5% gives a failure of more than every 5000 years in expectation.