Protect acknowledged durable commits under a declared network/region failure model, with explicit latency and minority unavailability. This is not a promise to survive loss of all durable copies.
Student edition · start with the guarantee
Preserve acknowledged critical commits under network partitions while separating ordering, durability, and availability.
Correctness contract: RPO=0 applies to acknowledged durable commits within the declared fault budget and safe recovery protocol. Minority operations requiring current authority are unavailable; unrelated mergeable data can use weaker semantics.
Basic HTTP, databases, and programming are assumed. Specialized terms are explained below. Named products motivate the problem; this is an educational design, not a claim about their current internals. Capacity numbers are illustrative decimal payload estimates, not benchmarks. Add indexes, protocol overhead, replicas, headroom, and failure capacity before provisioning.
Some data is unforgiving. A payment, a ledger entry, an order confirmation: once you tell a client “done,” that fact must survive anything short of the whole planet going dark — including the moment a fiber cut or a switch failure splits your cluster into two halves that can no longer talk to each other. That moment, the network partition, is where casual designs quietly lose writes or, worse, let two halves diverge into histories that can never be reconciled. This guide is about the layer that prevents both outcomes: how the CAP theorem forces a real choice the instant a partition happens, how consensus and quorums decide what “committed” means, how synchronous replication buys a zero recovery-point objective at a latency cost, and how fencing and epochs stop a split brain. Its companion, Multi-Datacenter Routing & Failover, covers the routing and RPO/RTO operational side — getting users to a healthy region and evacuating a dead one; this page is the consistency and consensus layer underneath it.
Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.
CAP and consistency models
During a network partition, a distributed service cannot offer both linearizable operations and successful completion of every eligible request at nonfailed nodes. CAP consistency is linearizability; it is not durability or 'no bytes lost'.
Example. A minority that cannot contact the authority blocks or rejects a linearizable read/write. A mergeable append log can accept local writes on both sides and preserve both records, while not giving one-copy ordering.
Limit. Causal/session/eventual guarantees are not a universal availability ladder. Sticky routing alone fails after failover unless the new replica has satisfied the client's dependencies.
Quorum
A set of replicas whose responses are sufficient for an operation. In a fixed set of N replicas, read size R and write size W overlap whenever R+W>N. A majority is one particular quorum, not the definition of every quorum.
Example. With N=3, writes to {A,B} and reads from {B,C} share B. If the write completed durably and replicas preserve a comparable version, B carries that version forward.
Limit. Overlap alone does not provide linearizability: concurrent or failed writes, sloppy replica sets, and version selection matter. Consensus adds protocol rules to preserve decisions.
Raft terms and commit rules
Raft elects at most one leader per logical term and replicates an ordered log. To advance commit by counting replicas, the leader requires a majority storing an entry from its current term; earlier entries then commit as part of that prefix.
Example. A new leader commits a current-term no-op before relying on old-term prefix entries. Log up-to-date voting and matching rules preserve committed history.
Limit. Terms are not fixed time intervals. Old leaders from earlier terms can remain unaware. Durable term/vote state, membership rules, read barriers, and client-request dedup are required.
Write-ahead log and fsync
A WAL records updates before data pages are considered committed. Recovery replays it after a crash. fsync (or an equivalent storage contract) requests that buffered bytes reach durable storage rather than only process/OS memory.
Example. A server acknowledges after its WAL commit and required replica writes are durably accepted. A process crash can then reconstruct the committed update.
Limit. Appending to a file alone does not guarantee power-loss durability. Device behavior, filesystem ordering, replicas, corruption, and the declared fault budget still matter.
Linearizability
Each completed operation appears to occur at one instant between its invocation and response, respecting real-time order. A read that begins after a write finishes cannot return a value older than that write, unless a later write superseded it.
Example. A write x=7 returns success; a later read must return 7 or a value from a later ordered write. A read overlapping that write may return the old or new value.
Limit. Not the same as durability or transaction serializability. A leader may be stale; linearizable leader reads need current authority and an applied-state barrier.
Failure domains and redundant capacity
A failure domain is a set of components vulnerable to one shared event: process, host, rack, zone, or region. Redundancy must separate domains and leave enough surviving capacity to carry peak demand.
Example. Five replicas placed 2/2/1 across three regions leave at least three after any one region fails. A 3/1/1 layout can lose its quorum with the largest region.
Limit. Independent-failure probability formulas are illustrative assumptions. Shared code/config, dependencies, routing, and control planes can fail all replicas together. N+1 machines does not imply tolerance of a whole zone.
Fencing tokens
A strictly increasing grant number attached to operations. The protected resource atomically compares it with its durable highest accepted token and rejects older operations, making superseded clients unable to overwrite newer effects.
Example. A has token 33 and pauses. B acquires 34 and writes. When A sends token 33 later, the resource rejects it because its fence is already 34.
Limit. A new grant must be installed at the resource before it promises exclusion there. Token 33 can still pass until 34 is observed. Equal-token operations also need sequence/idempotency rules if they can arrive out of order.
Intuition first
A bank has branches in three cities, joined by phone lines. A deposit counts only after at least two cities have written it in their ledgers. If one city's phone line is cut, that city can still read its ledger. It cannot record new deposits, because it cannot reach a second city. Customers there wait, but no deposit is ever lost or recorded twice.
1. Requirements & Scope
The problem is to preserve every acknowledged durable commit under a specified failure budget, such as any single-region loss with non-Byzantine nodes and surviving durable copies. No finite system promises survival of arbitrary loss of all copies. A write may commit even when its ACK is lost; client retries must use operation identity to resolve that uncertainty.
Specify protected operations, failure domains, accepted latency, and unavailable behavior. Critical balance/inventory mutations need their business invariants plus storage ordering; append-only mergeable events may retain bytes with weaker consistency. State RPO=0 as a target tied to the actual acknowledgement/recovery model.
2. What “Zero Data Loss” Means
The phrase sounds absolute, but it hides a precise distinction that separates a senior answer from a hand-wave: the difference between a write that is acknowledged and a write that is committed. Zero data loss is a promise about committed writes only, and the whole design is an effort to make those two words mean the same thing.
Received. A node has the write in memory but has not made it durable or agreed on it. It can vanish on a crash.
Committed. A quorum of nodes has durably stored the write and agreed on its position in the log. It will survive the loss of a minority of nodes.
Acknowledged. The client has been told “done.” The cardinal rule is: never acknowledge before committed. If you ack on receipt and the node dies before the write replicates, you have lost data the client believes is safe — the exact failure “zero data loss” forbids.
So RPO = 0 is achievable only if acknowledgement strictly follows durable, replicated commit. The numbers below frame the cost of holding that line across regions.
Quantity
Assumption
Result
Cross-region round trip
3,000 mi = 4,828 km; light in fiber ≈ 200,000 km/s (⅔ c) gives a 48 ms RTT floor; real routes are longer
~60–80 ms RTT
Sync commit penalty
every write waits one quorum RTT
+~70 ms per write, on the hot path
Local fsync
flush WAL to durable media
~0.1–10 ms depending on device (NVMe with power-loss protection is near the low end)
Quorum for N = 5
majority ≥ 3 must ack
survives loss of 2 nodes with RPO 0
Async alternative
ack locally, replicate later
fast, but RPO = replication lag > 0
Target
tier-1 critical data
RPO = 0 (sync/quorum) · some write unavailability tolerated
The load-bearing number is the ~70 ms cross-region RTT. Zero data loss means paying it on the write path; every design choice below is really a decision about where to pay it, or whether the data is critical enough to pay it at all.
3. CP vs AP: The Partition Choice
CAP says a partitioned service cannot provide both linearizable operations and successful completion of every eligible request at nonfailed nodes. It does not say CP automatically means durable or AP necessarily drops bytes. A locally available replicated log can preserve concurrent events while lacking one-copy ordering.
For critical shared invariants, use a safe authority and refuse/defer operations that cannot contact it. For mergeable data, accept under a documented weaker ordering/merge contract. Eventual convergence and causal/session guarantees are different dimensions, not a universal 'correctness versus loss' slider. Outside partitions, stronger coordination still has a latency cost.
4. The Consistency Models Ladder
Consistency models are not one total ladder. Linearizability respects real-time operation order; sequential consistency preserves an agreed order and each process's program order but not necessarily wall time. Causal consistency respects dependencies; session guarantees include read-your-writes and monotonic reads. Availability depends on operations, dependencies, and client movement.
Sticky sessions alone do not prove read-your-writes after failover: the selected replica must have incorporated the client's write/dependency token or wait/catch up. Linearizability can be composed over single-object operations; transaction serializability provides an equivalent serial transaction order, while strict serializability also respects real time. Durability is separate.
A linearizable read through a leader needs current authority plus an applied-state barrier. A stale leader flag is insufficient; use the implementation's ReadIndex/quorum or correctly bounded lease protocol.
5. Consensus & the Replicated Log
A replicated consensus log orders committed commands under durable election/log rules. Majority overlap is one ingredient, not the whole protocol. In Raft, terms are logical integers, not bounded time intervals; leaders of old terms may remain unaware while a newer-term leader exists.
To advance commit by replica counting, the leader needs a durable majority storing an entry from its current term. Earlier entries commit as its prefix. Safe voting/log matching preserve already committed entries. For leaderless storage, R+W>N proves fixed-set overlap but not automatically linearizability; partial/concurrent writes and sloppy sets matter.
Linearizable reads need current authority and applied committed state. Client IDs/operation dedup live in the replicated state machine so a committed command with a lost ACK is not applied twice. The downloaded finite quorum model illustrates set arithmetic only; use a reviewed consensus implementation for production.
6. Synchronous Replication & Durability
A durable commit needs storage and protocol guarantees: WAL/persistent vote-log state, fsync or an equivalent durable-write contract, and a valid commit rule. Memory or OS-cache receipt is not enough for the declared power-loss model. Durable placement determines which node/region losses can be survived.
Cross-region acknowledgement costs communication latency when the selected commit set must include a remote region. A majority concentrated in one region need not include a remote copy. Quorum size alone does not universally rank durability: placement, acknowledgement storage semantics, correlation, and safe recovery matter. State the fault budget and never claim RPO=0 under loss of all durable copies.
7. Placing Replicas So Every Majority Spans Regions
A quorum only protects you from losing a region if every possible majority includes at least two regions. Otherwise a write can commit inside one region and die with it. Compare three ways to place N = 5 replicas (a majority is 3):
Layout
Majorities inside one region
Survivors if the worst region is lost
Verdict
3 in A, 2 in B
1 of 10 (the three A nodes)
2 (lose A) → no quorum
Bad: can lose acked writes and stall
3 in A, 1 in B, 1 in C
1 of 10
2 (lose A) → no quorum
Bad for the same reason
2 in A, 2 in B, 1 in C
0 of 10
3 or more → quorum survives
Good: every commit is in ≥ 2 regions
2-2-1 placement. The leader L needs 2 more acks. The fastest pair is A2 (local) plus the nearest of B or C, so a commit costs one RTT to the nearest other region.
This is why clusters that must survive a region loss use at least three regions. With only two regions, one of them always holds a majority. Losing that region loses the quorum, and possibly acked writes too.
8. Fencing, Epochs & Split-Brain
Old leaders may remain alive and unaware. Consensus followers reject stale terms and cannot commit conflicting history without protocol quorums; external resources need their own atomic installed epoch/fence check. A token only fences older holders once recognized at that resource, unless current authority is checked on every effect.
Persist highest token with the effect atomically; check-then-apply races. Same-token operations require suitable ordering/idempotency. Revoking a lease or changing DNS does not physically stop a paused holder. Scope safety to recognized grants and the actual activation boundary.
9. Degraded Mode & Disaster Recovery
A partition is not a clean win/lose; it is a state you operate in, sometimes for minutes. The design must define exactly how each side behaves while split, and how the system heals afterward.
Reject writes (CP, the default for critical data). The minority side returns a clear, retryable error — “no quorum, try later” — rather than accepting a write it cannot safely commit. Reads may still be served from the last known state if slightly stale reads are acceptable, or refused if they must be linearizable. The majority side keeps serving normally.
Accept and reconcile (AP, only for tolerant data). Both sides accept writes and merge later using conflict-free replicated data types (CRDTs), last-writer-wins with care, or application-level merge. This keeps everyone available but must be reserved for data where a merged or dropped update is acceptable — never for a ledger.
Healing. When the partition clears, the minority catches up by replaying the log entries it missed from the majority. Because committed history never forked (log matching), catch-up is a replay, not a merge — that is the payoff of having chosen CP.
Disaster recovery. Beyond partitions, plan for losing a whole region permanently: keep the quorum spread across enough independent failure domains that a majority survives any single region loss, take periodic backups and ship the WAL off-site for the truly catastrophic case, and — critically — rehearse. A recovery path exercised only during a real outage does not work. The operational mechanics of evacuating and repointing traffic live in the routing & failover guide.
10. Worked Trace: A Partition Minute by Minute
Setup: the 2-2-1 cluster above, leader L in region A, election timeout 1–2 s (cross-region). At t=0 region A loses contact with B and C.
Time
Region A (2 nodes, minority)
Regions B + C (3 nodes, majority)
t=0
L keeps taking writes. It can reach only A2, so nothing commits. Clients wait.
Heartbeats stop arriving.
t≈1.4 s
Client requests time out with "not committed". Nothing was acked, so nothing is lost.
B1's timer fires. It starts term 8 and gets votes from B2 and C1. B1 is leader.
t≈2 s
L has not heard from a majority for a full timeout. It steps down (CheckQuorum) and rejects writes.
B1 commits a no-op, then serves writes. Commits cost one B–C RTT.
t=5 min
Reads: refused if they must be linearizable. Stale reads only if the product allows them.
Normal service for clients that can reach B or C.
Heal
L and A2 see term 8, become followers, drop their uncommitted entries, and replay the log from B1.
Leader B1 carries on. Leadership can move back to A later if you want.
The client's side
A timed-out write is unknown, not failed. It may or may not have committed. Clients must retry with an idempotency key, so a retry of a write that did commit is not applied twice.
11. Bottlenecks & Tradeoffs
The tensions here are fundamental — they come from the network and from CAP/PACELC, not from any particular implementation.
Durability vs latency. RPO = 0 requires a synchronous quorum commit, taxing every write with a cross-region RTT and an fsync. Async removes the tax but reopens a data-loss window. This is the central trade; it can be placed, not eliminated.
Consistency vs availability. Under a partition, CP refuses minority writes to stay correct; AP accepts them to stay up and pays in divergence. Choose per data type — money is CP, a counter can be AP — rather than picking one globally.
Quorum size vs fault tolerance. A larger N tolerates more failures but makes every quorum slower and needs more independent regions; a small N is fast but fragile. Odd N (3, 5) avoids ties and gives a clean majority.
Write throughput vs single leader. Routing all writes through one leader gives a clean order but makes the leader a bottleneck. Sharding the keyspace into many independent Raft groups (one leader each) restores horizontal write scale while keeping per-shard consistency.
Safety vs failover speed. Aggressive election lowers downtime but risks flapping on a transient blip; conservative election is safe but slower. Quorum detection plus a brief confirmation window balances the two — and fencing makes even a wrong guess non-catastrophic.
12. Summary
Guaranteeing zero data loss across a partition is one idea applied relentlessly: never call a write safe until a durable quorum agrees, and never let more than one authority exist. Everything else is placing the cost of that promise.
Concern
Mechanism
What does “zero data loss” mean?
Acknowledge only after a durable, replicated commit — RPO = 0.
What does a partition force?
CAP: choose CP (reject minority writes) for critical data; AP only where divergence is tolerable.
How do nodes agree on one history?
Consensus (Raft/Paxos): single leader per term, replicated log, majority commit.
How is a read guaranteed fresh?
Read through the consensus leader (ReadIndex or lease). In quorum stores, W + R > N gives overlap, but you still need versions and care with partial writes.
How is a write made durable?
WAL + fsync on a quorum before acknowledging — committed survives region loss.
How is split brain prevented?
Quorum election (one leader) plus fencing tokens / monotonic epochs rejecting stale writers.
How does the system heal?
Minority replays missed log entries after the partition clears — a replay, not a merge.
What does it cost?
A cross-region round trip and an fsync on every critical write — scope it to data that needs it.
The recurring theme: you cannot beat physics or CAP, so you place their cost deliberately. Make “acknowledged” equal “committed by a durable quorum,” choose CP for the data that must not lose or diverge, and prevent split brain with quorum plus fencing rather than trusting silence — then prove it in disaster drills before a real partition proves it for you.
Worked example: five replicas across three regions
Compare majority size three in layouts 3/1/1 and 2/2/1.
Read top to bottom. The table below explains the state and guarantee at each step.
Step
State, calculation, and reasoning
1. Commit in layout 3/1/1
Three local A copies can acknowledge without a remote durable copy. Loss of region A leaves two survivors and can lose that acknowledged data.
2. Commit in layout 2/2/1
Every three-node quorum spans at least two regions. Losing any one region leaves at least three nodes, so quorum recovery remains possible under the declared single-region fault.
3. Recover committed history
Survivors follow consensus log/election rules, not arbitrary newest-timestamp selection. A new Raft leader commits current-term history before relying on its inherited prefix.
4. Handle the minority
It rejects/blocks linearizable writes and freshness-critical reads. Stale read-only data can be served only with an explicit weaker contract.
Check your understanding: Does AP necessarily mean losing bytes?
No. AP logs/CRDTs can preserve and merge concurrent records while lacking linearizable ordering or particular business invariants. CAP consistency is not durability.
Run a small, testable model
Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:
python3 concepts.py quorum
python3 concepts.py test
The model exhaustively enumerates majority placements and survivor quorums; it does not implement consensus.
The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.
"Can you have zero loss and stay available?" Not for writes on the minority side. Say CP, and say who waits.
"What does a write cost?" One RTT to the nearest other region plus an fsync. Give the number: about 60–80 ms coast to coast.
"How many regions?" At least three, placed 2-2-1 or 1-1-1, so no region holds a majority.
"What about reads?" Leader reads with ReadIndex or a lease. Follower reads are stale unless they wait for the commit index.
"What does the client do on timeout?" Retry with an idempotency key, because the result is unknown.
14. Common Mistakes
"W + R > N means linearizable." It means overlap. You still need versions, and partial or sloppy writes break it.
Two regions for region-loss safety. One region always holds a majority. Use three.
Acking before fsync. A power cut then loses an "acknowledged" write.
Treating a timeout as a failure. The write may have committed. Retry safely with idempotency keys.
Mixing up serializable and linearizable. One is about transactions, the other about recency.
15. Check Yourself
Five replicas are placed 3 in region A and 2 in region B. Region A burns down. What happens?
Answer
Only 2 of 5 remain, which is not a majority, so no writes are possible. Worse, a write committed on the three A nodes alone may never have reached B. That acked write is gone.
Why does a 2-2-1 layout survive any single region loss?
Answer
No region holds 3 nodes, so every majority spans at least 2 regions and every commit has a copy outside any one region. Losing the largest region leaves 3 nodes, still a majority.
What is the minimum RTT between two cities 3,000 miles apart over fiber?
Answer
3,000 mi is 4,828 km. At about 200,000 km/s that is 24.1 ms one way, so 48.3 ms round trip. Real routes add distance and hops, giving about 60–80 ms.
With highest-version selection, a read reaching the partial write may return new, while a later nonoverlapping read can return old. A real-time new-then-old sequence without an intervening write violates linearizability; arbitrary two-read disagreement alone needs ordering/context to establish that violation.
Linearizability is violated if a read starts after a completed write and returns the prior value. Weaker models are not necessarily violated: causal/session dependencies and previous reads must be specified. If B has no dependency on A and no prior newer read, this stale read may fit those weaker contracts.
During a partition, a client's write to the minority side times out. What should the client do?
Answer
Treat the result as unknown and retry, ideally against the majority side, with the same idempotency key. The server then applies it at most once even if the first try committed.
16. Key Terms
RPO / RTO
Data you may lose / time you may be down.
Linearizable
Each completed operation appears to occur at one instant between its invocation and response, respecting real-time order. A read that begins after a write finishes cannot return a value older than that write, unless a later write superseded it. Example and limits above.
Serializable
Transactions equal some serial order.
Quorum
A set of replicas whose responses are sufficient for an operation. In a fixed set of N replicas, read size R and write size W overlap whenever R+W>N. A majority is one particular quorum, not the definition of every quorum. Example and limits above.
Sloppy quorum
Stand-in nodes accept writes during failures.
Fencing token
A strictly increasing grant number attached to operations. The protected resource atomically compares it with its durable highest accepted token and rejects older operations, making superseded clients unable to overwrite newer effects. Example and limits above.
Idempotency key
A client-chosen ID so retries apply once.
CheckQuorum
A leader steps down if it cannot reach a majority.
17. Further Reading
Martin Kleppmann, Designing Data-Intensive Applications, ch. 5 (quorums and their limits) and ch. 9 (linearizability, consensus).
Seth Gilbert and Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", 2002 (the CAP proof).
Daniel Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design", IEEE Computer, 2012 (PACELC).
Maurice Herlihy and Jeannette Wing, "Linearizability: A Correctness Condition for Concurrent Objects", ACM TOPLAS, 1990.
Corbett et al., "Spanner: Google's Globally-Distributed Database", OSDI 2012.
Kyle Kingsbury's Jepsen analyses and the consistency models map at jepsen.io.