Part 5 · Lesson 5.4
Ninety Seconds Without the Other Building
Where we are: Chirp's database shards each have a leader in one availability zone and replicas in another (lessons 2.1, 2.5 and 5.1). Lesson 5.3 set out what each feature needs from those copies. This lesson is about what happens when the copies can't talk to each other at all.
What you’ll learn
- What the CAP theorem actually says, in its narrow, precise form
- Why “CP or AP” is a choice you make per feature, not per database
- PACELC: the latency-versus-consistency trade you make every day, not just in failures
- How majorities let one side of a split keep going safely
Lesson 5.4 Ninety Seconds Without the Other Building
Step 1 of 14 · 1 min · The story
At 2:41 on a Tuesday afternoon, the network link between Chirp's two availability zones started dropping almost every packet. Both buildings were fine. Every server in each one was running. They simply couldn't reach each other.
It lasted ninety seconds. Here's what happened in that time:
- App servers in zone B couldn't reach the shard leaders, which were all in zone A. Every write from zone B failed: posts, likes, follows. About half of Chirp's users, whichever ones the load balancer had sent to zone B, saw errors when they did anything.
- Reads from zone B kept working, from zone B's replicas, which slowly fell behind, since no new writes were reaching them.
- The automatic failover system (lesson 2.5) in zone B noticed that the leaders seemed to be gone, and started promoting zone B's replicas to leaders. If the link had stayed down twenty seconds longer, both zones would have had a leader for the same shards, both accepting writes. Split brain.
The failover system had been set up to promote after 60 seconds, and nobody had thought hard about what "the leader is unreachable" means when the leader is actually fine and still serving half the users.
This is the situation the CAP theorem is about. It's one of the most quoted results in distributed systems, and one of the most misquoted. This lesson explains what it actually says, why the useful version of it is a per-feature choice, and the bigger everyday trade-off that a later idea, PACELC, adds.
Step 2 of 14 · 1 min
What CAP says
In 2000, Eric Brewer suggested that a distributed system can't have all three of:
- Consistency: every read sees the latest write (in the formal version, this means linearizability, lesson 5.3).
- Availability: every request to a working node gets a response (not an error, not a timeout).
- Partition tolerance: the system keeps working when the network between nodes fails.
In 2002, Seth Gilbert and Nancy Lynch proved a precise version of it.
It's usually summarized as "pick two of three." That summary is misleading, because you don't get to pick partition tolerance away. Networks fail: links drop, switches crash, cables are cut, cloud zones lose connectivity. Any system running on more than one machine will experience partitions. So the real statement is:
When the network is partitioned, you must choose: either refuse some requests (keeping consistency), or answer them with possibly stale or conflicting data (keeping availability).
That's it. It's a statement about what to do during a partition. It says nothing about normal operation.
Step 3 of 14 · 1 min
The choice, concretely
Think about zone B during those ninety seconds. A user there taps "post." The app server can't reach the shard's leader in zone A. It has two options:
Refuse. Return an error ("Couldn't post, try again"). Nothing inconsistent can happen, because nothing was written anywhere it shouldn't be. This is choosing consistency (often written "CP").
Accept. Write the post somewhere in zone B (a local copy that accepts writes) and tell the user it worked. Chirp stays available for that user. But zone A doesn't know about the post, and if zone A also accepted conflicting writes in the meantime (an edit to the same profile, a claim on the same giveaway code), the two sides now disagree, and someone has to reconcile them when the link comes back. This is choosing availability ("AP").
Neither is "correct." It depends on what's being written.
Step 4 of 14 · 1 min
CP or AP is a choice per feature
You'll often see databases labelled "CP" or "AP." It's a rough guide at best. Most databases are configurable, and the labels use CAP's very narrow definitions, which many real systems don't fit neatly. Martin Kleppmann's 2015 essay "Please stop calling databases CP or AP" makes the case in detail.
The more useful way to think: for each feature, which matters more during a partition, never being wrong or never being down? This is lesson 5.3's table again, viewed from the failure side:
| Feature | During a partition, prefer | Why |
|---|---|---|
| Claiming a username or giveaway code | Refuse (consistent) | Two winners is worse than a short error |
| Changing account email or password | Refuse | Security-sensitive; must have one truth |
| Posting | Accept, if possible | Posts are new rows with new IDs, so they can't conflict (lesson 5.3) |
| Liking | Accept | A like is a new row, and counts are already eventual (lesson 4.5) |
| Reading feeds and profiles | Answer from what you have | Slightly stale is far better than nothing |
So "CP or AP" isn't a property of Chirp. Within Chirp, usernames are CP and likes are AP, and each feature's code decides what to do when the leader is unreachable.
Chirp's ninety seconds were "CP for everything," by accident: every write from zone B failed, including likes and posts, which could safely have been accepted and caught up later.
Step 5 of 14 · 1 min
Majorities: how one side keeps going
There's a middle path that most well-designed systems use, and it fixes the split-brain risk too.
Suppose a shard has three copies across three zones, instead of two across two. When the network splits, one side always has at least two of the three: a majority. A rule follows naturally:
Only the side with a majority of copies may elect a leader and accept writes.
The majority side carries on normally: its users can read and write. The minority side, the zone cut off alone, refuses writes (it might still serve possibly stale reads). When the partition heals, the minority side catches up from the majority. There can never be two leaders, because there can't be two majorities.
This is the principle behind consensus protocols like Raft and Paxos (lesson 6.5), and behind the leader-election systems in tools like etcd and ZooKeeper. It's why three is the usual minimum for anything that needs a leader: with two copies, a split leaves each side with exactly half, so neither side can safely continue.
Chirp's setup had two zones, so neither side of a split had a majority. Its failover was guessing. The fix was to add a third zone, even though it held only a small tie-breaking node for the failover system rather than a full database copy, so that failover decisions were made by a majority vote.
Step 6 of 14 · 1 min
PACELC: the trade-off you make every day
CAP only talks about partitions, which are rare: minutes a year, if you're lucky. In 2010, Daniel Abadi pointed out that there's a related trade-off you face all the time, even when the network is perfectly healthy. He called it PACELC:
If there's a Partition (P), choose between Availability (A) and Consistency (C). Else (E), when things are normal, choose between Latency (L) and Consistency (C).
The "else" part is the one that affects users every day. Even with no failures at all, keeping copies consistent means waiting for them. Lesson 2.5's synchronous replication is the clearest example: a write isn't confirmed until another copy has it.
- If the other copy is in the same zone, that wait is a fraction of a millisecond. Cheap.
- In another zone, a millisecond or two. Usually fine.
- In another region, tens or hundreds of milliseconds. Every write. That's a real cost users feel.
So every replicated system sits somewhere on this line: wait for more copies, and get stronger guarantees and less data loss in a disaster; wait for fewer, and get faster writes. Lesson 5.5's multi-region design is mostly a series of decisions about where to sit on it.
Some rough examples of how systems lean (all configurable to some degree):
- Single-leader databases like Postgres with asynchronous replicas favour latency in normal operation, and lose recent writes on failover (lesson 2.5).
- Cassandra and Dynamo-style stores favour availability and latency by default, with per-request settings (lesson 5.3's quorums) to lean the other way.
- Google's Spanner and databases inspired by it favour consistency, paying for it with cross-replica coordination on every write, and use careful engineering (including very precise clocks) to keep that cost as low as possible.
Step 7 of 14 · 1 min
What partitions really look like
Real partitions are rarely as clean as "two halves that can't talk":
- Partial. Zone A can reach zone C, and zone B can reach zone C, but A and B can't reach each other. Each sees a different picture of who's alive.
- One-way. A's packets reach B, but B's don't reach A.
- Slow, not broken. The link works but with huge delays, so timeouts fire and nodes think there's a partition. Lesson 6.1 covers why choosing timeouts is hard.
- Inside one machine. A long garbage-collection pause or a frozen virtual machine can make a perfectly healthy node look dead for several seconds. When it wakes up, it may still believe it's the leader. This is exactly the split-brain case lesson 2.5 warned about, and why fencing matters.
The practical rule: any node can be cut off at any time, for any length of time, and it might not know. Design so that a node which has lost contact stops making decisions only a leader should make.
Step 8 of 14 · 1 min
From the real world: 43 seconds, 24 hours
The best-documented CAP decision of the last decade is GitHub's, on 21 October 2018.
GitHub ran MySQL primaries in its US East data center, replicating to US West. Failover was handled by Orchestrator, a tool that runs a consensus group across sites and promotes a replica when a primary looks dead. During routine maintenance to replace failing network equipment, the connection between US East and the rest of GitHub's network was lost for 43 seconds.
In those 43 seconds, two things happened. Applications in US East kept writing to the East primaries, and those writes weren't replicated West. Meanwhile, Orchestrator's majority, which could no longer see the East primaries, promoted the West replicas, exactly as designed. When the network came back, GitHub had two histories: a few seconds of writes on the old East primaries that the new West primaries had never seen, and new writes on the West primaries since promotion. And apps in the East were now writing across the country, adding latency to every query.
GitHub's choice is the instructive part. Failing back to East quickly would have meant throwing away the writes made on West since promotion, or the stranded East writes. They chose not to lose data: they paused webhooks and Pages builds, restored from backups, let replicas catch up, and reconciled the stranded writes, while running degraded. That took 24 hours and 11 minutes.
It's CAP in practice: a partition happened, the system briefly stayed available on both sides, and paying back the consistency took a day. Two follow-ups GitHub described are worth copying: make sure automated failover can't promote across regions without the application layer being ready for it, and treat cross-region topology as something you test, not something you assume.
Step 9 of 14 · 1 min
Going deeper: how Spanner pays for consistency in milliseconds
PACELC says that even without partitions, you trade latency for consistency. Google's Spanner shows how far careful engineering can push that trade.
Spanner promises external consistency: if transaction T1 commits before T2 starts, anywhere in the world, T2's timestamp is greater than T1's. That needs timestamps that mean the same thing on every machine, and clocks on different machines never agree exactly. Spanner's answer is TrueTime: instead of returning "the time," it returns an interval, [earliest, latest], guaranteed to contain the real time. Google keeps that interval small with GPS receivers and atomic clocks in its data centers; the paper reported uncertainty (ε) typically between about 1 and 7 milliseconds.
The commit rule is then simple:
- Give the transaction a timestamp no earlier than TrueTime's
latest. - Wait until TrueTime's
earliesthas passed that timestamp, so the timestamp is definitely in the past everywhere. This is called commit wait, and it lasts about 2ε. - Only then make the commit visible.
Any transaction that starts after that moment, on any machine, will get a larger timestamp. The consistency guarantee costs a few milliseconds per write, and that cost is exactly proportional to clock uncertainty. That's why Google invested in clocks rather than algorithms, and why systems without such clocks (CockroachDB, YugabyteDB) take different approaches, like hybrid logical clocks (lesson 4.3) plus restarting reads that fall into an uncertainty window.
Step 10 of 14 · 1 min
What Chirp changed
- Added a third zone, holding a lightweight voting member for the failover system, so leader changes require a majority. A zone cut off alone can no longer promote its own leader.
- Shard leaders step down if they can't reach a majority for a few seconds, so an isolated old leader stops accepting writes (fencing, lesson 2.5).
- Per-feature behaviour when the leader is unreachable: likes and posts are written to a local queue and applied when the leader is reachable again (they can't conflict); username claims, account changes and giveaway codes fail with a clear error.
- Reads keep working from local replicas during a partition, and the app shows a small "you might be seeing slightly old data" notice if the replica is more than a minute behind.
- Ran a deliberate partition test between zones every quarter, during a quiet hour, to check all of this still behaves as designed.
Step 11 of 14 · 1 min
In the simulation
Stage 4 cuts the network between your zones (and, later, regions) for a few minutes. The dashboard shows which features errored and which kept working, and whether anything ended up inconsistent afterwards: duplicate usernames, two leaders, lost writes. Making everything CP is safe but painful; making everything AP is pleasant until reconciliation.
Step 12 of 14 · 1 min
If you're here for an interview
CAP comes up a lot, and it's a place where precise answers really stand out:
- State it correctly: during a network partition, choose between consistency and availability. Partition tolerance isn't optional.
- Avoid labelling a whole system "CP" or "AP" without nuance. Choose per operation, and give examples from the design you're discussing.
- Mention majorities: odd numbers of replicas, only the majority side writes, no split brain.
- Bring up PACELC: in normal operation, the trade-off is latency versus consistency, and that's the one that shapes everyday performance.
Step 13 of 14 · 2 min
Try these yourself
1. A system keeps two copies of each shard, in two zones, and lets either side elect a leader if it can't see the other. What happens during a partition, and what would you change?
Both sides may elect a leader and accept writes: split brain, with diverging data. Neither side has a majority, so neither can safely decide alone. Add a third voter (a third copy, or just a lightweight voting member in a third zone), and allow only the side with a majority to have a leader.
2. During a partition, a user in the minority zone tries to change their password. Should it succeed? What about liking a post?
The password change should fail with a clear error: it must have one authoritative value, and the minority side can't safely decide. The like can be accepted locally and applied once the partition heals, because a like is a new row that can't conflict, and counts are already eventually consistent.
3. A database is described as "AP." Does that mean it can never give strongly consistent reads?
Not necessarily. Many such databases let you choose per request, for example reading and writing with quorums (lesson 5.3), at the cost of more latency and of failing requests when too few replicas are reachable. The label describes a default lean, not a fixed property.
4. Chirp's write leaders are in Mumbai. Someone suggests synchronous replication to a replica in Frankfurt "for safety." Using PACELC, what's the trade-off?
In normal operation, every write would wait for a round trip to Frankfurt, well over 100 ms added to every post, like and follow. In exchange, losing the Mumbai region would lose no confirmed writes. A common middle ground: synchronous to another zone in Mumbai, asynchronous to Frankfurt (lesson 5.5).
5. A leader node freezes for 20 seconds because of a long garbage-collection pause. Meanwhile, the others elect a new leader. What must happen when the old leader wakes up?
It must not accept writes as if it were still the leader. Systems prevent this with fencing: a leadership term number or token that the storage layer checks, so writes carrying an old term are rejected, or by having leaders stop accepting writes when they can't confirm they still hold a majority's support. Lesson 6.5 goes into this.
Step 14 of 14 · 1 min
Further reading
- Eric Brewer, "CAP Twelve Years Later: How the 'Rules' Have Changed," IEEE Computer, 2012.
- Seth Gilbert and Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," 2002.
- Daniel Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer, 2012 (the PACELC paper).
- Martin Kleppmann, "Please stop calling databases CP or AP," 2015.
- Jason Warner, "October 21 post-incident analysis," GitHub blog, October 2018.
- James C. Corbett et al., "Spanner: Google's Globally-Distributed Database," OSDI 2012, section 3 (TrueTime) and 4.1 (commit wait).