Replication, Quorums, and Read/Write Paths

The write was acknowledged at 14:03:11.208. The leader lost power 7 ms later. After failover, the order was absent.

The incident record says the service used three replicas. That fact does not settle whether the response was honest. The old leader may have appended the record only to memory, flushed it locally, transmitted it to one follower’s operating-system cache, waited for a majority to make the log entry durable, or waited until another replica had applied the change to readable state. Each path can be called “replicated,” yet each promises something different when a process, host, device, zone, or region fails.

The review begins by replacing one overloaded word—success—with four events:

Suppose the contract requires an acknowledged order to survive loss of any one storage host. A local flush is insufficient even when the service has two asynchronous followers. The acknowledgment must wait until the protocol establishes a durable copy outside the leader’s host, and failover must select a successor containing every acknowledged entry. If the contract instead permits a bounded recovery point objective, a faster local acknowledgment may be valid—but the possible loss window must be stated in time and operations.

The controlling rule is simple: choose replication by the meaning and failure behavior of an acknowledgment; replica count by itself is not a durability or latency guarantee.

Replicas exist for different jobs

Replication copies state or a state-changing history across failure boundaries. Five motives recur, and one topology rarely maximizes all five:

• Durability: preserve acknowledged effects despite a named loss, such as a process, host, device, zone, or region.
• Availability: retain a legal read or write path while some components are unreachable.
• Read scale: serve eligible reads from more execution and storage capacity.
• Locality: place a readable or writable copy near a user or dependent service.
• Recovery: restore a failed or corrupt copy from another trusted source within an objective.

Name the motive and failure scope separately. Three copies on one host do not tolerate host loss. Three replicas in one zone may tolerate a node failure but not a zone failure. Two live replicas are not a backup when the same erroneous delete, application bug, or operator command propagates to both. Backups and retained logs address historical recovery; replicas primarily maintain current service state.

A design record should also distinguish data replicas from voters. A non-voting learner may receive the log without affecting commit quorum. A witness may vote without holding all user data. An asynchronous analytical follower may support read scale but be ineligible for failover. Counting all of them as “replicas” conceals the protocol.

Topology determines who orders and who waits

Leader-based replication

One leader accepts writes for an ownership scope and orders them in a log. Followers receive that order. Reads may go to the leader, to followers with a freshness rule, or through a protocol that proves a follower is sufficiently current.

The fast path is easy to explain: validate, append, replicate, reach the configured commit rule, apply, respond. The slow path includes a lagging follower, a full network window, disk stalls, log compaction, and flow control. The failure path needs leader election, a term or epoch, catch-up, and client redirection. The recovery path includes snapshot transfer and replay.

Leader placement creates a write hot spot but gives conflicting writes one ordering point. Batching and pipelining can make that point efficient. A leader is not automatically a single machine for the whole database; partitioned systems can have many leaders over disjoint ownership ranges. Chapter 26’s placement skew then applies to leader load.

Multi-leader replication

Several leaders accept writes, often in different regions or disconnected domains. This can localize write latency and preserve acceptance during a partition. It also permits concurrent updates whose order is not already shared.

The design must say which objects may be written in multiple places, how conflicts are detected, which merge policy is deterministic, which invariants can survive concurrent execution, and how users learn about a rejected or compensated result. Last-writer-wins is a policy, not absence of conflict; it can discard a valid update because a timestamp happened to compare later. Allocating disjoint ownership to each leader avoids many conflicts but turns the arrangement into partitioned single-writer authority.

Use multi-leader paths when local acceptance and disconnected operation justify application-visible reconciliation. Do not use the label to defer invariant design to Chapter 28.

Leaderless replication

A coordinator sends an operation to a replica set without requiring one permanent leader for the key. A write may wait for (W) responses among (N) intended replicas; a read may consult (R), compare versions, and reconcile. Coordinators may be clients, stateless routers, or replicas.

This arrangement can preserve a path when a particular node is unavailable and can offer tunable latency/consistency behavior. The protocol still needs version identity, concurrent-write handling, membership, failure assumptions, and repair. A sloppy quorum that substitutes temporary nodes outside the preferred replica set improves acceptance but weakens the simple intersection story until hints return and convergence completes.

Chain replication

Writes enter at a head and flow through an ordered chain; reads commonly use a tail that has seen committed updates. The path gives a clear order and can separate write ingress from read service. A longer chain adds hop and recovery sensitivity. Reconfiguration must preserve the prefix/suffix invariants of the chain and prevent removed members from continuing as authorities.

The useful comparison is not “centralized versus distributed.” It is who owns order, which replicas lie on the acknowledgment path, where reads enter, and what reconfiguration must prove.

Quorum overlap is useful arithmetic, not a complete guarantee

For a fixed replica set of size (N), any read set of size (R) and write set of size (W) must overlap when:

[ R + W > N ]

The minimum overlap is (R + W - N). In the fixture, (N=3), (R=2), and (W=2), so every such pair shares at least one replica.

That statement is combinatorial. Turning it into a useful read guarantee requires more assumptions:

1. The read and write use the same authoritative replica set and membership epoch.
2. A response counted toward (W) means the version reached the promised persistence boundary.
3. The intersecting replica returns the version or digest needed by the arbitration rule.
4. Version comparison identifies causality or a deterministic winner; concurrent values are not silently confused.
5. Failed writes, hinted writes, clock rules, deletes, and membership changes fit the protocol.
6. The read waits for and reconciles the required responses rather than returning the first convenient value.

Even with all six, overlap does not by itself provide linearizability. A protocol must also control concurrent order and real-time visibility. Nor does majority voting mean every acknowledged operation has reached every replica. The remaining replica can lag, so a ONE read can still be stale.

A quorum across failure domains is only as independent as its placement. Three voters on one power domain satisfy arithmetic and fail together. During reconfiguration, old and new configurations need an overlap rule; otherwise two disjoint majorities can each believe they are authoritative.

Trace the commit point before tuning the path

The fixture models three paths. The numbers are illustrative, deterministic inputs—not a storage benchmark:

For Ledgerline, the user contract says an acknowledged reservation record must survive any one storage-host loss. The 6 ms option cannot satisfy that contract. The 11 ms option can satisfy it only when the follower is on a different eligible host, both stable writes mean what the contract assumes, and failover never elects a replica missing acknowledged entries. The 22 ms chain may offer useful ordering or throughput behavior, but it pays more path latency in this teaching configuration.

Do not add the two follower latencies in a parallel quorum path. The leader waits for the required order statistic—the fastest eligible follower here—not every follower. Conversely, do not report the 11 ms median as a tail promise. At high percentiles, follower device and network tails, batching, queue wait, and correlated zone conditions matter.

An acknowledgment record should identify:

operation: append reservation event
authority scope: ledger partition 81, epoch 42
acknowledgment means: leader + one eligible remote host stable
commit point: term/epoch 42 log index 9,184,221 on a majority
visibility: leader after apply; followers only under freshness/session policy
failure scope: any one process or storage host
not covered: zone loss, correlated firmware fault, logical deletion
client ambiguity: query by idempotency key after deadline

This record connects Chapter 25’s completion protocol to replication. A client timeout after commit is still an ambiguous response, not permission to invent a new operation identity.

Read paths must declare time and session semantics

A leader read can be current with respect to that leader’s committed order if the leader still proves authority and has applied the required entry. A follower read can be cheaper or closer but may lag in log receipt, durable storage, apply, secondary indexes, or cache invalidation. “Replica lag” must therefore name the position being compared.

Useful lag measures include:

• receive-position distance in bytes or log entries;
• durable-position distance;
• apply-position distance;
• wall-clock age of the newest applied source event, with clock caveats;
• estimated catch-up time at current replay demand; and
• user-impact rate: stale, redirected, failed, or deadline-missed reads.

A bounded-staleness read should name both a version/time bound and the behavior when no replica qualifies. Choices are fail, wait within the deadline, route to a current authority, or return an explicitly older snapshot. Silent fallback to an arbitrarily stale replica changes the contract.

The modeled lag population contains 100,000 follower-read opportunities: 92% are at most 50 ms behind, another 5% are at most 250 ms, 2.5% are between 250 ms and 2 s, and 0.5% exceed 2 s. A 250 ms bound accepts 97% locally. If the follower tier receives 30,000 reads/s and every nonqualifying read goes to the leader, 900 reads/s transfer to the leader. That fallback load belongs in leader capacity and failure tests.

The lag distribution must be segmented by replica, partition, operation, traffic class, and system state. An aggregate 97% can hide one tenant whose follower is perpetually hours behind. Age derived from source timestamps can be distorted by clock skew; position-based measures avoid that ambiguity but need a conversion to user-visible freshness.

Session guarantees are end-to-end routing rules

Read-your-writes requires a read after a completed write to observe at least that session’s version. Monotonic reads prevent the session from moving backward after observing a version. A sticky replica can approximate both while healthy, but failover breaks the approximation unless the client or gateway carries a minimum version and the next replica waits, catches up, redirects, or rejects.

Carry a session token such as (partition, epoch, commit_position) when the product needs the guarantee. Validate the token against current ownership. Do not use a wall-clock timestamp alone unless the protocol defines its ordering and uncertainty semantics. Tokens add metadata and may route traffic toward a smaller eligible set; measure the induced concentration.

Follower reads also interact with transactions. A set of individually fresh-enough objects need not form one consistent snapshot. Chapter 28 separates object recency from transaction isolation.

Convergence work belongs to the capacity model

Asynchronous copies can diverge because a replica was unavailable, a message was lost, or concurrent versions arrived in different orders. Systems use several complementary mechanisms:

• Hints or deferred delivery remember a missed destination and replay later. Retention and coordinator loss bound what they can recover.
• Read repair detects disagreement on objects consulted by a read and may repair those replicas. Cold keys may never be read.
• Anti-entropy compares ranges or version summaries and transfers differences independently of foreground access.
• Log catch-up replays a retained ordered history from a known position.
• Snapshot/bootstrap copies a base image, then replays the delta created during the copy.

Read repair is not a substitute for full anti-entropy. Background repair is not free because it consumes storage reads, hashes, network, writes, compaction, cache, and scheduling. Deletes require special care: if a deletion marker expires before an isolated old replica participates in repair, stale data can reappear in some designs.

Telemetry should join logical effects to replica work: foreground logical writes/s, replica messages and bytes/write, local and remote stable latency, acknowledgment mode, unapplied entries, lag age/position, conflicts, repairs, hinted bytes, bootstrap progress, replay rate, and wasted or superseded versions. Report repair goodput separately from bytes scanned.

Failover is a transfer of authority, not a health-check flip

A failure detector cannot distinguish a dead leader from a slow or partitioned one with certainty. Promotion therefore needs a protocol that chooses one current term or epoch and fences prior authorities.

A safe leader-based transition usually includes:

1. stop or expire the old authority through quorum/term rules rather than operator hope;
2. elect an eligible replica whose log satisfies the protocol’s completeness rule;
3. assign a higher term or epoch;
4. reject requests and storage mutations carrying older authority;
5. catch up or remove lagging members before they vote or serve strict reads; and
6. reconcile client operations whose response was lost around the transition.

Fencing must reach the resource that could be corrupted. A token checked only by the service does not protect a storage system that still accepts writes from the old process. A lease can reduce coordination for a bounded time, but its safety depends on clock/expiry assumptions and still needs a monotonically increasing fence at downstream effects.

Split brain is not simply “two nodes are running.” It is two authorities able to produce effects for the same scope without an allowed merge rule. Multi-leader operation may permit concurrent authority for mergeable objects; a reservation counter with a hard upper bound cannot accept the same behavior accidentally.

Catch-up cost determines recovery time. Promoting the least-lagged replica may be safer and faster than the nearest one. Adding a voter before it has caught up can increase quorum size or create a fragile majority while loading the current leader with snapshot traffic. Learner/non-voter states make this transition explicit.

Replication amplification competes with foreground work

For a payload of (B) bytes and replication factor (n), a simple leader fan-out sends approximately (B(n-1)) network payload bytes before protocol framing, encryption, retries, compression, and repair. Storage demand is not merely (Bn): each replica may write a log, index, checksums, compaction output, and retained versions.

The fixture’s 1.5 KiB logical payload and three replicas produce 3 KiB of basic replication network payload and 6.3 KiB of modeled storage writes when per-replica storage amplification is 1.4. These are dimensional examples, not universal multipliers.

Placement changes both guarantee and cost. Cross-zone synchronous replication adds distance and egress while covering a wider failure domain. Cross-region acknowledgment may dominate the latency budget. Keeping all voters near one another lowers nominal latency but reduces correlated-failure tolerance. A common compromise uses synchronous replicas across nearby independent domains, asynchronous copies farther away, and an explicit regional recovery point objective. The right answer follows the contract, not the topology fashion.

Background demand becomes foreground during failure. Losing one of three replicas may increase read load on two survivors, trigger re-replication, reduce cache warmth, and force stricter reads toward the leader. N-minus-one capacity must cover the new mixture, not just nominal bytes/s.

Applied recovery budget: rebuild without creating another incident

Ledgerline must replace a 2.4 TiB replica. The model adds 8% for changes arriving during the base copy, for 2.592 TiB of transfer. The replication link has a 320 MiB/s safe budget under the teaching workload:

At 72 MiB/s, modeled rebuild time is:

[ T = \frac{2{,}457.6\ \text{GiB} \times 1.08 \times 1{,}024\ \text{MiB/GiB}} {72\ \text{MiB/s}} = 37{,}748.736\ \text{s} \approx 10.49\ \text{h} ]

An unthrottled 180 MiB/s rebuild would combine with 168 MiB/s foreground and 54 MiB/s normal replication for 402 MiB/s, exceeding the 320 MiB/s bound before reserve. The likely result is queue growth, follower lag, write-tail inflation, and perhaps another failover.

The controller should target foreground SLOs and lag, not a fixed maximum copy rate alone. Pause or reduce rebuild when device queue age, stable-write latency, network loss, or foreground deadline misses rise. Keep a minimum progress rate if remaining under-replication creates unacceptable exposure. Validate the snapshot, replay to a named commit position, verify checksums or logical invariants, and only then make the replica eligible for strict reads or voting.

Bootstrap and repair can expose sensitive data. Apply tenant authorization, encryption, residency, retention, and deletion rules to every temporary snapshot and stream. Remove failed partial copies with evidence; “temporary” replicas often outlive the incident.

Mechanism interactions change the safe path

Replication does not operate in isolation. Several adjacent mechanisms can improve its nominal behavior while worsening its failure path.

Partitioning multiplies replica sets. A three-replica claim applies per partition, not necessarily to a whole transaction or scatter read. A query that touches twelve partitions can wait on twelve different lag and failure populations. Rebalancing changes membership while replication catches up; Chapter 26’s authority epoch and this chapter’s replica-set epoch must describe one coherent cutover. If the directory routes epoch 43 while two replicas still enforce epoch 42, retrying at the client can reach both authorities.

Retries multiply replication work. One logical write replicated to three nodes already creates multiple storage and network operations. If clients, gateways, leaders, and replication transports all retry independently, the attempt count grows before the original operation’s outcome is known. Preserve Chapter 25’s logical operation identity through leader changes. The new leader should find the committed or pending result by idempotency key rather than append a semantically new command.

Admission protects quorum health. A majority protocol can remain available while one replica is down, but its remaining voters have less queue and failure headroom. Continuing to admit nominal peak traffic while rebuilding can push stable-write latency beyond the caller deadline, which creates ambiguous responses and retries. Admission should price the slowest required quorum path, replication buffer occupancy, and recovery demand—not host CPU alone.

Caching can hide replica lag until invalidation fails. A follower may have applied version 90 while a node-local cache still serves version 87. Measuring log lag alone then understates user staleness. Conversely, a cache hit may satisfy a bounded-staleness contract even while the follower is catching up, provided the cache entry carries a verifiable source version. Treat cache state as another derived replica with authority, freshness, and invalidation rules.

Compression and batching reshape failure units. Compressing replication streams lowers link demand but spends CPU on leaders and followers. Large log batches amortize flush and protocol cost but can increase the number of client operations waiting behind one stable write. A partially transmitted or corrupt batch needs a restart boundary and checksum. Measure useful committed operations per CPU second and per network byte, plus the tail added by batch formation.

Consistency determines whether a read is merely recent or legally composed. Quorum reads can discover a recent version of one key without producing a serializable snapshot across keys. A follower may be within 250 ms and still lack a transactionally related row. Chapter 28 turns those application invariants into snapshot, ordering, and coordination requirements. Do not upgrade a freshness statement into a transaction claim.

These interactions suggest a discriminating failure test. Slow one follower’s durable storage, remove another replica, start a bounded rebuild, and send a production-shaped mixture of idempotent writes and session reads. Observe logical goodput, stable quorum latency, fallback concentration, retries, cache version, repair bytes, and recovery time. The test is useful only if correctness assertions verify acknowledged effects and session floors while the mechanisms compete for the same resources.

Replication topology record

Copy this artifact into a design review:

workload and unit: ______________________________________________
authoritative scope and membership epoch: _______________________
replication purposes, ranked: ___________________________________
failure domains covered / excluded: _____________________________

write path:
  ordering authority: ___________________________________________
  persistence points: ___________________________________________
  commit rule: __________________________________________________
  client acknowledgment means: _________________________________
  ambiguous-response lookup: ____________________________________

read path:
  eligible replicas by operation: _______________________________
  freshness/snapshot rule: ______________________________________
  session token and fallback: ___________________________________
  partial/unavailable behavior: _________________________________

failure and recovery:
  election/reconfiguration rule: ________________________________
  term/epoch fence checked by: __________________________________
  repair/anti-entropy ownership: _________________________________
  rebuild bytes, rate, headroom, and target time: _______________
  promotion validation: _________________________________________

evidence:
  ack latency distribution: _____________________________________
  lag and user-impact distribution: _____________________________
  amplification per useful operation: ___________________________
  degraded/recovery goodput: ____________________________________

Field questions

• What state is stable when the client sees success?
• Which single failure can still erase that state?
• Do read and write replica sets share membership, version, and arbitration assumptions?
• Can a session move backward after routing or failover?
• Where is an old term rejected at the actual effect boundary?
• Which traffic is displaced by repair, replay, snapshot, or bootstrap?
• How long can the system remain under-replicated at the safe recovery rate?
• Are voters, learners, analytical followers, and backups counted separately?
• Which aggregate lag view hides a tenant, partition, or region tail?
• What happens when recovery itself encounters overload or another failure?

Design drill: challenge the acknowledgment, then lose a replica

Select an acknowledgment for a service that requires p99 write latency below 35 ms, must survive one host loss with no acknowledged-write loss, permits 500 ms follower staleness for anonymous reads, and requires read-your-writes for authenticated sessions. Provide the topology, commit point, failure-domain placement, session token, timeout/ambiguity behavior, and proof that an old leader is fenced.

Then reveal that a 3 TiB replica is lost while the surviving link runs at 70% of its safe budget. Calculate rebuild headroom and time with a 12% delta, decide which reads may remain on followers, and define abort/throttle thresholds. A strong answer may choose a different topology, but it cannot spend the same bandwidth twice or weaken the acknowledgment silently.

Durable decision rules

1. State the failure scope and acknowledgment meaning before selecting replica count.
2. Treat quorum overlap as one protocol ingredient; verify membership, persistence, version, arbitration, and ordering assumptions.
3. Route follower reads with explicit freshness, snapshot, and session behavior, including the load created by fallback.
4. Transfer authority with terms/epochs and downstream fencing; health checks alone cannot prevent split brain.
5. Measure replication, repair, and rebuild per useful operation and reserve degraded-state foreground headroom.
6. Promote a recovering replica only after its state and eligibility boundary are verified.
7. Keep historical recovery separate from live replication so replicated mistakes remain recoverable.

Chapter 28 starts where this one stops. Replication can preserve copies and establish an order for a log, but the application still needs to decide which object, transaction, session, and business-process histories are legal.

Evidence and transfer limits

• DeCandia et al., “Dynamo: Amazon’s Highly Available Key-value Store”, provides the primary design account for versioned leaderless replication, sloppy quorums, hinted handoff, and anti-entropy in one availability-oriented system. Its workload and conflict policy do not define all leaderless stores.
• Ongaro and Ousterhout, “In Search of an Understandable Consensus Algorithm”, defines terms, leader election, majority-committed logs, and membership reasoning for Raft. It is protocol evidence, not a promise about a particular database’s client acknowledgment or apply point.
• van Renesse and Schneider, “Chain Replication for Supporting High Throughput and Availability”, supplies the original chain-replication protocol and performance analysis under its failure model.
• Apache Cassandra replication documentation distinguishes consistency levels, read repair, hints, and anti-entropy in that implementation; repair documentation makes the operational I/O cost explicit. Version-specific behavior must be checked before applying it.
• PostgreSQL 18 standby documentation shows one implementation’s distinction among asynchronous replication and synchronous remote write, flush, and apply behavior. Those names and boundaries are not portable contracts.
• etcd 3.6 learner design documents a non-voting catch-up state and promotion checks in one Raft-based system. The exact thresholds are implementation details.
• The executable model in examples/performance-engineering-system-design-handbook/part-03/replication-paths/ reproduces the 6/11/22 ms paths, one-replica quorum intersection, 3 KiB network and 6.3 KiB storage teaching amplification, 97% bounded-staleness eligibility, 900 reads/s fallback, and 10.49-hour rebuild. All are modeled inputs; none is an observed product benchmark or durability proof.