Concept 8: Distributed Consensus & Replication

System Design Bible — File 08 of 10 Difficulty: ★★★★★ Prerequisites: Files 04, 06, 07, plus the failure-model fundamentals in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

This is the hardest file in the bible because it confronts the fundamental difficulty of distributed systems head-on. Four ideas make it tractable.

0.1Why we keep copies at all (redundancy for reliability)#

A single copy of data on a single machine is a guarantee of eventual loss: disks die, machines catch fire, data centers lose power. At the scale of thousands of servers, something is always broken — hardware failure isn't an exceptional event, it's a constant background rate (File 09 §1.2). So to not lose data and to stay available when a machine dies, you must keep redundant copies on multiple machines: if one holds the data and dies, another still has it. This is replication — the same data, copied to several nodes. It buys you two things: durability (the data survives failures) and availability (you can still serve it from a surviving copy). Everything in this file flows from this necessity. But — and this is the whole drama — the moment you have more than one copy, you have the problem of keeping the copies in agreement, which turns out to be shockingly hard. Hold this: redundancy is mandatory for reliability, and redundancy is what creates the agreement problem.

0.2The network is unreliable (the fallacy that breaks everything)#

Here is the fact that makes distributed systems fundamentally different from single-machine programming: the network between machines is unreliable and you cannot fix it. Messages between nodes can be delayed (arrive seconds late), dropped (never arrive), duplicated, or reordered. Worse — and this is the crux — a node cannot tell the difference between "the other node crashed" and "the other node is fine but the network between us is slow or broken." From node A's perspective, "B hasn't replied in 5 seconds" could mean B is dead, or B is alive and working but the reply is stuck in the network, or B got the message but its reply was dropped. You genuinely cannot distinguish these. This single ambiguity is the source of nearly every hard problem in this file — split-brain, the CAP theorem, the impossibility results. New distributed-systems engineers assume the network is reliable (one of the famous "fallacies of distributed computing"); shedding that assumption is the mental leap this file requires. Fix it firmly: you can never be sure whether a silent node is dead or just unreachable.

0.3What "state" and "consistency" mean here#

State is data that persists and can change — a bank balance, an inventory count, who the current leader is. A stateless service (File 01's app tier) holds none, so its copies are trivially interchangeable. A stateful system (a database) holds the authoritative data, and when you replicate it, each copy has its own version of the state — which can drift apart if updates reach the copies in different orders or some updates get lost. Consistency (in this file's sense) is the question: do all the copies show the same, up-to-date value, and does the system behave as if there were just one copy? Strong consistency means every read sees the latest write (the system looks like a single machine even though it's many). Eventual consistency means the copies might temporarily disagree but will converge to the same value if updates stop. This is a different "consistency" from the C in database ACID (File 11) — a notorious source of confusion; here it's specifically about replicas agreeing. Getting the copies to agree, reliably, over the unreliable network of §0.2, despite the crashes of §0.1 — that agreement problem is consensus, the subject of this file.

0.4What a majority (quorum) buys you — the one trick to hold onto#

Before the details, plant one seed that recurs everywhere: the magic of a majority. If you have N nodes and you require that any decision be agreed by more than half of them (a majority, ⌊N/2⌋+1), then a beautiful property holds: any two majorities of the same set must overlap in at least one node (you can't have two different groups each containing more than half — they'd have to share a member). That overlap is the linchpin of correctness: it means a later majority always contains at least one node that participated in the earlier majority, so information can't be "lost" between decisions, and — crucially — you can never have two separate majorities acting independently (which would be the "split-brain" disaster of two leaders). Every quorum system and every consensus algorithm in this file (Raft, Paxos, W/R quorums) is ultimately exploiting this one fact. You don't need the details yet — just carry the intuition: majorities always overlap, and that overlap is what keeps a distributed system honest.

0.5What "state" actually is, and why copying it is the hard part#

Everything in this file is about copying state, so it is worth being brutally precise about what that word means, because the word is used loosely everywhere and the looseness hides the whole difficulty.

State is the set of facts a system remembers between requests. Concretely, on a database server, state is: the bytes of every row in every table as they currently sit on disk and in memory; the indexes that point at those rows; the transaction log; the list of currently-open transactions and the locks they hold; the sequence counters; the on-disk metadata that says which file holds which table. It is everything that would make the answer to the same question different tomorrow than it is today. If you shut the machine down and start it again, the state is what must come back.

Why is state the hard part? Contrast it with a stateless service — File 01's application tier. A stateless web server remembers nothing between requests: you send it GET /price?sku=42, it computes an answer (probably by asking a database), returns it, and forgets you exist. Two stateless servers are therefore interchangeable: it does not matter which one your request lands on, because neither one holds anything the other lacks. That interchangeability is exactly what makes a load balancer (File 01) work, what makes autoscaling work, and what makes "just add another box" a valid answer. You can add a hundred stateless servers in a minute and remove ninety of them a minute later and nothing is lost, because there was nothing there to lose.

Now put state on those boxes and every one of those properties evaporates:

Mutable versus immutable state — why one is easy and one is hard. If state never changed after being written — if every fact were written once and never updated — replication would be nearly trivial: copy the bytes anywhere, as many times as you like, and every copy is correct forever, because there is no such thing as a "newer" version to be out of date with. This is exactly why content-addressed, immutable systems are easy to replicate: a CDN cache entry (File 05), an object in S3 that is only ever replaced wholesale, a Git commit, a Kafka log segment (File 07). It is mutation — the fact that the value of key balance:alice was 100 and is now 40 — that creates the concept of "stale," and staleness is the enemy this entire file fights. Hold this framing, because it explains a design pattern you will see repeatedly: systems make replication tractable by turning mutable state into an append-only immutable log of changes, and then replicating the log instead of the state. That is the single most important structural idea in this file.

Hold this: state is what the system remembers; it has mass, it changes while you copy it, and mutation is what makes copies capable of being wrong.

0.6The Fallacies of Distributed Computing — each one unpacked#

In the mid-1990s, engineers at Sun Microsystems (L. Peter Deutsch and later James Gosling) collected a list of assumptions that programmers coming from single-machine development reliably make and that are reliably false the moment their program spans two machines. They are called the Eight Fallacies of Distributed Computing. Most treatments list them and move on, which teaches nothing. Each one has a specific physical cause and a specific consequence for replication, so take them one at a time.

Fallacy 1 — "The network is reliable." The assumption is that if you send a message, it arrives. It is false at every layer. A packet can be dropped because a switch's output queue was full (a buffer overrun — switches have finite memory and when more traffic arrives for a port than the port can drain, the excess is discarded, silently, by design). A cable can be unplugged by a technician working on the next rack. A NIC can fail into a state where it transmits but does not receive. A firewall rule can be pushed that blocks one port between two subnets. Cloud providers do maintenance on their network fabric continuously. TCP hides some of this by retransmitting, but TCP retransmission has a limit; when it gives up, your connection dies with an error, and there is no layer below you that can fix it. Consequence for replication: a leader's "here is the new write" message to a follower may simply never arrive, and the leader will not automatically know.

Fallacy 2 — "Latency is zero." The assumption is that calling a function on another machine costs about what calling a local function costs. A local function call is on the order of 1 nanosecond. A round trip to a machine in the same rack is roughly 0.1–0.5 milliseconds — a hundred thousand times more. A round trip between two availability zones in the same cloud region is roughly 0.5–2 milliseconds. A round trip from Virginia to Frankfurt is roughly 90 milliseconds, and from Virginia to Sydney roughly 200 milliseconds. Those last numbers are not engineering sloppiness you can optimize away; they are set by the speed of light in fibre, which is about 200,000 km/s (light in glass travels at roughly two-thirds its vacuum speed). Virginia to Frankfurt is about 6,500 km of great-circle distance and considerably more of actual fibre, so ~65 ms is the floor one way and you cannot beat it with a faster CPU or a bigger budget. Consequence for replication: a synchronous replica in another continent adds a full round trip — 90 ms or more — to every single write, which is the entire argument of §5.

Fallacy 3 — "Bandwidth is infinite." The assumption is that you can send as much data as you like. A 10 Gbps NIC moves at most about 1.25 GB per second, and cross-region links are metered and expensive (AWS inter-region data transfer is billed per gigabyte; at roughly $0.02/GB, replicating 10 TB per day across regions is about $200 per day, or $73,000 per year, in transfer fees alone). Consequence for replication: the replication stream competes for bandwidth with the live traffic, and a replica that has fallen far behind and is trying to catch up can saturate the link and slow down the very leader it is trying to follow — a feedback loop that turns a small lag into an unbounded one.

Fallacy 4 — "The network is secure." The assumption is that anything on your network is trustworthy. Traffic between datacenters crosses infrastructure you do not own; traffic inside a cloud VPC crosses a shared physical fabric. Consequence for replication: replication streams carry your entire database in plaintext unless you configure TLS on them, which is why PostgreSQL's sslmode=require on the replication connection and MySQL's MASTER_SSL=1 exist and why a replica in another region without them is a data-exfiltration channel.

Fallacy 5 — "Topology doesn't change." The assumption is that the set of machines and the paths between them are fixed. In reality nodes are added and removed continuously (autoscaling, rolling upgrades, spot instance reclamation), IP addresses are reassigned, DNS records change, and cloud providers migrate your VM to different physical hardware without telling you. Consequence for replication: a replica's identity cannot be "the machine at 10.0.1.7" — it must be a logical identity tracked in a membership list, and changing that membership list safely is itself a consensus problem (this is the membership-change hazard in §19.2 and Raft's joint consensus, deferred to File 18).

Fallacy 6 — "There is one administrator." The assumption is that one person or team understands and controls the whole system. In reality your database team, your network team, your security team, and your cloud provider each change things independently. Consequence for replication: the classic outage where the security team tightens a firewall rule at 02:00, the replication link dies, nobody notices because the leader keeps serving happily, and the divergence is discovered days later at failover time. This is why lag monitoring with alerting (§14.4) is not optional garnish; it is the only thing that catches this class of failure.

Fallacy 7 — "Transport cost is zero." The assumption is that moving data between machines is free in CPU as well as in money. It is not: every replicated write costs serialization (turning in-memory structures into bytes), system calls, TCP processing, and on the receiving side deserialization and disk I/O. Consequence for replication: a replication factor of 3 does not merely triple your storage bill — it also multiplies your write-path CPU and IOPS, which is why "just add more replicas" has a real ceiling.

Fallacy 8 — "The network is homogeneous." The assumption is that all links behave alike. In reality an intra-rack link, a cross-AZ link, a cross-region link, and a VPN tunnel to an on-prem datacenter have wildly different latency, loss, and MTU characteristics. Consequence for replication: a quorum (§0.4) that spans three AZs behaves completely differently from one that spans three regions, and a replica group with one member on a slow link will have its tail latency set by that member — which is precisely why quorum systems ack on the fastest majority rather than waiting for everybody.

Hold this: every one of the eight is a specific physical or organizational fact, not a pessimistic mood, and each one maps to a concrete replication design decision later in this file.

0.7Failure detection — the impossibility that motivates everything else#

This is the single most important prerequisite in the file. Read it twice.

The problem, stated exactly. Node A wants to know whether node B is alive. A's only instrument is messages: A can send something to B and see whether a reply comes back. Suppose A sends a message and 5 seconds pass with no reply. What can A conclude?

Here are the possible worlds, all consistent with A's observation:

A cannot distinguish these. Not "it is hard to distinguish"; not "we lack a good library for it." It is information-theoretically impossible in an asynchronous network, because "no message has arrived yet" is exactly the same observation in all five worlds and no additional observation A can make will separate them. The only thing that could separate them is a bound on message delay — knowing "if B were alive, the reply would have arrived within T" — and an asynchronous network offers no such bound. This is precisely the ingredient the FLP impossibility result (§1.3) turns into a theorem.

Therefore every failure detector in every distributed system in the world is a guess. Not a measurement. A guess, implemented as a timeout, and it will be wrong in both directions.

**Sub-Concept: The timeout dilemma (why there is no correct value for T).** Every failure detector reduces to: "declare B dead if no response within T." The choice of T is a pure trade-off with no optimum, and it is worth working through with real numbers because the shape of this trade-off recurs in every failover configuration you will ever tune.

**Set T too short — say 500 ms. You detect genuine crashes fast: a leader that dies is replaced in well under a second, so the write outage is short. But now consider a perfectly healthy leader that experiences a 700 ms garbage-collection pause (entirely ordinary for a JVM-based system with a multi-gigabyte heap, and not rare — a full GC on a 32 GB heap can exceed a second). Its followers see no heartbeat for 700 ms, exceed the 500 ms timeout, declare it dead, and hold an election. This is a false positive: a healthy leader was deposed for no reason. The cost is not merely the wasted election — it is that (a) the cluster is unavailable for writes during the election, (b) any writes the old leader accepted but had not yet replicated may be lost when the new leader takes over (§11.5), and (c) the old leader, when its GC pause ends, still believes it is the leader and may try to accept more writes — which is exactly how split brain** (§11.3) starts. Worse still, false positives cluster: whatever caused the pause (load spike, GC, disk stall) tends to hit several nodes at once, so you get repeated spurious failovers, a pathology called flapping or an election storm (§19.2).

**Set T too long — say 30 seconds. False positives essentially vanish; almost nothing pauses for 30 seconds. But now a leader whose power supply genuinely fails at 12:00:00 is not replaced until 12:00:30, and for those 30 full seconds every write in the system fails. If you are processing 5,000 writes per second, that is 150,000 failed requests** from one machine dying. You have traded a small chance of unnecessary disruption for a guaranteed 30-second outage on every real failure.

**There is no value of T that avoids both.** You are choosing your poison: unnecessary failovers or slow recovery. Real systems pick a T in the 5–15 second range for database failover (PostgreSQL/Patroni defaults are around a 10-second loop with a 30-second leader lease; MongoDB's electionTimeoutMillis defaults to 10,000 ms; etcd's election timeout defaults to 1,000 ms because it is a small, low-latency, in-datacenter cluster with tiny state and a cheap election) and then spend real engineering effort on making the consequences of a false positive survivable rather than on making false positives impossible — because they cannot be made impossible. That reframing is the mark of a senior answer: you do not solve failure detection, you bound the damage of getting it wrong, which is what fencing tokens (§11.4) exist for.

The refinement everyone should know: the phi-accrual failure detector. Rather than a binary alive/dead verdict from a fixed threshold, Cassandra and Akka use a detector (from Hayashibara et al., 2004) that maintains a sliding window of recent inter-arrival times of heartbeats from each peer, fits a distribution to them, and outputs a continuous suspicion level φ = −log₁₀(probability that a heartbeat this late would occur if the node were healthy). φ = 1 means roughly a 10% chance this is normal jitter; φ = 8 means roughly a 10⁻⁸ chance. The application then picks its own threshold (Cassandra's phi_convict_threshold defaults to 8). The win is adaptivity: a peer across a noisy WAN link whose heartbeats normally vary by ±200 ms is automatically given a looser effective timeout than a peer in the same rack whose heartbeats arrive like a metronome, without any human tuning either one. The limit: it still cannot distinguish the five worlds above — it just makes a better-calibrated guess.

Sub-Concept: Heartbeats — the mechanism, and what they actually prove. A heartbeat is a small message sent on a fixed interval whose only purpose is to say "I am still here." In Raft the leader sends an empty AppendEntries RPC roughly every 50 ms; in MongoDB replica-set members ping each other every 2 seconds; in Cassandra a gossip round runs every second. The receiver keeps, per peer, a timestamp of the last heartbeat received, and a background task compares now − last_heartbeat against the timeout T.

The direction matters and is usually taught wrong. There are two arrangements. In push heartbeating the monitored node sends to the monitors ("I'm alive"); in pull heartbeating the monitor polls the monitored node ("are you alive?"). Push scales better (one message per node per interval instead of N×N polls) and is what leader-based systems use, because the leader must send heartbeats anyway to assert leadership. Pull gives the monitor control over timing and lets it distinguish "you didn't send" from "I didn't ask."

What a received heartbeat proves, precisely: that at the moment the heartbeat was generated, that process was running enough to generate it, and that a path existed from it to you. That is all. It does not prove the node is currently alive (it may have died 1 ms after sending), it does not prove the node is useful (a database process can heartbeat happily while its disk is read-only and every query fails — this is the difference between liveness and readiness, File 01 §6.2), and it does not prove the node is not also talking to someone else who thinks it is the leader.

The tuning relationship you must know: the heartbeat interval and the timeout are not independent. If heartbeats go every H ms and you time out at T ms, you tolerate ⌊T/H⌋ − 1 consecutive lost heartbeats before a false positive. Practitioners keep T at roughly 5–10× H — Raft's canonical guidance is broadcastTime ≪ electionTimeout ≪ MTBF, e.g. 0.5 ms broadcast, 150–300 ms election timeout, months of MTBF. Set T = 2H and a single dropped UDP heartbeat triggers a failover; set T = 100H and you have simply chosen a very long T.

The failure mode to name in an interview: heartbeats travel on a different path from real work. A node whose heartbeat thread has priority and whose worker threads are starved will heartbeat perfectly while serving nothing — the zombie node. The fix is to make the health signal do real work: check that a trivial query actually executes and returns, not merely that a TCP connection can be opened.

Sub-Concept: Leases — a timeout you can actually reason about, and the clock assumption it smuggles in. A lease is a time-limited grant of a right. "You are the leader until 12:00:10" rather than "you are the leader until I say otherwise." The mechanism: the grantor (a quorum of peers, or a coordination service like etcd) records that node A holds the lease with an expiry time; A must renew it before expiry by contacting the grantor again; if A fails to renew, the lease lapses at its expiry and a new holder may be granted one.

What this buys you that a plain heartbeat does not. With plain heartbeats, when the followers stop hearing from the leader they know only that they cannot hear it — the leader might be happily serving clients on the other side of a partition. With a lease, the leader itself is bound: a correct leader must stop acting as leader when its own clock says the lease has expired, whether or not it can talk to anyone. That converts a one-sided guess into a two-sided contract, and it is the difference between "we hope there is one leader" and "there is at most one leader, provided the clock assumption holds." Because of this, a lease-holding leader can safely serve linearizable reads locally without a quorum round trip — it knows nobody else can be leader while its lease is valid — which is a huge performance win (it is exactly what CockroachDB's leaseholder and etcd's leader read lease do, §17.4).

The clock assumption, stated exactly — this is the part people miss. A lease's safety does not depend on clocks being synchronized to a common absolute time; it depends on bounded clock drift rate. If the grantor says "10 seconds from now" and both parties measure 10 seconds using their own hardware, safety requires that the leader's 10 seconds is not longer in real time than the grantor's 10 seconds by more than the safety margin. A quartz crystal typically drifts on the order of tens of parts per million (say 50 ppm, or about 4 seconds per day), which over a 10-second lease is 0.5 ms — comfortably safe. But drift rate is not the real hazard; process pauses are. If the leader is descheduled for 40 seconds (a long GC, a VM live-migration, a hypervisor stall, or someone suspending the process with SIGSTOP), it wakes up believing its lease is still valid when it expired 30 seconds ago and has already been granted to someone else. Nothing in the lease protocol prevents this, which is why leases are always paired with fencing tokens (§11.4): the lease makes two leaders unlikely, and the fencing token makes the second leader's writes harmless when it happens anyway.

Implementation names you should recognize. etcd exposes leases as first-class objects: LeaseGrant(TTL) returns a lease ID, LeaseKeepAlive renews it on a stream, and any key attached to the lease with Put(key, val, lease=id) is automatically deleted when the lease expires — which is how you build a self-cleaning distributed lock or service registry. ZooKeeper achieves the same with ephemeral znodes: a node in the tree that exists only while the creating session's heartbeats continue, and vanishes automatically when the session times out (tickTime × syncLimit, typically 2 s × 5 = 10 s). Consul calls them sessions with a TTL. In every case the same trade lives underneath: shorter TTL means faster detection of a dead holder but more renewal traffic and more risk that a healthy holder is evicted by a hiccup.

Hold this: you can never know whether a silent node is dead, slow, or unreachable; every failure detector is a timeout, every timeout is a guess, and good design is about bounding the damage of a wrong guess rather than eliminating wrong guesses.

0.8Durability, the page cache, and fsync — why an acknowledged write can still vanish#

Replication exists to protect data. But before you can reason about copies of data being safe, you must know what "this write is safe" means on a single machine, because the answer is far weaker than most engineers assume and the gap is where a large fraction of real data-loss incidents live.

The layers a write passes through. When your application executes INSERT INTO orders … and the database returns success, the bytes have travelled through a stack of buffers, and each layer can lose them independently:

 1. Application buffer      (your process's memory)          lost if: process crashes
 2. OS page cache           (kernel memory, "dirty pages")   lost if: OS/kernel panics or power fails
 3. Disk write cache        (RAM on the drive itself)        lost if: power fails (unless battery/capacitor-backed)
 4. Persistent medium       (NAND flash cells / magnetic platter)   survives everything short of hardware death

The page cache. When a process calls write(fd, buf, n), the kernel copies those n bytes into its own memory — the page cache — marks those pages dirty (meaning "the in-memory version is newer than the on-disk version"), and returns success immediately, typically in a few microseconds. Nothing has touched the disk. The kernel will flush dirty pages to the device later, on its own schedule, governed on Linux by knobs like vm.dirty_expire_centisecs (default 3000, i.e. dirty pages older than 30 seconds become eligible for writeback), vm.dirty_background_ratio (default 10, i.e. background flushing starts when dirty pages exceed 10% of available memory), and vm.dirty_ratio (default 20, at which point writing processes are blocked and forced to flush synchronously). This design is not a bug — it is what makes filesystems fast, because it batches many small writes into few large sequential ones and lets the kernel reorder them for the disk's benefit. But it means **a successful write() guarantees nothing about durability.** If the power fails 100 ms later, those bytes were never on the disk and are simply gone.

**fsync — the barrier that actually means something.** fsync(fd) tells the kernel: do not return until every dirty page belonging to this file has been handed to the storage device and the device has confirmed it is on stable media. This is the system call that converts "the OS has my data" into "the hardware has my data." It is expensive precisely because it is real work: on a spinning disk it costs a seek plus a rotation, on the order of 5–10 ms; on a consumer SSD roughly 0.1–1 ms; on an enterprise NVMe SSD with power-loss protection roughly 20–100 µs. That range spans three orders of magnitude and it is why "how often do you fsync" is the single biggest lever on a database's write throughput. A system that fsyncs once per transaction on a spinning disk is capped at roughly 100–200 transactions per second per disk, no matter how many CPUs you have — this is exactly the physical wall that group commit (batching many transactions into one fsync) was invented to work around.

The disk write cache — the layer that lies. Drives contain their own volatile RAM buffer and, by default, report a write as complete when it lands in that buffer, not when it reaches the flash or the platter. So even fsync can be defeated: the kernel asks the drive to flush, the drive says "done," and the data is still in volatile RAM. This is why the kernel issues an explicit FLUSH CACHE / Force Unit Access command as part of fsync on drives that honour it, why enterprise SSDs advertise PLP (Power Loss Protection) — on-board capacitors holding enough charge to drain the buffer to flash after a power cut — and why RAID controllers ship with BBU (Battery-Backed Write Cache). Consumer SSDs frequently do not have PLP; this is the concrete, mechanical reason "don't run your production database on consumer SSDs" is not snobbery. You can inspect and control this on Linux with hdparm -W (query/set the drive write cache) and observe the cost with fio --fsync=1.

Now the punchline that connects to the rest of the file. Put those three facts together and you get the reason replication exists even on a single well-configured machine's behalf:

Hold this: **write() means "the kernel has it," fsync() means "the device says it has it," and neither means "this data will survive the machine" — only replication means that.**

0.9The Write-Ahead Log (WAL) — the structure everything in this file is built on#

Almost every replication mechanism in this file works by shipping a log. So you cannot understand replication until you understand what that log is, and it is not the text file in /var/log.

The plain definition. A write-ahead log is an **append-only file of records describing every change to the database, written and made durable before the corresponding change is applied to the actual data pages. "Write-ahead" is literal: the log entry goes to stable storage ahead of the data. Other names for the same idea: PostgreSQL calls it the WAL; MySQL/InnoDB calls it the redo log** (files named ib_logfile0, ib_logfile1); Oracle calls it the redo log; SQLite has a WAL mode; MongoDB's WiredTiger calls it the journal; and the general database-theory name is ARIES-style logging (from the 1992 IBM paper that defined the canonical algorithm).

Why it exists — the problem it solves. Consider a database updating a row. The row lives inside an 8 KB page (PostgreSQL's page size; InnoDB uses 16 KB) somewhere in a multi-gigabyte data file. Updating it in place means: read the page into memory, modify the bytes, write the page back. Now ask what happens if the power fails during that write-back. Two disasters are possible:

Now note why you cannot fix this by just being careful about the order of the data writes: the pages are scattered, so making the update durable means many random writes, each costing a seek (5–10 ms on a spinning disk), and you cannot make several random writes atomic with respect to a power cut.

The insight. Do not try to make the data-page updates atomic. Instead, first write a compact, sequential, append-only record of your intent to a single file, force it to stable storage with one fsync (§0.8), and only then — lazily, in the background, whenever convenient — update the actual data pages. The log write is sequential, which is the fastest thing a storage device does (a spinning disk that manages 150 random IOPS can stream 150 MB/s sequentially — three orders of magnitude more useful work per second). If you crash, you have a complete, ordered record of everything that was supposed to happen, and you can make it happen again. You have converted many random durable writes into one sequential durable write plus deferred cleanup. That is the whole trick, and it is why every serious storage engine on earth has a WAL.

What is actually in a WAL record. Physically the WAL is a series of variable-length records, each with a header and a payload. The header carries: a LSN (Log Sequence Number) — a monotonically increasing identifier for the record's position in the log, which in PostgreSQL is literally the byte offset in the logical WAL stream, printed as 0/16B3B80; the transaction ID (XID) the record belongs to; the record length; the resource manager ID (which subsystem — heap, btree, transaction commit — should interpret the payload); a CRC checksum over the record so a partially-written tail record can be detected and discarded on recovery; and the previous record's LSN, chaining the log backwards. The payload carries the change itself, in one of two forms:

Most real engines use a physiological hybrid: physical at the page level, logical within the page ("insert this tuple into this page" rather than "write these exact bytes"), which keeps replay cheap while surviving small layout differences.

Why append-only, specifically. Three independent reasons, and it is worth being able to state all three:

The two rules that make it correct. ARIES states them as:

Recovery, step by step, with concrete values. The database keeps a checkpoint — a periodically written marker saying "as of LSN 0/16A0000, every data page change up to that point has been flushed to the data files." On restart after a crash:

What breaks. If the WAL disk fills, the database stops accepting writes — this is not a bug, it is the only safe response, and it is why an abandoned PostgreSQL replication slot (§17.2) that pins WAL forever is a genuine production-outage generator. If fsync is disabled (fsync = off in PostgreSQL, innodb_flush_log_at_trx_commit = 0 in MySQL) the log write is not durable and a crash loses committed transactions — these settings exist for bulk-load scenarios and are catastrophic in production. If checkpoints are too infrequent, recovery must replay a huge amount of log and startup takes many minutes; if they are too frequent, you pay constant random page-flush I/O. That is the checkpoint tuning trade-off (checkpoint_timeout, default 5 min in PostgreSQL; max_wal_size, default 1 GB).

The tie-back — and it is the most important sentence in Section 0. A WAL is already an ordered, append-only, self-describing stream of every change the database has ever made. A replica that starts from a copy of the data files as of LSN X and then receives and applies every WAL record after X will arrive at exactly the same state as the leader. Replication, in almost every production database on earth, is therefore not a special subsystem at all — it is the crash-recovery log, redirected over a TCP socket to another machine instead of only to the local disk. Everything in §6 is a variation on how you encode and ship that stream.

Hold this: the WAL turns "keep two machines identical" into "send one machine's ordered change log to another and replay it," and that reduction is what makes replication implementable at all.

1Architectural Definition & "The Why"#

1.1The Plain Definitions#

Put simply: replication gives you copies; consensus makes the copies agree. Without consensus, replicas drift and you get conflicting answers.

1.2"The Why" — Reliability Requires Redundancy, Redundancy Creates Disagreement#

Every prior file pushed us toward many nodes: load-balanced app servers, cache clusters, shards, ring members, Kafka brokers. The moment your data lives on more than one machine, two brutal truths appear:

So you need redundancy for reliability — but redundancy means coordinating copies over an unreliable network, which is hard: how do 5 replicas agree on "the balance is $100, and this withdrawal happened before that one" when they can't perfectly communicate and any of them might crash mid-decision? That is the consensus problem, and it's the theoretical heart of distributed systems.

1.3What This Solves — and the Impossibility That Frames It#

Consensus underpins nearly everything reliable: leader election (Files 07/10), distributed locks, atomic commits, configuration/membership (ZooKeeper/etcd), replicated state machines (databases), and ordering. But it's bounded by hard impossibility results:

Sub-Concept: FLP Impossibility. The FLP result (Fischer–Lynch–Paterson, 1985) proves that in a fully asynchronous network (no bound on message delay), no deterministic consensus algorithm can guarantee it always terminates if even one node can crash — because you can never distinguish a crashed node from an infinitely slow one. Real systems dodge FLP by using timeouts / partial synchrony (assume the network is usually timely) and randomization/leaders — they sacrifice guaranteed termination in pathological cases to get practical progress almost always. This is why consensus algorithms use election timeouts and can briefly stall during instability.

1.4Why You Replicate — Three Distinct Reasons That Pull in Different Directions#

"Why replicate?" sounds like it has one answer. It has three, they are genuinely different goals, and — this is the part interviewers probe — the design that best serves one of them is often actively bad for the others. If you cannot say which of the three you are optimizing for, you cannot justify any of your other choices, because every knob in this file (how many replicas, where they sit, synchronous or not, leader or leaderless) resolves differently depending on the answer.

Reason 1 — Durability and fault tolerance: "do not lose the data, and keep serving when a machine dies."

This is the reason of §0.1. A single disk has an annualized failure rate around 1–2%; a fleet of 10,000 disks therefore loses on the order of 100–200 disks a year, roughly one every two days, as a matter of routine. A single machine is also subject to correlated failures that no amount of local redundancy fixes: the power distribution unit for its rack, the top-of-rack switch, a bad kernel upgrade, a fire suppression discharge. So you keep the data on at least two, conventionally three, physically independent machines — and independent is load-bearing. Three replicas in one rack survive a disk failure but not a rack failure. Three replicas in three availability zones (§2.3) survive a datacenter failure. Three replicas in three regions survive a regional disaster but pay §0.6 Fallacy 2's speed-of-light tax on every synchronous operation.

What this reason wants from the design: synchronous replication (§5), because a write that only exists on one machine is not actually protected yet; replicas spread as far apart as possible, because correlated failure is the enemy; and a modest number of them — three or five — because durability improves with steeply diminishing returns (going from one copy to two removes almost all of the risk; going from three to four removes very little) while cost scales linearly.

What this reason will cost you: every write must reach multiple machines before it can be acknowledged, so your write latency is set by the slowest replica you insist on waiting for, and the further apart you spread them the worse that gets.

Reason 2 — Read scalability: "we have far more reads than writes, and one machine's CPU/IOPS cannot serve them all."

Most systems are read-dominated, often extremely so — a social feed, a product catalogue, a news site can easily run at 100:1 or 1000:1 read:write. One machine has a fixed budget of CPU cycles, memory bandwidth, disk IOPS, and NIC bandwidth (File 01 §0.6). When reads exhaust it, you can add replicas and fan reads out across them: with a leader and five followers, six machines serve reads instead of one, and — the key point — you have not had to change the data model at all, unlike sharding (File 04), which forces you to choose a partition key and gives up cross-shard transactions and joins. Read replicas are the cheapest scaling move in the book, which is why File 04 §0.6's escalation ladder puts them before sharding.

What this reason wants: many replicas (ten, twenty — as many as the leader can feed); asynchronous replication, so that adding readers does not slow down the writer; and replicas placed near the readers.

What this reason will cost you: those replicas are, by construction, behind the leader (§7), so the reads they serve are stale — and now your application has to cope with a user who updates their profile and then sees the old version, which is §7.2. It also does nothing for write throughput: every replica must apply every write, so the write ceiling of the whole system is still the write ceiling of one machine. That is the wall that forces sharding (File 04), and saying this sentence in an interview — "read replicas scale reads, not writes; the write wall is why you eventually shard" — is one of the highest-signal things you can say.

Reason 3 — Geographic latency: "our users are 15,000 km from our database and physics is charging them 200 ms."

A user in Sydney querying a database in Virginia pays ~200 ms per round trip (§0.6, Fallacy 2), and a page that makes five sequential dependent queries pays a full second before anything renders. No amount of code optimization touches this; it is distance divided by the speed of light in glass. The fix is to put a copy of the data near the user: a replica in ap-southeast-2 turns 200 ms into 2 ms. This is the same argument that produced CDNs (File 05), applied to a mutable database instead of to static assets.

What this reason wants: replicas in many regions; and — the moment users in those regions need to write, not merely read — it wants multi-leader or leaderless topologies (§4.2, §4.3), because forcing a Sydney user's write to travel to a Virginia leader gives back the entire latency win you were chasing.

What this reason will cost you: accepting writes in more than one place is the single most expensive decision in this file. It creates write conflicts (§9) — two regions modifying the same record concurrently, with no global order to break the tie — and conflict resolution is either lossy (last-write-wins silently discards someone's work, §9.1), complicated (version vectors and application-level merge, §9.2/§9.5), or restrictive (CRDTs, §9.4, which only work for data types whose operations commute).

How the three pull against each other — the summary you should be able to draw.

The tension is direct and unavoidable. Durability wants replicas far apart and synchronous — which is the most expensive possible combination for latency (a synchronous Frankfurt replica adds ~90 ms to every Virginia write, §5.2). Read scaling wants asynchrony, which by definition creates the lag that breaks read-your-writes. Geographic latency wants local writes, which destroys the single global order that made everything else simple.

The senior framing: there is no configuration that maximizes all three, so a design conversation must start by ranking them. A payments ledger ranks durability first and accepts the latency (§18.1's Spanner is the extreme version of this choice). A social feed ranks read scalability and geographic latency first and accepts eventual consistency (§18.3's Dynamo-style stores). A collaborative document editor ranks geographic latency first and pays for it with CRDTs (§9.4). Say which of the three you are optimizing before you say which topology you would pick, and the topology choice will then defend itself.

2The Recursive Sub-Concept Tree#

2.1Sub-Concept: Consistency (in the replication sense)#

Consistency here means: do all replicas show the same, up-to-date value, and does the system behave as if there were a single copy? Strong consistency = every read returns the most recent write (the system looks like one machine). Eventual consistency = if writes stop, replicas converge to the same value eventually, but a read might return stale data in the meantime. (Note: this "C" is different from the "C" in ACID transactions — a classic point of confusion.)

2.2Sub-Concept: Availability#

Availability means every request to a non-failed node receives a (non-error, non-timeout) response — the system stays up and answering even when some nodes are down or unreachable. A system can be "up" but return stale data (available but not strongly consistent), or refuse to answer to avoid returning stale data (consistent but not available). That tension is the CAP theorem (Section 3).

2.3Sub-Concept: Partition (Network Partition)#

A network partition is when the network splits so that groups of nodes can't talk to each other, even though each group is alive. Node group A and node group B are both running but can't communicate. Partitions are not optional — over a real network they will happen: a switch fails, a cable is cut, or the link between cloud AZs drops. (An AZ — Availability Zone — is a cloud provider's unit of failure isolation: one or more physically separate datacenters within a region, with independent power, cooling, and networking, connected to sibling AZs by fast links. "Replicate across 3 AZs" means "survive the loss of an entire datacenter" — and the inter-AZ links are exactly where partitions happen.) This is why CAP forces a choice (Section 3).

2.4Sub-Concept: Quorum#

A quorum is a minimum number of nodes that must agree for an operation to be considered successful — typically a majority (⌊N/2⌋ + 1 of N nodes). The magic of majorities: any two majorities of the same set must overlap in at least one node. That overlap guarantees that a later majority "sees" the result of an earlier majority — which is how the system stays consistent without every node participating. Quorums are the mathematical engine behind both leaderless replication (Section 5) and leader-based consensus (Section 6). With N=5, quorum = 3; the system tolerates 2 failures and still has a majority.

2.5Sub-Concept: Split-Brain#

Split-brain is the catastrophic failure where a network partition causes two nodes to both believe they are the leader (or two halves to both accept writes), producing divergent, conflicting state that's hard or impossible to reconcile. Quorums prevent split-brain: if a leader needs a majority to act, then a partition can have at most one side with a majority, so at most one leader can function. The minority side steps down. This is why consensus systems insist on odd N and majority quorums.

2.6Sub-Concept: Replicated State Machine (RSM)#

The core abstraction consensus enables: if every replica starts in the same state and applies the same commands in the same order, they all end in the same state. So the whole problem of "keep replicas identical" reduces to "agree on a single ordered log of commands" — and that's exactly what Raft/Paxos do: they agree on the order of entries in a replicated log (the same log abstraction from Kafka, File 07, now with consensus behind it). Databases are RSMs over their write log.

Determinism — the hidden requirement. The RSM argument has a precondition that is easy to miss and that causes real bugs: the commands must be deterministic. "Apply the same commands in the same order → reach the same state" is only true if applying a command produces the same result on every machine. A command like UPDATE sessions SET last_seen = NOW() is not deterministic: NOW() returns a different value on each replica, so each replica ends in a different state despite having applied "the same command." Neither is INSERT INTO t VALUES (RAND()), nor a command whose effect depends on a trigger, a stored procedure that reads the local clock, or a UUID() call, nor DELETE FROM t LIMIT 10 when t has no deterministic ordering (each replica may delete a different ten rows). This is not an abstract concern — it is precisely the failure mode that makes statement-based replication dangerous (§6.1) and that drove MySQL to make row-based binary logging the default. Remember the precondition as part of the definition: a replicated state machine requires a deterministic state machine.

2.7Sub-Concept: The Replication Position — LSN, GTID, oplog timestamp, and offset#

Every replication system needs an answer to the question "how far along is this replica?" — and the answer must be a value you can compare, store, and hand to a client. That value is the replication position, and each system has its own name and encoding for it. You will meet all of these in vendor documentation and in monitoring dashboards, so learn them properly rather than treating them as opaque strings.

Why it must exist. Three separate jobs require it, and none of them can be done without it. (1) Resumption: when a replica reconnects after a network blip, it must tell the leader "I have everything through here, send me the rest" — otherwise the leader would have to resend everything from the beginning. (2) Lag measurement: "how far behind is this replica?" is literally leader_position − replica_position (§7.4). (3) Consistency tokens: to give a client read-your-writes (§7.2) you hand it the position of its own write and require any replica serving it to have reached at least that position. That third use is why the position must be exposed to applications, not hidden inside the database.

PostgreSQL — the LSN. A LSN (Log Sequence Number) is a 64-bit value that is literally the byte offset of a record within the notional infinite WAL stream (§0.9). It is printed as two 32-bit halves in hexadecimal separated by a slash: 0/16B3B80. The left half is the high 32 bits (the "logical WAL file number" region) and the right half is the low 32 bits (the offset within it). Because it is a byte offset, arithmetic on it is meaningful: pg_wal_lsn_diff('0/16B4000', '0/16B3B80') returns 1,152 bytes, which is exactly how PostgreSQL reports lag in bytes. You obtain positions with pg_current_wal_lsn() on the leader and pg_last_wal_replay_lsn() on a replica; the difference of those two is the replica's byte lag. LSNs are strictly increasing and never reused within a timeline (a timeline is a branch identifier that increments when a replica is promoted, so that WAL written by the new leader can never be confused with WAL written by the old one — this is what prevents a promoted replica's history from silently overwriting the original's).

MySQL — file+position, and then GTIDs. Classic MySQL replication identifies a position as a binary log file name plus a byte offset, e.g. mysql-bin.000042:19384. This works but is brittle in exactly one important way: the coordinates are meaningful only on the machine that produced them. If replica B was following leader A and A dies, B's recorded position mysql-bin.000042:19384 refers to A's binlog files; if you now want B to follow the newly promoted C, you must translate that position into C's coordinate system, and there is no reliable general way to do it. That single problem is why failover in old MySQL topologies was a manual, error-prone ritual.

GTIDs (Global Transaction Identifiers) fix it by naming transactions instead of file positions. A GTID is <source_uuid>:<transaction_number>, e.g. 3E11FA47-71CA-11E1-9E33-C80AA9429562:23, where the UUID identifies the server that originally executed the transaction and the number is a per-server counter. Each server maintains a gtid_executed set — a compact range-encoded set such as 3E11…:1-23, A2B3…:1-7 meaning "I have executed transactions 1 through 23 from server 3E11 and 1 through 7 from server A2B3." Now failover is arithmetic: to attach B to C you simply say CHANGE MASTER TO MASTER_AUTO_POSITION=1, B sends its gtid_executed set, C computes the set difference, and sends exactly the transactions B is missing. The GTID travels with the transaction through every hop of the topology, so it means the same thing everywhere. Enable with gtid_mode=ON and enforce_gtid_consistency=ON. The cost: GTID mode forbids a few operations that cannot be assigned a single GTID cleanly (notably CREATE TABLE … SELECT in older versions, and mixing transactional and non-transactional tables in one transaction), and the executed-set can grow large in a topology with many historical servers.

MongoDB — the oplog entry timestamp. MongoDB's oplog (operations log) is a capped collection named local.oplog.rs, and each entry carries a ts field of BSON type Timestamp, which is a 64-bit value made of a 32-bit Unix seconds count plus a 32-bit per-second ordinal counter, e.g. Timestamp(1721600000, 17) meaning "the 17th operation in that second." Ordering is lexicographic on the pair. MongoDB also exposes an opTime = {ts, t} where t is the election term, so that operations from different leadership epochs can never be confused (the same job PostgreSQL's timeline does). Clients receive these as cluster time and operation time tokens and can pass them back with afterClusterTime in a read concern to demand a replica that has caught up — MongoDB's causal-consistency mechanism (§7.2, §17.3).

Kafka — the offset. In Kafka (File 07) the position is simply an integer offset per partition: the index of a record in that partition's log. Because a Kafka partition is an append-only log with no separate data files, the offset is the whole story. A follower's log_end_offset compared to the leader's is exactly the ISR lag (§17.6).

What breaks. Positions from different lineages are not comparable — comparing a replica's LSN against a leader that has since been through a failover, or comparing GTIDs from a server whose UUID was regenerated because someone copied a data directory (the infamous duplicate server_uuid, which makes two servers claim to have executed the same GTIDs and silently skip real transactions), produces nonsense. Always compare positions within one timeline/term, and never clone a data directory without clearing the server identity file.

Tie-back: every mechanism later in this file — lag monitoring (§7.4), consistency tokens (§7.2), failover replica selection (§11.2), CDC (§6.3) — is manipulating one of these four values. They are the currency of replication.

2.8Sub-Concept: Replication Factor and Replica Placement#

The plain definition. The replication factor (RF), sometimes written N, is the number of copies of each piece of data that the system maintains. RF = 3 means every row/key/partition exists on three distinct nodes.

Why the number 3, specifically. It is not arbitrary and it is not superstition; it falls out of two constraints multiplying together.

First, majority quorums need an odd count (§0.4). With RF = 2, a majority is 2 — meaning you tolerate zero failures while retaining a quorum, which makes RF = 2 strictly worse than useless for consensus purposes: you doubled your storage cost and gained no fault tolerance for coordinated decisions. With RF = 3, a majority is 2, so you tolerate one failure. With RF = 4, a majority is 3, so you still tolerate only one failure — the fourth copy costs 33% more storage and buys nothing in fault tolerance. With RF = 5, a majority is 3, so you tolerate two. Hence the familiar 3 → 5 → 7 progression and the rule "odd numbers only."

Second, the math of independent failures. If a single node has availability 0.99 (roughly 3.5 days of downtime a year) and failures were independent, the probability that all three replicas are simultaneously down is 0.01³ = one in a million; the probability that all two of an RF = 2 set are down is 0.01² = one in ten thousand — a hundred times worse. Going to RF = 4 gets you one in a hundred million, an improvement you almost never need, and the reason you almost never need it is that at that point your failures are no longer independent and the model stops applying: a bad configuration push, a poisoned schema migration, or an operator running DROP TABLE hits all N copies at once regardless of N. This is the mathematical statement of §14.3's rule that replication is not backup.

Placement — the part that actually determines whether RF means anything. Three replicas on three VMs that the cloud scheduler happened to place on the same physical host give you RF = 3 and the fault tolerance of RF = 1. Real systems therefore express placement as a hierarchy of failure domains:

The vocabulary differs by system but the idea does not: Cassandra models this as snitches and rack/datacenter awareness with the NetworkTopologyStrategy replication strategy, where you write {'dc1': 3, 'dc2': 3} to mean "three replicas in each of two datacenters, and place each datacenter's three in three different racks." HDFS calls it rack awareness and hard-codes a specific policy: with RF = 3, put one replica on the writer's local node, the second on a different rack, and the third on that same second rack but a different node — a deliberate compromise that survives a rack loss while only paying one cross-rack network hop instead of two. Kubernetes expresses it as pod anti-affinity and topology spread constraints, with topologyKey: topology.kubernetes.io/zone meaning "spread these pods across zones."

Worked example of why placement dominates. You run RF = 3 in a single AZ. Your annual probability of losing that AZ is, say, 0.1%. Your data-loss probability is therefore at least 0.1% per year no matter how many replicas you add inside that AZ — adding a fourth, fifth, and sixth copy in the same AZ moves the number not at all. Move to one replica in each of three AZs and the data-loss probability becomes the probability that all three AZs fail together, which is orders of magnitude smaller. Three copies badly placed are worth less than two copies well placed. That is the sentence to say in an interview.

What breaks. The classic failure is silent placement collapse: the cluster was correctly spread across three AZs, then over months of node replacements and autoscaling events, two of the three replicas for some partitions drifted into the same AZ, and nobody noticed because the RF is still 3 and every dashboard is green. Detect it by auditing placement, not by trusting RF — nodetool status per datacenter in Cassandra, hdfs fsck -blocks -locations in HDFS, checking the AZ of each member in a MongoDB replica set. The second classic failure is quorum loss from an even split across two AZs: with RF = 4 spread 2+2 across two AZs, losing either AZ leaves exactly 2 of 4 — not a majority — so the cluster becomes unavailable for writes even though half the data is fine. This is why "spread across three AZs" (or 2 AZs plus a tiebreaker/arbiter node in a third) is the standard advice, and it is a genuinely common production mistake.

Tie-back: N in the W + R > N quorum formula (§8.1) and the "majority" in every consensus algorithm are counting nodes, and the whole point of those formulas is fault tolerance — which is only real if the nodes being counted actually fail independently.

2.9Sub-Concept: Replication Lag (the term, precisely)#

Replication lag is the amount by which a replica's applied state trails the leader's. It is the single most important operational metric in this entire file, and it is worth being precise because the word hides three different measurements that behave differently (each is developed fully in §7.4).

Tie-back: every anomaly in §7 is caused by nonzero lag, every mitigation in §7 is a way of tolerating or bounding it, and the amount of data you lose on an asynchronous failover (§11.5) is exactly the lag at the instant the leader died.

2.10Sub-Concept: Fencing Token (Epoch Number) — the general defence against a stale actor#

You will meet this concept in full, with worked traces, in §11.4. It is introduced here because it is referenced earlier than that and because it is the single most reusable idea in distributed systems.

The plain definition. A fencing token is a monotonically increasing number issued alongside a lock or a leadership grant, which the holder must present with every operation and which the resource being protected must remember and enforce: having seen token 34, the resource rejects anything arriving with a token ≤ 34.

Why it exists. §0.7 established that a lease can be believed valid by a paused process after it has actually expired and been reissued. So you must assume that at some moment two processes will both believe they hold the same lock. A fencing token does not prevent that belief — it makes the stale believer's actions ineffective, by giving the storage layer the information it needs to tell the two apart. It converts an unsolvable detection problem into a trivial comparison. Every leadership abstraction in this file has one under a different name: Raft calls it the term, Paxos the ballot or proposal number, ZooKeeper the zxid and the czxid/version on a znode, Kafka the leader epoch, MongoDB the election term t, PostgreSQL the timeline ID, and Chubby simply the sequencer. Recognizing that they are all the same idea, and saying so, is a strong senior signal.

Tie-back: without fencing, a majority quorum only makes split brain unlikely; with fencing, split brain becomes harmless. Full mechanism, worked trace, and the "why the storage layer must participate" argument are in §11.4.

2.11Sub-Concept: Snapshot (Base Backup) and Catch-Up#

The plain definition. A snapshot — PostgreSQL calls it a base backup, MySQL a dump or a physical backup, MongoDB an initial sync, Raft a state-machine snapshot — is a copy of the complete data as of one specific replication position (§2.7). Catch-up is the subsequent process of applying the log records generated after that position until the replica has converged with the leader.

Why both halves are necessary. §0.5 established that state changes while you copy it, so a naive file copy of a live database is a fuzzy, useless smear. The universal fix is the two-phase construction: (1) obtain a copy that is consistent as of position P — which the database can produce cheaply because MVCC (multi-version concurrency control: the storage engine keeps older versions of rows so that a long-running reader can see a stable snapshot of the database while writers continue) lets it serve a frozen view without blocking writers; (2) stream every log record from P onward and apply it. When the second phase's application rate exceeds the leader's generation rate, the replica converges and can switch to live streaming. The whole reason this works is the WAL of §0.9: the log gives you a well-defined position P to anchor the snapshot to, and a complete record of everything after it.

Worked example with real numbers. A 2 TB PostgreSQL database, leader generating 20 MB/s of WAL, being seeded over a 10 Gbps link that you throttle to 300 MB/s to avoid starving live traffic. Phase 1 (pg_basebackup) takes 2,000,000 MB ÷ 300 MB/s ≈ 6,700 seconds ≈ 1 hour 51 minutes. During that time the leader produced 6,700 s × 20 MB/s = 134 GB of WAL, all of which must have been retained (this is what a replication slot or a large wal_keep_size is for, §17.2 — and it is also why an over-long base backup can cause the leader's WAL directory to fill and take the leader down). Phase 2 replays that 134 GB; if the replica can replay at 60 MB/s while the leader keeps producing 20 MB/s, it closes the gap at a net 40 MB/s, so it needs 134,000 MB ÷ 40 MB/s ≈ 3,350 seconds ≈ 56 minutes to catch up. Total: about 2 hours 47 minutes before the new replica is usable. This number is why "just add a replica" is not an incident-response action — it is a plan you execute before you need it.

What breaks. If the replica's replay rate is lower than the leader's generation rate, the gap never closes and the replica is permanently and increasingly behind — the classic cause being single-threaded apply (§7.5) against a multi-threaded writer. If required WAL is discarded before the replica asks for it, the replica fails with "requested WAL segment has already been removed" and must be rebuilt from scratch. Full operational treatment is in §14.1.

Tie-back: every new replica, every rebuilt replica after a failure, and every restore from backup is this same two-phase snapshot-plus-log procedure; it is also exactly how a Raft leader brings a hopelessly-behind follower up to date when the log it would need has already been compacted away (File 18).

3The CAP Theorem (and PACELC)#

3.1CAP Stated Precisely#

CAP theorem (Brewer): a distributed data store can provide at most two of these three during a network partition:

3.2The Correct Interpretation (this is where candidates go wrong)#

**Partitions are not optional — they will happen on any real network. So P is mandatory. CAP is therefore really a binary choice you make only when a partition is occurring: C or A?**

**When there is no partition (the normal case), a well-designed system provides both** C and A. CAP only forces the trade during a partition. Saying "we're a CP system" doesn't mean you're unavailable normally — it means you'd choose consistency if a partition hit.

3.3PACELC — The More Complete Model#

CAP ignores the normal, no-partition case, where there's still a trade-off. PACELC: if Partition, choose A or C; Else (normal operation), choose Latency or Consistency.

PACELC captures the real everyday trade: even with a healthy network, strong consistency costs latency because you must coordinate replicas (wait for a quorum/leader) before answering. This is the deeper insight interviewers reward.

4Replication Models#

There are exactly four topologies worth knowing, and they are distinguished by one question: where are writes allowed to be accepted? Single-leader says "in exactly one place." Multi-leader says "in several places, independently." Leaderless says "anywhere, and we'll use quorums to sort it out." Chain replication says "in exactly one place, but reads come from a different place." Every real system is one of these four or a composition of them, and the entire cost structure of a design follows from the choice. Each gets the full RULE 4 treatment below — mechanism, ASCII diagram, a worked failure trace with named nodes and values, pros, cons, complexity, and when to use it — and §4.5 closes with the comparison table and the decision rule.

4.1Single-Leader (Leader/Follower, a.k.a. Master/Replica, Primary/Secondary)#

Model: One node is the leader; all writes go to it. The leader applies the write and replicates it to followers. Reads can go to the leader (fresh) or followers (scale reads, maybe stale).

4.1.1 The mechanism in full, step by step#

The naming is a minefield, so fix it first: leader = master = primary = source, and follower = replica = secondary = standby = slave. PostgreSQL says primary/standby, MySQL says source/replica (formerly master/slave), MongoDB says primary/secondary, Kafka says leader/follower for each partition. They are the same role. This file uses leader and follower.

Here is what physically happens when a client writes, traced through every component:

                       (all writes)                   (async or sync stream of log records)
     Client ──── W ──────────────►  ┌───────────┐  ──────────────────────►  ┌────────────┐
                                    │  LEADER   │                           │ FOLLOWER 1 │ ── R ──► Client
     Client ──── R (fresh) ───────► │  node-A   │  ──────────────────────►  ├────────────┤
                                    │           │                           │ FOLLOWER 2 │ ── R ──► Client
                                    │  WAL ───► │  ──────────────────────►  ├────────────┤
                                    └───────────┘                           │ FOLLOWER 3 │ ── R ──► Client
                                          │                                 └────────────┘
                                          ▼                                 (reads only; possibly stale)
                                     data files

Why writes must go to only one place — the property this buys. A single leader means every write passes through one serialization point, so there is a single, globally agreed order of all writes, for free, without any coordination protocol at all. Two concurrent writes to the same row are ordered by the leader's lock manager exactly as they would be on a single machine. That is why single-leader replication cannot have write conflicts — not because conflicts are resolved well, but because they are structurally impossible. Everything that makes multi-leader and leaderless hard (§9's entire conflict-resolution apparatus) is the price of giving up this one property. Say that sentence in an interview.

4.1.2 Worked failure trace: the leader dies with un-replicated writes#

Setup: leader node-A, followers node-B and node-C. Asynchronous replication. Leader's WAL position is LSN 0/5000. node-B has replayed to 0/5000; node-C is 400 bytes behind at 0/4E70 because it is on a busier host.

 t=0.000  Client X: UPDATE accounts SET balance=900 WHERE id=1   → node-A
 t=0.002  node-A: writes WAL record at LSN 0/5000..0/50A0, fsyncs, ACKs client X  ("success")
 t=0.003  node-A: begins sending 0/5000..0/50A0 to node-B and node-C
 t=0.003  *** node-A loses power ***  (the packets to B and C were in the NIC queue)
 t=0.004  Client Y: UPDATE accounts SET balance=800 WHERE id=1   → connection refused
 t=10.00  Failover controller's timeout (§0.7) expires; declares node-A dead
 t=10.01  Controller compares candidates:  node-B at 0/5000,  node-C at 0/4E70
 t=10.02  Promotes node-B (furthest ahead). node-B's timeline increments 1 → 2.
 t=10.03  node-C is repointed at node-B and fetches 0/4E70..0/5000
 t=10.5   Writes resume against node-B

What was lost: the write at 0/5000..0/50A0 was acknowledged to client X as successful, and no follower ever received it. It is gone. Client X believes the balance is 900; the system says 800. There is no error anywhere, no alert, no log line — this is a silent lost update, and it is the defining hazard of asynchronous replication (§5.4 traces the money version of it).

**What if node-C had been promoted instead of node-B?** Then everything between 0/4E70 and 0/5000 — potentially many transactions, not just one — would be lost too. This is why every failover controller's first job is to pick the most advanced candidate, and why "how do you choose which replica to promote?" is a standard interview question (§11.2). Note this also implies you must be able to compare candidates, which is exactly what §2.7's positions are for.

And the nastier variant: suppose node-A did not lose power but merely became unreachable (a partition, §2.3), and it kept accepting writes from clients that could still reach it. Now node-A has writes 0/5000 onward, and node-B — promoted — has a different set of writes at the same positions. When the partition heals you have two divergent histories with overlapping positions and no automatic way to merge them. This is split brain, and §11.3 walks it in full.

4.1.3 Pros, cons, complexity, when to use#

Pros — and why each follows from the design:

Cons — and why each follows from the design:

Complexity/cost: one round trip client→leader for a write plus, if synchronous, one leader→follower round trip. Storage cost = N × data. Network cost = (N−1) × write volume leaving the leader. Operationally the expensive part is not steady state — it is the failover machinery (§11) and the monitoring (§14.4).

When to use it — the decisive conditions. Use single-leader by default, and specifically whenever: (a) all your writes can physically fit through one machine, which for a well-tuned PostgreSQL or MySQL instance on modern NVMe hardware is on the order of tens of thousands of writes per second — far more than most companies ever reach; (b) you need real transactions, constraints, or joins; (c) your users are concentrated in one region, or you can tolerate remote users' write latency; (d) your team is not large enough to operate a conflict-resolution strategy. Do not use it when you genuinely need multi-region writes with low latency, or when your write volume exceeds one machine and you cannot shard.

Synchronous vs asynchronous replication (a crucial knob):

4.2Multi-Leader (Master-Master)#

Model: Multiple leaders accept writes (e.g., one per datacenter), replicating to each other.

4.2.1 The mechanism in full#

Each leader behaves exactly like the single leader of §4.1 for its own clients: it accepts writes, orders them locally, writes its WAL, acknowledges. The difference is that it also acts as a follower of every other leader, consuming their replication streams and applying their writes to its own storage. So each node runs two roles simultaneously.

        US-EAST clients            EU-WEST clients            AP-SOUTH clients
              │                          │                          │
              ▼                          ▼                          ▼
       ┌─────────────┐            ┌─────────────┐            ┌─────────────┐
       │  LEADER A   │◄──────────►│  LEADER B   │◄──────────►│  LEADER C   │
       │  (Virginia) │            │ (Frankfurt) │            │  (Mumbai)   │
       └──────┬──────┘            └──────┬──────┘            └──────┬──────┘
              │  ▲                       │                          │  ▲
              │  └───────────────────────┼──────────────────────────┘  │
              └──────────────────────────┼─────────────────────────────┘
                                    (every leader replicates to every other)
              │                          │                          │
        local followers            local followers            local followers

**The replication topology between the leaders is itself a design choice**, and it is a genuine source of production bugs:

How a write is tagged so it doesn't echo. Every replicated write carries the identity of the leader that originated it (MySQL's server_id / GTID source UUID, §2.7). When a leader receives a replicated write, it applies it and forwards it onward, but a leader will not apply a write whose origin is itself. Without this, an all-to-all mesh would loop writes forever.

4.2.2 Worked failure trace: the conflict that single-leader cannot have#

Setup: leaders A (Virginia) and B (Frankfurt), all-to-all, asynchronous inter-leader replication with ~90 ms one-way latency. Row: products(id=7, stock=1) — one unit left.

 t=0.000  User in NY:  UPDATE products SET stock=0 WHERE id=7 AND stock=1   → A
 t=0.001  A: applies. A's copy: stock=0. Acks the NY user: "you bought it."
 t=0.002  A: begins shipping the change to B (arrives ~t=0.092)
 t=0.010  User in Berlin: UPDATE products SET stock=0 WHERE id=7 AND stock=1 → B
 t=0.011  B: applies — because B's copy STILL SAYS stock=1; the check passes.
          B's copy: stock=0. Acks the Berlin user: "you bought it."
 t=0.092  A's change arrives at B.  B now has: local stock=0, incoming stock=0.
 t=0.101  B's change arrives at A.  A now has: local stock=0, incoming stock=0.
 t=~0.1   Both converge to stock=0.  No error is raised anywhere.
          *** You have sold one unit twice. ***

Look at what failed and why. The WHERE stock=1 guard — a compare-and-set, the standard single-machine technique for exactly this problem — did not protect you, because the compare was evaluated against stale local state on B. Conditional updates only work when there is a single authority evaluating the condition. Nor did any conflict-detection scheme help, because the two writes did not even conflict in the last-write-wins sense — both set stock=0, so they agree! Convergence was achieved and correctness was still violated. This is the crucial lesson: conflict resolution restores convergence, not correctness. Two replicas agreeing on a wrong value is still wrong.

A second trace, showing the constraint problem. Two users sign up simultaneously with email='x@y.com' in different regions. Each leader's UNIQUE(email) index accepts its own insert, because neither has seen the other's. When the streams cross, each leader tries to apply a row that violates its own unique constraint. There is no good outcome: the replication stream halts with an error (MySQL's replication simply stops and pages you), or one row is silently discarded, or you end up with duplicate accounts. Uniqueness is a global property and multi-leader has no global authority, so multi-leader databases either forbid unique constraints across leaders, or partition the key space so each key has a home leader, or accept manual repair. This is one of the strongest practical arguments against multi-leader, and naming it is a high-signal interview move.

The pattern that makes multi-leader safe. Both traces have the same shape: two leaders touching the same item. The industrial fix is therefore to make that impossible by construction — partition the data so that each item has exactly one home leader that owns writes for it (users in EU write EU-owned rows; users in US write US-owned rows), and route any cross-ownership write to the owner. You then have, in effect, many single-leader systems sharing a deployment. This is what "multi-region active-active" means in almost every production system that actually works, and it explains the residual latency cost: a European user editing an American-owned record still pays the transatlantic round trip.

4.2.3 Pros, cons, complexity, when to use#

Pros:

Cons:

Complexity/cost: L×(L−1) replication streams in a mesh; cross-region bandwidth billed per GB (§0.6, Fallacy 3); conflict detection metadata (a version vector per key is O(number of leaders) bytes of overhead per value); and the largest cost of all, the application-level engineering to define merge semantics.

When to use it — the decisive conditions. Use multi-leader when and only when: users in multiple geographies must write with local latency and you have verified single-leader's remote-write latency is genuinely unacceptable; or each region must keep accepting writes during a cross-region partition; or your clients are inherently offline-capable (mobile, desktop sync); or your data type is naturally conflict-free (append-only event logs, counters, sets — i.e. CRDT-shaped, §9.4). Do not use it when you have any global uniqueness or balance constraint, when your team cannot articulate a merge rule for every mutable field, or — most commonly — when the real motivation was "high availability," which single-leader-plus-failover gives you far more cheaply.

4.3Leaderless (Dynamo-style)#

Model: No leader — any replica accepts reads and writes; the client (or a coordinator) writes to several replicas and reads from several, using quorums to stay consistent. Uses consistent hashing (File 06) to place replicas.

Sub-Concept: Merkle Tree (how anti-entropy compares replicas cheaply). Two replicas need to answer "which of our millions of keys differ?" without shipping all the data to compare. A Merkle tree is a tree of hashes over the dataset: the leaves are hashes of individual key ranges, and each parent node is the hash of its children, up to a single root hash. To compare, the replicas exchange just the root: if the roots match, the entire datasets are identical — comparison done in one hash. If they differ, descend: compare the children, recurse only into the subtrees whose hashes differ, and you arrive at exactly the divergent key ranges in O(log N) hash exchanges instead of a full scan. Cassandra/Dynamo repair uses precisely this; it's also the integrity backbone of Git and blockchains. Cost: the tree must be built/maintained (repair in Cassandra is a heavyweight scheduled operation), and hash granularity trades precision against tree size.

**Sub-Concept: Version Vector (how you detect conflicts). A timestamp can't safely order writes across nodes (clocks skew). A version vector** attaches to each value a small map of {replica → counter} — e.g., {A:2, B:1} meaning "this value has seen 2 updates via A and 1 via B." On every update, the handling replica increments its own counter. Comparison then reveals causality: if one vector's entries are all ≥ the other's (e.g., {A:3,B:1} vs {A:2,B:1}), the first descends from the second — it's simply newer, keep it. But if each is greater somewhere ({A:3,B:1} vs {A:2,B:2}), neither saw the other: the writes were truly concurrent — a genuine conflict that must be resolved (LWW, CRDT merge, or hand both versions to the app, as Dynamo's shopping cart famously did). The vector's job is exactly this: distinguish "stale copy" (safe to discard) from "concurrent conflict" (must merge) — something wall-clock timestamps fundamentally cannot do.

4.3.1 The mechanism in full, with concrete values#

The defining move is that there is no promotion, no election, and no failover — because there was never a special node whose loss requires any of those things. A node being down is not an event that requires a control-plane reaction; it is just a node that some requests skip. That is the single reason this topology exists, and everything else about it is a consequence.

Setup for the whole walk-through: 6 nodes on a consistent-hashing ring (File 06) named n1…n6; replication factor N = 3; the key cart:42 hashes to a ring position whose three successive nodes are n2, n3, n4 — these are the key's preference list (Dynamo's term) or natural replicas. Client-side quorum settings W = 2, R = 2.

                 ring position of hash("cart:42")
                            │
        ─── n1 ──── n2 ──── n3 ──── n4 ──── n5 ──── n6 ───(wraps)
                     └───── preference list (N=3) ─────┘
                       replicas: n2, n3, n4

  WRITE (W=2)                              READ (R=2)
  coordinator sends to n2,n3,n4            coordinator sends to n2,n3,n4
  waits for 2 acks ──► ACK client          waits for 2 responses
  (3rd may arrive later, or never)         compares versions, returns newest,
                                           repairs the stale one in background

The write path, step by step.

The read path, step by step.

4.3.2 Worked trace: the failure that requires no failover#

n3 crashes at t = 0. Watch what happens — and specifically, watch what doesn't.

 t=0.000  n3 loses power.
 t=0.100  Write to cart:42 arrives. Coordinator sends to n2, n3, n4.
          n2 acks (1.1 ms). n4 acks (1.4 ms). n3 times out at 2000 ms.
          W=2 was satisfied at 1.4 ms → CLIENT GOT SUCCESS AT 1.4 ms.
          *** No election. No promotion. No write outage. Latency unchanged. ***
 t=0.100+ Coordinator stores a HINT for n3 (§10.2): "when n3 returns, give it this write."
 t=5.000  Read of cart:42. Coordinator asks n2, n3, n4. n2 and n4 respond, R=2 met.
          Reads are fine too. n3's absence is invisible to clients.
 t=600    n3 reboots. Gossip informs the cluster. Coordinators replay their hints to n3.
 t=650    n3 is fully caught up.  No human was involved at any point.

Compare this with §4.1.2's single-leader trace: 10 seconds of total write unavailability, a promotion decision, a lost acknowledged write, and a repointing of every other replica and every client. The leaderless topology paid for this with everything in §8 and §9 — quorum arithmetic, no transactions, conflict resolution, background repair — but the availability property is genuinely, structurally better, and that is why Amazon built Dynamo this way after the 2004 holiday-season outages that motivated the paper.

Now the trace where it goes wrong. With W = 1, R = 1 (maximum availability, minimum guarantee): a write goes to n2 only and is acked. A read a millisecond later is served by n4, which has not received it. The client reads back a value older than the write it just performed — a read-your-writes violation (§7.2) that the quorum condition would have prevented. This is not a bug; it is the configuration doing exactly what you asked. The whole point of §8 is choosing W and R deliberately rather than accepting a default.

4.3.3 Pros, cons, complexity, when to use#

Pros:

Cons:

Complexity/cost: N×data storage; each write costs N network sends and W waits; each read costs R responses. Background repair traffic adds a continuous baseline load. Metadata cost of version vectors is O(replicas) per value.

When to use it — the decisive conditions. Use leaderless when: write availability during failures is the top requirement and you can tolerate eventual consistency; you have a very high write volume of independent keys (time series, events, sensor data, messages) with no cross-key invariants; you need multi-region with local quorums; or your access pattern is key-value/wide-row with no joins. Do not use it when you need transactions, when your data has global invariants (balances, inventory, uniqueness), when your team is small (the operational surface — repair, compaction, tombstones, topology — is large), or when you would spend the whole time fighting the absence of a query language.

4.4Chain Replication (and CRAQ) — the under-taught topology#

Chain replication (van Renesse & Schneider, OSDI 2004) is rarely covered in interview prep and is worth real treatment, both because it is genuinely used in production (Azure Storage, Hibari, Ceph's primary-copy chains, FAWN, and — in its CRAQ variant — parts of several distributed stores) and because it is the cleanest existing demonstration that strong consistency and high read throughput are not fundamentally in tension; the usual tension is an artefact of the leader-based design, not a law.

4.4.1 The mechanism#

Arrange the N replicas in a totally ordered chain: a head, some middle nodes, and a tail.

   WRITES                                                          READS
     │                                                               ▲
     ▼                                                               │
  ┌──────┐      ┌────────┐      ┌────────┐      ┌──────┐             │
  │ HEAD │─────►│ MID 1  │─────►│ MID 2  │─────►│ TAIL │─────────────┘
  │ (n1) │      │  (n2)  │      │  (n3)  │      │ (n4) │
  └──────┘      └────────┘      └────────┘      └──────┘
     ▲                                              │
     └──────────── ACK travels back ◄───────────────┘   (or tail acks the client directly)

Why this gives strong consistency, argued from first principles. Every node applies writes in the same order — the order the head assigned — because a node only ever receives writes from exactly one predecessor along a linear path, so there is no possibility of reordering. And the tail applies a write strictly last in the chain. Therefore: if the tail has applied a write, every node before it has already applied it; and if the tail has not applied a write, no client has been told it committed. Reading from the tail therefore returns exactly the set of committed writes and nothing else — which is linearizability, achieved without any quorum, any voting, or any consensus round. The correctness argument is a single sentence, which is why the paper is famous. Compare with the leader-based case, where a leader that is about to be deposed can serve a read that reflects a write that will later be lost.

Compare the network cost. Primary-backup with N replicas: the primary sends N−1 messages, so its outbound bandwidth is the bottleneck and grows with N. Chain: every node sends exactly one message (except the tail), so the load is perfectly balanced and no node's NIC is a chokepoint. The cost is latency: the write must traverse N sequential hops, so latency is the sum of N link latencies rather than the max of N parallel ones. With 4 replicas at 0.3 ms per hop that is 1.2 ms instead of 0.3 ms. That is the whole trade: chain replication converts a bandwidth bottleneck into a latency penalty.

4.4.2 Failure handling, node by node#

This is where chain replication is elegant, because each of the three cases is genuinely simple. A separate, small, consensus-backed service — the master or configuration manager, typically Paxos/Raft-based (File 18) and holding almost no data — monitors the chain and publishes the current membership. Note the pattern: the chain does the data work, and a tiny consensus service does the membership work. This is the same "small CP core, large fast data plane" pattern as §18.2.

Why this is simpler than leader failover: at no point does anyone hold an election, and at no point can two nodes both believe they are the head, because the configuration manager, not the nodes, decides the chain and hands out a configuration epoch (a fencing token, §2.10/§11.4).

4.4.3 The problem, and CRAQ as the fix#

The obvious flaw: all reads hit the tail, so read throughput is one node's throughput, and adding replicas does not help — in fact it makes writes slower (more hops) without helping reads at all. Chain replication as published trades read scalability away entirely.

CRAQ (Chain Replication with Apportioned Queries, Terrace & Freedman, USENIX ATC 2009) fixes this and is the version worth knowing. The insight: any node in the chain can serve a read, provided it knows whether its own copy is committed.

The mechanism: each node stores, per object, a list of versions rather than one value, and marks each version clean or dirty. A version becomes dirty when the node receives the write and forwards it; it becomes clean when the node learns the tail has committed it (the commit acknowledgement propagating back up the chain carries this news). Then:

Why this is still linearizable: a clean version is by definition one the tail has committed; a dirty read defers to the tail's committed version number, which is the authoritative commit point. Either way the client sees exactly the tail's committed history.

The performance consequence, with numbers. For a read-mostly workload — say 99% reads — almost every version is clean, so almost every read is served locally by whichever of the N nodes you asked. Read throughput therefore scales linearly with chain length: a 4-node chain serves roughly 4× the reads of plain chain replication, at full strong consistency. For a write-heavy workload on a hot object, most versions are dirty, every read costs a small version query to the tail, and throughput degrades toward — but importantly, not below — plain chain replication, because the tail query is a tiny fixed-size message rather than a full object read. CRAQ therefore gets you strong consistency with read throughput that scales like an eventually-consistent system, on read-heavy workloads. That is a genuinely unusual combination, and naming CRAQ in an interview when asked "how do you scale strongly-consistent reads?" is a strong differentiator, alongside leader leases (§0.7) and Spanner's read-only timestamps (§18.1).

4.4.4 Where it is used, and the pros/cons/when#

Azure Storage is the flagship production example. Its stream layer replicates each extent (a chunk of an append-only stream) across three extent nodes arranged as a chain: the client appends to the primary/head, which forwards down the chain, and the append is acknowledged only when the last node in the chain has it. Microsoft's SOSP 2011 paper describes this directly, and it is why Azure Storage can offer strongly-consistent reads on a highly available blob store. Ceph uses a closely-related primary-copy chain within each placement group. Hibari (a key-value store from Gemini Mobile) is a direct implementation of chain replication. FAWN-KV used it for a cluster of low-power nodes. Several production systems adopt chain replication within a shard while using consensus for shard membership.

Pros: linearizable reads and writes with no quorum round trips at all on the data path; perfectly balanced network load (one send per node); a strikingly simple correctness argument; simple, election-free failure handling; and with CRAQ, read throughput that scales with replica count while staying strongly consistent.

Cons: write latency is the sum of N hops, not the max — worst-case among all topologies, and it becomes prohibitive if the chain spans regions (a 3-region chain costs 90 + 90 ms). It depends on an external configuration service for membership, so you have not escaped consensus — you have confined it. Plain chain replication has no read scaling. A single slow node slows every write, because the chain is serial and there is no "wait for the fastest majority" escape hatch — this is the opposite of a quorum's straggler tolerance and is chain replication's most important practical weakness. Recovery of a failed middle node requires the sent-but-unacked bookkeeping described above.

Complexity: write = N sequential hops; read = 1 hop (tail) or 1 local + occasional tail query (CRAQ). Storage N×. No voting messages at all.

When to use it — the decisive conditions. Use chain replication when you need strong consistency inside a single datacenter (so per-hop latency is sub-millisecond and the serial cost is tolerable), when your workload is read-heavy (use CRAQ), and when you already have a small consensus service available to manage configuration. It is especially natural for append-only, immutable-chunk storage — which is exactly why blob/object stores (Azure Storage, File 09) adopt it. Do not use it when the replicas span regions, when writes are latency-critical and N is large, or when you cannot tolerate one slow node dragging the whole write path.

4.5The Four Topologies Compared, and the Decision Rule#

The decision rule — say this out loud:

Anti-recommendation: the most common wrong pick is choosing multi-leader for high availability. Availability is a failover problem, and single-leader with a good failover controller (§11.2, §17.2) gives you seconds of downtime and zero conflicts. Multi-leader gives you zero downtime and a permanent, unbounded conflict-resolution obligation. The second most common wrong pick is choosing leaderless because "Cassandra scales" for a workload with transactional invariants — you will spend the next two years reimplementing transactions badly in the application layer.

5Quorums & Tunable Consistency#

5.1The N/W/R Formula (the leaderless heart)#

In a leaderless system with N replicas per key:

**Sub-Concept: The Quorum Condition W + R > N. If the write set and read set are large enough to overlap, every read is guaranteed to touch at least one replica that has the latest write → strong (quorum) consistency**. Example: N=3, W=2, R=2 → W+R=4 > 3 → overlap guaranteed. The reader takes the value with the newest version among the R responses. If W + R ≤ N, reads and writes might not overlap → you can read stale data (eventual consistency), but with lower latency / higher availability.

5.2Tuning the Trade-off#

You tune W and R per operation to slide along the consistency/latency/availability spectrum:

This per-query tunable consistency (Cassandra/DynamoDB let you pick ONE/QUORUM/ALL) is a favorite interview topic: you trade consistency ↔ latency ↔ availability by choosing W and R.

5.3Sloppy Quorums & Their Caveat#

To stay available during partitions, Dynamo-style systems use sloppy quorums: if the "home" replicas are unreachable, write to any W reachable nodes (with hinted handoff to deliver later). This boosts availability but means W+R>N no longer strictly guarantees overlap during a partition → weaker consistency exactly when it's stressed. Know that "quorum" under a sloppy quorum isn't the strict guarantee.

6Consensus Algorithms: Raft (deep) & Paxos#

When you need strong consistency with a single agreed order (leader-based), you use a consensus algorithm to elect a leader and replicate a log. Raft is the one to know deeply (designed to be understandable); Paxos is the classic ancestor.

6.1Raft — Designed for Understandability#

Raft decomposes consensus into three subproblems: leader election, log replication, safety. Nodes are in one of three roles: Leader, Follower, Candidate.

(A) Terms. Time is divided into terms (monotonically increasing numbers). Each term has at most one leader. Terms act as a logical clock to detect stale leaders (a message from an older term is rejected).

(B) Leader Election.

(C) Log Replication.

(D) Safety / Log Matching. Raft only elects a candidate whose log is at least as up-to-date as the majority (voters reject candidates with staler logs), guaranteeing the new leader has all committed entries. Conflicting follower entries are overwritten to match the leader.

Result: a replicated log agreed upon by a majority, tolerant of ⌊N/2⌋ failures, with a single leader ordering all writes → a linearizable replicated state machine.

6.2Paxos (and Multi-Paxos)#

Paxos (Lamport) is the original consensus algorithm. Basic Paxos agrees on one value via two phases with roles (Proposers, Acceptors, Learners):

Majorities guarantee that once a value is chosen, any future proposal will learn and re-propose it → agreement.

6.3Byzantine vs Crash Faults (a boundary)#

Raft/Paxos assume crash faults (nodes fail by stopping/being slow, but don't lie). They do not tolerate Byzantine faults (nodes sending malicious/arbitrary/contradictory messages) — that needs BFT protocols (PBFT, and blockchain-style consensus), which require 3f+1 nodes to tolerate f liars (vs 2f+1 for crash faults). Inside a trusted datacenter, crash-fault consensus (Raft/Paxos) is standard; BFT is for adversarial/trustless settings (blockchains). Know the distinction; interviewers may probe it.

7Consistency Models Spectrum#

From strongest (most expensive) to weakest (cheapest/most available):

Sub-Concept: CRDTs (Conflict-free Replicated Data Types). Data structures (counters, sets, maps, sequences) designed so that concurrent updates on different replicas can be merged automatically and deterministically without conflicts — the merge is commutative/associative/idempotent, so all replicas converge no matter the order they receive updates. They let you have strong eventual consistency (AP) without manual conflict resolution — the basis of collaborative editing (Google Docs-like), Redis CRDTs, Riak. A great "how do you resolve multi-leader conflicts?" answer.

8Pros, Cons & Trade-offs#

8.1Benefits#

8.2Costs & Trade-offs#

9Interview Diagnostic Framework (Symptom → Solution)#

10Real-World Engineering Scenarios#

10.1Google Spanner — Global Strong Consistency (CP/EC)#

Spanner is a globally-distributed, externally consistent (linearizable) SQL database:

10.2etcd / ZooKeeper — The Coordination Backbone (CP)#

Kubernetes' brain (etcd) and countless systems' coordinator (ZooKeeper) are small, strongly-consistent stores:

10.3Amazon DynamoDB / Cassandra — Tunable AP at Scale (PA/EL)#

11Interview Gotchas & Failure Modes#

11.1Classic Questions#

11.2Failure Modes & Mitigations#

12Whiteboard Cheat Sheet#

 REPLICATION = copies (availability/durability).  CONSENSUS = make copies AGREE on an ordered log.

 CAP (only bites DURING a partition, which is unavoidable):
    CP -> refuse on minority side, stay correct (etcd, ZK, Spanner, HBase)   [banks, config, locks]
    AP -> keep serving, converge later/eventual (Cassandra, DynamoDB, Riak)  [carts, feeds, DNS]
 PACELC: if Partition -> A or C ; Else (normal) -> Latency or Consistency (strong C always costs latency)

 REPLICATION MODELS:
    Single-leader: writes->leader->followers. sync(no loss,slow) vs async(fast,loss window). SPOF->failover
    Multi-leader:  multi-region writes -> conflicts -> LWW/version-vectors/CRDT
    Leaderless(Dynamo): any replica; quorum W/R; read-repair+hinted-handoff+anti-entropy(Merkle)

 QUORUM: majority = floor(N/2)+1. Any two majorities overlap.
    W + R > N  => read overlaps latest write => strong. Tune W,R for consistency<->latency<->availability.
    N=3,W=2,R=2 balanced. Odd N (3->tolerate1, 5->tolerate2). Prevents SPLIT-BRAIN.

 CONSENSUS (crash-fault, majority):
    RAFT: roles Leader/Follower/Candidate; TERMS; randomized election timeout; majority vote -> 1 leader;
          AppendEntries replicates log; entry COMMITTED when majority has it; never lose committed entry.
    PAXOS/Multi-Paxos: prepare+accept phases; same guarantees; general but subtle. Raft = understandable.
    Byzantine (liars) -> needs BFT (3f+1), for trustless/blockchain. Datacenter = crash-fault only.

 CONSISTENCY SPECTRUM (strong->weak): linearizable > sequential > causal > read-your-writes > eventual
 FLP: async consensus can't guarantee termination if a node can crash -> use timeouts/leaders in practice.
 CRDT: auto-mergeable types -> strong eventual consistency w/o manual conflict resolution.

One-sentence summary for an interviewer:

"Replication keeps redundant copies for availability; consensus (Raft/Paxos, via majority quorums) makes those copies agree on a single ordered log so the system is linearizable and split-brain-free; CAP says that during an unavoidable network partition you must choose CP (refuse to stay correct — banks, etcd/Spanner) or AP (stay up, converge later — Cassandra/Dynamo), and PACELC adds that even normally, strong consistency costs latency; leaderless systems tune the trade per-query with **W + R > N quorums, and you resolve conflicts with version vectors/CRDTs — always replicate across AZs with an odd** node count and never hand-roll consensus."

End of File 08. Next → File 09: Distributed File/Object Storage (metadata servers, block/object storage, erasure coding).