Database Replication: Keeping Copies in Sync

TL;DR: Replication keeps N copies of your data on N nodes so reads scale out and a single failure does not lose data. Single-leader with semi-sync replication is the default for most OLTP workloads. Reach for multi-leader or leaderless only when you have proven geo-latency needs. The hard part is not copying bytes; it is failover without split-brain. GitHub learned this when a 43-second network partition caused 24 hours of recovery and up to 954 unreconciled writes on a single cluster¹. Every replication decision is a separable choice (topology, sync mode, failover policy, multi-region) with measurable consequences.

Learning Objectives

After this module, you will be able to:

• Distinguish leader-follower, multi-leader, and leaderless replication
• Choose sync vs async replication based on durability and latency requirements
• Reason about replication lag and its impact on read-your-writes
• Design a failover procedure that avoids split-brain
• Understand tunable consistency (R + W > N) in leaderless systems
• Explain how Aurora’s 4-of-6 quorum and Spanner’s Paxos groups differ in practice

Intuition

Imagine you run a chain of bank branches. Each branch keeps a ledger. At the end of the day, every branch sends its new entries to headquarters, which reconciles them and ships the combined ledger back overnight.

This works until two branches approve conflicting loans to the same customer on the same day. Now headquarters has a conflict it cannot resolve without calling both branch managers. That is multi-leader replication with last-write-wins, and it silently loses data.

A safer model: one branch is the “main office.” All loan approvals go there. The other branches get read-only copies of the ledger, updated every few minutes. If the main office burns down, you promote the branch with the freshest copy. But during the promotion, nobody can approve loans. That gap is your failover window.

The tension between “every branch can approve loans” (availability, low latency) and “only one branch approves loans” (consistency, no conflicts) is the fundamental trade-off in database replication. Every topology you will learn in this chapter is a different answer to that tension.

Theory

Why replicate

You replicate for four reasons, and they are separable:

1. Durability. If the primary’s disk dies, a replica has the data. Without replication, you rely on backups with a recovery point measured in hours.
2. Availability. If the primary process crashes, a replica can take over in seconds rather than the minutes a cold restore requires.
3. Read scaling. Route read queries to replicas. Read throughput scales linearly with replica count².
4. Geo-latency. Place a replica in Singapore so users there read local data instead of crossing the Pacific to us-east-1.

These four goals pull in different directions. Durability wants synchronous writes to at least one replica. Read scaling wants many async replicas. Geo-latency wants replicas far away, which makes synchronous writes expensive. Every replication design is a weighted combination of these four.

Topologies

flowchart LR
    subgraph SL["Single-leader (Postgres, MySQL)"]
        C1[Client] -->|write| L1[Primary]
        L1 -->|WAL stream| R1[Replica 1]
        L1 -->|WAL stream| R2[Replica 2]
        C1 -.->|read| R1
    end
    subgraph ML["Multi-leader (DynamoDB Global Tables)"]
        C2[Client DC1] -->|write| LA[Leader DC1]
        C3[Client DC2] -->|write| LB[Leader DC2]
        LA <-->|async replicate| LB
    end
    subgraph LL["Leaderless (Cassandra)"]
        C4[Client] -->|write| Co[Coordinator]
        Co -->|W=2| N1[Node 1]
        Co -->|W=2| N2[Node 2]
        Co -.->|W=2| N3[Node 3]
    end

Single-leader is the workhorse. All writes go to one node (the primary), which ships a log of changes to followers. PostgreSQL streams the Write-Ahead Log (WAL). MySQL ships the binary log (binlog). MongoDB ships the oplog². The primary is the single source of truth. Followers are read-only copies.

Multi-leader lets two or more nodes accept writes and replicate to peers. DynamoDB Global Tables in MREC mode (the default) accept writes in every region with typically under 1 second replication lag³. The price: conflict resolution. Almost always last-write-wins (LWW), which silently discards the “loser” when two regions write the same key concurrently.

Leaderless (Dynamo-style) has no designated primary. The client or a coordinator fans writes to N replicas and waits for W acknowledgements. Reads fan to R replicas and take the freshest. Netflix benchmarked Cassandra at 1.1 million client writes per second on 288 EC2 nodes with RF=3⁴.

Consensus-based (Raft, Paxos) is sometimes treated as single-leader, but the safety guarantees differ. Every write is committed only after a majority of replicas persist it. No data loss on single-node failure. Automatic leader election. etcd, CockroachDB, Spanner, and TiKV all use this model⁵.

Chain replication arranges replicas in a linear chain. Writes enter at the head and flow tail-ward; reads come from the tail. Simpler than Paxos but requires an external configuration master. Described by van Renesse and Schneider⁶ and used in Windows Azure Storage⁷.

Sync vs async vs semi-sync

The sync-versus-async choice answers one question: how many seconds of writes can you afford to lose on a single-machine failure?

PostgreSQL exposes this as synchronous_commit with settings on, remote_write, and remote_apply. The minimum wait on sync is one network round trip to the standby². MySQL’s semi-sync uses a timeout (GitHub sets 500 ms) that falls back to async if replicas are slow⁸. This gives best-effort lossless failover within a datacenter.

Log-based replication

Every single-leader system ships changes via a log. The format matters:

• Physical log (WAL). PostgreSQL streams raw WAL records (page-level changes). Compact, fast, but tied to the exact storage format. You cannot replicate between different Postgres major versions without logical decoding².
• Binary log (binlog). MySQL ships row-level changes (before/after images) or statements. Row-based is the production default because statement-based has non-determinism bugs (NOW(), RAND())¹⁰.
• Oplog. MongoDB ships idempotent operations in a capped collection. Replicas tail the oplog and apply operations¹¹.
• Logical replication. A higher-level format (row changes as structured data) that decouples replication from storage format. PostgreSQL’s logical replication slots, MySQL’s binlog in row format, and Debezium’s CDC connectors all operate at this level.

The key distinction: physical replication is faster but locks you to one engine version. Logical replication is slower but enables cross-version upgrades, heterogeneous replication, and CDC pipelines.

Consensus replication (Raft and Paxos)

Raft decomposes consensus into three sub-problems: leader election, log replication, and safety⁵. A leader accepts proposals, appends them to its log, sends AppendEntries RPCs to followers, and declares an entry committed when a majority have persisted it. The etcd raft library uses a 10:1 ElectionTick-to-HeartbeatTick ratio with randomized election timeouts to avoid split votes¹².

stateDiagram-v2
    [*] --> Follower
    Follower --> PreCandidate: election timeout (pre-vote)
    PreCandidate --> Candidate: pre-vote granted by quorum
    PreCandidate --> Follower: pre-vote failed
    Candidate --> Leader: majority vote
    Candidate --> Follower: higher term seen
    Leader --> Follower: quorum lost or higher term

Paxos is equivalent in fault tolerance but harder to implement correctly. Spanner uses Paxos groups per tablet with TrueTime (clock uncertainty typically between 1 and 7 ms) to achieve external consistency across the entire database¹³. The practical difference: Raft is what you debug at 3 AM because it decomposes cleanly into election + replication + safety. Paxos is what Google runs because they built it first and have 20 years of operational tooling.

Failover

Failover has three parts: detection, election, and fencing.

Detection. Naive ping-based monitoring suffers false positives during network glitches. GitHub’s Orchestrator uses holistic detection: it declares the master dead only when it cannot reach the master AND all replicas report replication is broken from their end¹⁴¹⁵.

Election. Orchestrator picks the most up-to-date replica based on a rules matrix (version, format, semi-sync status, datacenter)¹⁶. Patroni delegates to a Distributed Configuration Store (etcd, Consul, or ZooKeeper) so the election is itself a Raft decision¹⁷.

Fencing. The old primary must stop accepting writes. Without fencing, split-brain is inevitable on network partition. STONITH (“shoot the other node in the head”) via IPMI power-off is the nuclear option. Patroni uses a DCS lease that expires if the primary cannot renew it¹⁷. GitHub uses HAProxy’s hard-stop-after to terminate old connections after reload⁸.

sequenceDiagram
    participant Client
    participant Old as Old Primary
    participant FT as Failover Tool
    participant New as New Primary
    Client->>Old: write
    Old--xFT: heartbeat lost
    FT->>FT: detect failure (holistic)
    alt Without fencing
        FT->>New: promote
        New-->>FT: ok
        Client->>Old: write (SPLIT-BRAIN)
        Client->>New: write
    else With fencing (STONITH / lease)
        FT->>Old: STONITH / lease expire
        Old-->>FT: confirmed dead
        FT->>New: promote
        New-->>FT: ok
        Client->>New: write (single writer)
    end

Multi-region replication

Three production approaches dominate:

• DynamoDB Global Tables (MREC). Async cross-region replication with LWW conflict resolution. Typical lag under 1 second. SLA: 99.999% availability³. Best for idempotent writes where silent conflict resolution is acceptable.
• Aurora Global Database. Storage-level cross-region replication with under 1 second lag. Up to 10 secondary regions. Write forwarding lets secondary-region reads route writes back to the primary region¹⁸. Best for read-heavy multi-region with a single write region.
• Spanner. Synchronous Paxos across regions. Every write waits for a majority of voting replicas. External consistency via TrueTime. Best when you need global strong consistency and can tolerate cross-region write latency¹³.

Real-World Example

GitHub’s 2018 MySQL incident: 43 seconds that took 24 hours to fix

On October 21, 2018, a 43-second network partition between GitHub’s East Coast network hub and their primary East Coast datacenter triggered a cascade that took 24 hours and 11 minutes to fully resolve¹.

The setup. GitHub ran multiple MySQL clusters (by 2023, the fleet had grown to 50+ clusters with 1,200+ hosts)¹⁹. Each cluster used semi-sync replication with a 500 ms timeout. Orchestrator ran on Raft across datacenters for coordinated failover. Applications reached the primary through Consul-backed HAProxy⁸.

The partition. At 22:52 UTC, connectivity between the network hub and the East Coast DC dropped for 43 seconds. Orchestrator-on-Raft, holding quorum in the remaining DCs, correctly detected the primaries as unreachable and promoted West Coast replicas to primary¹.

The split-brain. During those 43 seconds, East Coast applications kept writing to the old primaries. When the network healed, both sides had accepted writes the other had not seen. One of the busiest clusters had 954 writes in the affected window that had not been replicated¹.

The decision. GitHub chose data integrity over speed. They kept the West Coast as primary (it had the Orchestrator-blessed identity), forced East Coast apps to incur cross-country latency, and spent 24 hours draining the backlog of webhooks and GitHub Pages builds. The divergent writes were manually reconciled¹.

The lesson. Automated failover without application-tier readiness for cross-region latency creates a new failure mode. GitHub’s post-mortem recommended constraining Orchestrator to prevent cross-region promotion unless the application can tolerate the latency change¹. The failover tool optimizes for “any healthy primary exists”; the application assumes a local-DC primary in its latency budget.

flowchart TD
    subgraph EC["East Coast DC"]
        App1[App servers] -->|writes| OldP[Old Primary]
        OldP -->|semi-sync| R1[Replica]
    end
    subgraph WC["West Coast DC"]
        App2[App servers] -->|reads| R2[Replica]
    end
    subgraph Orch["Orchestrator Raft cluster"]
        O1[Node 1] --- O2[Node 2] --- O3[Node 3]
    end
    OldP -.->|43s partition| Orch
    Orch -->|promote| R2
    R2 -->|becomes new primary| App2
    App1 -->|still writing!| OldP

Trade-offs

Common Pitfalls

Exercise

You run a global SaaS on Postgres in us-east-1 with async replicas in eu-west-1 and ap-southeast-1 for reads. A customer in Singapore reports that after saving, refreshing immediately shows old data. Diagnose, and design three alternatives: (1) pin reads to primary after writes, (2) synchronous APAC replica, (3) move to a multi-region SQL engine. Quantify the latency cost of each.

Key Takeaways

• Single-leader async is the default and solves most problems. Understand replication lag and you are 90% of the way there.
• Synchronous replication trades latency for durability. Use semi-sync with a short timeout (500 ms) for best-effort lossless failover within a datacenter.
• Multi-leader is deceptively attractive. Conflicts are always harder than they look, and LWW silently loses data.
• Leaderless (Dynamo-style) with tunable R/W gives you a knob to trade consistency for availability per query, but R + W > N is not linearizability.
• Automated failover without fencing is a split-brain waiting to happen. Always fence the old primary before promoting the new one.
• Replication is not a backup. A bad DROP TABLE replicates everywhere in seconds. You still need point-in-time restore.
• Aurora’s 4-of-6 quorum tolerates an AZ failure plus one extra segment loss without losing data⁹. That is the bar for cloud-native durability.

Further Reading

• Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases (Verbitski et al., SIGMOD 2017) - The canonical Aurora paper; “the log is the database” and the 4-of-6 quorum design explained from first principles.
• MySQL High Availability at GitHub (Shlomi Noach, 2018) - Orchestrator + Consul + GLB in production detail; the architecture behind the 10 to 13 second failover target.
• October 21 post-incident analysis (GitHub, 2018) - The 24-hour outage from a 43-second partition; the canonical split-brain war story for any replication discussion.
• In Search of an Understandable Consensus Algorithm (Ongaro and Ousterhout, USENIX ATC 2014) - The Raft paper; required reading before working with etcd, CockroachDB, or TiKV.
• Dynamo: Amazon’s Highly Available Key-value Store (DeCandia et al., SOSP 2007) - The paper that launched the leaderless category and defined (N, W, R) tunable quorums.
• Spanner: Google’s Globally-Distributed Database (OSDI 2012) - Paxos + TrueTime; the synchronous multi-region blueprint that trades latency for global strong consistency.
• Jepsen: MongoDB 4.2.6 (Kyle Kingsbury, 2020) - How “full ACID” claims meet network partitions; essential reading for healthy skepticism about replication guarantees.
• PostgreSQL: High Availability, Load Balancing, and Replication - The reference for streaming replication, synchronous commit modes, and PITR configuration.

Flashcards

References