Getting nodes
to agree
Atomic commit across machines, and the algorithms that make fault-tolerant agreement possible.
→ next · ← back · N notes · F full screen
Agreement is everywhere.
Leader election
All nodes must agree who the leader is, or you get split brain.
Atomic commit
A transaction spanning several nodes must commit everywhere or nowhere.
Uniqueness
Two users claiming the same name at once: exactly one must win.
Two-phase commit
All or nothing, across machines.
2PC: prepare, then commit.
Distributed transactions in practice.
Inside one database
Spanner, VoltDB, MySQL Cluster: all nodes run the same software, so it can be optimised.
XA across systems
The Java JTA API ties a database and a message broker into one transaction. Lowest common denominator.
Why people avoid XA
In-doubt transactions keep locks; the coordinator becomes a single point of failure; it can’t detect deadlocks across systems or work with SSI.
Failures get amplified: if any participant or the coordinator is unhealthy, everything waits.
Fault-tolerant consensus
Raft, Paxos, Zab: agreement that survives crashes.
What a consensus algorithm promises.
Agreement
No two nodes decide differently.
Integrity
No node decides twice.
Validity
A decided value was actually proposed.
Termination
Every node that doesn’t crash eventually decides, as long as a majority is alive.
Viewstamped Replication, Paxos, Raft, and Zab actually decide a sequence of values: total order broadcast.
Lab: majorities
Click nodes to crash or restore them.
The price of consensus.
- Every decision needs a majority vote: effectively synchronous replication.
- Most algorithms assume a fixed set of members; adding nodes is tricky.
- Timeouts detect dead leaders, so a flaky network causes constant re-elections.
- Edge cases are subtle, even in Raft.
Coordination services
Outsourced consensus.
ZooKeeper and etcd: a tiny, very reliable database.
Linearizable atomic operations
Compare-and-set to implement locks and leases.
Total order
Every operation gets a monotonically increasing ID: ready-made fencing tokens.
Failure detection and watches
Sessions with heartbeats, ephemeral nodes that vanish when a client dies, and change notifications.
Run on 3 or 5 nodes. Used for leader election, partition assignment (Kafka, HBase), and service discovery.
Now, our system.
DB + message broker
When we write to PostgreSQL and publish an event, do we rely on JTA/XA, on luck, or on a pattern like an outbox table?
In-doubt work
Do we have any process that can stop halfway across two systems, e.g. ledger updated but bank file not created?
Who decides?
Leader election for schedulers and consumers: are we using a real coordination service or homemade locks?
Bounded blast radius
If our coordination dependency goes down, what stops? Is that acceptable?
Batch processing
From Unix pipes to MapReduce and Spark: bulk computations over big data. Chapter 10.