Primary-backup replication

Deep dive

How it works

Parts:

• Primary — orders, appends and ships writes; holds an epoch.
• Backup — appends in order, replays, keeps an apply cursor, acks.
• Arbiter — small, durable (etcd, ZooKeeper); grants a lease and increasing epochs.
• Ack rule — async, semi-sync (any k backups) or sync (all).

1. The primary appends the write (position, epoch, payload) to its log and fsyncs.
2. It ships the entry. A backup rejects a lower epoch, catches up on a gap, appends, acks.
3. The client is answered once the rule is met: 0, 1 or all acks.
4. The primary renews its lease with the arbiter.
5. On expiry the arbiter grants epoch e+1 to the backup with the highest (last epoch, last position); it re-aligns the others.
6. A returning old primary is rejected (stale epoch), truncates its divergent tail and rejoins as a backup, or is rebuilt from a snapshot.

client ─write─► PRIMARY(e=7) ──entry──► BACKUP 1 ─ack─┐   async: reply before acks
                  │ lease                BACKUP 2 ─ack─┤   semi: reply after 1 ack
               ARBITER (epoch counter)                  │   sync: reply after all acks
failover: lease expires → arbiter grants e=8 → freshest backup promoted → e=7 writes rejected

Code

Three ack rules, a random-point crash, promotion of the freshest backup, and a stale primary that keeps writing.

#[derive(Clone, Copy, PartialEq)]
pub enum Mode { Async, SemiSync, Sync } // client ack after 0, any 1, all backups

#[derive(Clone)]
pub struct Node { pub epoch: u64, pub log: Vec<u64>, pub up: bool }

pub struct Rng(pub u64);
impl Rng {
    pub fn next(&mut self) -> u64 { self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17; self.0 }
}

pub struct Cluster { pub nodes: Vec<Node>, pub primary: usize, pub mode: Mode, pub arbiter_epoch: u64 }

impl Cluster {
    pub fn new(n: usize, mode: Mode) -> Self {
        let node = Node { epoch: 1, log: vec![], up: true };
        Cluster { nodes: vec![node; n], primary: 0, mode, arbiter_epoch: 1 }
    }

    /// Backup side: refuse a stale epoch (fencing), drop the tail that diverges from the
    /// sender's log, append the rest. Idempotent.
    pub fn ship(&mut self, from: usize, to: usize) -> bool {
        let (ep, src) = (self.nodes[from].epoch, self.nodes[from].log.clone());
        let b = &mut self.nodes[to];
        if !b.up || ep < b.epoch { return false; }
        b.epoch = ep;
        let common = b.log.iter().zip(&src).take_while(|(x, y)| x == y).count();
        b.log.truncate(common);
        b.log.extend_from_slice(&src[common..]);
        true
    }

    /// `p` is the node that believes it is primary. Returns the ack wait, None if not acked.
    pub fn write(&mut self, p: usize, v: u64, rng: &mut Rng) -> Option<u64> {
        if !self.nodes[p].up { return None; }
        self.nodes[p].log.push(v);                    // local append (+ fsync in real life)
        let need = match self.mode { Mode::Async => return Some(0), Mode::SemiSync => 1, Mode::Sync => self.nodes.len() - 1 };
        let mut acks = vec![];
        for b in (0..self.nodes.len()).filter(|&b| b != p) {
            let rtt = 100 + rng.next() % 300;         // simulated round trip to backup b
            if self.ship(p, b) { acks.push(rtt); }
        }
        acks.sort();
        if acks.len() >= need { Some(acks[need - 1]) } else { None }
    }

    /// Background shipping: all of async, the straggler of semi-sync.
    pub fn tick(&mut self, rng: &mut Rng) {
        let p = self.primary;
        for b in (0..self.nodes.len()).filter(|&b| b != p) {
            if rng.next() % 2 == 0 { self.ship(p, b); }
        }
    }

    /// Lease expired: the durable arbiter grants epoch+1 to the freshest live node.
    /// (Real systems compare last epoch, then index.)
    pub fn failover(&mut self) {
        self.arbiter_epoch += 1;
        let best = (0..self.nodes.len()).filter(|&i| self.nodes[i].up)
            .max_by_key(|&i| self.nodes[i].log.len()).unwrap();
        self.nodes[best].epoch = self.arbiter_epoch;
        self.primary = best;
        for i in (0..self.nodes.len()).filter(|&i| i != best) { self.ship(best, i); }
    }
}

#[test]
fn failover_loses_nothing_unless_async() {
    for mode in [Mode::Async, Mode::SemiSync, Mode::Sync] {
        let (mut lost, mut zombie_acked) = (0, 0);
        let mut rng = Rng(0x9E3779B97F4A7C15);
        for _ in 0..2000 {
            let mut c = Cluster::new(3, mode);
            let mut acked = vec![];
            for v in 0..20 + rng.next() % 80 {        // crash at a random point
                if c.write(0, v, &mut rng).is_some() { acked.push(v); }
                c.tick(&mut rng);
            }
            c.nodes[0].up = false;
            c.failover();
            lost += acked.iter().filter(|v| !c.nodes[c.primary].log.contains(v)).count();
            c.nodes[0].up = true;                     // old primary wakes with epoch 1
            let before = c.nodes[c.primary].log.clone();
            zombie_acked += c.write(0, u64::MAX, &mut rng).is_some() as u32;
            assert_eq!(c.nodes[c.primary].log, before);   // fenced: the new primary's log is untouched
            c.ship(c.primary, 0);                     // rejoin: drop divergent tail
            assert_eq!(c.nodes[0].log, c.nodes[c.primary].log);
        }
        if mode == Mode::Async { assert!(lost > 0) } else { assert_eq!((lost, zombie_acked), (0, 0)) }
    }
}

Test passes: over 2,000 crashes per mode async lost 657 of 118,889 acknowledged writes (0.55 %); semi-sync and sync lost none; the stale primary reached no backup.

Complexity and constants

• Write: one local fsync plus 0 (async) or 1 (semi-sync, sync; parallel) round trips. Mean ack wait in the simulation (backup round trip uniform 100-399 units): 0 / 199 / 299, the minimum vs maximum of two draws.
• The primary sends each entry n−1 times; large writes cap at about 1/(n−1) of its NIC rate (chain replication avoids this).
• Failover = failure timeout + arbiter grant + catch-up; Patroni defaults: lease TTL 30 s, loop 10 s.
• Keep the log until every backup consumed it, or replace it by a snapshot (state-machine snapshots).

Efficiency

• Cost: one acknowledged write = local fsync (order of 0.1-1 ms on NVMe) + for semi-sync/sync one datacenter round trip (order of 0.1-0.5 ms) + backup fsync; bound: fsync and the primary's NIC.
• Levers:
  • batch writes per ship and fsync — throughput grows with batch size, latency adds the window (group commit) — busy primaries.
  • ack from any 1 of N (ANY 1 in PostgreSQL) — fastest backup, not slowest: 199 vs 299 units in my simulation — backups in different zones.
  • ship a physical log, not statements — no re-execution on backups (PostgreSQL docs) — same major version; logical logs cost more but cross versions.
  • read from backups — read capacity grows with backups — lag-tolerant reads.
  • compress the stream — fewer bytes (PostgreSQL wal_compression) — billed cross-zone links.
• Naive → standard → state of the art:
  • sync to all, one entry per round trip · slowest backup, fsync + RTT per write.
  • async with automatic failover · no write wait, loses the unshipped tail.
  • batched any-1 semi-sync, arbiter-granted epochs · one RTT to the fastest backup per batch.

Implementation notes

• Put the epoch in every log entry and request; only the arbiter increments it. Promote by (last epoch, last position).
• A primary that cannot renew its lease stops serving. A paused process wakes after expiry, so backups or storage also check the epoch (fencing token); else power it off (STONITH).
• Catch-up: stream from the backup's position if the primary still has it, else snapshot plus tail. PostgreSQL slots keep WAL for a lagging standby (max_slot_wal_keep_size caps the disk); Redis PSYNC resumes only inside its bounded backlog.
• Read-your-writes on a backup: return the commit position with the reply; the backup waits until it applied it (PostgreSQL remote_apply delays the commit instead).

Pitfalls

• Async plus automatic failover drops acknowledged writes; Patroni's maximum_lag_on_failover only bounds it.
• Two nodes, no arbiter: a network cut leaves two primaries.
• Fencing the backups does not stop a stale async primary acking its clients (2,000 of 2,000 probes in my simulation).
• An old primary holds writes the new one never saw: rewind to the common prefix (pg_rewind).
• Sync with one backup down blocks all writes; use an any-1 rule.

Variants and alternatives

In production

• Relational: PostgreSQL streaming replication with Patroni's leader lease; MySQL semi-sync.
• Cache/KV: Redis, async by default, WAIT to confirm replicas.
• VM fault tolerance: VMware FT holds the primary VM's output until the backup acks the log; a shared-storage test-and-set picks the survivor.
• Storage: Ceph replicated pools write through a primary OSD.
• Brokers: Kafka partition leader, in-sync replicas, leader epochs (partitioned commit log).

Implementations

Sources

• PostgreSQL docs: replication, synchronous_commit, standbys.
• Redis docs: Replication, WAIT.
• Patroni docs: Dynamic configuration.
• MySQL Reference Manual, Semisynchronous Replication (no link: the site refuses automated checks).
• Scales, Nelson, Venkitachalam, The Design of a Practical System for Fault-Tolerant Virtual Machines, ACM SIGOPS OSR 44(4), 2010. paper
• Budhiraja, Marzullo, Schneider, Toueg, The Primary-Backup Approach, in Distributed Systems (ed. Mullender), 2nd ed., 1993.