Database Internals — Episode 4

The Database Internals finale opens with anti-entropy. The hosts compare broadcast, Merkle trees for finding divergence, hinted handoff for an unavailable replica, and version vectors for version history. Read repair postpones conflict resolution until a read, while gossip spreads state through an epidemic process.

The distributed-transactions section dissects two-phase commit: participants first promise they can write, then a coordinator announces the decision. Losing it blocks progress, replication masks only some failures, and three-phase commit is rare. Calvin uses a sequencer to order transactions in advance and execute a shared plan.

Spanner combines Paxos within replica groups with two-phase commit across shards. Google uses TrueTime for global ordering; it returns an interval rather than an exact timestamp. The conversation covers the cost of distributed operations, local and cross-shard paths, and databases inspired by Spanner.

The final chapter covers consensus, validity, termination, and equivalence to atomic broadcast. Paxos separates proposers, acceptors, and learners, while proposal numbers protect the chosen value. Multi-Paxos avoids repeated elections, and Raft supplies a concrete leader-and-log model. Byzantine failures introduce the 3f + 1 threshold.