Durability across machines: replication, quorums and erasure coding

How do copies on several machines raise durability, and what do they cost?

(This article is deliberately short and arithmetic. How replication is organized, how leaders are elected, how repair and failover work, and how membership and fencing are handled are subjects of their own. Here we only keep what changes the meaning of "yes" and the odds of losing data.)

Replication as durability: positions on the ack ladder

For durability, replication matters in one way: when does the primary say "yes"? Three common positions:

Mode	The primary says "yes" when...	Survives	Cost	Does not survive
Asynchronous	its own log is durable, without waiting for any replica	a restart of the primary (rung 4 only)	none	loss of the primary machine: the last moments of writes can be lost
Semi-synchronous	at least one replica has received (written to its own log or memory) the record	loss of the primary machine, as long as the replica survives	+1 network round trip (RTT), about 0.2–1 ms in the same availability zone	a replica that acknowledged receipt but had not yet made it durable
Synchronous	at least one replica has made the record durable on its own media	loss of the primary machine and of the replica's process; rung 5	+1 RTT plus the replica's flush	simultaneous loss of both failure domains

(Rule: each step up the ladder adds about one network round trip and one more flush on another machine.)

In Postgres the position is a pair of settings. synchronous_standby_names names the replicas the primary waits for, and synchronous_commit says how far: remote_write (the replica has received the record and handed it to its operating system: semi-synchronous), on (the replica has flushed it: synchronous) or remote_apply (it is also visible to queries on the replica). With no replica named, every setting is asynchronous.

The acknowledged-but-not-committed window

Every mode below synchronous has a window in which the client has been told "committed" and the record is not yet durable on a second machine. With asynchronous replication the window is the whole replication lag: whatever has not reached a replica when the primary dies is lost, even though the client was told it was committed. This is Nadia's 300 ms of missing transfers. With semi-synchronous replication the window shrinks: a replica can acknowledge receipt of a record, and the primary can say "yes" to the client. If the primary and that replica then fail before the record is applied anywhere durable, the record is lost.

Quorum writes: the durability arithmetic of W, R and N

In a quorum system, data is stored on N replicas. A write succeeds when W of them confirm it. A read asks R of them.

The usual rule W + R > N is taught as a consistency statement: any read set overlaps any write set in at least one replica, so a read sees the latest write. Here we use it as a durability statement, and the quantity that matters for durability is W, not the overlap rule:

W is the number of copies that exist when you say "yes". If W = 1, one machine failing right after the ack can destroy the only copy. If W = 2, you survive any single failure.
W + R > N says nothing about how many machines can fail without data loss. That is decided by W (and by the failure domains in which those W copies live).

Durability arithmetic under correlated failure

Before the arithmetic, one assumption has to be said out loud: replication, quorums and erasure coding all divide by a failure probability that is assumed to be independent. Independence is assumed almost everywhere and is true almost nowhere. What really kills clusters are correlated failures: the same rack, the same firmware version, the same bad manufacturing batch, the same bad deploy, the same operator.

MTTDL (Mean Time To Data Loss) is the usual figure of merit. A simplified estimate for 3 replicas assumes: each disk fails independently with yearly probability p, and a failed disk is rebuilt within a short repair window.

Worked example (independent failures)

p = 1% per year. The chance that all 3 specific disks fail in the same year is p³ = 0.01³ = 10⁻⁶ (one in a million). With a repair time of a day, the chance is far lower still. That is the manager's calculation. It looks like extreme safety.

RelationshipLosing every replica →

p^{3} = 0.0 1^{3} = 1 0^{- 6}

$p$: yearly probability that one disk fails
$n$: copies kept
$p_{common}$: yearly probability of a defect that takes all disks of the batch together

independent: pⁿone common cause at 5%

Data table

Yearly chance of losing every copy, by replicas (p = 1% per disk)
Replicas n	series	Chance all are lost in a year
1	independent: pⁿ	0.01
1.06	independent: pⁿ	0.008
1.13	independent: pⁿ	0.006
1.19	independent: pⁿ	0.004
1.25	independent: pⁿ	0.003
1.31	independent: pⁿ	0.002
1.38	independent: pⁿ	0.002
1.44	independent: pⁿ	0.001
1.5	independent: pⁿ	0.001
1.56	independent: pⁿ	0.001
1.63	independent: pⁿ	0.001
1.69	independent: pⁿ	0
1.75	independent: pⁿ	0
1.81	independent: pⁿ	0
1.88	independent: pⁿ	0
1.94	independent: pⁿ	0
2	independent: pⁿ	0
2.06	independent: pⁿ	0
2.13	independent: pⁿ	0
2.19	independent: pⁿ	0
2.25	independent: pⁿ	0
2.31	independent: pⁿ	0
2.38	independent: pⁿ	0
2.44	independent: pⁿ	0
2.5	independent: pⁿ	0
2.56	independent: pⁿ	0
2.63	independent: pⁿ	0
2.69	independent: pⁿ	0
2.75	independent: pⁿ	0
2.81	independent: pⁿ	0
2.88	independent: pⁿ	0
2.94	independent: pⁿ	0
3	independent: pⁿ	0
3.06	independent: pⁿ	0
3.13	independent: pⁿ	0
3.19	independent: pⁿ	0
3.25	independent: pⁿ	0
3.31	independent: pⁿ	0
3.38	independent: pⁿ	0
3.44	independent: pⁿ	0
3.5	independent: pⁿ	0
3.56	independent: pⁿ	0
3.63	independent: pⁿ	0
3.69	independent: pⁿ	0
3.75	independent: pⁿ	0
3.81	independent: pⁿ	0
3.88	independent: pⁿ	0
3.94	independent: pⁿ	0
4	independent: pⁿ	0
4.06	independent: pⁿ	0
4.13	independent: pⁿ	0
4.19	independent: pⁿ	0
4.25	independent: pⁿ	0
4.31	independent: pⁿ	0
4.38	independent: pⁿ	0
4.44	independent: pⁿ	0
4.5	independent: pⁿ	0
4.56	independent: pⁿ	0
4.63	independent: pⁿ	0
4.69	independent: pⁿ	0
4.75	independent: pⁿ	0
4.81	independent: pⁿ	0
4.88	independent: pⁿ	0
4.94	independent: pⁿ	0
5	independent: pⁿ	0
5.06	independent: pⁿ	0
5.13	independent: pⁿ	0
5.19	independent: pⁿ	0
5.25	independent: pⁿ	0
5.31	independent: pⁿ	0
5.38	independent: pⁿ	0
5.44	independent: pⁿ	0
5.5	independent: pⁿ	0
5.56	independent: pⁿ	0
5.63	independent: pⁿ	0
5.69	independent: pⁿ	0
5.75	independent: pⁿ	0
5.81	independent: pⁿ	0
5.88	independent: pⁿ	0
5.94	independent: pⁿ	0
6	independent: pⁿ	0
1	one common cause at 5%	0.05
1.06	one common cause at 5%	0.05
1.13	one common cause at 5%	0.05
1.19	one common cause at 5%	0.05
1.25	one common cause at 5%	0.05
1.31	one common cause at 5%	0.05
1.38	one common cause at 5%	0.05
1.44	one common cause at 5%	0.05
1.5	one common cause at 5%	0.05
1.56	one common cause at 5%	0.05
1.63	one common cause at 5%	0.05
1.69	one common cause at 5%	0.05
1.75	one common cause at 5%	0.05
1.81	one common cause at 5%	0.05
1.88	one common cause at 5%	0.05
1.94	one common cause at 5%	0.05
2	one common cause at 5%	0.05
2.06	one common cause at 5%	0.05
2.13	one common cause at 5%	0.05
2.19	one common cause at 5%	0.05
2.25	one common cause at 5%	0.05
2.31	one common cause at 5%	0.05
2.38	one common cause at 5%	0.05
2.44	one common cause at 5%	0.05
2.5	one common cause at 5%	0.05
2.56	one common cause at 5%	0.05
2.63	one common cause at 5%	0.05
2.69	one common cause at 5%	0.05
2.75	one common cause at 5%	0.05
2.81	one common cause at 5%	0.05
2.88	one common cause at 5%	0.05
2.94	one common cause at 5%	0.05
3	one common cause at 5%	0.05
3.06	one common cause at 5%	0.05
3.13	one common cause at 5%	0.05
3.19	one common cause at 5%	0.05
3.25	one common cause at 5%	0.05
3.31	one common cause at 5%	0.05
3.38	one common cause at 5%	0.05
3.44	one common cause at 5%	0.05
3.5	one common cause at 5%	0.05
3.56	one common cause at 5%	0.05
3.63	one common cause at 5%	0.05
3.69	one common cause at 5%	0.05
3.75	one common cause at 5%	0.05
3.81	one common cause at 5%	0.05
3.88	one common cause at 5%	0.05
3.94	one common cause at 5%	0.05
4	one common cause at 5%	0.05
4.06	one common cause at 5%	0.05
4.13	one common cause at 5%	0.05
4.19	one common cause at 5%	0.05
4.25	one common cause at 5%	0.05
4.31	one common cause at 5%	0.05
4.38	one common cause at 5%	0.05
4.44	one common cause at 5%	0.05
4.5	one common cause at 5%	0.05
4.56	one common cause at 5%	0.05
4.63	one common cause at 5%	0.05
4.69	one common cause at 5%	0.05
4.75	one common cause at 5%	0.05
4.81	one common cause at 5%	0.05
4.88	one common cause at 5%	0.05
4.94	one common cause at 5%	0.05
5	one common cause at 5%	0.05
5.06	one common cause at 5%	0.05
5.13	one common cause at 5%	0.05
5.19	one common cause at 5%	0.05
5.25	one common cause at 5%	0.05
5.31	one common cause at 5%	0.05
5.38	one common cause at 5%	0.05
5.44	one common cause at 5%	0.05
5.5	one common cause at 5%	0.05
5.56	one common cause at 5%	0.05
5.63	one common cause at 5%	0.05
5.69	one common cause at 5%	0.05
5.75	one common cause at 5%	0.05
5.81	one common cause at 5%	0.05
5.88	one common cause at 5%	0.05
5.94	one common cause at 5%	0.05
6	one common cause at 5%	0.05

Principle: Independence is assumed →

Now add correlation. The three disks came from the same batch, in the same rack, with the same firmware. Suppose the batch has a defect that makes the yearly failure probability of all its disks 5% together (one common cause). Then the chance of losing all three in a year is on the order of 0.05, not 10⁻⁶: about 50,000× worse. In practice, MTTDL computed under independence overstates real durability by orders of magnitude. So:

Replication factor buys much less than p^N once batch, rack and software correlation are included.
The cheap gains come from spreading the copies across failure domains (different racks, different zones, different software versions or vendors), more than from adding a fourth copy in the same domain.
Silent corruption (When the storage lies) is correlated within a drive and batch, so it is a correlated failure as well.