Cover

CMU Database Group · 1:24:53 · Watch on YouTube

Summary

Lecture 23 of CMU 15-445/645 (Fall 2024) covers how an OLTP database keeps ACID guarantees when its data is spread across multiple nodes. It walks the full design space of replication — primary-replica vs multi-primary, K-safety, synchronous/quorum/eventual propagation, continuous vs on-commit timing, and active-passive vs active-active execution — then the atomic commit protocols that make nodes agree: two-phase commit with its recovery paths and optimizations, followed by Paxos, Multi-Paxos, and Raft. It closes with the CAP theorem, split brain and its two remedies, the PACELC extension, and Google's reversal from transaction-free BigTable to transactional Spanner.

The whole lecture assumes friendly, non-malicious nodes; distrust would require a Byzantine fault tolerant protocol, which costs 5–10x more.

flowchart TD
    A["Distributed OLTP transactions"] --> B["1. Replication"]
    A --> C["2. Atomic commit / consensus"]
    A --> D["3. Consistency under failure"]
    B --> B1["Configuration:\nprimary-replica / multi-primary"]
    B --> B2["K-safety threshold"]
    B --> B3["Propagation:\nsync / quorum / eventual\ncontinuous vs on-commit"]
    B --> B4["Execution:\nactive-passive vs active-active"]
    C --> C1["Two-phase commit\n(unanimous, blocking)"]
    C --> C2["Paxos / Multi-Paxos\n(majority, non-blocking)"]
    C --> C3["Raft\n(freshest log leads)"]
    D --> D1["CAP: consistent or available"]
    D --> D2["Split brain\nhalt vs reconcile"]
    D --> D3["PACELC:\nelse latency vs consistency"]

Topics

  1. Course Logistics and Recap of Distributed Architectures — 0:27
  2. The Distributed Transaction Problem — 8:23
  3. Replication Configurations and K-Safety — 15:22
  4. Propagation Schemes, Timing, and Execution Models — 25:11
  5. Atomic Commit / Consensus Protocols — 41:53
  6. Two-Phase Commit (2PC) — 50:16
  7. Paxos, Multi-Paxos, and Raft — 1:04:56
  8. CAP Theorem, PACELC, and Conclusion — 1:16:40

Full source: transcript.md

Key takeaways

  • Two-phase commit is a degenerate case of Paxos. The Lamport–Gray paper shows they are essentially the same protocol; the only real difference is that 2PC requires unanimous agreement while Paxos requires only a majority (49:47, 50:16, 1:06:07).
  • 2PC blocks on coordinator failure; Paxos does not. Under 2PC no other transaction can commit while the survivors resolve the undecided one — otherwise a transaction that read the pending data could commit and violate ACID. Paxos keeps making progress as long as a majority is alive (57:35, 57:47, 1:16:05).
  • The commit decision and the leader-election decision are the same decision — electing a primary is just another transaction with slightly different semantics, which is why one protocol handles both (42:41).
  • Practical defaults settled by the lecture: use primary-replica (≈99% of deployments), active-passive execution (reuses existing WAL infrastructure; almost every system does it), and continuous propagation (aborts are rare, so streaming log records early wins) (15:47, 31:29, 41:34).
  • Active-active only saves intermediate network traffic, and demands full determinism from the DBMS — a billion-record update ships a billion WAL records under active-passive and none under active-active, but it requires seeded randomness, shared timestamps, serializable ordering, and stored procedures. VoltDB is essentially the only system that pulls it off, and lower isolation levels break it outright (34:35, 36:18, 41:17).
  • Early acknowledgement after prepare is the optimization worth having: once every participant votes OK the transaction is committing regardless, so the client can be answered one round trip early. Early prepare voting, by contrast, is rarely implementable because SQL cannot tell you which query is the last one for a node (59:21, 59:46, 1:01:04).
  • Real Multi-Paxos leader leases vary by two orders of magnitude: Spanner 10s, YugabyteDB 2s, CockroachDB 5 min default, TiDB 10s — the tradeoff being election frequency against failure-detection delay (1:15:01, 1:15:31).
  • CAP reduces in practice to one question: on a network partition, halt or reconcile? Distributed relational systems halt the minority side and never face conflicting values; NoSQL systems reconcile afterwards, usually via last-write-wins (Cassandra). Vector clocks push MVCC conflict resolution into application code — Riak tried it and it was a nightmare (1:17:25, 1:19:53, 1:20:42, 1:21:25).
  • BFT protocols run 5–10x slower than the protocols covered here, so blockchain-style trustlessness has no place in an OLTP DBMS unless you genuinely cannot trust your own nodes (13:50, 14:23).
  • Google reversed the NoSQL wave it started: after dropping transactions in BigTable, it built Spanner on the argument that programmers should deal with the performance cost of overusing transactions rather than perpetually coding around their absence (1:22:32, 1:23:09, 1:23:32).