Foundations: Many Nodes, One Truth — Distribution & Consensus

What you'll learn

• Replication Deep Dive (How Data Stays in Sync Across Nodes)

  Replication serves three purposes: (1) keep data geographically close to users (latency), (2) allow the system to continue working even if some machines fail (availability), (3) scale out read throughput (multiple machines serving read q…

• Three Replication Architectures

  | Architecture | Writes Go To | Reads From | Conflict Handling | Use Case | |---|---|---|---|---| | Single-Leader | One designated leader | Leader + followers | None (one write point) | Most OLTP systems (Postgres, MySQL) | | Multi-Leade…

• Single-Leader (Master-Slave) Replication

  How it works: All writes go to the leader. The leader writes to its local storage, then sends the change as a replication stream to all followers. Each follower applies changes in the same order the leader processed them.

• Synchronous vs Asynchronous Replication

  | Mode | Leader Behavior | Trade-off | |---|---|---| | Synchronous | Waits for follower to confirm write before acknowledging client | Guaranteed: follower has up-to-date copy. Risk: one slow follower blocks all writes | | Asynchronous |…

• Setting Up New Followers (Without Downtime)

  You can't just copy data files — the leader is constantly receiving writes. The process: 1. Take a consistent snapshot of the leader's database at a specific point (without locking — most databases support this: pgbasebackup, MySQL's xtr…

• Handling Node Failures

  Follower failure (catch-up recovery): - Each follower keeps a log of received changes from the leader - If it crashes, on restart it knows the last transaction it processed - Connects to leader, requests all changes since that point → ca…

• Replication Log Implementations

  How does the leader actually send changes to followers? Four approaches: | Method | Mechanism | Advantage | Disadvantage | |---|---|---|---| | Statement-based | Send SQL statements (INSERT, UPDATE, DELETE) | Simple, compact | Broken by n…

• Replication Lag — The Problems It Causes

  Asynchronous replication means followers are always some time behind the leader. Under normal load this lag is a fraction of a second, but under heavy write load or network problems it can grow to seconds or minutes. Problem 1: Reading y…

• Timeouts and Failure Detection

  The timeout dilemma: - Too short → false positives (declare healthy nodes dead during load spikes) → unnecessary failovers → cascading load - Too long → users wait too long for error detection → prolonged downtime No "correct" fixed time…

• Unreliable Clocks

  Every machine has its own clock (quartz oscillator) — not perfectly accurate and drifts differently on each machine. NTP synchronization helps but has limits. Two types of clocks: | Clock Type | What It Measures | Sync'd via NTP? | Can J…

• Process Pauses

  A node can be paused at any point for an unpredictable duration: | Cause | Duration | Note | |---|---|---| | GC (stop-the-world) | Milliseconds to minutes | Even "concurrent" collectors occasionally pause | | VM suspend/resume | Arbitrar…

• Truth is Defined by the Majority

  A node cannot trust its own judgment — it might be the one that's wrong (network partition isolating it, clock drifting, paused by GC). The other nodes declared it dead; it can't unilaterally override that. Quorum principle: Decisions re…

• Byzantine Faults

  Nodes that deliberately lie or send corrupted responses. In most datacenter systems, we assume non-Byzantine faults — nodes are honest but may be slow, crash, or have stale data. Byzantine fault tolerance is needed only for: - Aerospace…

• System Models

  | Timing Model | Assumption | Practical? | |---|---|---| | Synchronous | Bounded delays, bounded pauses, bounded clock error | No — real systems have unbounded delays | | Partially synchronous | Usually bounded, occasionally unbounded |…

• Safety vs Liveness

  | Property Type | Definition | Example | Under Faults | |---|---|---|---| | Safety | "Nothing bad happens" — if violated, can point to exact moment | Uniqueness, correct ordering | Must always hold, even in failures | | Liveness | "Somet…

• Consistency and Consensus

• Linearizability (Atomic Consistency)

  The strongest single-object consistency guarantee: make the system behave as if there is only a single copy of the data and all operations on it are atomic. Core guarantee (recency): Once any client's read returns a new value, ALL subseq…

• Linearizability vs Serializability

  These are frequently confused but are different guarantees: | | Linearizability | Serializability | |---|---|---| | Scope | Single object (one register/key) | Multi-object transactions | | Guarantee | Recency — reads see most recent writ…

• When You Need Linearizability

  1. Leader election: All nodes must agree on who the leader is — requires linearizable lock (ZooKeeper, etcd) 2. Uniqueness constraints: Two users can't register the same username concurrently — needs linearizable compare-and-set 3. Cross…

• Can Replication Provide Linearizability?

  | Replication Method | Linearizable? | Why | |---|---|---| | Single-leader (reads from leader) | Potentially yes | But uses snapshot isolation? Then no. Delusional leader? Then no. | | Consensus algorithms | Yes | ZooKeeper, etcd use con…

• The Cost of Linearizability

  If a network partition occurs between datacenters: - Multi-leader: Each DC continues independently → available but NOT linearizable - Single-leader: Only leader DC serves reads/writes → linearizable but clients in other DC become unavail…

• Ordering and Causality

  Causal ordering: If operation A happened before B (A influenced B), then everyone must see A before B. Concurrent operations (no causal link) can be seen in any order. | Consistency Model | Ordering | Performance | |---|---|---| | Linear…

• Total Order Broadcast

  A protocol guaranteeing two properties: 1. Reliable delivery: If delivered to one node, delivered to all 2. Totally ordered delivery: All nodes see messages in the same order Equivalence: Total order broadcast ≡ consensus ≡ linearizable…

• Two-Phase Commit (2PC)

  Algorithm for atomic commit across multiple nodes: either all commit or all abort. The promise system: 1. Coordinator assigns global transaction ID 2. Participants execute transaction, take locks 3. Coordinator sends prepare — "Can you d…

• 2PC vs Consensus

  | | Two-Phase Commit (2PC) | Consensus (Raft, Paxos, Zab) | |---|---|---| | Votes needed | ALL participants must vote "yes" | Majority suffices | | Coordinator failure | System blocks until coordinator recovers | New leader elected, syst…

• Fault-Tolerant Consensus

  Formal properties: - Uniform agreement: No two nodes decide differently - Integrity: No node decides twice - Validity: If v is decided, some node proposed v - Termination: Every non-crashed node eventually decides How consensus algorithm…

• ZooKeeper / etcd — Coordination Services

  Not general-purpose databases. They hold small amounts of data (fits in memory) replicated via total order broadcast across all nodes. What they provide: - Linearizable atomic operations: Compare-and-set for distributed locks (only one s…