Distributed Consensus
Transcript
Made automatically from the video's sound, so it may contain mistakes. Click a line to play from there.
Welcome back everyone to the ARC 2 finale of our Explainer series, The Illusion of Time and Order. If you're a vibe coder or a back-end systems engineer who survived the first five episodes, you've had quite a journey.
But today we are leaving the safety of a single node and stepping into the chaotic, highly unpredictable reality of distributed consensus. We've got a packed agenda for this finale. We'll quickly look beyond the acid database, hit the mathematical impossibility walls, dive into quorums, paxos and raft, terrifying you with some real-world split-brain disasters and byzantine faults in the wild, and finally, wrap up with the pragmatic playbook.
Alright, let's jump right into section one. Beyond the acid database, leaving the single node sanctuary. Having perfectly solved concurrent races inside one isolated acid database, we now have to confront what happens when machines share absolutely nothing except an asymmetric packet-dropping network.
In this environment, hardware will inevitably fail. You literally cannot assume the network is friendly, meaning theoretical failure modes suddenly become very dangerous practical realities. Mathematical impossibility walls, where we learn that perfection is quite literally mathematically impossible.
Before we even try to build a flawless distributed system, we need to look at the 1985 FLP impossibility result by Fisher, Lynch and Patterson, which actually won the Dykster Prize. They mathematically proved that no deterministic asynchronous consensus protocol can guarantee both safety and liveness if even one single node crashes.
Basically, you cannot guarantee your system will always safely reach an agreement. You are ultimately forced by Gilbert and Lynch's CAP theorem to make a hard choice. Do you want linearizable safety or do you want right availability during a network partition?
You can't have both. And the maths behind fault tolerance here is totally unforgiving. To tolerate simple crash-stop faults, your cluster size needs to be 2F plus 1. So to survive just one single crash, you need three nodes.
But the rules change entirely if nodes start acting maliciously or if they pass corrupted data due to bugs. To survive these arbitrary Byzantine faults, protocols like PBFT require at least three F plus 1 nodes.
The network overhead absolutely skyrockets when machines start lying to each other. Okay, section three. Quorums, Paxos, and Raft. Navigating the impossible.
Since perfect consensus is impossible, engineers developed overlapping majority quorums. To make a decision, a majority of nodes must agree. Specifically the floor of N divided by two plus one.
This brilliantly illustrates why a two-node cluster has literally zero fault tolerance. If one fails, consensus is impossible. And look at a four-node cluster.
The majority is three, meaning you can still only tolerate one failure. It survives no more crashes than a three-node cluster, but you've increased network overhead and slow down rights. Never run an even-numbered cluster for consensus.
To coordinate these quorums, we use some heavy algorithmic machinery. Paxos uses a complex two-phase approach with separate leader election, though flexible Paxos can tweak those quorum intersections. But then you have Ongaro and Alsterhout's Raft, which simplifies things immensely by making strong leader election and integrated first phase.
Raft relies on monotonic terms and randomized election timeouts to break split vote live locks, ensuring leader completeness and a strict one-way log flow. So what happens when these systems break? Section 4.
Real World split-brain disasters. When the network lies. Let's look at GitHub's infamous east-west network partition outage in October 2018. A routine database migration caused high load, tricking the health checks into flipping primaries.
When a subsequent partition hit, a rogue node was elected, creating a 43-second MySQL split brain scenario. Two primaries were accepting rights simultaneously. That brief 43 second illusion of order completely broke foreign keys, misrouted private repositories to the wrong users, and required 24 hours of agonizing manual right reconciliation.
But even more terrifying is the tale of a 90-second network partition that isolated two active file servers. Thinking the other was dead, both servers issued a Stonith command, which literally stands for Shoot the Other Node in the Head.
Because of the partition, the messages were delayed in transit. When the network finally recovered, those delayed commands were delivered perfectly on time. Both servers successfully shot each other in the head simultaneously, resulting in a flawless, totally mutually assured destruction outage.
Byzantine faults in the Wild. Cloudflare's partial switch failure. Network partitions are bad enough, but a Byzantine fault where nodes receive conflicting information is a true nightmare.
In November 2020, Cloudflare had a partial network switch failure. The control plane remained up, so it looked healthy to monitoring, but the data plane was secretly blackholing packets. This created non transitive reachability.
In their three node etcd cluster, node A could talk to Node B, but its packets to leader node C were dropped. Node B, however, could reach everyone. They had entirely conflicting views of reality, invisible to standard health checks.
Because Node 1 couldn't see the leader, it panicked and initiated endless raft leader elections. Node 2, seeing a perfectly healthy leader, rejected those votes. This trapped the Raft protocol in endless election thrashing, entirely freezing the etcd cluster.
This freeze triggered a massive automated Postgres failover. The new primary became overwhelmingly overloaded, and it degraded the entire Cloudflare dashboard, making it 80 times slower for over six hours. So, how do we actually survive this?
Let's cover section 6, the pragmatic playbook. First, you have to avoid the vibe coder trap. Do not write clever 15-line Redis lock wrappers or let node cron run eight times across your autoscale pods, or hack together DIY active-active sync scripts.
As Martin Kletman proved with his Stop the World Garbage Collection pause proof during the whole Redlock debate, a client can acquire a lease, freeze during a 15-second GC pause past its lease expiry, and wake up as a zombie to overwrite data another client just safely saved.
You absolutely must use monotonically increasing fencing tokens at the storage layer, like an EtSeter resource version or Zookeeper ZZID. For most of us, stick to the Yagney playbook. Default to a robust single primary Postgres setup, using PG TriAdvisory Exact Lock for Singleton Crons and 4UpdateSkip Locked for Worker Cues.
Just keeping an eye on Brandor's MVC C dead tuple ceiling. Only adopt three or five-node managed raft or Paxos clusters like EtSida, Spanner, or Cockroach DB when multi-node survival is genuinely required. Well, having navigated the treacherous waters of distributed state, our next explainer will drop all the way down to the silicon itself.
If our database integers are perfectly safe, why is basic floating point maths fundamentally broken? Join us next time for Arc 3 S08E07, where we find out exactly why 0.1 plus 0.2 does not equal 0.3.
See you then.