Replication Strategies (Leader-Follower, Multi-Leader, Leaderless)

1. What Is It?

Replication is the practice of keeping copies of the same data on multiple machines. It serves three purposes: high availability (if one node fails, others serve traffic), read scalability (distribute reads across replicas), and reduced latency (place replicas geographically close to users).

The fundamental challenge of replication is handling writes: when the same data exists on multiple machines, how do you ensure they stay consistent? The three main replication strategies answer this differently:

• Single-leader (leader-follower): One node accepts all writes. Simpler, but the leader is a write bottleneck.
• Multi-leader: Multiple nodes accept writes. More available, but writes can conflict.
• Leaderless: Any node accepts reads and writes. Maximum availability and write throughput, but requires quorum coordination and conflict resolution.

2. How It Works

Strategy 1: Single-Leader (Leader-Follower) Replication

All writes go to the leader (also called primary, master). The leader replicates changes to followers (replicas, standbys) via a replication log. Reads can go to any replica.

-+ResetFullscreen

A WAL (Write-Ahead Log) is a sequential file that records every database write before it's applied to the main data files. In replication, the leader streams its WAL to followers so they can replay the same writes.

Synchronous vs Asynchronous Replication:

PostgreSQL streaming replication is the canonical leader-follower implementation. The primary sends a continuous stream of WAL (Write-Ahead Log) records to standbys via the replication protocol. Each standby tracks its position using the Log Sequence Number (LSN). Same-region async lag is typically sub-100ms; cross-region can reach seconds.

Replication lag and consistency problems:

Timeline:
t=0:  Write "user.email = alice@new.com" → Leader
t=0:  Leader confirms write to client
t=1s: Follower still showing "alice@old.com" (lag = 1s)

Problem 1: Read-your-writes violation
  User writes email change → leader (t=0)
  User immediately reads profile → routed to follower (t=0.5s)
  Follower shows OLD email → "my change wasn't saved!"

Problem 2: Monotonic reads violation
  First read → Follower 1 (lag=0s) → shows new post
  Second read → Follower 2 (lag=5s) → post doesn't exist yet
  "The post I just read has vanished!"

Fix: Route user's reads to the leader (or the specific follower they wrote to)
     for at least N seconds after a write.

Failover:

1. Followers detect leader failure via missed heartbeats (timeout: typically 3–10s)
2. Election: followers vote, require a quorum (a majority of nodes — e.g. 2 of 3 — that must agree before a decision is made); Raft uses randomized 150–300ms election timeouts
3. Winning follower promotes to leader; clients re-discover via load balancer or ZooKeeper
4. Total failover time in production: typically 6–20 seconds

Split-brain risk: A partitioned old leader that's still alive may accept writes simultaneously with a newly elected leader → data divergence. Prevention: require strict quorum (minority partition rejects writes) + STONITH (Shoot The Other Node In The Head — forcibly fence the old leader).

Strategy 2: Multi-Leader (Active-Active) Replication

Multiple nodes accept writes independently. Changes replicate to all other leaders asynchronously.

-+ResetFullscreen

Write conflicts: When Client A updates record X to "Alice" via Leader 1, and Client B simultaneously updates the same record X to "Bob" via Leader 2, both writes succeed locally. When they replicate to each other, there's a conflict: who wins?

Conflict resolution strategies:

CRDTs in production: Riak's CRDT implementation powers League of Legends' chat service at 7.5 million concurrent users, using G-Counter (grow-only counter) and OR-Set (observed-remove set) CRDTs.

Multi-leader use cases:

• Multi-datacenter replication (each datacenter has its own leader)
• Offline-first mobile applications (device is its own leader while offline; syncs when reconnected — CouchDB uses this model)
• Collaborative editing (Google Docs uses OT/CRDT to handle simultaneous edits to the same document)

Strategy 3: Leaderless (Dynamo-Style) Replication

No designated leader. Clients write to and read from multiple nodes simultaneously. Any node can accept any request.

-+ResetFullscreen

Quorum reads and writes (W + R > N):

N = 3 replicas for key K
W = 2 (need 2 ACKs before confirming write)
R = 2 (need 2 responses for a read)

W + R = 4 > N = 3

Overlap guarantee: at least 1 node in every read set has seen the latest write
→ Strong consistency: always read the most recent write

If W=1, R=1: 1+1=2 ≤ 3 → eventual consistency (fast, but may return stale data)
If W=3, R=1: 3+1=4 > 3 → strong consistency (every replica acknowledged the write)

Read repair: When a client reads from multiple nodes and detects version discrepancies (one node has old data), it writes the newer version back to the stale nodes. Happens synchronously at read time.

Anti-entropy: Background process that continuously scans replicas for divergences (using Merkle trees to efficiently compare large datasets) and synchronizes missing data. Unlike log-based replication, anti-entropy doesn't preserve write order — it just ensures eventual convergence.

Hinted handoff: If a node is temporarily unreachable when a write occurs, another node temporarily stores the write with a "hint" — when the target node recovers, the hint is replayed. Improves availability at the cost of brief inconsistency.

Version tracking with vector clocks:

Initial: key X = "" at all nodes
         VC = [N1=0, N2=0, N3=0]

Write "alice" from Client A via N1:
  N1: X="alice", VC=[N1=1, N2=0, N3=0]

Concurrent write "bob" from Client B via N2:
  N2: X="bob", VC=[N1=0, N2=1, N3=0]

N1 and N2 replicate to each other:
  N1 VC=[N1=1, N2=0] vs N2 VC=[N1=0, N2=1]
  Neither dominates the other → CONFLICT
  Both values preserved as siblings → application resolves

Comparison Table

3. When to Use It (and When NOT To)

Use Single-Leader When:

• Simplicity and strong consistency are the priority: Single-leader provides the strongest consistency guarantee (synchronous mode), and conflict-free write ordering simplifies application logic.
• Read-heavy workload: Many follower replicas serve reads; one leader handles all writes. 90% of web apps fit this pattern.
• ACID transactions are required: Multi-leader and leaderless make cross-node transactions much harder; single-leader keeps transaction scope local to the leader.
• Operational simplicity matters: Managed databases (RDS, Cloud SQL) all default to single-leader; well-understood failure modes.

Use Multi-Leader When:

• Multi-datacenter active-active: Low write latency in each region (writes don't cross the WAN). Essential when a single-leader in Region A would add 100+ ms to every write from Region B.
• Offline-first clients: Mobile apps that need to function without connectivity. Each device is its own "leader"; syncs when online (CouchDB's model).
• Collaborative real-time editing: Multiple users editing the same document simultaneously. CRDTs or OT (Operational Transformation) handle merging.

Use Leaderless When:

• Maximum availability is required: No single point of failure; can tolerate multiple node failures while still accepting writes (as long as W nodes are reachable).
• High write throughput at global scale: Cassandra, DynamoDB — write to the nearest node, replicate asynchronously.
• Tunable consistency: Different operations in the same system can use different quorums (e.g., financial reads use W=3,R=3; analytics reads use W=1,R=1).

Anti-Patterns:

• Using async single-leader and routing all reads to followers: You will violate read-your-writes consistency. Users will see their changes "disappear." Always route post-write reads back to the leader (for a configurable window).
• Multi-leader without conflict resolution: Silent LWW data loss is worse than no multi-leader. Design conflict resolution before enabling multi-leader.
• Leaderless with W=1: Tuning for maximum write speed at the cost of consistency. Fine for analytics; dangerous for user-visible data.
• Assuming replicas are fully in sync: Replication lag is real. Never make business decisions (e.g., "deduct inventory") based on a replica read without ensuring it's reading from the quorum.

4. Real-World Usage

PostgreSQL — Streaming Replication (Single-Leader)

PostgreSQL uses physical streaming replication: the primary sends WAL records to standbys via a replication connection. Standbys replay WAL to stay current. The synchronous_standby_names config option controls whether any standbys are synchronous (wait for ACK before confirming write) — enabling semi-synchronous mode for critical data. Organizations like GitLab run PostgreSQL with one synchronous standby for durability + multiple async standbys for read scaling.

Cassandra — Leaderless (Dynamo-Style)

Cassandra's leaderless design comes directly from Amazon's Dynamo paper. Each key is replicated across N nodes determined by consistent hashing. Clients use a "coordinator" node (any node can be coordinator) that fans out writes to the N replica nodes. Tunable consistency lets teams choose their CP/AP tradeoff per query: QUORUM for financial operations, LOCAL_ONE for analytics. Cassandra's gossip protocol handles anti-entropy between nodes, and hinted handoff handles temporary node unavailability.

CouchDB — Multi-Leader with MVCC

CouchDB implements multi-leader replication for its "offline-first" use case. Each CouchDB instance is an independent leader. Replication is bidirectional and explicit: you trigger replication between instances. Conflicts are detected and stored as document revisions — the application code chooses the winner or merges. This model enables mobile apps that store data locally in CouchDB and sync to a central server when connectivity is available.

5. Interview Cheat Sheet

5 Sentences to Show Deep Understanding

1. "Single-leader replication eliminates write conflicts by funneling all writes through one node — the trade-off is a write throughput ceiling and a single point of failure, mitigated by failover automation (Raft/Paxos leader election) and async replication for low-latency writes at the risk of replication lag."

2. "Replication lag creates three consistency anomalies in async single-leader replication: read-your-writes violations (user reads a replica that hasn't received their write yet), monotonic reads violations (user reads from two replicas at different lag depths), and causality violations — all solvable by routing reads to the leader for a short window after writes."

3. "Multi-leader replication makes write conflicts unavoidable — when two leaders independently accept conflicting writes to the same key, there's no global write ordering to determine which is 'correct.' The safest conflict resolution is CRDTs (mathematically conflict-free data structures); the most common is Last-Write-Wins (LWW), which silently discards concurrent writes."

4. "Leaderless quorum W+R>N guarantees that any read set overlaps with at least one node from the write quorum — with N=3, W=2, R=2: any 2-node read set and any 2-node write set must share one node, ensuring the latest write is always visible. Setting W+R ≤ N gives eventual consistency with faster reads and writes."

5. "Vector clocks detect concurrent writes in leaderless systems: if neither [N1=1, N2=0] dominates [N1=0, N2=1], the writes were concurrent — both values are preserved as 'siblings' and the application must reconcile them. This explicit conflict surfacing is more correct than silently picking a winner with LWW."

Common Follow-Up Questions

Q: How does PostgreSQL replication failover work and how long does it take? A: (1) Followers stop receiving heartbeats from the primary; after a configurable timeout (typically 3–10s), they declare the primary dead. (2) Patroni/repmgr/pg_auto_failover (HA tools) elect a new primary — the candidate with the most recent WAL position wins. (3) Other standbys reconfigure to follow the new primary. (4) Load balancer or DNS update points clients to the new primary. Total time: typically 6–20 seconds including detection + election + client reconnection.

Q: What is the "tombstone" problem in leaderless systems? A: When you delete a record in a leaderless system, you can't just remove the data — if a replica missed the delete (due to lag), the next anti-entropy sync would restore the deleted record. Instead, a "tombstone" marker is written that signals deletion. Anti-entropy then propagates the tombstone. The problem: tombstones accumulate indefinitely unless compacted. Cassandra's compaction process removes tombstones after a configurable gc_grace_seconds (default: 10 days), after which the old deleted values are guaranteed to have been replicated.

Q: When would you choose multi-leader over single-leader? A: Multi-leader shines when write latency across WAN is unacceptable. Example: a globally distributed app with users in US, EU, and APAC. With single-leader in US, EU and APAC writes cross the Atlantic/Pacific (100–200ms one-way). With multi-leader, each region has a local leader, writes complete in <10ms locally, and regions sync asynchronously. The cost is conflict resolution complexity. Business logic that requires global sequential ordering (e.g., sequential ticket numbers, bank transfers) should stay single-leader despite the latency.

Q: How does Cassandra handle a node failure during a write? A: Hinted handoff: if one of the W target replicas is unreachable, the coordinator temporarily stores the write with a "hint" — a record saying "deliver this write to Node X when it comes back." When Node X recovers, the coordinator replays the hint. This maintains availability (the write succeeds as long as W nodes respond, even if the originally targeted node is down) at the cost of brief inconsistency on Node X until the hint is replayed.

Connections to Other Building Blocks

• CAP Theorem & PACELC: Replication strategy directly determines CAP/PACELC position. Single-leader sync = CP (PC/EC); leaderless with W=1,R=1 = AP (PA/EL); leaderless with W+R>N = CP.
• Consensus (Raft/Paxos): Leader election in single-leader systems uses Raft/Paxos. These consensus protocols are what makes failover safe (prevents split-brain by requiring majority quorum).
• Sharding & Partitioning: Replication and sharding are orthogonal: sharding splits data across nodes (partition by key), replication copies each partition to multiple nodes. Every shard has its own replication group.
• Write-Ahead Log (WAL): PostgreSQL streaming replication works by shipping WAL records from primary to standbys. The WAL is both the durability mechanism and the replication mechanism.
• Distributed Locking: Multi-leader systems need distributed locks or CRDTs to handle concurrent writes safely. Leaderless systems need quorum coordination.