The probability of data loss in large clusters

m1rko March 29, 2017 at 23:40

The probability of data loss in large clusters

Transfer

This article uses MathJax to render mathematical formulas. JavaScript must be enabled for MathJax to work.

Many distributed storage systems (including Cassandra, Riak, HDFS, MongoDB, Kafka, ...) use replication to preserve data. They are usually deployed in a “ just a bunch of disks, JBOD ” configuration - like this, without any RAID to handle failures. If one of the disks in the node fails, then the data of this disk is simply lost. To prevent irretrievable data loss, the DBMS stores a copy (replica) of data somewhere on disks in another node.

The most common replication factor is 3 - this means that the database stores three copies of each piece of data on different disks connected to three different computers. The explanation for this is approximately the following: drives rarely fail. If the disk fails, then there is time to replace it, and at this time you have two more copies from which you can restore data to the new disk. The risk of failure of the second disk while you restore the first is low enough, and the probability of death of all three disks at the same time is so small that it is more likely to die from an asteroid.

Let's take a look at the napkin: if the probability of failure of one disk in a certain period of time is 0.1% (to choose an arbitrary number), then the probability of failure of two disks is (0.001) ² = 10^-6 , and the probability of a failure of three disks is (0.001) ³ = 10 ^-9 , or one in a billion. These calculations suggest that disk failures occur independently of each other - which is not always true in reality, for example, disks from the same batch from the same manufacturer may have similar defects. But for our approximate calculations will do.

So far, common sense triumphs. Sounds reasonable, but unfortunately for many storage systems this does not work. In the article I will show why so.

So easy to lose data, la la laaa

If your database cluster really consists of only three machines, then the probability of simultaneous failure of all three is really very small (except for correlated failures, such as a fire in the data center). However, if you switch to larger clusters, then the probabilities change. The more nodes and disks in your cluster, the greater the chance of data loss.

This is a counterintuitive thought. “Of course,” you think, “each piece of data is still replicated on three disks. The probability of a disk failure does not depend on the size of the cluster. So why does cluster size matter? ”But I calculated the probabilities and drew a graph that looks like this:

For clarity, this is not the probability of a single node failing, but the probability of irreversible loss of three replicassome piece of data, so restoring from a backup (if you have one) will remain the only way to restore the data. The larger the cluster, the more likely data loss. You probably didn’t expect this when you decided to pay for replication factor 3.

In this graph, the y axis is slightly arbitrary and depends on many assumptions, but the direction of the graph is scary. If we assume that the node has a 0.1% failure chance for a certain period of time, then the graph shows that in a cluster of 8000 nodes the chance of irreversible loss of all three replicas for a given data fragment (for the same time period) is about 0.2%. Yes, you read it right: the risk of losing all three copies of data is almost twice as highthan the risk of losing one node! What is the point of replication then?

Intuitively, this graph can be interpreted as follows: in a cluster of 8000 nodes, almost certainly several nodes are always dead at any given time. This is normal and not a problem: a certain level of failures and node replacement was assumed as part of routine maintenance. But if you're out of luck, then there is some piece of data, for which all three replicas are among those nodes that are now dead - and if this happens, then your data is lost forever. Lost data makes up only a small part of the entire data set in the cluster, but this is still bad news, because when using replication factor 3 you usually think “I don’t want to lose data at all”, and not “I don’t care about the periodic loss of a small amount of data if there are few of them. " Maybe this particular piece of lost data is really important information.

The likelihood that all three replicas are dead nodes is fundamentally dependent on the algorithm the system uses to distribute data across replicas. The graph at the top is calculated with the assumption that the data is divided into sections (shards), and each section is stored in threerandomly selected nodes (or pseudo-random with a hash function). This is a case of sequential hashing , which is used by Cassandra and Riak, among others (as far as I know). I'm not sure how replica assignment works in other systems, so I will be grateful for the tips of those who know the features of various storage systems.

Calculation of the probability of data loss

Let me show you how I calculated the upper graph using a probabilistic model of a replicated database.

Suppose that the probability of losing a single node is

$p = P (\ text {node loss})$ . We ignore the time in this model, and just look at the probability of failure in a certain arbitrary period of time. For example, may suggest that

$inline$ - this is the probability of a node failure on a certain day, which makes sense if approximately one day is required to replace the node and restore lost data to new disks. For simplicity, I will not distinguish between a failure of a node and a disk failure , but I will only consider irreversible failures (ignoring failures when a node returns to service after a reboot).

Let be

$inline$ will be the number of nodes in the cluster. Then the probability that

$inline$ of

$inline$ the node fails (assuming that the failures are independent of each other), corresponds to the binomial distribution :

$P (f \ text {nodes failed}) = \ binom {n} {f} \, p ^ f \, (1-p) ^ {nf}$

Member

$inline$ Is the probability that

$inline$ node failed, member

$(1-p) ^ {nf}$ - the probability that the remaining

$inline$ remained in service, and

$\ binom {n} {f}$ Is the number of different choices

$inline$ of

$inline$ node

$\ binom {n} {f}$ interpreted as the number of combinations of

$inline$ by

$inline$ . This binomial coefficient is calculated as:

$\ binom {n} {f} = \ frac {n!} {f! \; (nf)!}$

Let be

$inline$ will be a replication factor (usually

$inline$ ) Assuming that

$inline$ of

$inline$ node failed, what is the probability that a particular section has everything

$inline$ their replicas on failed nodes?

Well, in a sequentially hashed system, each section is assigned to the nodes in an independent and random (or pseudo-random) way. There is for this section

$\ binom {n} {r}$ various ways of appointment

$inline$ replicas to nodes, and all these assignments can happen with the same probability. Moreover, there is

$\ binom {f} {r}$ different ways to choose

$inline$ replicas of

$inline$ failed nodes - these are the ways in which everything

$inline$ replicas can be assigned to failed nodes. Now we calculate the part of the assignments that leads to the failure of all replicas:

$P (\ text {partition lost} \ mid f \ text {nodes failed}) = \ frac {\ binom {f} {r}} {\ binom {n} {r}} = \ frac {f! \; (nr)!} {(fr)! \; n!}$

(The vertical bar after “partition lost” means “provided” and indicates conditional probability : probability is given under the assumption that

$inline$ node failed).

So, here is the chance that all replicas of one particular section are lost. What about a cluster with

$inline$ sections? If one or more partitions are lost, we lose data. Therefore, in order not to lose data, it is necessary that all

$inline$ sections were not lost:

$\ begin {align} P (\ text {data loss} \ mid f \ text {nodes failed}) & = 1 - P (\ text {partition not lost} \ mid f \ text {nodes failed}) ^ k \ \ & = 1 - \ left (1 - \ frac {f! \; (Nr)!} {(Fr)! \; N!} \ Right) ^ k \ end {align}$

Cassandra and Riak refer to the sections as vnodes, but this is the same. In general, the number of sections

$inline$ independent of the number of nodes

$inline$ . In the case of Cassandra, there is usually a fixed number of partitions on a node ; default

$k = 256 \, n$ (set by the parameter num_tokens), and this is another assumption I made for the graph at the top. In Riak, the number of partitions is fixed when the cluster is created , but usually the more nodes, the more partitions.

Having collected everything in one place, we can now calculate the probability of losing one or more partitions in a cluster of size

$inline$ with replication factor

$inline$ . If the number of failures

$inline$ less than the replication factor, we can be sure that no data is lost. Therefore, you should add the probabilities for all possible values for the number of failures

$inline$ from

$r \ le f \ le n$ :

$\ begin {align} P (\ text {data loss}) & = \ sum_ {f = r} ^ {n} \; P (\ text {data loss} \; \ cap \; f \ text {nodes failed}) \\ & = \ sum_ {f = r} ^ {n} \; P (f \ text {nodes failed}) \; P (\ text {data loss} \ mid f \ text {nodes failed}) \\ & = \ sum_ {f = r} ^ {n} \ binom {n} {f} \, p ^ f \, (1 -p) ^ {nf} \ left [1 - \ left (1 - \ frac {f! \; (nr)!} {(fr)! \; n!} \ right) ^ k \ right] \ end { align}$

This is a little excessive, but it seems to me an accurate assessment. And if you substitute

$inline$ ,

$inline$ and

$k = 256 \, n$ and check the values

$inline$ from 3 to 10,000, then get the chart at the top. I wrote a small Ruby program for this calculation.

You can get a simpler approximation using the union boundary :

$\ begin {align} P (\ text {data loss}) & = P (\ ge \ text {1 partition lost}) \\ & = P \ left (\ bigcup_ {i = 1} ^ k \ text {partition } i \ text {lost} \ right) \\ & \ le k \, P (\ text {partition lost}) = k \, p ^ r \ end {align}$

Even if the failure of one partition is not independent of the failure of another partition, such an approximation is still applicable. And it seems that it pretty closely matches the exact result: on the graph, the probability of data loss looks like a straight line, proportional to the number of nodes.

The approximation says that this probability is proportional to the number of sections, which is the same based on a fixed number of 256 sections per node.

Moreover, if we substitute the number of 10000 nodes in the approximation, we get

$P (\ text {data loss}) \ le 256 \ cdot 10 ^ 4 \ cdot (10 ^ {- 3}) ^ 3 = 0.00256$ which closely matches the result from the Ruby program.

But in practice ...?

Is this a problem in practice? I do not know. Basically, I think this is an interesting counterintuitive phenomenon. I heard rumors that this led to real data loss in companies with large database clusters, but I did not see the problem documented somewhere. If you are aware of discussions on this subject, please show me.

Calculations show that to reduce the likelihood of data loss, you should reduce the number of partitions or increase the replication factor. Using more replicas costs money, so this is not an ideal solution for large clusters that are already expensive. However, changing the number of partitions is an interesting compromise. Cassandra initially used one partition per node, but several years ago it switched to 256 partitions per nodein order to achieve better load balancing and more efficient balance recovery. The flip side, as can be seen from the calculations, is a much higher probability of losing at least one of the sections.

I think it is possible to develop a replica assignment algorithm in which the probability of data loss does not grow with the cluster size or at least does not grow so fast, but where at the same time the properties of good load distribution and balance restoration are preserved. This would be an interesting area for further research. In this context, my colleague StefanI noticed that the expected data loss rate remains unchanged in a cluster of a certain size, regardless of the replica assignment algorithm - in other words, you can choose between a high probability of losing a small amount of data and a low probability of losing a large amount of data! Think the second option is better?

You need really large clusters before this effect really manifests itself, but clusters of thousands of nodes are used in different large companies, so it would be interesting to hear people with experience on such a scale. If the probability of irreversible data loss in a cluster of 10,000 nodes is really 0.25% per day, this means a 60% chance of data loss per year. This is much more than the “one in a billion” chance of dying from the asteroid I spoke of at the beginning.

Are architects of distributed data systems aware of the problem? If I understand correctly, there are a few things to consider when designing replication schemes. Perhaps this post will draw attention to the fact that just having three replicas does not make you feel safe.

Tags: