Multi-Paxos

Deep dive

How it works

Parts:

• ballot — (round, node_id), unique and totally ordered; the leader's epoch
• acceptor state — promised ballot plus, per slot, the last accepted (ballot, value); persisted before replying
• leader (proposer) — runs phase 1 once, then phase 2 per slot
• learner — applies chosen values strictly in slot order
• quorum — a majority of 2f+1 acceptors (Flexible Paxos: phase-1 and phase-2 quorums only need to intersect)

Roles: proposers (leader), acceptors (persist state), learners (apply chosen values). Usually every node plays all three.

1. Phase 1a (Prepare b, from_slot): the new leader picks ballot b higher than any it has seen.
2. Phase 1b (Promise): an acceptor with promised < b sets promised = b (fsync) and returns every (slot, accepted_ballot, value) it holds for slots ≥ from_slot.
3. With promises from a majority, for each slot the leader must re-propose the value with the highest accepted ballot; slots with no reported value in the gap get a no-op.
4. Phase 2a (Accept b, slot, v): an acceptor with promised ≤ b stores (b, v) for the slot (fsync) and replies.
5. Phase 2b: majority of accepts → value chosen; leader notifies learners (often piggybacked on the next Accept).
6. Steady state repeats only 4-5. A rejection carrying a higher ballot means another leader exists: step down.

new leader:  Prepare(b) ──► majority Promise(accepted...) ──► Accept(b, s, v) ──► majority ──► chosen
steady:                                                     Accept(b, s+1, v') ──► majority ──► chosen

Code

use std::collections::{BTreeMap, HashMap, HashSet};

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug, Default)]
pub struct Ballot { pub round: u64, pub node: u32 } // derive(Ord): round first, then node

#[derive(Clone, Debug)]
pub struct Accepted { pub ballot: Ballot, pub value: Vec<u8> }

#[derive(Default)]
pub struct Acceptor {
    pub promised: Ballot,                  // persistent
    pub log: BTreeMap<u64, Accepted>,      // slot -> last accepted, persistent
}

pub enum Promise { Ok(Vec<(u64, Accepted)>), Nack(Ballot) }

impl Acceptor {
    /// One prepare covers every slot >= from_slot: the Multi-Paxos optimization.
    pub fn prepare(&mut self, b: Ballot, from_slot: u64) -> Promise {
        if b <= self.promised { return Promise::Nack(self.promised); }
        self.promised = b; // fsync before replying
        Promise::Ok(self.log.range(from_slot..).map(|(s, a)| (*s, a.clone())).collect())
    }
    pub fn accept(&mut self, b: Ballot, slot: u64, value: Vec<u8>) -> Result<(), Ballot> {
        if b < self.promised { return Err(self.promised); }
        self.promised = b;
        self.log.insert(slot, Accepted { ballot: b, value }); // fsync before replying
        Ok(())
    }
}

pub struct Leader {
    pub ballot: Ballot,
    pub n: usize,
    pub first_slot: u64,                    // first slot not known chosen
    promises: HashSet<u32>,
    recovered: BTreeMap<u64, Accepted>,     // highest-ballot value seen per slot
    pub next_slot: u64,
    acks: HashMap<u64, HashSet<u32>>,
    pub ready: bool,                        // phase 1 complete
    pub chosen: BTreeMap<u64, Vec<u8>>,
}

impl Leader {
    pub fn new(ballot: Ballot, n: usize, first_slot: u64) -> Self {
        Leader { ballot, n, first_slot, promises: HashSet::new(), recovered: BTreeMap::new(),
                 next_slot: first_slot, acks: HashMap::new(), ready: false, chosen: BTreeMap::new() }
    }
    fn majority(&self) -> usize { self.n / 2 + 1 }

    /// Returns Accept messages (slot, value) to broadcast once phase 1 completes.
    pub fn on_promise(&mut self, from: u32, accepted: Vec<(u64, Accepted)>) -> Vec<(u64, Vec<u8>)> {
        if self.ready || !self.promises.insert(from) { return vec![]; }
        for (slot, a) in accepted {
            let keep = self.recovered.get(&slot).map_or(true, |cur| a.ballot > cur.ballot);
            if keep { self.recovered.insert(slot, a); }
        }
        if self.promises.len() < self.majority() { return vec![]; }
        self.ready = true;
        let end = self.recovered.keys().next_back().map_or(self.first_slot, |s| s + 1);
        let mut out = Vec::new();
        for slot in self.first_slot..end {
            // Must re-propose what may already be chosen; fill holes with no-ops.
            let v = self.recovered.get(&slot).map_or(Vec::new(), |a| a.value.clone());
            out.push((slot, v));
        }
        self.next_slot = end;
        out
    }

    pub fn propose(&mut self, value: Vec<u8>) -> Option<(u64, Vec<u8>)> {
        if !self.ready { return None; }
        let s = self.next_slot;
        self.next_slot += 1;
        Some((s, value))
    }

    pub fn on_accepted(&mut self, from: u32, slot: u64, value: &[u8]) -> bool {
        let maj = self.majority();
        let set = self.acks.entry(slot).or_default();
        set.insert(from);
        if set.len() >= maj && !self.chosen.contains_key(&slot) {
            self.chosen.insert(slot, value.to_vec());
            return true;
        }
        false
    }
}

Learners apply chosen strictly in slot order; a slot can be chosen before an earlier one.

Complexity and constants

• Steady-state per command: 1 RTT, 2(n−1) messages, 1 fsync on each acceptor (batched).
• Leader change: phase 1 over all unchosen slots, then phase 2 for recovered ones: 2 RTT plus re-proposal bytes.
• Basic single-decree Paxos per operation (no stable leader) costs 2 RTT; Cassandra's classic lightweight transactions take 4 round trips because they add a read and a commit phase.
• With 5 replicas across 3 regions, commit latency ≈ RTT to the 2nd-nearest remote replica.

Efficiency

• Cost: steady state is 1 round trip and 2(n−1) messages per batch, plus one fsync on each acceptor (batched). Leader change is 2 round trips plus re-proposal bytes. With 5 replicas over 3 regions, commit latency is about the RTT to the 2nd-nearest remote replica. Bound: fsync latency inside a data center, network RTT across regions.
• Levers:
  • batch commands per Accept and fsync once per batch — fsync and message cost per batch, not per command (above) — any load
  • pipeline many slots in flight — throughput limited by bandwidth, not RTT (above) — high-latency links
  • Flexible Paxos, |Q2| = 2 of 5 with |Q1| = 4 — smaller commit quorum, lower tail latency (Howard et al. 2016) — rare leader changes
  • leader lease — local linearizable reads, no quorum round per read (Chubby, Spanner) — read-heavy workloads
  • piggyback "chosen" notices on the next Accept — no separate learner messages (above) — steady state
• Naive → standard → state of the art:
  • single-decree Paxos per operation · 2 RTT per command
  • Multi-Paxos, stable leader, batching and pipelining · 1 RTT per batch
  • leaderless EPaxos for non-conflicting commands · 1 RTT from any replica (Moraru et al. 2013)

Implementation notes

• Persist promised and accepted values before replying; treat them as the write-ahead log.
• Make ballots unique: (round, node_id); on a Nack, jump to round = seen.round + 1.
• Leader election is outside Paxos proper: use a lease (Chubby/Spanner style) so only one proposer runs phase 2 and reads can be served locally.
• Flexible Paxos: with N = 5 you may use |Q2| = 2 for faster commits if every phase 1 uses |Q1| = 4. Useful when leader changes are rare.
• Batch and pipeline: many slots in flight; one Accept message carries a batch.
• Snapshots + truncate acceptor logs below the applied index; a lagging replica fetches a snapshot.

Pitfalls

• Proposing your own value in a slot where some acceptor reported an accepted value: violates safety. Always take the highest-ballot one.
• Promise check off by one: prepare needs b > promised, accept needs b >= promised.
• Dueling proposers: two leaders keep preempting each other; add randomized backoff and a leader lease.
• Holes: a new leader must fill unreported gaps with no-ops, or learners stall forever.
• "Paxos Made Live" lesson: disk corruption and the gap between the paper and a real system (snapshots, membership, testing) dominate effort.

Variants and alternatives

In production

Google Chubby, Spanner (one Paxos group per split, leader leases), Megastore; Ceph monitors; Cassandra lightweight transactions (per-partition Paxos); Neon safekeepers (Paxos-like WAL quorum).

Implementations

Sources

• Leslie Lamport, The Part-Time Parliament, ACM TOCS 1998. paper
• Leslie Lamport, Paxos Made Simple, ACM SIGACT News 2001. paper
• Tushar Chandra, Robert Griesemer, Joshua Redstone, Paxos Made Live: An Engineering Perspective, PODC 2007. paper
• Heidi Howard, Dahlia Malkhi, Alexander Spiegelman, Flexible Paxos: Quorum Intersection Revisited, OPODIS 2016. paper
• Iulian Moraru, David Andersen, Michael Kaminsky, There Is More Consensus in Egalitarian Parliaments, SOSP 2013. paper
• Harald Ng, Seif Haridi, Paris Carbone, Omni-Paxos: Breaking the Barriers of Partial Connectivity, EuroSys 2023. paper · code