Leader/Follower — Replica-Lag Anomalies, Failover Data Loss, Log-Shipping & Raft Leader Completeness (Deep Dive)

Why the basic leader/follower story isn’t enough

A follower is not a live copy of the leader — it is a replay of the leader’s log running behind it by some lag ℓ. Almost every surprising bug in a leader/follower system, from a user not seeing their own write to a full-blown split-brain, is that one fact showing up somewhere you didn’t expect it. This page covers the gaps the base pattern lesson and the Raft mechanics lesson leave open: what lag ℓ does to reads, what happens when failover is a script instead of a vote, what “acked” really means under async replication, why Raft’s safety guarantee is a forced consequence rather than an assumption, and how the log itself gets shipped.

Reading from followers under replica lag: three anomalies

Every anomaly below reduces to the same mechanism: a follower's state at wall-clock time t is the leader's state at time t−ℓ. Route a read to the wrong follower at the wrong moment and you see the past — the only question is whose past, and whether it's consistent with what you saw a moment ago.

Two distinct violations are visible in that single trace:

• Read-your-writes violation (t=50ms): the client wrote a value and, on its very next read, does not see it — because that read landed on a follower that hasn't replicated the write yet.
• Monotonic-reads violation (t=50ms → t=100ms → t=150ms): the same client observes bio go “Engineer” → “Senior Engineer” → “Engineer”. Time appears to run backward, because each read was served by a different follower at a different point in its own replay of the log.

A third anomaly needs two causally related writes rather than one: consistent-prefix violation. Say a user posts a comment (write C1) and then replies to it (write R1); if C1 and R1 land on different shards/partitions with independent lag, a reader can observe R1 (“reply to C1”) on a shard that's caught up while C1's shard is still behind — seeing the effect (the reply) before its cause (the comment) exists at all.

Mitigations

• Read-your-writes: sticky routing (send that client's reads to the leader, or to the same replica it wrote through, for a short window after a write) or a version token — the client remembers the LSN of its last write and the router only picks a replica whose applied-LSN is ≥ that token.
• Monotonic-reads: pin a client/session to one replica for the session's lifetime (session affinity) so its own view of the log only ever moves forward, even if that replica is behind others.
• Consistent-prefix: route causally related writes to the same shard/partition, or carry causal metadata (a dependency/vector clock) so a reader is only shown an effect once its cause is also visible.

Split-brain under externally-orchestrated failover

The base pattern lesson already distinguishes self-organizing consensus (Raft-style, term-based) from externally-orchestrated failover (Patroni, Orchestrator, MHA). The second case has no term/epoch of its own — the orchestrator watches health and issues a promote command, and a promote command creates a new leader without necessarily silencing the old one. That gap is where split-brain lives.

1. Leader L1 hits a long GC pause (or a network blip). It is not dead — it's alive, holding its socket — but it stops answering health checks.
2. The orchestrator's health check to L1 times out three times in a row and declares it dead. It promotes follower F2, which starts accepting writes as the new leader.
3. L1's GC pause ends a moment later. It resumes exactly where it left off. Because there's no consensus term for it to check against, it has no way to know a new leader now exists — and it keeps accepting writes from any client whose connection pool or stale DNS entry still points at it.
4. Now two nodes, L1 and F2, both believe they are the leader and both accept writes. Two clients writing the “same” record diverge with no reconciliation rule — classic dual-primary split-brain.

The root cause: “detected as dead” and “actually stopped” are not the same event once there's no vote/term to enforce it. Two fencing mechanisms close that gap:

• Fencing tokens: a monotonically increasing number handed out on every promotion — the orchestrator's bolted-on substitute for Raft's term. Any downstream system in the write path (shared storage, a lock service, the database itself) rejects a write carrying a lower token than the highest one it has already seen, so L1's writes — still carrying the old token — get rejected the instant F2's higher token shows up anywhere.
• STONITH (shoot the other node in the head): instead of merely assuming L1 is dead, the orchestrator actively kills or isolates it on promotion — power it off, revoke its network access, revoke its storage lease. This removes the “GC-paused but still alive” case entirely: L1 is now physically unable to serve traffic.

Without one of these, a promote command is a wish, not a guarantee.

Failover data loss and log divergence

Under asynchronous replication, “acked to the client” and “durable on a majority” are two different events — the leader can ack a write the instant it appends to its own log, before any follower has seen it. That gap is exactly where failover data loss lives, and it produces a second problem on top: a diverged log that has to be reconciled, not merged, when the old leader comes back.

Loss: leader L1's log holds LSN 100 (replicated), then 101 (qty=5) and 102 (qty=3) — both acked to their clients the moment L1 wrote them locally, before either reached follower F, whose replicated position is still 100. L1 crashes. F is promoted; its log tops out at 100. LSNs 101 and 102 are gone — not delayed, gone — because they were never durable anywhere but L1's now-dead disk. The client was told “success” for writes that no longer exist in the system.

Rejoining and divergence: L1 restarts and rejoins as a follower. It still has its own 101 (qty=5) and 102 (qty=3) sitting in its local log — entries the new leader F never saw. Meanwhile F, since being promoted, has taken its own fresh writes at those same positions: 101′ (qty=8), 102′ (qty=2). Same LSNs, two different entries — the logs have diverged at position 101.

L1 cannot simply keep its own 101/102 and append F's on top — that would create two different, simultaneously “true” histories of what happened at position 101, which defeats the entire reason leader/follower exists: a single, unambiguous order of writes. Instead L1 must truncate — discard its own divergent tail back to the last point of agreement (LSN 100) — and then replay F's log forward from there. Its own acked-but-unreplicated 101/102 are not merged in; they are deleted. Why not replay them instead of discarding? Because F's log is the one with quorum backing going forward, while L1's extra entries were never acknowledged by a majority — from the system's point of view they never durably happened. Replaying them would silently splice un-quorumed history into a quorumed log, which is exactly the conflict leader/follower replication exists to prevent in the first place.

Raft Leader Completeness — derived, not assumed

The Raft mechanics lesson states that “the election rule guarantees a new leader already has [every committed entry]” — here is why that's true, not just that it is. The formal property (Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm): if an entry is committed in a given term, it is present in the logs of every leader of every higher-numbered term. It falls directly out of two rules Raft already has for other reasons, stacked together:

1. The up-to-date check in RequestVote. A follower grants its vote to a candidate only if the candidate's log is at least as up to date as its own — compared first by the term of the last log entry, then, if those tie, by log length. A voter with a “better” log refuses to vote for a candidate with a “worse” one.
2. Quorum overlap. Both committing an entry and winning an election require a majority of the same N nodes. Any two majorities drawn from the same N nodes must share at least one node — there just aren't enough nodes left for two disjoint majorities to exist.

Traced: the majority-intersection argument

Take N=5 nodes {A, B, C, D, E}.

1. Entry X is committed in term 3: term-3's leader (A) appended X and replicated it to a majority — say {A, B, C} (3 of 5). “Committed” means exactly this: durable on a majority.
2. Later, a term-4 election happens. Any winning candidate needs votes from a majority — say candidate D wins with votes from {C, D, E} (3 of 5).
3. Both {A, B, C} and {C, D, E} are 3-of-5 subsets of the same 5 nodes. By the pigeonhole principle (3 + 3 − 5 = 1), they must share at least one node. Here that node is C.
4. C is in both majorities: C has X in its log (from step 1, as one of the committers) and C voted for D (from step 2, as one of the electors).
5. But rule 1 (the up-to-date check) says C only grants its vote to D if D's log is at least as up to date as C's own. C's log contains X. For D's log to be “at least as up to date” as one that already contains X, D's log must also contain X — a candidate missing a committed entry is by definition less up to date than a voter who has it, so that voter would refuse it.
6. Therefore D, the new term-4 leader, is guaranteed to already have X. It never had to be told about it, discover it, or reconstruct it — the guarantee is a forced consequence of “commit needs a majority” + “election needs a majority” + “voters refuse a worse log,” not an extra mechanism bolted on top.

This is also why the log-divergence rollback from the previous section only ever runs in one direction. A rejoining old leader or follower can have extra, uncommitted entries that must be truncated — but a newly elected Raft leader can never be missing a committed entry, so it never needs the reverse repair.

Log-shipping mechanisms: a design axis

How the leader ships the log to a follower decides what a follower actually is — a re-execution of the same commands, a byte-for-byte copy of the storage engine's internals, or an independent database applying row-level deltas. Three mechanisms, in increasing order of decoupling from the leader's storage engine (Kleppmann, DDIA, ch. 5):

• Statement-based. The leader ships the literal write statement (“UPDATE orders SET qty = qty - 1 WHERE id = 42”) and the follower re-executes it. Very compact — one line ships an update of any size — but it breaks the instant a statement is non-deterministic: NOW(), RAND(), auto-increment counters, or a trigger that reads another table can all produce a different result when “the same” statement runs again later on the follower. This is why MySQL's original statement-based replication mode was mostly abandoned in favor of row-based.
• WAL / physical. The leader ships the low-level bytes it's already writing to its own write-ahead log — disk-block-level changes. Deterministic by construction (it's literally the same bytes, replayed) and cheap to produce, but it ties the follower to the exact same storage-engine version and format as the leader: you cannot use it to replicate into a different engine, and you can't do a zero-downtime major-version upgrade this way, since a follower on a newer WAL format can't parse the older bytes (or vice versa). Postgres physical (streaming) replication works this way.
• Logical / row-based. The leader ships a decoded, engine-independent description of the change (“table orders, row with PK=42: qty 5→4”), decoupled entirely from the storage engine's internal byte format. This is what enables heterogeneous replicas — a different engine or version on the follower side — rolling/zero-downtime upgrades, and change data capture (CDC) pipelines feeding Kafka or an analytics store. It costs more to produce and apply than raw WAL bytes and needs the source schema to expose a stable row identity. Postgres logical replication, MySQL row-based binlog, and Debezium-style CDC are all this.

When each is right: statement-based only if every statement in the workload is provably deterministic (rare enough that it's mostly a historical footnote today); WAL/physical for a same-engine, same-version HA pair — the cheapest, most faithful option when that's all you need; logical/row-based the moment you need a different consumer on the other end — CDC, an analytics replica, a heterogeneous database, or an upgrade you can't afford to do as a hard cutover.

Pitfalls

• Trusting “the follower will catch up eventually” without bounding staleness — silently serving arbitrarily stale reads to whoever gets routed to the slowest replica.
• Treating a health-check timeout as proof the old leader stopped. In externally-orchestrated failover, without fencing tokens or STONITH, a promote decision and split-brain are the same event, not a hypothetical risk.
• Replaying a rejoined old leader's divergent tail instead of truncating it — this silently forks the log's history rather than reconciling it.
• Picking statement-based log shipping without auditing every write for determinism — a single NOW() or auto-increment desyncs replicas with no error raised anywhere.
• Assuming Raft's Leader Completeness protects a non-Raft system. The guarantee is a consequence of Raft's own commit-quorum-and-election-quorum coupling; a Patroni/Postgres pair or an async MySQL replica gets no such guarantee unless synchronous replication is explicitly turned on.

Judgment layer

Synchronous vs. asynchronous replication

Synchronous replication guarantees no acked write is ever lost on failover, at the cost of write latency including a round trip to at least one follower and reduced write availability — a slow or unreachable follower stalls every write. Asynchronous replication gives low, predictable write latency at the cost of a data-loss window exactly the size of “whatever was acked but not yet replicated” when the leader dies. A named alternative that sits between the two: Raft-style consensus with a quorum commit — commit is majority-durable (so nothing acked is ever lost) without waiting on one specific, fixed follower (any majority will do, so one slow node doesn't stall writes) — at the cost of running a full consensus protocol (leader election, term bookkeeping) instead of a single leader-to-follower ack.

Which log-shipping mode

Default to WAL/physical for a straightforward same-engine HA pair — it's the cheapest and most faithful option when the follower is just a hot standby of the same engine and version. Move to logical/row-based the moment you need a different kind of consumer on the other end: CDC into an event stream, an analytics-only replica, or a major-version upgrade you need to do without a hard cutover. Avoid statement-based unless every statement in the workload has been specifically audited for determinism — the failure mode (silent divergence) has no error to catch it.

Takeaways

• Every replica-lag anomaly is the same root cause wearing a different hat — a follower is the log at (leader's time − lag) — and the fix is always either pin the reader (sticky routing / session affinity) or stamp the write (a version token the router checks against).
• Externally-orchestrated failover has no term or epoch by default, so “detected dead” is never automatically “actually stopped.” Fencing tokens and STONITH aren't optional hardening — they are the only thing standing between a promotion and split-brain.
• Async replication acks before durability; a rejoining old leader's extra entries were never quorum-backed, so they are truncated, not replayed — that's the actual mechanism behind “failover can lose data,” not just a hand-wave.
• Raft's Leader Completeness isn't a promise you take on faith — it's the forced consequence of “commit needs a majority” + “election needs a majority” + “a voter refuses a worse log,” all riding on the same quorum-overlap guarantee that also rules out split-brain.

Re-authored/Deepened for this guide, drawing on Martin Kleppmann's Designing Data-Intensive Applications (Ch. 5, “Replication”) and Diego Ongaro & John Ousterhout, “In Search of an Understandable Consensus Algorithm” (Raft, 2014); diagrams hand-authored (SVG) for this guide.