The yearly chance of losing data, and how chunks with parity beat full copies on it and on disk.
What you will learn
Work out the yearly chance of losing data kept on several machines.
Compare full copies with erasure coding by durability and by raw disk.
Place copies or chunks across zones so that losing a zone loses nothing.
What durability means
Availability asks whether you can reach your data now. Durability asks whether it still exists. A store that is down for a minute is unavailable; a store that has lost a file has lost it for good.
Disks fail all the time in a large fleet. What loses data is not one failure but enough failures at once: every piece of an object gone before the first lost piece has been rebuilt somewhere else. So durability depends on three figures: how often a disk fails, how long a failed piece takes to rebuild, and how many pieces an object can lose and still be read.
The chance of losing an object
Let a disk fail with probability fwhat its symbols mean in a year, and let rebuilding a failed piece take Twhat its symbols mean hours. The chance that another given disk is also down at some moment is about
p=f×8760Twhat its symbols mean
since a year has 8,760 hours. An object spread on nwhat its symbols mean disks that survives swhat its symbols mean losses is lost when one of them fails and s of the other n−1 are down at the same time, which happens in a year with a chance of about
n×f×(sn−1)×pswhat its symbols mean
With f at 2% and T at 72 hours, pwhat its symbols mean is about 0.00016. Three full copies (n=3, s=2) lose an object with a chance of about 1.6×10−9 a year. That sounds small, but it is one or two objects lost a year for every billion kept.
Erasure coding
Erasure coding keeps data safe with less raw disk than full copies. An object is split into kwhat its symbols mean data chunks, and mwhat its symbols mean parity chunks are computed from them; the k+mwhat its symbols mean chunks go to k+m different machines, and any k of them are enough to rebuild the object.
With 8 data and 4 parity chunks, an object survives losing any 4 of its 12 machines, and it takes 12÷8=1.5 times its size in raw disk, against 3 times for three copies. Its yearly chance of loss, by the formula above with n=12what its symbols mean and s=4what its symbols mean, is about 6×10−14: far safer, for half the disk.
It is not free. A write must compute and store all k+m chunks, and a read must gather k of them from k machines, so each request touches more machines. Rebuilding a lost chunk means reading k others. Erasure coding suits large objects kept for a long time and read now and then; full copies still suit small, hot data.
Spread across zones
A zone can fail as a whole, taking every machine in it. The pieces of an object must be spread so that one zone never holds more of them than the object can lose. With 8 + 4 chunks over three zones, each zone holds 4 chunks, which is exactly what the object can spare. With three copies over three zones, each zone holds one copy.
Objects stored as 8 data and 4 parity chunks on 12 nodes, four in each of three zones.
The API servers split each object into 12 chunks, one to a node, four in each zone. Any 8 chunks rebuild the object, so it survives losing any 4 nodes, or a whole zone, for one and a half times its size in raw disk.
Customers: 1 × Users
Load balancer: 6 × Load balancer
Storage API: 9 × App server
Data nodes: 12 × NoSQL store
Customers sends requests to Load balancer
Load balancer sends requests to Storage API
Storage API sends requests to Data nodes
Key takeaways
Durability is the chance data still exists, set by the failure rate, the rebuild time and how many pieces an object can lose.
Erasure coding with kwhat its symbols mean data and mwhat its symbols mean parity chunks survives m losses for (k+m)÷kwhat its symbols mean times the raw disk, against three times for three copies.
Spread the pieces so that no zone holds more of an object than it can lose.