Replication — Leader/Follower, Multi-Leader, Leaderless

Learning goal: Pick a replication topology (leader/follower, multi-leader, leaderless) for a workload and reason about failover, split-brain, and replication lag.

Why this session exists

Replication keeps additional copies of state across selected failure domains. It's also the source of split-brain, stale reads, and dropped writes if you get it wrong. This session compares three common topologies and uses a PostgreSQL reference exercise plus bounded Python models so you can read a doc page (‘we use multi-leader with LWW conflict resolution’) and immediately know what to worry about.

You will be able to

• Contrast leader/follower, multi-leader, and leaderless replication in one sentence each.

• Reason about sync vs async replication and their durability vs latency trade-offs.

• Explain read-your-writes, monotonic-read, and eventual-consistency guarantees at replica level.

• Diagnose split-brain scenarios and describe the two mainstream defences (quorum + fencing).

Prerequisites

• S042 · Transactions & ACID — durability and isolation semantics.
• S070 · CAP & PACELC — the theoretical frame we'll instantiate.
• S062 · Load balancers — read replicas often sit behind an LB.

Original resource trail and reading purpose

The exact original preparation URLs remain optional discovery pointers. Video titles and creator labels are historical finding labels: identity, playback, contents, runtime and availability were not verified. Neither the old 25-minute preparation total nor the 90-minute session slot is a measured completion time; use the existing intuition → visual → reference/model → failure analysis → recall route at your own pace. No claim of perpetual maintenance for all 130 lessons follows.

• “Database Replication Explained” — historical ByteByteGo label: optional topology overview; the old animation/quality praise is unverified.
• “Postgres Replication Deep Dive” — historical Hussein Nasser label: optional WAL, streaming and hot-standby topics, not evidence for a “most-used” ranking or this lesson's PostgreSQL 16 commands.
• “Cassandra vs. ScyllaDB: Evolutionary Differences” — historical ScyllaDB label: optional consistent-hash placement and quorum topics. No specific product behavior is accepted from the unseen recording.
• PostgreSQL current high-availability chapter: original navigation entry to replication/streaming documentation; the version 16 references below, not the moving current alias, govern the reference exercise.
• Amazon DynamoDB technical whitepaper: retained exact original destination, but not identified as the Dynamo SOSP 2007 paper. The original “sections 4 and 5” advice must not be transferred to this different document without inspecting it. For the historical design use the separately cited 2007 Dynamo paper below.
• Kleppmann, “Please stop calling databases CP or AP”: optional replication/CAP interpretation; retaining the link does not endorse every argument or the former unqualified praise.

(a) Intuition · 5 min

A newspaper with one editor, many editors, or none

One editor (leader/follower): the editor writes every story. Copies are printed at 500 newsstands. Readers can pick up any newsstand copy, but every change goes through the editor. If the editor is sick, no new stories go out until someone is promoted.

Multiple editors (multi-leader): New York and London both have editors who can independently publish. Occasionally they publish contradictory stories at the same time; the papers must be reconciled after the fact ("we're going with New York's version").

No editor (leaderless): Any writer can drop off a story at any newsstand. Newsstands gossip changes among themselves. To make sure YOUR story is really out, you drop it off at three newsstands. Checking overlapping sets of newsstands ensures at least one shared copy, provided membership is fixed. Deciding which version is valid still needs a protocol.

Leader/follower (Postgres, MySQL, Redis, MongoDB, most SQL DBs): one write leader; N read followers. Simple mental model, but leader failover is a serious operation.

Multi-leader (CouchDB-style bidirectional replication or independently writable databases): writes accepted at multiple authorities; concurrent conflicts are possible and require a resolution policy.

Leaderless (Dynamo, Cassandra, Riak, Scylla): a contacted node may coordinate operations against the replicas responsible for the key; the coordinator contacts those replicas (write to W of N, read from R of N); W + R > N proves intersection of fixed replica sets, not general linearizability.

The three topologies at a glance

One-line summary each

• Leader/follower — one node accepts writes; N replicas stream changes. Simplest to reason about; failover is the hard problem.

• Multi-leader — multiple leaders accept writes independently, replicate to each other. Great for latency at write time; conflict resolution is the price.

• Leaderless — no fixed per-key write leader at this model level. A client/coordinator waits for the configured W and R response counts; those need not be majorities. No single write-leader promotion; membership changes, conflict resolution and repair still require protocols.

The two orthogonal knobs you'll turn

Sync vs async is a SEPARATE choice from topology

Topology and acknowledgment policy are separate choices. A single leader can wait for none, one, a quorum or all selected followers; a leaderless coordinator can wait for a chosen response count. The latency is governed by the required responses, not necessarily the slowest node in the cluster. An acknowledgment may mean received in memory, written to the OS, durably flushed, or applied so reads can observe it. Do not call all four “synchronous and safe.” PostgreSQL 16's synchronous_commit and synchronous_standby_names specify this boundary; setting synchronous_commit=on alone does not create a synchronous standby.

A quick history so the ecosystem makes sense

The 2007 Dynamo paper describes consistent-hash placement, vector-clock versions, hinted handoff and anti-entropy: availability requires reconciliation work, not just more replicas. PostgreSQL's physical WAL streaming is a different design: followers replay one primary's log. Raft's 2014 paper adds explicit terms, election restrictions and replicated-log commitment rules. These examples explain the ecosystem without treating a modern managed service's brand as one replication topology. MySQL's binlog-based replication is another log-propagation example; the original 1996 date and the broad 1980 IBM attribution are not established here. Managed offerings such as Aurora, Cosmos DB, Spanner and CockroachDB expose differing APIs and configurations; “cloud-native primary-primary” is not a shared guarantee. Early replication research, binlog/WAL evolution and managed abstractions remain useful comparison topics without an invented chronology or universal topology.

Leader/follower — the classic

Compare replication topologies by following the write first, then asking where a read may go. In the leader/follower layout, one node orders writes while the other nodes receive its log.

The read client has more possible destinations than the write client. That creates read capacity, but a follower's answer depends on how far its WAL replay has progressed—a distinction the bidirectional topology changes rather than removes.

Multi-leader — writes accepted in multiple regions

Move the write entry point closer to each region's clients. The bidirectional link now has to reconcile changes made independently, not simply replay one leader's ordered history.

Local writes avoid waiting for a distant leader, but simultaneous updates can disagree. The conflict-resolution label is an application semantics decision hiding inside an infrastructure arrow.

Leaderless — quorum reads/writes

Remove the fixed write leader and track how many replicas participate in each operation. The client now needs a rule for choosing replicas and interpreting the versions they return.

The repair links matter alongside the read and write arrows: replicas that missed an operation still need to converge. Quorum overlap is part of the reasoning, but version handling and failure assumptions determine what a read can safely claim.

The three topologies compared

Leader / Follower

PostgreSQL physical streaming · MongoDB replica sets

• Writes to the current authority; reads from replicas only where the engine, routing and read contract permit

• One ordered replication stream; SQL isolation and read routing still require explicit settings

• Promotion requires an external failover controller or operator plus fencing

• Async replication → potential data loss on leader crash

• Fit: OLTP, ‘standard SQL app’

Multi-Leader

Independently writable databases with bidirectional change replication

• Independently acknowledged local writes can avoid a cross-region wait; synchronous policies still pay their required coordination cost

• Conflicts on same key → app or DB must resolve

• Useful when independently accepted updates have defined merge semantics

• Independent conflicting writes need explicit merge/transaction semantics; topology alone is not a SQL isolation level

• Fit: global collaboration, offline mobile sync

Leaderless (Quorum)

Dynamo · Cassandra · Riak · Scylla

• A client or coordinator contacts the key's replicas; the API/configuration determines W and R (not every product lets a client choose arbitrary counts)

• If W + R > N, fixed read/write replica sets intersect; additional protocol assumptions govern freshness

• No unique write-leader failover, but unavailable replicas and membership changes can still block requests

• Some protocols expose siblings; others reconcile timestamps internally. Inspect the actual contract.

• Fit: high write throughput, high availability

Sync vs async — the durability/latency dial

Replication copies state; failover chooses who may accept new writes. Synchronous acknowledgement must specify whether it means received, written, flushed or applied, and which replicas participate. Asynchronous replication creates a potential data-loss window if the only durable copy is destroyed before shipping. A replica's current lag is an observation, not a guaranteed RPO under every failure.

Read-your-writes can be implemented by carrying a commit/log position and reading only from a replica that has applied it, falling back or waiting when necessary. “Read from the leader for N seconds” is a heuristic unless replica lag is bounded by the contract. For leaderless replication, R + W > N guarantees set intersection under fixed membership; it does not by itself guarantee linearizability with concurrent writes, sloppy quorums, partial failures and timestamp reconciliation. A stale leader may keep running after a lease expires. Sink-enforced monotonically increasing fencing tokens prevent it from writing after a newer owner has taken over.

An eventual-convergence claim additionally requires successful delivery or repair after updates stop and a compatible reconciliation rule. A replica that remains disconnected forever need not catch up. Read repair covers records actually read; anti-entropy can cover unread divergence. Deletes need retained tombstones or equivalent version state so an old replica cannot resurrect removed data during repair.

Acknowledgment, read visibility and failover arithmetic

In PostgreSQL 16, with synchronous standbys configured, on waits for durable remote WAL flush, remote_write waits for a standby OS write (not protection from its OS crash), and remote_apply waits for replay. With no synchronous standbys configured, the non-off settings provide local flush only. Even remote_apply does not mean every other asynchronous replica is current.

Suppose the primary's local durable step takes 2 ms and candidate replica acknowledgments arrive 3, 8 and 40 ms after sending. Waiting for two of those three adds 8 ms in a sequential teaching model, not 40 ms. If both durable copies are in one zone, losing that zone defeats the durability assumption. Promotion must choose a survivor containing the committed prefix; arbitrary promotion can discard an acknowledgment even when another suitable copy survives.

A replica can replay 18 MB/s while the primary generates 20 MB/s. Backlog grows by 2 MB/s: after ten minutes, 1,200 MB are queued. When generation falls to 10 MB/s, net catch-up is 8 MB/s and that backlog takes 150 seconds to drain, assuming rates stay constant. Adding another equally constrained replica does not make either one replay faster. Replicas also spend CPU and I/O applying changes; read capacity is not simply replica count times the primary's spare capacity.

Session positions and fencing

For read-your-writes on one ordered log, carry the successful write's position, say 1,240. A follower applied through 1,230 cannot serve that session yet; one through 1,250 can. For monotonic reads, retain the greatest observed position too. After reading position 1,270, the same session must not be routed to a replica at 1,250. Position comparisons require the same history/timeline; a promotion to a divergent history cannot be made safe by comparing raw numbers.

A leader paused at epoch 8 can resume after epoch 9 is elected. The old process may still believe it is leader. Election safety is not sink fencing: the storage destination must reject epoch 8 once epoch 9 is authoritative, or the old primary must be prevented from writing by a reliable isolation mechanism. Lease expiry in the old process's memory is not enough. PostgreSQL's failover documentation explicitly requires a way to stop the old primary acting as primary.

(c) Hands-on · 25 min

Two exercises retain different purposes: PostgreSQL 16 reference instructions show real observability and bootstrap contracts; the deterministic Python fixture demonstrates exactly what quorum arithmetic does and does not prove. The database exercise was not deployed here.

PostgreSQL 16 reference exercise

Use disposable, isolated PostgreSQL 16 instances with no production data. Configure the primary with wal_level=replica and enough max_wal_senders for both backup and streaming. Create a least-privilege replication role, restrict its pg_hba.conf entry to the standby address using the authentication required by your environment, and provision credentials through a private prompt or protected credential file—not pasted shell history. Keep any published local ports bound to loopback. Never delete an existing container or data directory to make a lesson work.

Run this as the PostgreSQL OS account, against an existing configured primary, into a new empty destination owned by that account. Set the two environment variables deliberately; the host/port must describe the isolated primary. The command fails rather than erasing a nonempty destination.

# Reference fragment: prerequisite primary/role/access rules must already exist.
: "${PGHOST:?Set the isolated primary host}"
: "${STANDBY_DATA:?Set a new empty directory owned by postgres}"
pg_basebackup -h "$PGHOST" -p 5432 -U replicator -W   -D "$STANDBY_DATA" -Fp -Xs -R -P

-R writes standby.signal and recovery connection settings; -Xs streams required WAL during backup. Arrange subsequent authentication through an appropriate protected passfile and verify generated connection configuration before starting the standby as the PostgreSQL account. A successful backup is not a running standby. Start with the version-matched server tooling, check readiness rather than sleeping a fixed three seconds, then verify SELECT pg_is_in_recovery(); returns true there.

On the primary, in the scratch application database:

CREATE TABLE replication_lesson (id integer PRIMARY KEY, balance integer NOT NULL);
INSERT INTO replication_lesson VALUES (1, 1000);
SELECT pg_current_wal_lsn();
SELECT application_name, state, sync_state,
       pg_wal_lsn_diff(sent_lsn, replay_lsn) AS sent_not_replayed_bytes,
       write_lag, flush_lag, replay_lag
FROM pg_stat_replication;

On the standby, query the same table and pg_last_wal_replay_lsn(). Wait for the captured primary position on the same timeline before expecting 1000. An insert on a hot standby should be rejected as read-only. Observe rather than promise a one-to-ten-millisecond delay. The reported lag intervals measure recent WAL acknowledgment delays, not a catch-up ETA; they can become NULL on an idle caught-up system. Compare byte positions and their trend as well.

WAL-retention exercise and answer: If generation is 20 MB/s and a receiver is absent for ten minutes, retaining the generated WAL alone needs about 12,000 MB before safety margin and other disk use. wal_keep_size is a minimum retention allowance, not a hard “lag exceeds 1 MB, fail now” threshold. A slot can retain WAL for a disconnected replica, consuming disk; configured max_slot_wal_keep_size limits can make needed WAL unavailable. Archive recovery may fill a gap if configured; otherwise use a fresh base backup. Alert on free disk, retained bytes and slot progress. Slots are not an unconditional substitute for capacity planning or a backup.

Quorum intersection fixture

Here all replicas initially hold version 0, writes complete sequentially to exactly the selected acknowledgers, and membership does not change. A read counts a responding replica even if its value is old. This avoids the incorrect shortcut of searching until enough replicas with nonempty values have been found. Versions are logical integers, not possibly equal or skewed wall clocks.

from itertools import combinations
 
N = 3
nodes = set(range(N))
checked = 0
for w in range(1, N + 1):
    for r in range(1, N + 1):
        stale_exists = False
        for written in combinations(nodes, w):
            replicas = [1 if i in written else 0 for i in range(N)]
            for read_set in combinations(nodes, r):
                observed = max(replicas[i] for i in read_set)
                if w + r > N:
                    assert observed == 1
                stale_exists |= observed == 0
                checked += 1
        assert stale_exists == (w + r <= N)
 
# A FAILED write can still be visible: it reached only one replica.
replicas = [2, 1, 1]  # v2 did not meet W=2
assert max(replicas[i] for i in (0, 1)) == 2
assert max(replicas[i] for i in (1, 2)) == 1
print('quorum combinations checked:', checked)
print('failed-write read regression:', 2, 1)
 
# Two independently accepted assignments need a merge policy.
a = {'title': ('red', 1, 'A')}
b = {'title': ('blue', 1, 'B')}
merged = max(a['title'], b['title'], key=lambda x: (x[1], x[2]))
assert merged[0] == 'blue'  # deterministic tie-break, not preservation of both intents
print('LWW winner:', merged[0])

What each block does

The 49 read/write-set combinations exhaust this three-replica fixture: with W=2 and R=2 all nine pairs intersect; with W=1 and R=1 there are disjoint pairs. That establishes a combinatorial fact, not the behavior of Cassandra during arbitrary failures. The failed-write fixture lets one read return version 2 and the next return 1; merely overlapping each completed write quorum did not enforce monotonic reads. A stronger protocol needs additional write completion, read repair/write-back or consensus rules.

The final fixture gives LWW a deterministic (version, origin) ordering. It converges to blue while discarding red. A version vector could identify these concurrent branches rather than arbitrarily rank them; an application merge or suitable CRDT must define what preserving both edits means. A grow-only counter represented as per-origin nonnegative components can merge those components by maxima and then sum, but that does not enforce an inventory lower bound or an access-control invariant.

Bounded position and fencing model

This companion uses one explicit history identifier and a monotonic sink epoch. It models a read gate and a destination that rejects obsolete tokens; it is not a PostgreSQL extension, an election protocol, or proof of crash-safe storage. Epoch activation here is an already-authorized external decision. The assertions expose the assumptions the prose requires.

from dataclasses import dataclass, field
 
 
def eligible(replica_history, applied, session_history, wrote, observed):
    return replica_history == session_history and applied >= max(wrote, observed)
 
 
@dataclass
class FencedSink:
    epoch: int = 0
    values: dict = field(default_factory=dict)
 
    def activate(self, epoch):
        if epoch <= self.epoch:
            raise ValueError("activation must advance authority")
        self.epoch = epoch
 
    def write(self, epoch, key, value):
        if epoch != self.epoch:
            raise ValueError("writer is not the active authority")
        self.values[key] = value
 
 
assert not eligible("h1", 1230, "h1", 1240, 1200)
assert eligible("h1", 1250, "h1", 1240, 1200)
assert not eligible("h1", 1250, "h1", 1240, 1270)
assert not eligible("h2", 9999, "h1", 1240, 1270)
sink = FencedSink()
sink.activate(8)
sink.write(8, "balance", 100)
sink.activate(9)
try:
    sink.write(8, "balance", 0)
except ValueError:
    pass
else:
    raise AssertionError("obsolete writer accepted")
assert sink.values["balance"] == 100
sink.write(9, "balance", 90)
assert sink.values["balance"] == 90

The newer epoch is installed before accepting its writes. A lost reply to a valid write is a separate retry/idempotency problem: fencing rejects old owners, not duplicates from the current owner. A real sink must durably and atomically enforce the epoch check with the mutation, including after restart; this in-memory model intentionally has neither durability nor concurrent execution.

(d) Production reality · 15 min

Common failure modes to internalise

• Split-brain: a timeout is evidence of missing communication, not proof the old primary is dead. Fence old write authority before promotion. Majority election prevents two leaders in the same Raft term under its assumptions, not two processes believing themselves leader in different terms.
• Stale reads: a fixed sticky-primary period is a heuristic unless lag is bounded. Use an applied-position token or a correctly implemented strong-read path.
• Acknowledged loss: asynchronous replication permits a loss window if the only durable copy is destroyed. Synchronous acknowledgment narrows specified failure exposure; it does not survive every correlated disaster.
• Replica resource saturation: retention does not make replay faster. Check replay throughput, query contention and disk before adding identical followers.

Promotion exercise: two standbys are respectively 2 and 10 seconds behind when the primary becomes unreachable. What should the operator do? Answer: determine whether the primary is dead or partitioned, fence its writes, compare durable/replayed positions on compatible timelines, inspect archive or surviving WAL, and select the most advanced valid candidate. Do not blindly promote the “last replica.” Whether to wait for recovery or accept potential loss is an explicit RTO/RPO business decision. A synchronous configuration would help only if its required surviving data and promotion rules cover this failure.

Historical incident pointer

The original GitHub October 2018 post-incident analysis remains an optional failover-investigation pointer. Its current destination, full contents, original region-direction narrative, 22 GB figure, recovery duration and praise were not verified here. The promotion exercise teaches the retained question—where acknowledged writes survived and how the old writer is excluded—without presenting the old anecdote as an observed or freshly verified outage.

Where this shows up in the rest of the plan

Consistency models supplies the history tests. Sharding splits ownership while replication copies each partition. Multi-region extends failure domains; CDC consumes logical changes but does not automatically create a safe failover replica. CAP/PACELC supplies the failure-model frame; consensus (Paxos/Raft) supplies specific election/commit rules, not a guarantee derived from topology alone. In a feed design, distinguish following a user from a database follower: fan-out/log replication, display freshness and account mutations have separate contracts.

(e) Recall + stretch · 10 min

1. One sentence per topology? Single-leader orders writes at one authority; multi-leader accepts independent writes requiring conflict rules; leaderless contacts replica sets and reconciles their responses without one fixed write leader.
2. Sync versus async? Sync waits for explicitly defined remote acknowledgment; async can acknowledge before remote durability. The difference affects latency, availability and potential loss—not just a “safe/unsafe” label.
3. What does R+W>N guarantee? Intersection for fixed member sets. It does not by itself settle concurrent/failed writes, sloppy quorums, clocks or membership changes.
4. Read-your-writes versus monotonic reads? The first prevents a session falling behind its writes; the second prevents it falling behind its prior reads. Carry both position requirements on a common ordered history.
5. Are ordinary Cassandra quorums sufficient for a bank balance? Not for a separate read/compute/write invariant. Use supported conditional/lightweight transactions or an appropriate transaction design; specify scope and serial consistency. Do not call ordinary quorum access “near-linearizable.”
6. Why a slot? It retains needed WAL for its consumer, at potential disk cost. Check retention limits and invalidation, and rehearse rebootstrap.

Four original recall questions, answered explicitly

What is replication lag, and how can it break read-your-writes? Distinguish bytes not yet sent, received WAL not durably flushed, and durable WAL not applied. If the successful write is at position 1,240 but the chosen follower has applied only through 1,230 on the same history, a read may miss it. Wait for the token, use an eligible replica, or fail under a deadline; a guessed sticky-primary timer is not a proof.

What is split-brain, and what stops an obsolete writer? Two processes can each believe they are primary after a partition or pause. A quorum election chooses authority under its protocol assumptions; sink-enforced fencing or reliable isolation makes the old authority unable to write. Routing new traffic elsewhere does not cancel the old process's queued writes.

What if one of two async standbys is ten seconds behind? Compare both candidates and the durable/replayed WAL on compatible timelines, fence the old primary, and look for surviving/archive WAL before choosing. Ten seconds of sampled lag is not automatically ten seconds of irretrievable data loss. The promotion exercise above makes the RPO/RTO decision explicit; synchronous replication helps only for covered failures and a suitable surviving candidate.

Why prefer a real election protocol to “first node to boot wins”? Raft uses terms, majority votes and log restrictions; its election-safety statement is at most one elected leader in a given term. Its log-commit rules matter too. A stale leader from a previous term can still believe itself current, so external side effects still require the appropriate authority/fencing protocol. This is not an impossible-split-brain guarantee for arbitrary database deployments.

Collaborative editor exercise and answer

Choose content, permissions and presence replication independently. A CRDT-based content design can accept concurrent edits and merge according to its type, provided updates are eventually delivered and persisted. That does not make revoked users authorized to keep editing. Permission changes need a separately enforced authorization policy with a revocation boundary, perhaps a strongly ordered owner record. Presence can expire and tolerate missed updates. Yjs and Automerge remain optional CRDT-library exploration topics from the original exercise, not libraries implemented or validated by this fixture. This is a proposed architecture, not a claim about Google Docs, Notion or Figma internals.

Explain-out-loud test

Explain why a received acknowledgment differs from a replayed one, compute the 1,200 MB backlog and 150-second catch-up example, and describe what rejects epoch 8 after epoch 9 is active. Those answers demonstrate the mechanism rather than repeating topology names.

What comes next

Continue with consistency histories, where observable behavior—not replica count—determines the guarantee.

Hub: The 6-Month Learning Plan

Sources and review boundary

Full-body review renewed 2026-10-10, replaying the saved 2026-10-07 primary passages and their raw/canonical hashes. Mutable documentation is accepted only at that saved evidence boundary, not represented as freshly fetched current service behavior. Numerical examples are explicit teaching assumptions. The bounded Python examples were run locally; no cloud/distributed deployment, PostgreSQL cluster, broker, object store, load benchmark or regional drill was executed. Compilation and diagram parsing do not establish deployed-system correctness.

• PostgreSQL 16 warm standby — Asynchronous WAL shipping exposes acknowledged-state loss if the primary copy is destroyed before shipping.; Slots retain WAL at possible disk cost, while limits can trade away catch-up history.
• Pg Sync — remote_apply waits for replay/visibility on configured synchronous standbys.; A synchronous_commit value alone does not configure synchronous standby replication.; remote_write is weaker than remote durable flush for OS failure.
• Pg Monitor — pg_stat_replication lag intervals are not a catch-up ETA.
• Pg Failover — PostgreSQL failover needs old-primary exclusion.
• Pg Retain — wal_keep_size is not an exact maximum or immediate failure threshold.
• Pg Backup — pg_basebackup needs an authorized replication connection.; pg_basebackup -R prepares standby connection state.
• Cass Guarantees — Cassandra lightweight transactions have a different consistency contract from ordinary writes.
• Dynamo Paper — Dynamo uses multiple ring positions per physical node.
• Azure Cosmos DB consistency levels — Cosmos session reads carry a token and require a sufficiently advanced replica.
• Raft extended paper, 2014 — Raft election safety is term-scoped.