Theory
Paxos Consensus Algorithm
📋 Overview
Paxos is the foundational protocol for distributed consensus, designed to allow a group of unreliable nodes to agree on a single value. Developed by Leslie Lamport, it is famously difficult to understand but underpins some of the most critical systems in the world (Google Spanner, Chubby). It ensures that despite network delays, partitions, or node failures, the system reaches a single, immutable decision.
🏗️ Core Principles & Characteristics
The Roles:
- Proposers: Propose values to be agreed upon.
- Acceptors: Vote on the proposals; they form the "memory" of the cluster.
- Learners: Replicate the decided value once a consensus is reached.
The Two-Phase Protocol:
- Phase 1 (Prepare): A Proposer sends a proposal number (N) to a majority of Acceptors. Acceptors promise not to accept any lower-numbered proposal.
- Phase 2 (Accept): If the Proposer gets a majority of promises, it sends an 'Accept' request with the value. If Acceptors haven't promised a higher N, they accept it.
⚖️ Trade-offs: Pros & Cons
- Pros: Proven safety (never reaches a wrong decision); handles asynchronous networks; no single point of failure.
- Cons: Livelock (Dueling Proposers); complex to implement correctly; high latency due to multiple round-trips ($2f+1$ nodes required to tolerate $f$ failures).
🌍 Real-World Implementation
- Google Spanner: Uses Multi-Paxos to replicate data across global data centers with high consistency.
- Cosmos DB: Implements Paxos for its underlying replication and consistency levels.
- Cassandra: Uses Paxos for "Lightweight Transactions" (LWT) like
INSERT IF NOT EXISTS. - Neo4j: Uses Paxos for leader election and cluster membership.
💡 Interview "Gotchas" & Tips
- Paxos vs. Raft: Raft is "Understandable Paxos." It enforces a strong leader, whereas Paxos is more symmetric. Mention that Raft is usually chosen for new implementations, but Paxos is the theoretical ancestor.
- Multi-Paxos: Explain that "Basic Paxos" only agrees on one value. To build a database, you need "Multi-Paxos," which elects a leader to skip the Prepare phase for subsequent writes, reducing latency.
- Safety vs. Liveness: Paxos guarantees Safety (nothing bad happens) but cannot always guarantee Liveness (something good eventually happens) in an asynchronous network (FLP Impossibility).
📐 Suggested Architecture Primitives
- Quorum (N/2 + 1): The minimum number of nodes required to reach consensus.
- Epoch/Ballot Number: A monotonically increasing counter to ensure proposal uniqueness.
- Replicated State Machine (RSM): The high-level pattern where consensus is used to build a consistent log of operations.
- Leases: Used in Multi-Paxos to maintain leader stability and prevent "Dueling Proposers."
Canvas