Replication, Quorums & Read-Your-Writes

Part 0. Start here

The problem: 500 lost orders and a stale checkout page

An orders database commits 5,000 transactions a second on its primary. It has two asynchronous replicas (copies that receive the primary's log after the commit, without the commit waiting for them), one in each of the other two Availability Zones: self-run PostgreSQL or MySQL, or RDS read replicas. The replicas serve reads and are the failover targets. During a heavy write burst, the primary's write-ahead log (WAL) reaches the replicas 100 ms after each commit (our example's number). At every instant of that burst, two things are true.

1. A failover loses acknowledged writes. Writes committed in the last 100 ms exist only on the primary:

• 5,000 commits a second × 0.1 s = 500 acknowledged transactions that no replica has yet.

If the primary dies now and a replica is promoted, 500 customers were told "OK" and their orders are gone. (Aurora is different: its replicas share one storage volume that already holds every commit, so an Aurora promotion loses nothing committed. Its lag only makes reads stale, which is the second problem.)

2. Users can't see their own writes. Anyone who saves and reloads before their write is applied on the replica their read lands on sees the old value. A checkout page that re-reads a just-saved shipping address from a replica ships to the old address. This happens on Aurora too: AWS says Aurora Replica lag is "usually much less than 100 milliseconds after the primary instance has written an update", and that it can rise "during periods where a large amount of write operations occur". A read inside that window, on the reader endpoint, is stale.

The big picture

Synthesizing vector architecture diagram...

What to notice: the write is committed when 2 of the 3 copies have it (the leader plus the fastest follower), and the OK carries a position. A read carrying that position may go to any copy that has applied it; if none has, it goes to the leader.

What you'll be able to do after this page

1. Say what a replica keeps and name the three positions that matter: stored, committed and applied (Part 1).
2. Say exactly when each replication mode acknowledges a write, what it loses in a failover, and what it does when followers are down (Part 2).
3. Measure replication lag in its two parts, and say which part decides stale reads and which decides lost writes (Part 3).
4. Give users read-your-writes and monotonic reads without sending every read to the leader (Part 4).
5. Use N, W and R, and say what W + R > N guarantees and what it doesn't (Part 5).
6. Walk through a leader election after a crash and explain why no committed write is lost (Part 6).
7. Explain what each side of a network partition can do, how a deposed leader is fenced, and how a database fails over (Part 7).
8. Bring a lagging follower back from the log or from a snapshot, without starving everyone else (Part 8).
9. Repair drifting copies, make deletes stick, and explain why replication is not a backup (Part 9).
10. Choose single-leader, multi-leader or leaderless, and synchronous or asynchronous, on equal terms (Part 10).
11. Map all of it to AWS services, and name the look-alikes that are not replication (Part 11).

You may have arrived from a step that relies on this: step 2.4 of the digital wallet loop (read-your-own-writes with min_version), step 1.3 of the message queue loop (Raft per log, commit on 2 of 3), step 1.6 of the key-value store loop ("when is a write done?", N = 3, W = 2, R = 2), or step 3.2 of the URL shortener loop (why an eventually consistent global table can't decide who owns an alias). This page is the "why" behind all four.

---

Part 1. What a replica keeps

Three copies, one truth: which copy is right when they disagree? Before any protocol, we need a picture of what each copy holds, so that "disagree" has a precise meaning.

One log, three copies

A replicated store keeps one ordered log of changes and copies it. The leader decides the order: each write becomes the next entry in its log. Each entry has a position (its index: PostgreSQL calls it an LSN, MySQL identifies transactions by GTID, Raft uses an index, Kafka an offset) and the term of the leader that created it (a counter that goes up with each new leader; Part 6). We draw an entry as term.index: 1.2 is the second entry, created by the term-1 leader.

"Replicated" means every copy has the same log in the same order. The copies differ only in how far along that log they are. So the questions on this page are all about positions: how far along is each copy, and which position does a write or a read wait for?

Stored, committed, applied

Every copy tracks three positions. They are different, and mixing them up is the source of most replication bugs.

On any copy, applied ≤ committed as far as it knows, and it never applies an entry it hasn't stored. The three positions can be far apart: a copy can have an entry on disk for hundreds of milliseconds before it applies it (Part 3).

Synthesizing vector architecture diagram...

Snapshot S1, at t = 106 ms, from the reference implementation. All three copies have entry 1.2 on disk; only A has applied it. B will apply it when the next heartbeat tells it 1.2 is committed (110.2 ms); C won't until a long report query stops blocking its apply (400.0 ms). Same log, three different answers to a read.

Three families

The page follows single-leader first, because most of the loops use it; Part 5 replays the same three copies without a leader, and Part 10 compares all three.

One exception needs no ordering at all: immutable data. A chunk of an object that is written once and never changed (the S3-like object storage loop, step 1.2) only needs enough copies; there is no "which version wins", because there is only one version. The mutable metadata record that points to the chunks is what needs a log.

What the WAL page already said

The Write-Ahead Log, fsync & Group Commit loop primitive's Part 10 has what "acknowledged" means on each engine (Kafka's acks=all, PostgreSQL's synchronous_commit, MySQL semi-sync, Raft, DynamoDB, Aurora) and what one replica's "on disk" costs. This page starts where that one stops: which copies wait, who leads, and which copy a read may use.

The example we follow

One key, addr:alice, on three replicas: A (AZ a), B (AZ b) and C (AZ c). Alice saves addresses from a laptop, a phone and a tablet; a checkout page, a report query, a repair job and a backup read them. We follow the key from its first write to its erasure. Every trace on this page comes from running a private reference implementation, a discrete-event simulator of these three replicas, not from working by hand.

The story has nine beats, each in its own Part: ways to say OK (Part 2), a stale checkout page (3), the fixes (4), the same replicas without a leader (5), A crashes mid-write (6), C is cut off (7), B comes back late (8), Alice is erased and a bad update reaches everyone (9), and choosing, with Alice in two Regions (10). Two side replays fork from the state after event 8, when all three copies hold "9 Elm St": the leaderless replay (rows Q1 to Q7, with their own clock, written q0, q3.0 and so on) and the two-Region replay (rows G1 to G3). The full event table is in Part 12.

---

Part 2. When to say OK: sync, async, semi-sync

At t = 0 the laptop saves Alice's first address, v1 "12 Oak St", which becomes entry 1.1 on A. At t = 1.2 ms, A loses power. Did Alice's write survive? It depends entirely on when A said OK, and on which copies had the entry by then. "We replicate" hides that choice; this Part makes it visible.

Trace: A dies at 1.2 ms

The same write under each mode, from the reference implementation. "OK at" is the time A would acknowledge if it lived; the last column is what happens if A dies at 1.2 ms and a follower is promoted.

Three lessons from one write:

• Asynchronous replication says OK before any other copy has the write. Any failover can lose the tail that hadn't shipped.
• A synchronous mode never loses a write it acknowledged to one failure, but it can keep a write it never acknowledged. The client that timed out must not assume "failed": a retry has to be safe to repeat, which is the Idempotency & Effectively-Once Processing loop primitive's subject.
• Latency depends on how the log is shipped. Raft-style logs send to followers while the leader syncs, so the commit waits for the slowest leg we need: max(local sync, the fastest follower's acknowledgement at W = 2). The slow follower C never enters the latency. PostgreSQL ships only flushed WAL, so its synchronous commit is local flush plus a round trip: 2.4 ms here, not 1.4. The WAL page's Part 10 has this latency rule with the same caveat.

When followers are down

The mode matters most when copies are missing. From the reference implementation, with the same timings:

The last cell is the dangerous one. Nothing fails, so nobody notices, but from that moment an OK means only "on the source's disk". The promise changed silently.

PostgreSQL's cancelled wait

A PostgreSQL commit that is waiting for its synchronous standby has already committed locally. If the client cancels the wait (or the connection is terminated), PostgreSQL can't un-commit it; it returns a warning instead:

textCopy
WARNING:  canceling wait for synchronous replication due to user request
DETAIL:  The transaction has already committed locally, but might not have been replicated to the standby.

That commit is now visible on the primary and possibly on no standby. If the primary fails before the standby receives it, a failover loses it. This is the same lesson as the WAL page's "a write on one disk but not on a quorum is not kept", in a form that looks like success: treat a cancelled synchronous wait as an unknown outcome, never as a replicated commit.

How many writes an asynchronous failover can lose

For an asynchronous copy, the writes at risk are the ones committed on the leader but not yet stored on the copy we promote:

Formula 1:

$$\text{writes at risk} \;=\; \text{commit rate} \times \text{shipping lag}$$

Shipping lag is the distance between the leader's commit position and the position the replica has received and flushed, measured in time. It is not the replica's replay (apply) lag: a replica can have an entry safely on disk while it is still waiting to apply it (Part 3), and a failover to it keeps that entry. With the hook's numbers: 5,000 commits a second × 0.1 s = 500 writes.

---

Part 3. Replication lag and stale reads

At 150 ms Alice's checkout page shows "12 Oak St", the address she replaced 48.6 ms earlier. Nothing crashed; every copy is healthy. This Part is about the gap between a write committing and a copy showing it, which is where most replication bugs in the loops come from.

Trace: the stale checkout

Back to the main line, with v1 on all three copies (applied by 10.2 ms). The reference implementation:

Synthesizing vector architecture diagram...

What to notice: C has v2 on disk from 105.8 ms, only 4.4 ms after the commit, yet both of its reads return the old address, because its apply is blocked until 400 ms. B, reached between them, shows the new one.

Shipping vs applying

The metrics you get mostly measure the second, or both together. PostgreSQL's pg_stat_replication view, on the primary, has three: write_lag (the standby has written the WAL), flush_lag (written and flushed) and replay_lag (flushed and applied). Failover loss follows the flush gap; stale reads follow replay_lag, which PostgreSQL's documentation says, for an asynchronous standby, "approximates the delay before recent transactions became visible to queries". On a standby, comparing pg_last_wal_receive_lsn() with pg_last_wal_replay_lsn() separates the two. Aurora's AuroraReplicaLag metric and RDS's ReplicaLag are about when a replica shows the writer's changes, so they are read-staleness numbers.

Where lag comes from

Measuring it and detecting a stuck replica

Position metrics tell you how far behind a replica is if it is still hearing from the leader. A replica that stopped receiving can look fine: MySQL's Seconds_Behind_Source compares the event being applied with its timestamp on the source, so when the applier has caught up with a slow receiver it shows 0, and MySQL's documentation warns that on a slow network it "often shows a value of 0, even if the replication receiver thread is late compared to the source"; if the receiver thread isn't running, it shows NULL. The robust check is a heartbeat row: once a second the primary writes the current time into a one-row table, and the monitor reads that row on each replica. Lag = now − the time in the row. It works whether the replica is slow, blocked or cut off, because a cut-off replica's row simply stops moving.

And lag is a distribution, not a number. "Usually much less than 100 milliseconds" and "typically within a second" are descriptions of the common case. They are never bounds: under a write burst, a blocked replay or a network problem, lag has no ceiling unless something enforces one (RDS's flow control for Multi-AZ DB clusters, or Aurora PostgreSQL's rds.global_db_rpo for a global database, both of which do it by slowing the writer). Design reads that tolerate the tail, and act on measured lag, like the paging library loop does when it widens its settle cutoff by the measured lag and moves reads to the writer above 5 s (steps R2.3 and R2.8).

Reads that go backwards

Events 5 to 7 show a second problem beyond staleness. The reader endpoint spreads reads across B and C, which are at different positions, so Alice saw new, then old. That breaks monotonic reads (never see an older state after a newer one). It is caused by load balancing across copies that differ, not by any single copy being slow.

---

Part 4. Read-your-writes and monotonic reads

Replay event 5: the checkout page's read at 150 ms is about to land on C, which hasn't applied v2. Which copy may answer? Neither "any replica" nor "always the leader" is a good answer. This Part gives the read enough information to choose.

The two promises

These are session guarantees: promises about what one user (one session) sees, not about the whole database. They are separate from transaction isolation levels, which are about concurrent transactions on one copy (Primitive #21: Isolation levels).

Two more, named for completeness: monotonic writes (my writes apply in the order I made them) and writes-follow-reads (a write I make after reading something is ordered after what I read). A single-leader log gives both for free, because every write goes through one ordered log.

The mechanism: carry the position

The write's OK carries its commit position p. The read carries the highest position this session must see, and the router only uses a copy that has applied at least that far.

textCopy
ON WRITE COMMIT:
  reply OK with p = the entry's position
  session.p_write = p                                  -- on the client, or in a server-side session record

ON READ:
  need = max(session.p_write, session.p_read)
  pick = the replica the load balancer chose
  if applied(pick) >= need: answer from pick
  else if another replica has applied(r) >= need: answer from r
  else wait up to a budget (say 20 ms) for pick to reach need
  else: answer from the leader
  session.p_read = the position of the copy that answered

DECISIONS (money, permissions, consent): read the leader, always

The fixes, on equal terms

The reference implementation replays events 5 to 7 under six policies. In every row, v2 is position 2; C has applied position 1 until 400 ms; B has applied 2 since 110.2 ms.

Engines and services

The wallet loop (steps R2.3 and 2.4) uses exactly F1 with a min_version; the payments loop (step R2.5) and the nearby friends loop (step R1.7) use the rule "anything that decides reads the writer".

The read half, end to end through the layers

The write half of this trace, from the client down to "W of N have it", is in the WAL page's Part 10. Here is the other half: where staleness can enter a read, following the event-5 read at 150 ms.

Synthesizing vector architecture diagram...

What to notice: the position check is the only step that knows about Alice's write. A cache hit above it skips the check entirely, and the replica's apply queue below it (C's blocked apply) is exactly what the check protects against.

---

Part 5. Quorums: N, W and R

Take the same three copies and remove the leader. A read with R = 1 lands on C and returns "9 Elm St", although a newer address was acknowledged a moment ago. Without a leader, nobody orders the writes, so "enough copies" has to be counted on both sides: the writes and the reads. This Part is that counting rule and its limits.

The leaderless replay

We fork the story after event 8, when A, B and C all hold v2 "9 Elm St" (version 2). The copies are now Dynamo-style: a coordinator (a node beside A, in AZ a) sends every write to all N home replicas and waits for W acknowledgements; a read asks R replicas and keeps the answer with the highest version. The replay has its own clock (q0, q3.0 and so on) and its own versions, q3, q4 and q5. Replica answer times, from the coordinator's request to the reply: A 1.0 ms, B 1.4 ms, C 6.0 ms, stand-in D 1.2 ms.

From the reference implementation:

Synthesizing vector architecture diagram...

What to notice: the write was acknowledged by A and B, so any two replicas include at least one that has it. The R = 2 read met A and returned q3; an R = 1 read that met only C would have returned the old value.

The overlap rule

Formula 2:

$$W + R > N$$

If the number of copies a write waits for plus the number a read asks is more than the number of copies, every read set shares at least one copy with every acknowledged write's set, so the read meets that write. With N = 3, W = 2 and R = 2: 2 + 2 = 4 > 3. With R = 1: 2 + 1 = 3, not more than 3, which is why Q2's R = 1 read could miss it.

A single-leader log is the special case where W is a majority and the leader's own copy decides reads: every majority overlaps every other majority, which is why a new leader elected by a majority must meet every committed entry (Part 6).

Latency is the W-th fastest replica for a write and the R-th fastest of those asked for a read (in the table, the reads ask the fastest replicas first). When the coordinator is itself a replica, a write waits for max(its own sync, the (W − 1)-th fastest other replica), the same rule as the Raft leader in Part 2. With 5 replicas and W = 3, a write waits for the second-fastest of the four others: more copies can make a write faster at the tail, because the slowest one is ignored, while costing more bytes and storage (Part 7 has the 3, 4 and 5 table).

Most stores let you choose per request: Cassandra's ONE, QUORUM and LOCAL_QUORUM (a quorum of the replicas in the local data center), as the key-value store loop does in step 2.1.

Where the overlap stops

W + R > N guarantees one thing: in normal operation, a read meets the latest acknowledged write. It does not make the store linearizable (every read sees every write that finished before it began, as if there were one copy). Three cases break the simple promise:

The consistency ladder

"Is a quorum store linearizable?" is the question behind all three rows. One table, strongest first, each with the mechanism on this page that provides it:

W + R > N on its own sits below linearizable: it gives "a read overlaps the latest acknowledged write" when there are no concurrent or failed writes, and nothing when the quorum is sloppy (next).

Sloppy quorums and hinted handoff, briefly

What if home replicas are down when a write arrives? A strict quorum counts only the N home replicas, so the write fails. A sloppy quorum lets a stand-in node accept the write with a hint naming the home replica it belongs to, and counts the stand-in toward W; the stand-in hands the write over when the home replica returns (hinted handoff). The 2007 Dynamo paper and Riak do this. Cassandra stores hints too, on the coordinator, but a hint doesn't count toward the consistency level (except at the special level ANY), so Cassandra's quorums stay strict. The key-value loop warns about exactly this in step 2.4 and its mistake list (R2.9 #5): a sloppy quorum mistaken for strong consistency.

Snapshot S7, after Q5 (q40): A holds q4 "7 Birch Ave"; B and C hold q3 "5 Ash Ct"; the stand-in D holds hints of q4 for B and C.

---

Part 6. The leader crashes: elections

Back on the main line. At 1,003.0 ms A loses power in the middle of a write: its entry 1.3 reached C but not B. Someone must take over, and the new leader must hold every committed write, including ones it can't tell were committed. This Part is how Raft does that; the same ideas (a term, one vote per term, "only the most up-to-date may win") appear in every consensus-backed failover.

Trace: A dies with index 3 half-sent

Snapshot S2 (t = 1,003.0, from the reference implementation):

Terms, votes, and why votes are written down

Raft's election rules, as far as our story needs them:

• Terms are a logical clock: each election starts a new, higher term, and each term has at most one leader. Every message carries its sender's term. A node that sees a higher term adopts it and becomes a follower; a message from a lower term is refused.
• Randomized timeouts: a follower that hears nothing from a leader for its election timeout (drawn at random, 150 to 300 ms in the Raft paper's example) becomes a candidate: it increments its term, votes for itself and asks the others for votes. Randomness makes it unlikely that two candidates split the votes; a split just means another round with new random timeouts.
• One vote per term, written to disk before it is sent. A node's current term and its vote are persistent state, updated on stable storage before it responds. Otherwise a node could vote, crash, restart with no memory of it, and vote again for someone else in the same term: two leaders in one term.
• The election restriction: a voter refuses a candidate whose log is less up-to-date than its own. The Raft paper's rule: "If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date."

textCopy
ON ELECTION TIMEOUT (no leader heard for my random timeout):
  term = term + 1; votedFor = me
  sync term and votedFor to disk                      -- before anything is sent
  send RequestVote(term, my last entry's term and index) to all

ON RequestVote(candidate, term, lastTerm, lastIndex):
  if term > myTerm: myTerm = term; votedFor = none; become follower
  upToDate = lastTerm > myLastTerm
             or (lastTerm == myLastTerm and lastIndex >= myLastIndex)
  grant = (term == myTerm) and votedFor in (none, candidate) and upToDate
  if grant: votedFor = candidate; reset my election timer
  sync myTerm and votedFor to disk                    -- before replying
  reply(myTerm, grant)

A CANDIDATE WITH VOTES FROM A MAJORITY (itself included) IS LEADER FOR THAT TERM

Why the restriction keeps every committed entry: a committed entry is on a majority, a winner needs votes from a majority, and any two majorities share a node. That shared node has the entry and refuses any candidate whose log lacks it.

Trace: who wins

From the reference implementation (the arithmetic shown in brackets):

B's timer fired first, yet C leads, because B's log was missing an entry C had. That is the restriction doing its job: 1.3 might have been committed as far as anyone alive knew.

Synthesizing vector architecture diagram...

What to notice: the first candidate loses because its log is shorter; every vote waits for a disk sync; and the commit waits for C's slow disk, which is now the leader's disk.

The no-op and the commitment rule

When C wins, it has entry 1.3 on its disk and knows a majority ({B, C}) will soon have it. Can it call 1.3 committed as soon as B stores it? Raft says no:

textCopy
LEADER, AFTER A FOLLOWER ACKNOWLEDGES:
  for N from my last index down to commitIndex + 1:
    if log[N].term == currentTerm and a majority (me included) has stored N:
      commitIndex = N            -- every earlier entry is committed with it
      break
ON WINNING AN ELECTION:
  append a no-op in the new term and replicate it

Snapshot S3 (t = 1,252.8):

The write that committed anyway

Alice's laptop never got an OK for v3: A died before it could send one, and the laptop times out at 3,000.0. Yet v3 is committed at 1,252.8 and is Alice's address everywhere. A client that treats a timeout as "failed" and writes something else, or retries a non-idempotent operation ("add $10"), gets it wrong. A timeout is an unknown outcome: retries must be idempotent, which the Idempotency & Effectively-Once Processing loop primitive builds.

Two costs of the election show in the trace:

• The write gap: from the crash to the first commit, 1,252.8 − 1,003.0 = 249.8 ms in which nothing could commit, including the vote syncs and a failed first round. At etcd's defaults (a 1,000 ms election timeout), expect seconds.
• The new leader's disk now sets the latency. Every commit in term 3 waits for C's own 5.6 ms sync: max(5.6, B's 1.4) = 5.6 ms. An election can move leadership onto the slowest disk; some systems prefer or transfer leadership to a better node afterwards.

---

Part 7. A partition and a split-brain attempt

The WAL page's branch R (ii) showed the short version: a leader cut off from its followers syncs writes to its own disk, the others elect a new leader, and when the old leader rejoins it deletes those writes. Here we slow that down. At 2,001 ms C's whole AZ is cut off from A and B, while Alice's tablet, in AZ c, can still reach C. C still believes it leads.

Trace: C keeps writing

Two leaders now exist, in different terms. Snapshot S4 (t = 2,201.4):

Synthesizing vector architecture diagram...

What to notice: both panels have a leader, but only "Majority: A and B" can commit. C's entry at index 5 has term 3; A's entry at the same index has term 4. That difference is what settles it when the link returns.

What each side can do

This is the drill The Network Partition That Elected Two Leaders in log terms. Page 03's Part 8 gave the lock-service consequence (a minority can't grant, release or expire a lock). Inside the log: in a 5-node cluster split 2 and 3, the 2-node side can't commit any client write, because a commit needs 3 of 5 copies. Its old leader keeps appending entries that time out; the 3-node side elects a leader in a higher term and carries on; when the partition heals, the old leader sees the higher term, steps down, and its uncommitted entries are deleted. Nothing is merged: the majority's log wins.

Terms fence the old leader

Every message carries its sender's term. When the link returns, the first message C sees from A has term 4, higher than C's 3: C becomes a follower at once. Any message C sends with term 3 is refused by A and B with "my term is 4". This is term fencing, and it covers everything that goes through the log. It doesn't cover anything the old leader did outside the log (an email it sent, a file it wrote to S3): those need a fencing token checked by that other system, which is the Leases, Fencing Tokens & Distributed Locks loop primitive's subject.

Reads on a leader that may be deposed

At 2,250 ms a client asks C for Alice's address. From the reference implementation:

textCopy
READ INDEX (a round trip per read, or per batch of reads):
  r = commitIndex
  send a heartbeat to every follower; wait for acks from a majority (me included)
  if I stepped down meanwhile: fail, redirect to the leader
  wait until applied >= r; answer from local state

LEASE READ (no round trip, but relies on clocks):
  lease_start = send time of the last heartbeat a majority acknowledged
  answer locally only while now < lease_start + lease
  choose lease < minimum election timeout - a margin for clock-rate difference

Why time the lease from the heartbeat's send: a follower resets its election timer when it receives the heartbeat, which is after the send, so the earliest any follower can start an election is (receive time + minimum timeout), which is later than (send time + minimum timeout). Ending the lease 10.2 ms before that leaves room for clocks that run at slightly different speeds. The Raft paper notes a lease "would rely on timing for safety"; how much margin clock behaviour needs is page 03's Part 3.

When the link returns

At 3,000.0 the link is restored. A's next heartbeat to C, in term 4, carries "previous entry 3.4, then 4.5 and 4.6".

Synthesizing vector architecture diagram...

What to notice: the previous entry matches, so C doesn't need to back up; the conflict is at index 5, where the terms differ, and C deletes from there. The tablet's write, never committed, is gone, and the tablet had never been told OK.

The truncation rule: when a follower accepts an append, any of its entries that conflict with the leader's (same index, different term) are deleted, together with everything after them, and the leader's entries are appended. Only uncommitted entries can ever be deleted this way, because a leader always holds every committed entry (Part 6).

Snapshot S5 (t = 3,010): all three copies hold 1.1 1.2 1.3 3.4 4.5 4.6, term 4, commit 6, and read "22 Maple Dr". C had 4.5 and 4.6 on disk at 3,005.8 and applied 4.6 then.

3 vs 4 vs 5 replicas

Even counts buy nothing: 4 tolerates one failure, like 3, at more cost. Five tolerates two, which matters most during maintenance, when one node is already down on purpose; the message queue loop (step R1.8) weighs exactly this. That is drill 11's second question: 3 nodes are cheaper and a commit waits for one follower, but one planned restart plus one failure stops writes.

When a database fails over

Database failover is the same election, run by a manager instead of by the replicas themselves:

1. Detect that the primary is gone (health checks, a consensus-backed manager, or the managed service).
2. Fence the old primary before promoting: stop it, revoke its access, or raise an epoch its writes must carry (page 03). Skipping this is how split brain happens.
3. Choose the most caught-up replica: the one with the highest stored position.
4. Promote it, and repoint the writer endpoint.
5. Bring the old primary back as a replica only after throwing away its unreplicated tail. PostgreSQL's pg_rewind does this: it synchronizes a data directory with another copy "after the clusters' timelines have diverged", which is the old-primary case.
6. Asynchronous replication loses the tail between the last shipped position and the crash (Formula 1).

Kafka's unclean leader election is the version of "promote a replica that lacks committed entries". Kafka's leader must normally come from the in-sync replicas (those caught up within replica.lag.time.max.ms). If every in-sync replica is lost, unclean.leader.election.enable=true lets an out-of-sync one lead, and the messages it never received are gone even though producers were told they were acknowledged. Apache Kafka's own default is false, but MSK's default configuration sets it to true for clusters without tiered storage (false with tiered storage). Set it to false for data you promised to keep, and accept that the partition is unavailable until an in-sync replica returns.

Failover between Regions (detection, routing, RPO and RTO decisions) is the Multi-Region Failover loop primitive's subject (coming).

---

Part 8. Catching up: log or snapshot

At 9,000 ms B comes back from a host failure. It needs entry 7 next, but the leader deleted entries 1 to 10 hours ago (in toy time, 3 seconds ago) to keep its log short. The leader can't send what it no longer has. This Part is how a follower catches up, and what the catching up costs everyone else.

Trace: B returns to a compacted log

Synthesizing vector architecture diagram...

What to notice: the log is always the first choice, because it sends only what is missing. A snapshot is the fallback when the log no longer reaches back far enough, and it is only useful if the log continues exactly where it ends.

Snapshot S6 (t = 9,803.0):

Log or snapshot

• Catch-up by log: the leader finds the last entry the follower has that matches its own (the backtracking of event 14, one step back per refusal or straight to the follower's hint) and sends everything after it. Cheap: it sends only the missing entries.
• Catch-up by snapshot: when the entries the follower needs have been compacted away, the leader sends a copy of its state at some position s, and then the log from s + 1. Expensive: the whole state, however little was missing.

The validity rule: a copy seeded from a snapshot at position s may follow the stream only if the stream still has everything from s + 1 onward (its first entry is at or before s + 1). Physical replication engines enforce it: a Raft leader sends a snapshot automatically when it lacks the entries, and a PostgreSQL standby that asks for WAL the primary has already removed gets an error ("requested WAL segment … has already been removed") instead of silently skipping it. The silent version of this gap, a change-stream consumer or a hand-built tool that starts from a snapshot and a later stream position, is the Change Streams & the Transactional Outbox loop primitive's Part 7.

Throttle every bulk transfer that shares a leader's disk and network with live replication: PostgreSQL's pg_basebackup --max-rate ("useful to limit the impact of pg_basebackup on the server"), Cassandra's stream_throughput_outbound (Cassandra's own configuration notes that streaming "can lead to saturating the network connection and degrading rpc performance"), and whatever your Raft library offers for snapshot sends.

The other side of the choice: a leader could keep its log longer so that followers always catch up by log. But the log's retention is pinned by its slowest reader, follower, backup shipper or change-stream consumer alike, and a reader that never returns fills the disk (the WAL page's Part 8). Engines bound it (a snapshot threshold, a slot size cap) and fall back to snapshots.

New members join the same way, and they should not vote until they have caught up: a node that counts toward the majority but has an empty log makes every commit wait for it or for someone else. etcd can add new members as learners (non-voting) for this reason. How membership changes themselves stay safe is beyond this page.

---

Part 9. Repair, deletes and what replication can't protect

Back in the leaderless replay, at q1,400: Alice's account was erased an hour ago (in toy time, 1.2 seconds ago), and her address "7 Birch Ave" is back on every copy. Nobody wrote it. A repair process copied it from a replica that had missed the delete. This Part covers how copies are repaired, why deletes need special care, and the failures that replication copies instead of preventing.

Trace: Alice's erased address comes back (Q7)

From the reference implementation, continuing the leaderless replay (all three copies hold q4 after Q6):

Read repair and anti-entropy

Read repair is what Q2 showed: a read that asks R ≥ 2 copies compares their versions, returns the newest, and writes it back to any copy it asked that was behind. Stores often ask one copy for the full value and the others only for a digest (a hash), which saves cross-AZ bytes; only a mismatch triggers full reads. Read repair only fixes keys somebody reads, and in Cassandra it is best-effort.

Anti-entropy repairs everything else. Each replica builds a Merkle tree: hashes of key ranges, then hashes of those hashes, up to one root. Two replicas compare roots; if they match, the ranges are identical and nothing moves. If they differ, they compare children and descend only where hashes differ, then copy just those ranges.

Synthesizing vector architecture diagram...

What to notice: the roots differ, but "Replica A" and "Replica B" agree on the right half (8e5e), so it is skipped; on the left half only the range "a to c" differs, and it is the only one copied. The labels show the first characters of each hash from the reference implementation's run with the 1,000 q-ms grace.

Both kinds of repair use the same cross-AZ links and replica disks as foreground traffic: building trees costs reads, and a large difference means a large transfer. Schedule and throttle them like snapshot transfers (Part 8).

A delete is a versioned write

A missing value looks exactly like a write that never arrived. So a delete can't simply remove the key: it writes a tombstone with a version, and repair treats it like any other newer version. The tombstone must stay until every copy has it. In a leaderless store, that means longer than any replica can be away, plus one full repair cycle. Cassandra calls this grace period gc_grace_seconds, 864,000 s (10 days) by default, and its documentation ties it to hints and repair: hints older than the grace period are not replayed, and hints for a down node are collected only for max_hint_window (3 hours by default). The key-value store loop (step 2.6) has the same rule: run a full repair on every replica more often than the grace period, or deleted data comes back.

A single-leader log avoids this particular trap: the delete is an entry in the log, and a returning follower must replay the log or install a snapshot taken after it (Part 8).

Which copy may a repair read?

A repair or compare job must read the leader, or a copy whose applied position is at or past the delete. Event 27 on the main line shows the window: at 10,000 ms a report blocks C's apply until 10,300 ms, and DELETE addr:alice (entry 15) commits at 10,001.4 on {A, B}. A applies it at 10,001.4, B at 10,010.2, but C still returns "22 Maple Dr" until 10,300.0. A job that reads C during that window and "fixes" another system from it brings the address back. The Change Streams & the Transactional Outbox loop primitive (Part 8, its event 28) shows exactly that job, and the tombstone that saves its consumers.

Snapshot S8 (t = 10,100): A and B have applied the delete (no addr:alice); C has stored entry 15 but applied only 14, and still reads "22 Maple Dr".

Backups remember

Replication applies the delete everywhere within milliseconds. Backups do not:

So an erasure promise ("we delete your data within 30 days") must name every one of those windows, or encrypt each user's data with a per-user key and delete the key (crypto-shredding), which makes every remaining copy unreadable at once. The YouTube loop (step 3.4) and the Google Drive loop (step R3.11) make the same point.

One bad update everywhere

Event 29, from the reference implementation: at 12,000.0 a buggy migration sets every address to "" in one transaction (entry 16). It commits at 12,001.4; A applies it at 12,001.4, B and C at 12,010.2. Every copy agrees on the wrong value within about 10 ms. Replication did its job perfectly: it copied the mistake as fast as it copies any write.

The recovery needs a copy from before the mistake: a point-in-time restore to t = 11,999 into a new cluster, then copying the correct values back (in real life, hours later); or a delayed replica that applies the log a fixed time behind (MySQL's SOURCE_DELAY: a transaction is "not executed until at least N seconds later than its commit"; PostgreSQL's recovery_min_apply_delay), which can be stopped before it applies the bad entry.

The two edges of backups meet here: the backup that saves you from event 29 is the same one that keeps Alice's erased address. Retention has to be long enough to recover from mistakes and short enough (or encrypted per user) to honour deletion.

---

Part 10. Choosing

Designs often pick a replication family by database brand: "we use Cassandra, so we're highly available", or "global tables, so every Region can write". The real choice is who may write a key and what an OK must survive. This Part puts the families and the modes side by side on equal terms.

The same write, three families

The v2 write, "9 Elm St", with the tiny example's timings (the client's own hop to the leader or coordinator not counted):

Families at equal durability

Comparing "async multi-leader" with "sync single-leader" compares durability levels, not families. So each family gets an asynchronous row and a synchronous or quorum row:

The bytes are the same. Replication sends every write to N − 1 other copies in every family and every mode; a synchronous mode waits for those bytes, it doesn't send more of them. The hook's 20 MB/s of cross-AZ traffic and its $1,036.80 a month are the same whether the two replicas are synchronous or not. The families differ only at the edges: the client's hop to the leader or coordinator (a cross-AZ hop for clients in other AZs), and reads with R > 1, which fetch from several copies (digest reads shrink that).

Sync, semi-sync and async on equal terms

Conflicts when many can write

With more than one writer, two writes to the same key can both succeed, and something must decide:

Two more traps with asynchronous multi-leader, both from the loops' fact-checks: a condition is checked only against the local copy (DynamoDB: "Conditional writes evaluate the condition expression against the version of the item in the Region"), so two Regions can both pass the same check; and a transaction is atomic only where it ran (DynamoDB: "only atomic within the Region where the operation was invoked"), so another Region can briefly see part of it.

Alice in two Regions

The two-Region replay forks from the state after event 8. addr:alice is an item in a DynamoDB global table in the default mode (multi-Region eventual consistency, MREC), with replicas in Regions R1 and R2; both hold "9 Elm St" at version 8. Each device writes with an optimistic check, "only if the version is still 8". We assume a replication delay of 800 ms (AWS: "typically within a second or less"). From the reference implementation:

Both conditional writes succeeded, both clients were told OK, and the laptop's address vanished without an error. Under multi-Region strong consistency (MRSC) (with a third Region or a witness), the laptop's write is replicated to at least one other Region before it returns, and "Conditional writes always evaluate the condition expression against the latest version of an item": the phone's check at g300 sees version 9 and fails, so the phone re-reads and the user decides. (A write to an item that is still being modified in another Region fails with ReplicatedWriteConflictException, which can be retried.)

For what happens when a whole Region fails (detection, routing, RPO and RTO), see the Multi-Region Failover loop primitive (coming); drill 05, "The Booking That Existed in Frankfurt but Not in Virginia", belongs to that page and is further reading after the replay above.

---

Part 11. On AWS

Every AWS database uses replication; what differs is where it says OK, what a read can see, and what a failover can lose. Stated only from AWS's public documentation and papers.

Managed services that use it

Running it yourself

Look-alikes that are not this mechanism

---

Part 12. What you've learned

Back to the 500 lost orders and the stale checkout

Our orders database had two asynchronous replicas 100 ms behind: 500 acknowledged orders at risk in any failover, and checkout pages reading old addresses. Here is how the pieces fix each, and what they cost:

• The 500 orders. Asynchronous replication says OK before any other copy has the write (Part 2). A quorum (commit on 2 of 3) plus an election rule that only lets an up-to-date copy win (Part 6) means no acknowledged write is lost to one failure: in our trace, A died with v3 half-sent, and C, the copy that had it, won. The cost: 1.4 ms per commit instead of 1.0 in a Raft-style log, or 2.4 ms in PostgreSQL, which ships after its local flush; and writes stop if two of three copies are gone. The cross-AZ bytes, 20 MB/s and about $1,037 a month on EC2, were being paid already.
• The stale checkout. C had v2 on disk 4.4 ms after the commit but didn't apply it for 298.6 ms (Part 3, snapshot S1). A position token in the write's OK, checked by the router, sent the read to B, which had applied it (Part 4). Sticky routing would only have made it consistently wrong.
• Around those two: W + R > N gives overlap, not linearizability, and a sloppy quorum loses even that (Part 5, S7); a partitioned leader can append but never commit, and its entries are deleted when it rejoins (Part 7, S4 and S5); a late follower catches up from the log or a throttled snapshot (Part 8, S6); repair must read a copy past the delete, tombstones must outlive any absence, and backups keep what replication erased (Part 9, S8); and last-writer-wins across Regions silently drops one of two acknowledged writes (Part 10).

The whole story, event by event

Main line (t in ms), from the reference implementation:

Leaderless replay (q ms): Q1 write q3 with C's copy lost, OK at q1.4 · Q2 R = 1 on C stale; R = 2 returns q3 and repairs C · Q3 C down at q15 · Q4 strict write fails, sloppy write OK at q21.2 via stand-in D · Q5 R = 2 on B and C returns q3 · Q6 hints delivered at q100 · Q7 tombstone q5 at q206.0, hint lost at q300, tombstones purged at about q1,201 and q1,206, Merkle repair at q1,400 copies q4 back (with a 2,000 q-ms grace, the tombstone wins).

Two-Region replay (g ms): G1 R1 writes "5 Ash Ct" if version 8 · G2 R2 writes "7 Birch Ave" if version 8 at g300 · G3 by g1,100 both Regions hold "7 Birch Ave"; the laptop's OK'd write is gone.

The cheat card

Failure checklist

• Does every OK mean what the product promises: which copies, synchronous or not, and what happens when followers are down?
• Is a semi-sync fallback to asynchronous alarmed?
• Are cancelled or timed-out commits treated as unknown outcomes, with idempotent retries?
• Are shipping lag and apply lag both measured, plus a heartbeat row that catches a replica that stopped receiving?
• Does every read that must see the user's own write carry a position, and does every decision read the leader?
• Is there a cache in front of replicas that skips the position check (including DAX with global tables)?
• Are quorums strict where the design relies on overlap, and is W + R > N counted over home replicas?
• Does failover fence the old primary before promoting, and pick the most caught-up copy?
• Is an unclean election the Kafka version of promoting a replica that lacks committed entries? Yes: set unclean.leader.election.enable=false for data you promised to keep (MSK defaults it to true without tiered storage).
• Are snapshot, rebuild and repair transfers throttled below the leader's spare network and disk?
• Is the tombstone grace period longer than any replica's possible absence plus one repair cycle, and do repairs read a copy past the delete?
• Do backups and PITR windows match both the recovery need and the deletion promise?

Think-first drills

Interview questions

Where to go next

• Write-Ahead Log, fsync & Group Commit: what one replica's "on disk" means, the acknowledgement table and the write half of the layer trace (Part 10).
• Leases, Fencing Tokens & Distributed Locks: fencing whatever an old leader touched outside the log, clock margins for leases, and lock services under failure (Part 8).
• Idempotency & Effectively-Once Processing: retries for writes whose outcome is unknown.
• Change Streams & the Transactional Outbox: lagging consumers, snapshot-plus-stream bootstraps and repair sources (Parts 7 and 8).
• The Sharding, Hot Keys & Rebalancing and Multi-Region Failover loop primitives (coming): replication within one shard is this page; Region-level detection, routing, RPO and RTO are that one.
• Primitive #09: Consensus, Raft and Paxos, for background, and Primitive #21: Isolation levels, for what session guarantees are not.
• Drill: The Network Partition That Elected Two Leaders, answered in Part 7.
• Loops: the key-value store (steps 1.6, 2.1 to 2.6, R3.8), the message queue (steps 1.3, R1.8, R1.11, R2.7), the digital wallet (steps R2.3, 2.4, 3.4), payments (steps R2.5, 3.5), the stock exchange matching engine (steps 1.4, 2.3, 2.4), the URL shortener (steps 3.1, 3.2), the news feed (steps R1.9, 3.1, 3.2), the paging library (steps R2.3, R2.8) and the Netflix case study (steps 1.3, R1.9, 3.4).