CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 6 of 8 · 4 min read

Durability: copies and erasure coding

Keeping data safe against failed disks, machines and whole data centres.

Think of important papers. One copy in a drawer is lost in a fire. A copy at home and another at a relative's house survives the fire. A smarter way, covered below, splits the papers into pieces and adds a few checksum pages, so any damaged pieces can be rebuilt.

First, the difference between two words that sound alike, from the book "Building Microservices": the availability of a service and the durability of its data are different things. Availability asks whether you can get the data now. Durability asks whether the data still exists at all. A system can be briefly down and lose nothing, or be up and have lost data.

Durability

Durability is the chance that stored data is not lost over a period of time.

Example: a store with durability of 99.999999999 percent per year loses, on average, one object in every 100 billion each year.

Vendors publish figures like that for their object stores, with many nines. Treat such a number as the vendor's claim and look up the current value; the book does not give one. The arithmetic shows what it means.

A worked example. A store holds 10 million objects with an annual loss chance of 0.000000001 percent each, that is, 1 in 100 billion (10 to the power −11).

  • Expected losses per year: 10,000,000 × 10⁻¹¹ = 0.0001 objects.
  • That is one object lost every 10,000 years, on average.
  • With 100 billion objects: 1 object per year.

The book "System Design Interview" describes the simplest protection in its cloud drive design: replicate. Amazon S3 supports replication within a region and across regions. A region is a geographic area with data centres. Redundant copies in several regions guard against data loss and keep files available. It also notes a cold storage tier for files that are not accessed for a long time, which costs less.

Replication

Replication keeps copies of the same data on several machines or sites, so the loss of one does not lose the data.

Example: each object is stored on three machines in three separate data centres.

With three full copies, raw storage is three times the data. For a petabyte of customer data that is 3 PB of disks.

A more economical method used in large object stores is erasure coding. This is a standard technique from outside the supplied books. The idea: split an object into k data pieces, compute m extra parity pieces from them, and store all k + m pieces on different machines. Any k of the k + m pieces are enough to rebuild the object.

Erasure coding

Erasure coding splits data into k pieces and adds m parity pieces so that any k of the k + m pieces can rebuild the data.

Example: with k = 6 and m = 3, an object is stored as 9 pieces, and any 6 are enough. Up to 3 pieces can be lost.

A worked example for 1 PB of data.

Method Pieces Raw storage Overhead Losses survived
3 full copies 3 3 PB 3.0 times 2 copies
Erasure coding 6 + 3 9 1 PB × 9 ÷ 6 = 1.5 PB 1.5 times 3 pieces
Erasure coding 10 + 4 14 1 PB × 14 ÷ 10 = 1.4 PB 1.4 times 4 pieces

Erasure coding with 6 + 3 stores half the raw data of three copies and survives more losses. The price: reads and repairs need more work. To rebuild one lost piece, the system must read 6 others and compute. A read of the whole object needs 6 machines to answer, which adds delay, so latency can be higher than with copies. Many systems keep new, hot data as copies and move older data to erasure-coded storage.

Other protections used with either method:

  • Checksums. Each piece stores a hash. A background job reads data and compares it, catching silent corruption (a flipped bit on disk) before the other copies are lost too.
  • Spread over failure zones. Pieces go on different racks, power feeds and data centres, so one fault takes out at most one piece.
  • Repair quickly. When a disk fails, the system rebuilds its pieces on healthy disks at once. The risk is the second and third failure arriving before the first is repaired.
  • Versioning and delete protection. Many buckets keep old versions and delay real deletion, to survive accidental deletes. No amount of replication protects against a program that deletes everything on purpose or by mistake.
  • Backups apart from the main system, under separate permissions.

Common mistake

Confusing replication with backup. A replica copies a deleted or corrupted file faithfully within seconds. A backup is a separate, older copy that a mistake cannot reach.

Check yourself:

  • How much raw storage does 2 PB need with erasure coding 8 + 4?
  • Why does a replica not protect against an accidental delete?