Durability: replication vs erasure coding

A storage system keeps data durable by storing more than one byte for every byte it is given. Replication stores whole copies: three copies cost 3 bytes per byte and survive the loss of any two. Erasure codingerasure coding: Storing data as data blocks plus parity blocks computed from them, so that lost blocks can be rebuilt from the rest. With 6 data and 3 parity blocks it keeps 1.5 raw bytes per byte, half of what three full replicas need, at extra CPU and network cost. More in “Estimating storage, bandwidth and cache memory” cuts the data into k pieces and computes m parity pieces from them, and any k of the k + m pieces rebuild the data: Reed-Solomon (10, 4) costs 1.4 bytes per byte and survives any four lost pieces. Erasure coding therefore protects as well or better on half the disks or fewer, and pays when a piece is lost, because rebuilding one piece reads k others. That is why most large stores keep hot data replicated and erasure-code data once it has cooled.

Copies, pieces and what each survives

Three numbers describe a scheme: the bytes it stores per byte of data, how many lost pieces it survives, and how many pieces a repair reads to rebuild one. The example computes them for the schemes this lesson compares.

# Copies against fragments: what each scheme stores per byte of data, how many lost pieces it survives, and how many
# pieces a repair reads to rebuild one. Replication keeps n whole copies; a (k, m) erasure code cuts the data into k
# fragments, adds m parity fragments, and rebuilds the data from any k of the k + m.
SCHEMES = [
    # name, data pieces k, extra pieces m, pieces read to rebuild one lost piece
    ("2 copies", 1, 1, 1),
    ("3 copies", 1, 2, 1),
    ("XOR parity (2, 1)", 2, 1, 2),
    ("Reed-Solomon (6, 3)", 6, 3, 6),
    ("Reed-Solomon (10, 4)", 10, 4, 10),
]

print(f"{'scheme':<22}{'pieces':>7}{'stored per byte':>17}{'survives':>10}{'repair reads':>14}")
for name, k, m, reads in SCHEMES:
    n = k + m
    print(f"{name:<22}{n:>7}{n / k:>17.2f}{m:>7} lost{reads:>14}")

print("\nFor 1 PB of data:")
for name, k, m, _ in SCHEMES:
    print(f"  {name:<22}{(k + m) / k:>5.2f} PB of disk")

scheme                 pieces  stored per byte  survives  repair reads
2 copies                    2             2.00      1 lost             1
3 copies                    3             3.00      2 lost             1
XOR parity (2, 1)           3             1.50      1 lost             2
Reed-Solomon (6, 3)         9             1.50      3 lost             6
Reed-Solomon (10, 4)       14             1.40      4 lost            10

For 1 PB of data:
  2 copies               2.00 PB of disk
  3 copies               3.00 PB of disk
  XOR parity (2, 1)      1.50 PB of disk
  Reed-Solomon (6, 3)    1.50 PB of disk
  Reed-Solomon (10, 4)   1.40 PB of disk

The HDFS documentation makes the same comparison for its default policy: six blocks stored three times use 18 blocks of disk, while 6 data and 3 parity blocks use 9 (HDFS erasure coding). So Reed-Solomon (6, 3) survives three lost pieces where three copies survive two, on half the disk. The last column is the catch. Rebuilding a lost copy reads one surviving copy; rebuilding a lost Reed-Solomon piece reads six or ten.

Where the pieces sit matters as much as how many there are. A failure domainfailure domain: A set of disks or machines that one fault can take down together, such as a host, a rack, a power feed or a zone. Copies or pieces of the same data are spread across failure domains so that one fault cannot take them all. is anything that can take many disks down at once: a host, a rack, a power feed, a zone. Three copies in three zones survive a zone outage, and so does a Reed-Solomon (6, 3) stripe with three pieces in each zone, as drawn above. Step through both layouts as the zones fail:

The rest of the design follows from a few more ideas, each in one sentence. XOR parity is the simplest erasure code: one parity piece rebuilds any single lost piece. Reed-Solomon codes extend it to m parity pieces, so any m pieces may be lost. Local reconstruction codes add parity for small groups, so most repairs read a few pieces instead of k. A degraded readdegraded read: A read of erasure-coded data whose wanted piece is missing: the reader fetches enough other pieces of the stripe and decodes the missing one, which costs more reads and CPU than a normal read. fetches other pieces and decodes when the piece it wanted is missing. Repair time is the window in which further failures can turn a damaged stripe into lost data.

How parity rebuilds a lost block, in code Pro: opens with a Pro, Premium or Ultimate pass