Database Internals — Episode 4

The first of today's three chapters is short: broadcast, anti-entropy, and gossip. Broadcast the author does not even illustrate — a node sends its neighbours a message that may get lost; one of the guests notes that entropy is a measure of disorder and it is fought with epidemic processes, in which everyone became an expert over the last couple of years. Merkle trees: leaves are hashed, hashes are glued bottom-up, and comparing two roots in logarithmic time shows whether the sets diverge and which leaves to sync; one of the guests adds that such reconciliation is not confined to databases: their own services compare data and push updates to each other the same way. Hinted handoff Alexander explains on Cassandra: if one node is unavailable during a quorum write, a neighbour keeps a hint and later delivers the write to its owner. Bitmap version vectors took Sergey two days, and he recommends an article that leads to dotted version vectors through happened-before, vector clocks, and sending only relevant events; the book, by his count, has two or three hundred references to external sources.

Read repair Vitaly describes through Dynamo-like databases: in DynamoDB conflicts between replicas are resolved by the client, in Cassandra and Scylla the last write wins, and the resolution itself is deferred until a real client reads — with the optimisation of taking data from one replica and digests from the rest; the downside is obvious: what is not read is not synced. The participants sort the mechanisms by scale: Merkle trees and version vectors shrink the comparison across the whole dataset, while hinted handoff and read repair act locally, where the activity is happening right now; the rest can be left alone, like a rarely used feature that works and bothers nobody. Gossip is Cassandra's trademark: the naive variant where everyone forwards to everyone creates an avalanche of messages, so a spanning tree is built or the number of neighbours is capped, and the lists are refreshed periodically; Alexander recalls seeing the same maths in descriptions of networks, and the déjà vu from this book keeps recurring.

Two-phase commit: the coordinator asks the participants whether they are ready and, on a unanimous yes, orders the commit; the main problem is coordinator failure, after which the participants are left in limbo waiting for its recovery. Vitaly recalls his first encounter with 2PC — Microsoft DTC, where every troubleshooting article began with "reinstall". A viewer asks what happens if a node promised and did not apply — Alexander answers: by the protocol it has failed, and this is fixed by replicating the participants, while a lying coordinator is already a Byzantine failure. Sergey makes a subtle point: a commit is not instantaneous, and in a transaction of "message to the queue plus row in the database" a reader may see the message before the row. Three-phase commit adds a phase and solves part of the problems, but demands cast-iron assumptions that real life lacks — nobody in the chat has met it in the wild.

Calvin is deterministic transactions: Sergey explains that the key part is not the plan but the sequencer — the logical order of applying transactions is fixed in advance, in ten-millisecond batches, and then the nodes execute it via the scheduler without coordination; the idea once clicked for Alexander — agree before, not during — and one of the guests values that a crashed node replays the same plan after coming back; the approach is used in YDB, described in a Habr article, although the original requires knowing the read/write set in advance. Sergey draws a parallel with Aurora, where a single sequencing point orders the WAL and storage scales without consensus — at the price that the sequencer may become the bottleneck. Spanner: Paxos groups with long-lived leaders per data range, 2PC between groups through a lock table, TrueTime with intervals instead of exact time; YugabyteDB follows in its footsteps with separate storage for distributed transactions, where latency is noticeably higher than local. Sharding, consistent hashing, and one more approach to snapshot isolation the club leaves for self-study.

Consensus means agreeing on a value proposed by one of the participants and finishing the process; before it the author introduces atomic broadcast: all live processes deliver the same messages in the same order, and that is equivalent to consensus — Alexander admits he understood why it is a broadcast only after rereading a third of the book. ZooKeeper's own protocol the participants take from the operator's side: throughput rests on a single leader, and tuning the timings balances sensitivity to losing the leader against slow recovery; epochs, synchronisation that finishes the previous leader's business, and no wonder Kafka is moving away from ZooKeeper. Paxos: proposers, acceptors, learners; Lamport's paper about some Greek island, where the reader feels like an archaeologist; Sergey retells the algorithm through a party with loud music where people agree on which bar to go to — and is told in reply that he is a worthy follower of Lamport, who later repented of explaining distributed algorithms through metaphors.

For Alexander it clicked on proposal numbers: having obtained a higher number, you do not propose your own value but join the one already accepted, and so the value is fixed. Single-decree Paxos is expensive per decision, so Multi-Paxos reserves the right to propose for the leader while it is healthy. Raft's authors made it understandable: leader election, with the leader telling everyone it is still alive, log replication, a reference implementation, and plenty of illustrations; with leader trouble Raft stalls while Multi-Paxos degrades into single-decree with several contenders — Sergey considers the possible election conflicts a feature, a "die" instead of complex determinism. Byzantine failures: PBFT survives f faulty nodes out of 3f+1, but, as one of the guests hedges while admitting he only skimmed the algorithm, it catches only those whose message hashes fail to match. The verdict on the book: one guest would propose a variation with no algorithms at all, only the "why"; another compares it to his own collection of white papers and admits the depth was missing in places — with it the book would have run to six hundred or a thousand pages instead of three hundred; Alexander read it over three or four months and calls that real work, but as a skeleton for further reading the book is good.