Durability and erasure coding
How a storage service keeps data through drive failures, and why it does not simply keep three copies of everything.
5 minute lesson
Still there is not the same as reachable
Two promises are easy to mix up. Durability says that data which was stored is not lost. Availability says that you can reach it right now. A service can be down for an hour and lose nothing. It can also answer every request and have lost a file.
- DurabilityIs the data still there?a failure here is permanent
- AvailabilityCan I reach it now?a failure here passes
Drives fail all the time
In a system with thousands of drives, some fail every week. Data survives only when it is stored more than once, on drives that do not fail together. The simple way is to keep three full copies.
- Drive Afull copy
- Drive Bfull copy
- Drive Cfull copy
A storage service cannot be reached for an hour because of a network fault. Afterwards every object is there, unchanged.
Which promise was broken?
- Availability, but not durability
- Durability, but not availability
- Both of them, for that one hour
- Neither, as no object was lost
Show the answer
- Availability, but not durability
For an hour the data could not be reached, so availability failed. Nothing was lost, so durability held. The two are measured separately, and durability is the stricter one: an outage ends, but an object that is gone stays gone.
Unreachable for a while is an availability failure. Lost for good is a durability failure.
Pieces instead of copies
- Split
Erasure coding cuts an object into data pieces. Here there are four.
- Datapiece A
- Datapiece B
- Datapiece C
- Datapiece D
- Add
It then calculates two extra pieces from them, called parity. The six pieces go to six different drives.
- Datafour pieces
- Paritytwo piecescalculated
- Lose
Two drives fail. Any four of the six pieces are enough to calculate the object again, so nothing is lost.
- Losttwo pieces
- Leftfour pieces
- Objectrebuilt
The same safety for half the space
Three copies
Replication
- Survives
- two lost drives
- Space
- 3 times the data
- Repair
- copy a piece
Four plus two
Erasure coding
- Survives
- two lost drives
- Space
- 1.5 times the data
- Repair
- read four and calculate
An object is stored as 4 data pieces and 2 parity pieces on 6 drives.
How many drives can fail before the object is lost?
- Two: any four pieces rebuild it
- One: all the data pieces are needed
- Four: two pieces are always enough
- Five: one piece holds the object
Show the answer
- Two: any four pieces rebuild it
The object can be calculated from any four of its six pieces. It does not matter whether the lost ones were data or parity. So two drives may fail. A third failure leaves three pieces, and the object cannot be rebuilt.
An erasure-coded object survives as many lost drives as it has parity pieces.
How does erasure coding protect an object, and what does it save compared with three copies?
Show the answer
The object is cut into data pieces, and extra parity pieces are calculated from them. All pieces go to different drives. Any set as large as the number of data pieces can rebuild the object, so as many drives may fail as there are parity pieces. With four data and two parity pieces that is two drives, the same as three copies, for 1.5 times the space instead of 3 times. The cost is calculation when data is rebuilt.
Recap
- Durability means stored data is not lost. Availability means it can be reached now.
- Data survives failures only when it is stored more than once, on drives that fail independently.
- Erasure coding stores data and parity pieces, and survives as many lost drives as it has parity pieces.