Replication Topologies: Leader-Follower, Multi-Leader, Leaderless

TL;DR. Replication topology decides who can accept writes and how those writes reach other replicas. Single-leader serializes all writes through one node for simple consistency but caps write throughput and adds failover risk. Multi-leader allows concurrent writes at multiple nodes for geo-distributed low latency but forces you to solve conflict resolution. Leaderless (Dynamo-style) removes the leader entirely for maximum availability but demands quorum math and anti-entropy. Default to single-leader with async replication unless you need multi-region writes (per-range-leader hybrid) or availability-first semantics (leaderless). The sync/async dimension is orthogonal: it controls durability guarantees, not topology¹.

Learning Objectives

• Compare single-leader, multi-leader, leaderless, and per-range-leader topologies across latency, consistency, availability, and operational complexity.
• Identify the workload characteristics (geo-distribution, write ratio, consistency needs) that determine the correct topology.
• Justify the per-range-leader hybrid as the default for global OLTP needing strong consistency.
• Evaluate DynamoDB’s evolution from leaderless to single-leader-per-partition and explain why Amazon made that shift.

The Core Trade-off

The fundamental tension: as you allow more nodes to accept writes, write latency drops and availability rises, but consistency becomes harder to maintain. A single-leader topology serializes all writes through one node, giving you a total order for free. Multi-leader and leaderless topologies accept writes at multiple nodes simultaneously, which means concurrent conflicting writes are possible and the system must reconcile them.

Orthogonal to topology is the sync/async dimension. Synchronous replication waits for follower acknowledgment before confirming a write. PostgreSQL benchmarks show synchronous-apply mode incurs roughly 50% write throughput penalty compared to async¹. Asynchronous replication confirms immediately on the leader, risking data loss if the leader fails before replication completes. These two axes (topology and timing) combine into six meaningful configurations; three dominate production systems.

flowchart LR
    subgraph "Write acceptance"
        SL["Single-Leader<br/>1 writer"]
        ML["Multi-Leader<br/>N writers"]
        LL["Leaderless<br/>any replica writes"]
    end
    subgraph "Propagation timing"
        Sync["Synchronous<br/>wait for ACK"]
        Async["Asynchronous<br/>fire and forget"]
    end
    SL --- Sync
    SL --- Async
    ML --- Async
    LL --- Async

Side-by-Side Comparison

The table misleads on “leaderless availability.” Sloppy quorums and hinted handoff let writes succeed even when the preferred replicas are down, but the resulting data may diverge and require reconciliation³. High availability is not free; it is paid in reconciliation complexity.

The “conflict resolution” row dominates the decision. If your team cannot invest in CRDT design or application-level merge logic, multi-leader and leaderless topologies will produce silent data loss via last-writer-wins⁶.

When to Pick Single-Leader

OLTP with strong consistency requirements. Bank ledgers, inventory systems, seat reservations. A single writer provides a total order without conflict resolution. PostgreSQL streaming replication and MySQL semi-sync are battle-tested for this pattern⁴.

Read-heavy workloads needing scale-out. Async followers serve reads. TimescaleDB/PostgreSQL benchmarks show 2.5x read throughput with 3 nodes and 4.8x with 5 nodes¹. The primary handles all writes; followers absorb read traffic.

Single-region deployments. When all clients are within one region, the latency penalty of routing writes to a single leader is negligible (1-5 ms same-AZ). The simplicity of a single writer outweighs any theoretical availability gain from multi-leader.

Named systems: PostgreSQL with Patroni, MySQL with Group Replication, Amazon RDS Multi-AZ, Aurora (storage-level quorum but single compute writer)⁸.

When to Pick Leaderless

Availability-first workloads tolerating eventual consistency. Shopping carts, session stores, time-series telemetry. Cassandra with LOCAL_QUORUM delivers low single-digit millisecond p99 writes in multi-region deployments². Any replica can serve any request; no failover needed.

Tunable consistency per operation. The same Cassandra cluster can serve ONE consistency for analytics queries and QUORUM for user-facing reads. This per-query flexibility is a distinctive strength of leaderless systems².

Write-heavy workloads with independent keys. When writes rarely conflict (distinct user sessions, IoT sensor data), the reconciliation cost is low and the write distribution benefit is high.

Named systems: Apache Cassandra, ScyllaDB, Amazon DynamoDB (original Dynamo paper³), Riak.

The Hybrid Path

Most production systems needing global strong consistency use the per-range-leader pattern: partition data into ranges, elect a consensus leader per range via Raft or Paxos, and place leaders near traffic sources.

CockroachDB divides the keyspace into ranges (default 512 MiB range_max_bytes), each replicated 3 times as an independent Raft group¹¹¹². Large clusters run tens of thousands of consensus groups¹³. Spanner uses Paxos per shard with TrueTime for external consistency, absorbing clock uncertainty of typically 1-7 ms via commit-wait¹⁴.

The result: globally it looks like multi-region active-active (any region can serve writes for its local ranges). Per-range it is classic leader-follower with consensus. You get strong consistency plus regional write locality without application-level conflict resolution.

flowchart TD
    subgraph "Region US-East"
        R1L["Range 1: Leader"]
        R2F["Range 2: Follower"]
        R3F["Range 3: Follower"]
    end
    subgraph "Region EU-West"
        R1F["Range 1: Follower"]
        R2L["Range 2: Leader"]
        R3F2["Range 3: Follower"]
    end
    subgraph "Region AP-South"
        R1F2["Range 1: Follower"]
        R2F2["Range 2: Follower"]
        R3L["Range 3: Leader"]
    end
    R1L <-->|"Raft"| R1F
    R1L <-->|"Raft"| R1F2
    R2L <-->|"Raft"| R2F
    R2L <-->|"Raft"| R2F2
    R3L <-->|"Raft"| R3F
    R3L <-->|"Raft"| R3F2

Real-World Examples

Amazon DynamoDB peaked at 89.2 million requests/sec during Prime Day 2021 with single-digit millisecond latency⁹. The original 2007 Dynamo paper described a leaderless system with consistent hashing and vector clocks³. In production, only 0.06% of Dynamo reads returned divergent (multiple) versions; 99.94% returned a single consistent version³. By 2022, DynamoDB had evolved to Multi-Paxos per partition for stronger consistency guarantees¹⁰. The metadata cache achieves 99.75% hit rate, but the backing store is always provisioned for full traffic to eliminate metastable failure modes⁹.

Amazon Aurora uses 6-way replication across 3 AZs with a write quorum of 4/6 and read quorum of 3/6⁸. Storage is segmented into 10 GB Protection Groups, each independently replicated. A failed segment repairs in under one minute on a 10 Gbit network⁸. This design tolerates losing an entire AZ without losing write availability.

CockroachDB runs tens of thousands of Raft groups in large clusters¹³. The leaseholder mechanism separates read coordination from Raft leadership: one replica per range handles all reads and writes without a full consensus round for reads¹¹. Cross-range transactions use two-phase commit over Raft, adding latency influenced by the number of ranges touched¹¹.

Common Mistakes

Decision Checklist

• Does the workload need writes from multiple regions with sub-50 ms latency? If yes, single-leader is out; choose per-range-leader (strong) or multi-leader (eventual).
• Is zero data loss on failover a hard requirement? If yes, synchronous replication to quorum is mandatory.
• Can you articulate a conflict resolution strategy (LWW, CRDTs, app-merge)? If not, avoid multi-leader and leaderless.
• What is the read:write ratio? Heavy-read with tolerance for seconds of lag favors async leader-follower for read scale-out.
• Does the system need per-operation tunable consistency? Leaderless (Cassandra) or per-range-leader (CockroachDB) support this; pure leader-follower does not.
• Is failover automated (Raft, Patroni) or manual? Manual failover with async replication guarantees data loss.

flowchart TD
    Start["New system design"]
    Q1{"Multi-region<br/>write locality needed?"}
    Q2{"Strong consistency<br/>required?"}
    Q3{"Can you build<br/>conflict resolution?"}
    Q4{"Zero data loss<br/>on failover?"}
    SL_Sync["Single-Leader (sync)<br/>PostgreSQL + Patroni"]
    SL_Async["Single-Leader (async)<br/>Read replicas"]
    PRL["Per-Range-Leader<br/>CockroachDB / Spanner"]
    ML["Multi-Leader<br/>CouchDB / custom"]
    LL["Leaderless<br/>Cassandra / ScyllaDB"]
    Start --> Q1
    Q1 -->|no| Q4
    Q4 -->|yes| SL_Sync
    Q4 -->|no| SL_Async
    Q1 -->|yes| Q2
    Q2 -->|yes| PRL
    Q2 -->|no| Q3
    Q3 -->|yes| ML
    Q3 -->|no| LL

Key Takeaways

• Single-leader is the correct default for single-region OLTP. It provides a total order without conflict resolution and scales reads via async followers.
• Multi-leader solves geo-distributed write latency but forces you to solve conflict resolution. If you cannot build the merge logic, do not pick this topology.
• Leaderless maximizes availability and write distribution but requires quorum math, anti-entropy, and reconciliation. DynamoDB itself moved away from pure leaderless to Multi-Paxos per partition¹⁰.
• The per-range-leader hybrid (CockroachDB, Spanner) is the modern answer for global OLTP: strong consistency plus regional write locality without application-level conflicts.
• Sync vs async is orthogonal to topology. It controls durability, not who accepts writes. Choose sync for zero-data-loss failover; accept the 50% throughput cost¹.

Further Reading

• Amazon DynamoDB USENIX ATC 2022: how DynamoDB evolved from leaderless Dynamo to Multi-Paxos per partition; the definitive case study in topology migration.
• Amazon Aurora: Quorums and Correlated Failure: why Aurora chose 6-copy quorum over simpler 2/3 models; essential reading for storage-layer replication.
• CockroachDB: The Resilient Geo-Distributed SQL Database, SIGMOD 2020: per-range Raft at scale with tens of thousands of consensus groups.
• High Availability and Scalable Reads in PostgreSQL, Timescale 2024: concrete benchmarks comparing sync, async, and standalone PostgreSQL throughput.
• Chain Replication for Supporting High Throughput and Availability, OSDI 2004: the chain replication paper; relevant for understanding Azure Storage and HDFS pipelines.
• MySQL Semi-Sync: Durability, Consistency, and Split Brains: practical analysis of semi-sync failure modes and split-brain scenarios.

Flashcards

References