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: - Latency — keep data geographically close to users. - Availability — allow the system to continue working even if some machines fail. - Read scale — scale out read throughput (multiple machines serving…

• 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…

• Redundancy and Replication

• Why Redundancy?

  Removing single points of failure. If one component fails, a redundant copy takes over seamlessly. Redundancy ≠ Backup ≠ Archiving: - Redundancy — live duplicate ready to take over immediately (hot standby) - Backup — periodic snapshot f…

• Replication Patterns

  | Pattern | How It Works | Trade-off | |---------|-------------|-----------| | Master-Slave | Writes to master, replicated to slaves; reads from slaves | Simple; master is SPOF | | Multi-Master | Writes to any node; bidirectional replica…

• RAID Levels (Storage Redundancy)

  What RAID is. Redundant Array of Independent Disks — a layer that takes several physical disks and makes them look like one logical disk to the operating system, trading between three goals: speed, capacity, and survival of a disk failur…

• Distributed Systems Challenges

  Working with distributed systems is fundamentally different from writing software on a single computer. On a single machine, operations are deterministic — if hardware works correctly, the same operation always produces the same result.…

• Why Not Just Use One Machine?

  Scalability isn't the only reason for distribution. Fault tolerance (keeping service running despite individual failures) and low latency (placing data geographically close to users) also require multiple nodes. You can't achieve these w…

• Unreliable Networks

  Distributed systems are shared-nothing — nodes communicate only over the network. The internet and datacenter networks are asynchronous packet networks: no guarantees on when (or if) a packet arrives. Six things that go wrong when you se…

• 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…