Lesson Beyond 2• 5 min read

Erasure coding and durability

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 ffwhat its symbols mean in a year, and let rebuilding a failed piece take TTwhat its symbols mean hours. The chance that another given disk is also down at some moment is about

p=f×T8760p = f \times \frac{T}{8760}what its symbols mean

since a year has 8,760 hours. An object spread on nnwhat its symbols mean disks that survives sswhat its symbols mean losses is lost when one of them fails and ss of the other n−1n - 1 are down at the same time, which happens in a year with a chance of about

n×f×(n−1s)×psn \times f \times \binom{n-1}{s} \times p^{s}what its symbols mean

With ff at 2% and TT at 72 hours, ppwhat its symbols mean is about 0.00016. Three full copies (n=3n = 3, s=2s = 2) lose an object with a chance of about 1.6×10−91.6 \times 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 kkwhat its symbols mean data chunks, and mmwhat its symbols mean parity chunks are computed from them; the k+mk + mwhat its symbols mean chunks go to k+mk + m different machines, and any kk 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.512 \div 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=12n = 12what its symbols mean and s=4s = 4what its symbols mean, is about 6×10−146 \times 10^{-14}: far safer, for half the disk.

It is not free. A write must compute and store all k+mk + m chunks, and a read must gather kk of them from kk machines, so each request touches more machines. Rebuilding a lost chunk means reading kk 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.

Customers1× instanceLoad balancer6× instancesStorage API9× instancesData nodes12× instancesCustomers1× instanceLoad balancer6× instancesStorage API9× instancesData nodes12× instancesCustomers1× instanceLoad balancer6× instancesStorage API9× instancesData nodes12× instances
Figure 1

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 kkwhat its symbols mean data and mmwhat its symbols mean parity chunks survives mm losses for (k+m)÷k(k + m) \div 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.
Sources3