Distributed Consensus and Split Brain Disasters
Transcript
Made automatically from the audio, so it may contain mistakes. Click a line to play from there.
Welcome to the final deep dive in arc two of our series, The Illusion of Time and Order. This is episode six. Distributed consensus and split brain.
Yeah, and we are finally tackling the real chaos today.
Exactly. I mean, just as a quick recap of episode five, we basically relied on one single rock solid ACID Postgres database to act as our ultimate tiebreaker for concurrent requests, right?
We did. It was our anchor.
Right. But today, we are asking a much scarier question. What actually happens when, say, a backhoe severs a fiber cable or a switch glitch slices the network between multiple database servers completely in half.
It is the nightmare scenario for any systems engineer, honestly.
It really is. And to set the stage, we have to talk about October 21st, 2018, over at GitHub.
Oh, the 43-second outage. Yes.
Yes. So there was this routine network maintenance task, and it triggered a connectivity blip between their U.S. East Coast and West Coast data centers. The physical fiber optics spanning the continent just dropped the connection.
And it was just for 43 seconds.
Literally 43 seconds. I mean, in human time, you can barely pour a cup of coffee in 43 seconds.
Right, but to an automated distributed system operating at the speed of light, that 43 seconds of silence is well, it's it's an absolute eternity.
It really is. It's a void. And it forced their automated systems to make some catastrophic assumptions in under a minute.
Because the East Coast and West Coast could no longer talk to each other, the failover mechanism just panicked.
Exactly. It panicked and promoted a new primary database on one side of the split.
And that right there is where the horror story actually begins.
Right. Because the isolated original primary database on the other side of the country, it had absolutely no idea it had been demoted.
Right. From its perspective, it didn't fail at all. The network just went quiet. So it kept right on to accepting rights from whatever local application servers it could still reach.
Which means within seconds, you have two diverging realities. You've got two primary databases, both eagerly accepting new user data, completely unaware of each other.
The textbook definition of a split brain scenario.
It is. And the fallout is terrifying. Because when a split brain happens, modern systems have this brutal last resort defense mechanism.
Yeah, the industry standard protocol, affectionately known as Stoneth.
I will always love the visceral naming conventions in computer science. Shoot the other node in the head.
It's aggressive, but I mean the reality of the situation is dire. If you have two nodes simultaneously claiming to be the absolute authority, they shouldn't try to negotiate.
Right. Negotiation just leads to corrupted data.
Exactly. They should try to forcefully power down or physically isolate the competing node to protect the integrity of the data. You've literally cut the power to the imposter.
But here is the massive twist in the GitHub story. Because of the way the network partitioned and then suddenly reconnected after just 43 seconds, both sides woke up.
They woke up and looked across the wire.
Yes. They looked across the wire, realized there was an imposter, and they both fired their stoneth commands at each other simultaneously.
Oh wow. So they both shot each other in the head.
They literally shot each other in the head. The result was a massive cascading outage. The automated systems just couldn't safely merge those two diverging realities back together.
Because it's not a math problem anymore at that point. It's a semantic human problem. You had users on the East Coast pushing code that conflicted with code pushed on the West Coast.
Right. And resolving that took GitHub engineers 24 hours of painstaking manual untangling. Just to stitch the database back together without losing any of your actual user data.
It is wild. And that incident really sets up our mission for this deep dive. We are going to explore the chaotic, unpredictable reality of distributed consensus.
We are going to unpack the theoretical walls of network physics, how real-world engines like Paxos and Raft try to survive those walls, and this is the big one why naive approaches to distributed locks often lead to silent data corruption.
Yeah, the kind of locks AI coding assistants just casually hand out these days.
Oh, we are definitely getting into the vibe coder traps later. But first, since we've spent this entire arc trying to impose order on time and concurrency, today the network is fighting back.
So we need to understand the fundamental laws of physics we are up against.
Right. And the giant brick wall that tells us perfection is mathematically impossible is the FLP impossibility result.
From the 1985 paper by Fisher, Lynch, and Patterson, it is a chilling proof.
It really is. They basically proved that in a purely asynchronous network, if even one single node might crash, a deterministic consensus algorithm can get stuck forever.
And to really grasp that, you have to strip away all your assumptions about how networks operate. In a purely asynchronous model, there are no guarantees about timing, none at all.
Right. A message could arrive in a millisecond, or it could sit in a router queue for a week.
Exactly. And the processors warning the nodes might operate at wildly different, unpredictable speeds. So imagine you are a server in this system, right?
Okay, I'm a server.
You need to agree on a piece of data with your peers. So you send out a vote and you wait. And the vote from one specific peer just it just doesn't come.
So what do I do?
Well, this is the crux of the FLP dilemma. You can never ever perfectly distinguish between a node that is actually crashed and a node that is perfectly healthy, but just experiencing a severe network delay.
Because there's no external source of truth. I only know it comes over the wire.
Precisely. If you decide, okay, I've waited long enough, I am going to assume this delayed node is dead, and you make a decision without it, you run a massive risk.
What if it was just delayed?
Right. What if a millisecond after you finalize the decision, that node suddenly wakes up from a CPU spike and sends a message that contradicts the decision you just committed.
Then I've violated consensus.
Exactly.
Okay, but let me push back on that. Why not just wait? If proceeding without them is dangerous, why doesn't the algorithm just say, hey, we don't move forward until we hear from everyone?
Because if the node actually did crash and you are waiting for a message that will never ever arrive, your entire system is permanently frozen. You sacrifice liveness entirely.
Oh, I see. So you're trapped. If you wait, you risk halting forever. If you move on, you risk data corruption.
And the FLP result mathematically proves that you cannot design a deterministic algorithm, meaning one with strict rules and no randomness that guarantees agreement under those conditions.
A chaotic network can always perfectly time its delays to keep a deterministic algorithm stuck in a loop forever.
Yep. And that theoretical impossibility gives birth to the painful practical reality we face every day, which is the cap theorem.
Cap. Consistency, availability, and partition tolerance.
Right. And the theorem states you cannot simultaneously guarantee all three when the network fails.
And since we know physical network partitions are guaranteed to happen, the P in CAP is not optional. The universe forces your hand. You have to choose.
You choose between being consistent or being available.
Let's ground this for you, the listener. Let's say you are building a banking app. If you choose consistency during a network partition, what does that actually feel like for the user?
If the network splits your cluster in half, a consistent system, a CP system, looks at the side that doesn't have a majority and says, I cannot guarantee the rest of the cluster will agree on this.
So it just shuts the door.
It refuses to accept any new rights. The user tries to transfer $50, and they just get a loading spinner that turns into a service unavailable error.
You preserve the pristine truth of the ledger, but you sacrifice availability.
Exactly. And if you go the other route, an AP system choosing availability.
You tell all nodes to keep accepting rights no matter what.
Right. You tell them just keep taking the user's money, log the transactions, and we will figure out the mess later.
Which is exactly what GitHub did. They chose availability and it led to a split brain. The East Coast moves $50, the West Coast moves the same $50 somewhere else. Both say success.
And the underlying truth of the financial ledger is completely shattered.
Okay, I need to synthesize this because it feels like a massive paradox. CAP says we have to sacrifice availability or consistency the second the network blips. Yeah. So how does the internet even function? How do global databases process billions of transactions without halting or corrupting everything?
The counterintuitive answer is we cheat.
We cheat the laws of physics?
We step around them. The keyword in FLP is deterministic. If your algorithm always waits exactly five seconds and always checks node A before node B, the network can thwart it.
So to beat a chaotic network, we have to become chaotic ourselves.
Exactly. We abandon determinism. We inject randomness. By using randomized timeouts and probabilistic voting, we mathematically deny the network the ability to keep us stuck forever.
It might force a tie once or twice, but eventually the random dice rolls align in our favor and we punch through the deadlock. That is brilliant.
It really is. But before we get to the actual engines that do this, like Paxos and Raft, we have to look at how we establish truth. And in distributed systems, truth is determined by majorities.
The wisdom of the crowd. But the math of fault tolerance and how we construct these majorities is a huge trap.
It is highly counterintuitive. Let's look at the math of the quorum.
Right. It's not just a simple majority vote. It's about overlapping majorities. The strict formula is the floor of N divided by two plus one.
So in a five-node cluster, N is five. Half a five is two point five. The floor, rounding down is two, plus one is three. You need three nodes to agree to make any decision.
And the reason this specific formula is non-negotiable is the geometric concept of overlap.
Right. If nodes A, B, and C agree on a right, they form a majority of three. Later, if nodes C D and E need to make a decision, basic geometry dictates those two groups must intersect by at least one node.
In this case, node C.
Exactly. Node C acts as the unbreakable memory of the cluster. It remembers the first decision and physically prevents the new group from contradicting it.
But the number of nodes you need depends heavily on the type of failure you expect. And this is where we have to talk about crash fault versus Byzantine faults.
A crash fault is what we deal with most days. A server just dies. The power supply blows, or a kernel panics. It stops sending messages entirely.
It's silence is its failure. And the math to survive that is two F plus one. To survive one crash, you need three nodes. To survive two, you need five.
But a Byzantine fault is a completely different beast. It doesn't just crash, it goes rogue.
Like a memory module flipping random bits or a compromised node actively lying. It tells node A the balance is a hundred dollars and tells node B the balance is zero.
Because of that active subversion, you need a much stricter threshold. You need three F plus one nodes. To survive just one single lying node, you need a minimum of four nodes.
And protocols like practical Byzantine fault tolerance or PBFT are incredibly complex, right?
Oh, incredibly. Every node has to cross-check every other node's story with cryptographic signatures. It creates an exponential explosion of network chatter.
We'll talk about when to actually use Byzantine protocols later in the playbook, but I want to focus on standard crash faults for a second. Because developers step on a massive landmine here.
The two node cluster trap.
Yes. You want redundancy, so you spin up a second server, a two-node cluster.
And you have achieved absolutely zero automatic failover safety. You've actually mathematically doubled your risk of downtime.
Let's walk you, the listener, through exactly why. You have two nodes. The majority formula is the floor of two divided by two, which is one, plus one is two. You strictly need two nodes to make a decision.
Yeah, one node dies.
You only have one node left.
And one is not a majority of two.
It's not.
That single node is paralyzed. It doesn't know if the other node died or if the network cable just got unplugged.
If it just assumed it was safe and started taking rights, and the other node did the same thing on the other side of a partition, boom, split brain.
So a correctly implemented consensus algorithm in a two-node cluster will simply freeze the entire system the moment one node goes down. It chooses consistency over availability.
So three nodes is the absolute minimum to survive one crash. You lose one, you have two left, two is a majority of three.
Right.
But here is the brain bender. Why is a four-server cluster absolutely no more resilient than a three-server cluster?
It comes back to the geometry. In a four-node cluster, the majority is three.
Okay, I lose one node. I have three remaining. Three is a majority, the system survives.
But what happens if you lose a second node?
Well, I only have two nodes left. Two is not a majority of four, the cluster halts.
Exactly. A three-node cluster tolerates exactly one failure. A four-node cluster tolerates exactly one failure. Adding that fourth node didn't buy you any fault tolerance.
It's like buying a four-legged table for an uneven floor. You just created more opportunities for a wobble. You added another machine that needs patching and can draw packets.
This is why professional infrastructure like etcd or zookeeper clusters are almost exclusively sized in odd numbers. Three, five, or seven.
A five-node cluster is the sweet spot. You need three for a majority. You can take one down for maintenance, and if another dies unexpectedly, you still have three.
Exactly. So now that we have our odd numbers, how do these nodes actually vote? That brings us to Paxos and Raft.
Paxos was the original, right? Right. By Leslie Lamport. It proved consensus was mathematically possible.
It did.
But it is famously difficult to understand and even harder to implement correctly.
It allows for a lot of concurrency with multiple nodes proposing different values at the same time.
Like five authors trying to write a novel by crossing out each other's sentences.
Right. The edge cases are a debugging nightmare, which is why Diego Ongaro and John Austerhout at Stanford created Raft. Their explicit goal was understandability.
They wanted the same safety guarantees as Paxos, but structured so mere mortals could actually code it.
And Raft does this by being much more authoritarian. It insists on a strict leader.
So how does Raft establish that order in, say, our five-node cluster?
Raft organizes time into strictly increasing epochs called terms. Think of them as logical clocks or presidential terms. Every term starts with an election to choose a single leader.
And that leader has absolute power for that term. All right requests must flow through the leader.
Yes. The leader receives a right, appends it to its local log, and sends an append entries request to the followers.
But it waits to hear back, right?
Exactly. It waits until a majority of followers reply that they've safely written it to disk. Only then does the leader commit the right and tell the user it succeeded.
It's very orderly.
Yes.
But what happens if the leader crashes, or tying it back to FLP? What if the network to the leader gets really slow?
This is where Raft uses randomness to defeat FLP. Every follower has an internal countdown timer, an election timeout. As long as it gets rapid-fire heartbeats from the leader, it resets the timer.
But if the heartbeats stop.
The timer hits zero. The follower assumes the leader is dead, increments the term number, declares itself a candidate, and asks for votes.
Wait, if all followers have timers and the leader dies, what stops all four from timing out at the exact same millisecond and voting for themselves? You'd have a massive tie.
And if the timers were deterministic, you would be stuck in an endless FLP loop. But Raft randomizes the election timeout every single time it resets, usually between 150 and 300 milliseconds.
So one node will almost always time out slightly before the others.
Yes. That fastest node becomes a candidate and fires off vote requests. And by the time the slower nodes' timers run out, they've already received the request. And Raft rules say if you see a valid request for a higher term, you must vote for them.
It's an elegant way to use chaos to create order. But executing that on physical copper wires is where things get messy, which brings us to Kyle Kingsbury and his Jepsen audits.
Kyle Kingsbury is a legend.
Jepsen is an automated testing framework that actively just tortures distributed databases.
Torture is the word.
He unleashes chaos. He uses Linux firewall rules to silently drop packets, pauses a node's mid-execution, forces clocks to drift.
And he audits systems like MongoDB, Elasticsearch, Cassandra. And the spoiler is almost all of them fail initially.
Let's walk through how a network partition actually forces a dirty read, like in one of those early MongoDB tests.
Okay. You have a primary node and two secondaries. The client sends a right to the primary. The primary writes it to its local log.
But before it can replicate it to a majority.
A network partition isolates the primary. The two secondaries hold an election, and one becomes the new primary, the cluster heals.
But the old primary doesn't know it's isolated yet.
Exactly. In older versions, if a client queried that isolated old primary, it would serve the data it just wrote to its local log, even though it was never replicated to a majority.
A dirty read.
And when the partition heals, the old primary sees it's out of date and rolls back that log. The data it just served effectively never existed. Kingsbury proved that implementing these protocols correctly is extraordinarily hard. And that leads us to the Cloudflare incident of 2020.
Yes. This is a master class in physical hardware failures creating logical paradoxes.
Cloudflare relies on etcd, which uses Raft. They had a massive cluster spread across racks. And a physical network switch started malfunctioning.
It didn't die completely, right? It entered a zombie state.
It corrupted its routing tables and created a non-transitive network topology.
Normally networks are transitive. If A can ping B and B can ping C, A can ping C.
But this broken switch scrambled the routing. Let's look at node one, node two, and node three. Node one could reach node two. Node two could reach node three perfectly fine. But node one could not reach node three at all.
Node A hears B, B hears C, but A is completely deaf to C.
And unfortunately, Node 3 happened to be the actively elected Raft leader.
Oh no. So node one is sitting there, deaf to the leader's heartbeats. Its randomized timer runs out, it increments its term, declares itself a candidate, and asks for votes.
Node 1 can't reach node three, but it can reach node 2. So it tells Node 2, hey, I haven't heard from the leader, my term is higher, vote for me.
But Node 2 can hear Node 3. Node 2 is getting healthy heartbeats from the leader.
But raft rules are strict. Node 2 sees node 1's higher term number. It is forced to step down and grant its vote to Node 1.
So you have conflicting views of reality. Node 1 thinks the leader is dead. Node 2 knows the leader is alive, but has to depose it.
And because they are trapped in this non-transitive triangle, they just entered an endless loop of tight elections. An election storm.
And because ETCD is a strictly consistent CP system, without a stable leader, it refuses all rights. It went read-only.
The entire control plane limped along for hours, all because one switch created a scenario where A couldn't hear C.
Which brings us to the most terrifying part. If Cloudflare can get taken down by a non-transitive switch black hole, what happens when everyday application developers try to build their own distributed locks?
It is a recipe for silent systemic data corruption. Let's shift to the application layer. The vibe coder trap.
Oh, this is huge right now with AI coding assistance.
A developer asks an AI how to run an hourly billing job. The AI spits out code using a local scheduling library like NodeCron or AP Scheduler. The developer drops it into the web server process. On their laptop, it runs flawlessly. The top of the hour hits, the job runs once.
But in the cloud, things scale.
Traffic spikes. Kubernetes scales the web server from one pod to six pods.
You now have six independent cron schedulers ticking away, totally unaware of each other.
Top of the hour hits.
All six fire the billing job at the exact same millisecond.
You discharged every subscriber six times.
An absolute disaster.
So the developers realize they need external coordination, a lock, and they inevitably reach for Redis.
The naive 10-line Redis lock.
You see this everywhere. It uses a set if not exists command.
Like a pod putting a currently occupied sign on an empty table.
Pod A sets the lock, pod B tries, sees the lock, and backs off. When pod A finishes, it deletes the lock.
It seems bulletproof, but it's an illusion. What if pod A acquires the lock, starts processing payments, and suffers a hard crash before it can delete the lock?
Live nure. The lock is orvined in Redis forever, pod B, C, and D will back off eternally. Your billing job is permanently deadlocked.
Until a human manually logs in and deletes the key. So developers try to patch this by adding an expiration timer, a TTL. They tell Redis to automatically evaporate the lock after five minutes.
But fixing the liveness failure introduces a safety failure. Silent data corruption. Let's walk through it. Pod A acquires the lock with a five-minute TTL. It starts processing, but the database is sluggish today.
Five minutes pass in the real world, and pod A is only halfway done.
Inside Redis, the timer expires, the lock evaporates. But pod A doesn't know that. It's still grinding away.
Now pod B wakes up, checks Redis, sees an empty table, and gets the lock. Pod B starts running the exact same billing job.
We're back to double charging customers.
But it gets worse. Let's say pod A finally finishes its painfully slow run. What's the last line of code?
To clean up.
Pod A sends a delete command to Redis.
But Pod A's lock already evaporated. The lock sitting there belongs to Pod B. Pod A blindly deletes Pod B's lock.
Oh no.
It rips up Pod B's protection while Pod B is still running.
And now Pod C swoops in, grabs a lock, and starts running the job a third time. It's a cascading failure.
How do you even fix that? First, acquiring the lock and setting the timer must be a single atomic breath. If you do it in two steps, the pod could crash in between.
But how do you stop Pod A from deleting Pod B's lock?
You have to sign your lock. Pod A must generate a unique cryptographic UUID and store it inside the lock.
So when Pod A finishes, it reads the lock, checks the signature, and only deletes it if it matches its own UUID.
Exactly. And that read check delete logic must also be completely atomic, usually requiring dedicated Redis commands or Lua scripts, so nobody overwrites it in the middle.
Okay, but there's another naive trap. The DIY two-node ping script. Server A is primary, server B is standby. Server B pings A every second. If the ping fails, server B promotes itself.
A classic flaw. What if server A is perfectly healthy? But the firewall between A and B has a momentary hiccup.
An asymmetric network failure.
Server B's pings fail, it panics and promotes itself. But server A is still happily talking to the internet.
Split brain.
Both servers think they are the absolute authority. You can never trust your own limited perspective of the network.
Okay, so let's say a developer uses the perfectly atomic, cryptographically signed Redis lock. They are safe, right?
Unfortunately, no. Even with flawless logic and a perfect network, you are still vulnerable to the passage of time itself. This brings us to the great Redlock debate.
Salvatore's San Filippo, the creator of Redis versus Martin Kletman, the distributed systems researcher.
Cleppin published a devastating critique of San Filippo's Redlock algorithm. Redlock relies on a dangerous assumption that wall clock time moves reliably across servers.
And we know clocks drift.
Yes, but Clettman highlighted something much more severe. The stop the world garbage collection pause.
Let's use an analogy. Imagine a worker process written in Java or Go. The runtime occasionally has to freeze the entire application to clean up memory safely.
Imagine the worker is a surgeon. The surgeon acquires our perfect Redis Lock, giving them a 10 second lease to operate. They start. One second in, a massive stop the world garbage collection pause triggers.
The surgeon instantly falls deeply asleep, mid-surgery, scalpel in hand. From their perspective, time just stops.
But the real world clock keeps ticking.
Nine seconds later, the Redis lock expires. A second surgeon claims the lock and begins operating on the same patient.
And then, after 15 agonizing seconds, the garbage collection finishes. The first surgeon abruptly wakes up.
They wake up from the dead.
And they have absolutely no idea 15 seconds just passed. They think that you're still one second into their lease.
Silent data corruption. And the cryptographically signed lock did nothing.
Because checking a lock at the application layer is fundamentally insufficient. You cannot trust the worker's sense of time. The ultimate authority must be at the storage layer itself.
The database acting as a bouncer. How do we achieve that mechanically?
Monotonic fencing tokens. Your lock service, like etcd generates a strictly increasing number every time a lock is granted.
So worker one gets a lock with token 33. It goes to the database and says, here's my data, my authorization is token 33.
The database checks its ledger, sees no token higher than 33, and accepts the right. It records that 33 is the highest token seen.
Then worker one gets hit by that 15 second garbage collection pause. Its lock expires, worker two gets a lock, and the service gives it token 34.
Worker 2 writes its data with token 34. The database updates its ledger.
Now the zombie wakes up. And the database bouncer says, sorry, I've already processed token 34. Your token 33 is stale, you're a zombie, right rejected. It completely negates the danger of unpredictable pauses. But the underlying storage system has to be smart enough to check those tokens, right?
Absolutely. Like Kubernetes using resource version in etcd. If your database doesn't support conditional rights based on external tokens, you don't have a correctness lock.
Wow. Okay. Knowing all these extreme dangers, how should you architect your systems tomorrow? Let's open the Judicious Architecture Playbook.
The first rule is the ultimate YAGNI rule. You aren't gonna need it. Do not distribute what fits on one single primary Postgres node.
Yes. A modern, well-tuned Postgres database can handle tens of thousands of transactions per second with full asset guarantees without ever touching a network wire.
So if you are prompting an AI to build an hourly billing job, don't let it build a fragile Redis lock. Use a built-in transaction scoped Postgres advisory lock.
Because if the worker crashes, its physical TCP connection to the database drops, and Postgres automatically clears the lock instantly.
No orphaned locks, no permanent deadlocks, no complex TTLs.
And for multiworker job cues, use Postgres with a queuing strategy where workers pull tasks and use a for update skip locked clause to just jump over rows that other workers are actively processing.
It turns a standard table into a highly concurrent queue. Brander Leach has written extensively about managing the MVCC vacuum boundaries for this, but for most apps, it is vastly more reliable than a network lock.
But what if you truly need multi-node coordination at a massive scale?
Then you apply the consistent core pattern.
The Supreme Court of your infrastructure.
And for choosing locks in your app code, what is the practical rule of thumb?
You categorize them into efficiency locks and correctness locks.
An efficiency lock is just an optimization. If the lock fails and two workers run a daily analytics report at the same time, you just waste a few cents of compute.
The data is still correct.
So a simple Redis lock with a unique token and item potent receiver is fine. But if a correctness lock fails, a customer is billed twice, or medical data's corrupted. For correctness, Redis is completely out.
You must use etcd or Zookeeper, and you must enforce monotonic fencing tokens at the storage layer.
Exactly. And finally, never touch Byzantine fault tolerance unless your nodes literally belong to mutually distrusting adversaries.
Because three F plus one algorithms like PBFT will just crush your performance for a threat model that doesn't exist in an enterprise environment. Just stick to standard crash faults.
Focus on proper configuration and Jepson style testing instead.
We have covered so much ground today. The network is an unreliable narrator, four node clusters are an illusion, and a 15-second garbage collection pause can turn your code into a zombie.
It has been a dense journey through ARC2. We built up these walls of consensus to protect our data. Yes. We are moving into deceptively broken primitives.
We'll learn why asking a modern CPU to calculate 0.1 plus 0.2 does not equal 0.3. The silicon itself lies to us.
It's going to be a fascinating look at the compromises baked into every microchip.
But before we go, I want to leave you with one final thought. We spent an hour discussing how to protect your system from lying networks and sleeping software. But what happens to your perfectly designed mathematically proven raft algorithm if a stray cosmic ray from space physically strikes your server and flips a single zero to a one deep inside your RAM during an election. If the hardware itself can be randomly altered by the universe, can you even trust the hardware?