CAP, Properly

Here are two commands. Same database. Same machine. Same second. The only difference between them is one word.

I ran both of those on a real three-node Cassandra cluster while the network was really, physically cut in half. The first one stayed available and handed me a possibly-stale answer. The second one chose to stay consistent and, being unable to, refused to speak to me at all.

So here's my question. Which of those is Cassandra?

It's a trick question. They're both Cassandra. Same cluster, same node, same partition, two seconds apart. The database didn't choose anything. I chose, by typing a different word.

Almost everything you have been told about CAP is downstream of a sentence that is simply not true — "pick two of the three." You don't pick two of three. You don't get to pick at all until the network breaks, and when it does, the thing making the choice is usually a flag on a query or a timeout in a config file that somebody left at the default.

This lesson is mostly demolition. Let's start with the question you already asked.

Back in Replication Topologies, we drew multi-leader replication, cut the link between two leaders, and watched both of them cheerfully accept a write to the same row. And I said that if you were now asking the obvious follow-up — during a partition, what should the system do? Keep taking writes on both sides and sort it out later, or refuse writes until it's sure who's in charge? — then you had just independently discovered the question that this lesson exists to answer.

So let's answer it, in plain words, before any theorems get involved:

When the network splits, every node on your system faces exactly one decision: answer, or wait.

Answer, using only what it can see locally — and risk being wrong, because the other side may know something it doesn't.

Wait for the other side to confirm — and if the other side never comes back, wait forever. Which, from the point of view of the human staring at your spinner, means be down.

That's it. That is the whole of CAP, and you could have derived it yourself on a napkin. Answer and risk being wrong, or wait and risk being down. Everything else in this lesson is either a proof that there is no third option, or a catalogue of the ways people pretend there is.

Consistency, Availability, Partition-tolerance: pick any two. You've seen the triangle. It's on a thousand slides and it's in a thousand interview answers, and it is wrong — not subtly wrong, but wrong in a way that makes people design worse systems.

Here is why. Partition tolerance is not a property you choose. It's a property the universe chooses for you. Gilbert and Lynch, in the paper that actually proved this thing, define a partition as the network being "allowed to lose arbitrarily many messages sent from one node to another" — and then they drop this parenthesis, which is the most important sentence in the whole paper and which almost nobody quotes:

"And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact instant the message is lost."

Read it twice. A single dropped packet is a partition. Not a severed transatlantic cable — a packet. One. The kind your network drops thousands of times a day and nobody files a ticket about.

So "we've decided not to be partition-tolerant" is not an architecture. It's a sentence like "we've decided not to have gravity." P is not a slice of the pie. P is the weather. You don't pick it; you dress for it.

Which means the triangle collapses into something much smaller, and much more useful:

You have C and A almost all of the time — the network is usually fine, and you get both, for free.
When a partition happens, and only then, you must give up one of them.

That's the theorem. It's not a menu with three items. It's a bill that arrives on the bad days.

You should see why it's true, because the proof is genuinely five lines long and it will change how you think about distributed systems generally — not just about CAP.

Split your nodes into two groups, G1 and G2, and cut every message between them. Call the value everybody starts with v0, and the new value somebody is about to write v1.

1. Somebody writes v1 to a node in G1. Availability says every request to a working node gets an answer — so that write must complete. It does. G1 now holds v1.
2. Somebody reads from a node in G2. Availability says that read must complete too. But no message from G1 ever arrived, so G2 answers with the old value, v0. It has nothing else to answer with.
3. Now the kill shot. From G2's point of view, that execution is identical to one in which the write never happened at all. Every message that would have told G2 otherwise was dropped. The bytes arriving at G2 are the same bytes in both worlds.
4. So G2 must return v0 — it is physically incapable of distinguishing "a write happened and I wasn't told" from "no write happened."
5. But the read began after the write finished. A read that starts after a write completes and returns the pre-write value is, by definition, not linearizable. Consistency is broken. ∎

That's it. That's the CAP theorem.

And notice what it actually says, because it's deeper than "you can't have all three." It says:

The read cannot tell the difference.

Not it's expensive to tell the difference. Not it's slow. It has no information with which to tell. You cannot make a correct decision using facts you do not possess, and a node on the far side of a partition does not possess them. Every impossibility result in distributed systems is, at heart, this same move — construct two different worlds that look identical to somebody, and then point out that they have to behave the same way in both.

So when a node behind a partition answers you, it isn't being clever. It's guessing, and it doesn't know it's guessing.

Enough theory. I built a three-node Cassandra cluster — cap1, cap2, cap3 — put Ana's shopping cart on all three, and then physically detached cap3 from the network. One node alone on one side, two nodes on the other.

I also turned off every self-healing feature Cassandra has (read_repair='NONE', hinted handoff disabled), because those mechanisms exist precisely to hide the damage I'm about to show you. Watching them repair it is the next lesson. Today we look at the wound.

The first thing I did was ask each side what it thought the world looked like.

Look at that carefully, because it's the whole problem in six lines.

Each side has declared the other one dead. Both of them are wrong. Neither of them is lying.

cap3 is in perfect health — the process is up, the disk is fine, it is serenely unaware that anything has happened. And cap1 has just filed it as DN, Down. Meanwhile cap3 has filed a matching report about cap1 and cap2. Both sides believe they are the survivors.

This is the proof from the last section, walking around in the world. Neither node can distinguish "they died" from "I got cut off." From the inside, those two catastrophes look exactly the same: the messages stopped.

Now, with the network still cut, I sat on the lonely node — cap3, the minority of one — and ran the two reads from the top of this lesson.

The first request is an AP request. It shrugged, read its own local copy, and gave me an answer it could not possibly verify. It stayed available and it accepted the risk of being wrong.

The second request is a CP request. It needed two replicas to agree and it could only reach one, so it did the honourable thing: it refused to answer at all. It stayed consistent by becoming unavailable — which is the exact behaviour The Consistency Spectrum predicted when it said that a linearizable system facing a network fault must either wait or error, and either way, it becomes unavailable. There it is, in an error message.

And now the point of the entire lesson:

Cassandra did not choose. The database did not choose. The flag on the query chose.

So the next time somebody tells you "MongoDB is CP and Cassandra is AP," you now know that sentence is not even wrong — it's the wrong shape. CAP is not a property of a database. It is a property of a single request. One cluster served me a CP request and an AP request out of the same node, in the same partition, inside the same second.

Brewer, the man who invented CAP, says exactly this in his own retraction: the choice between C and A "can occur many times within the same system at very fine granularity." Your shopping cart can be AP while your checkout is CP. They can be different tables. They can be different queries against the same table. That is the level at which this decision actually lives — and it's a level where you have real, cheap, per-endpoint control.

One more thing from that cut cluster, because it corrects a fear that makes people choose AP when they didn't need to.

While cap3 sat there refusing QUORUM reads, I ran the same QUORUM read on cap1 — the majority side. It worked. Instantly. Correctly.

Choosing consistency does not take your system down. It takes the minority down.

Two of the three nodes could still see each other, which means they could still form a quorum, which means they could still be sure. They kept C and they kept A, straight through the partition, because there was nothing they needed from the far side.

So the real cost of a CP system isn't "we go offline when the network hiccups." It's narrower and more manageable than that: whichever side of the split is smaller stops serving. Design your replica placement so that the side that stops serving is the side you can afford to lose — and suddenly "we chose consistency" costs a great deal less than the slide deck implied.

Now let's find out what the other choice actually costs, because "the data might be a bit stale" is a gross under-description and I want to show you the real thing.

Still partitioned. Ana is shopping. Her requests are being routed to whichever side of the split she can reach, which — because she's on a train — turns out to be both, at different moments.

On the majority side she adds a hat, and that write goes through at QUORUM: two replicas acknowledged it. It did everything right. It is, by any definition you like, a properly committed write.

On the minority side she adds a lamp, and that write goes through at ONE: a single lonely node accepted it and told her it was saved.

Then I healed the network and let the cluster come back together. Here is what each replica physically held on disk afterwards:

Twelve out of twelve. The hat is gone.

Sit with how offensive that is. The hat was written on the majority side. It was written at QUORUM. It waited for two acknowledgements and it got them. Two of the three replicas are still physically holding it right now. And it lost — completely, permanently, everywhere — to a write that a single isolated node accepted from a client that asked for no guarantees whatsoever.

Why? Because the lamp's timestamp was 1.99 seconds later, and the conflict was settled by comparing timestamps.

A timestamp is not a vote.

This is the sharp edge of the quorum promise from two lessons ago, and I warned you it was coming: R + W > N buys you overlap — your read is guaranteed to touch a node that holds the newest write. It does not buy you popularity. Two out of three replicas hold the hat and the hat still loses, because "newest" is decided by a clock, not by a headcount.

Ana was told her hat was saved. It is not saved. Nobody will ever tell her. No error was raised, no alert fired, no log line was written in red. The system worked exactly as designed and it quietly ate her data.

That is the bill for availability. Not staleness — loss. And notice we have now walked straight into the next question: when two writes collide like this, is last-timestamp-wins really the best we can do? (It is not, and it is not even close. That's Version Conflicts, and it's coming.)

There is one more piece, and it's the piece that turns CAP from trivia into something you can actually operate.

Everything so far assumed the system knows there's a partition. So let me ask the rude question: how?

Back on my cluster, I did something different. I didn't cut cap3 off and I didn't kill it. I froze it — a SIGSTOP, which is a perfectly faithful simulation of a monstrous garbage-collection pause. The process is alive. The network is fine. Every cable is plugged in. cap3 is simply… not answering right now.

Two queries, thirty seconds apart, against a machine whose state never changed once. The first one got a timeout — the system still had hope, so it held your request hostage while it waited. The second got Unavailable — the system had given up hope, convicted a healthy node of being dead, and stopped even trying.

What happened in between? A timer expired. That's all. That is the entire mechanism.

Gilbert and Lynch describe this precisely, in a section of the paper that people somehow never quote. Once you give nodes clocks, they say, a node waits for a reply and, if none arrives within 2 · t_msg + t_local, the node — and I am quoting — "concludes that the message was lost."

It concludes. It does not observe, discover, detect, or know. It runs out of patience and it guesses. And the paper is blunt about the consequence of guessing: it then answers from local state, and "in this case, atomic consistency may be violated."

So here is the thing to carry out of this lesson if you carry nothing else:

A partition is indistinguishable from a slow node. "Detecting a partition" is just giving up waiting. And the length of time you wait before giving up — that timeout, sitting in a config file, probably still set to the default — IS your CAP choice.

That's what the failure-detector dial from Sync vs Async Replication & Failover really was. We tuned it back then as an availability knob: too slow and you're down for longer, too fast and you get a false positive and two leaders. Now you can see what you were actually adjusting. You were choosing, in milliseconds, how much consistency to trade for how much availability, on every request, forever.

Nobody in your organisation thinks of that number as an architectural decision. It is the most important one in this lesson.

Let's clean up the vocabulary, because these phrases get people into real trouble.

"We're a CA system." There is no such thing, and saying it out loud is a reliable way to tell a room full of people that you haven't thought about the network. Gilbert and Lynch are explicit: CA is achievable "if there are no partitions" — that's not a design, that's an assumption, and it's an assumption the universe will violate on a Tuesday afternoon. A single-node database is "CA" only in the trivial sense that it has no network to break. The moment you replicate, CA leaves the menu. "We're CA" means "we're CP or AP and we haven't found out which yet."

"CAP-available" doesn't mean what you think it means. The paper's definition is "every request received by a non-failing node must result in a response" — and then, remarkably, it "puts no bound on how long the algorithm may run before terminating." A system that answers you next Tuesday is CAP-available. Meanwhile your beautiful 99.99% SLA, with its p99 latency budget, is not CAP-A if a single non-failing node is ever allowed to return an error. It's a different word that happens to be spelled the same. Your uptime number and CAP's A have almost nothing to do with each other.

And the theorem's own corners are ridiculous. Read §3.2 of the paper and you find that a perfectly CP system can be built by "the trivial system that ignores all requests" — a machine that answers nothing is flawlessly consistent and partition-tolerant — and a perfectly AP system can be built by "trivially return[ing] v₀, the initial value, in response to every request." A machine that always lies in exactly the same way is flawlessly available.

A theorem whose winning entries are "say nothing" and "always lie" is not a design tool. It is a constraint. Use CAP to know what you cannot have. Never use it to pick a database.

In 2012, Eric Brewer — who proposed CAP in the first place — wrote an article whose entire purpose was to stop people doing what everybody was doing with it. He opens by conceding that "the '2 of 3' formulation was always misleading because it tended to oversimplify the tensions among properties," and then points out how small the theorem's territory actually is:

"CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare."

Partitions are rare. So a design that forfeits consistency permanently, or availability permanently, in order to "be an AP system" or "be a CP system", is paying a tax every day for a problem that arrives occasionally. That's a bad trade, and it's the trade the triangle talks you into.

What Brewer proposes instead is not a letter. It's a plan, and it has three steps:

1. Detect the partition. (Which — as we now know — means give up waiting, at a threshold you chose.)
2. Enter an explicit partition mode, and deliberately limit what the system will do. Not "fall over", not "carry on regardless" — a designed, degraded mode where you have decided, in advance, which invariants you are willing to risk.
3. Recover when the network comes back: restore consistency, and — this is the part people skip — compensate for the mistakes you knowingly made while you were degraded.

And the example he uses is the best one in distributed systems, because it's the one that's been running in the street outside your flat for forty years.

The ATM. An ATM cannot always reach the bank. When it can't, it faces our question exactly: refuse, or answer? And it answers — it gives you money — because a cash machine that refuses to dispense cash is a worthless cash machine. But it doesn't answer blindly: it caps the withdrawal at some limit, say $200. It has accepted a bounded risk of violating the invariant balance ≥ 0.

And when the network comes back and it discovers you were overdrawn all along? It doesn't crash, and it doesn't pretend nothing happened. It charges you an overdraft fee.

That fee is a compensating transaction. The bank did not solve CAP. The bank priced it.

They worked out that "customers can always get $200" is worth more than "the balance is never momentarily wrong," they bounded the downside, and they built a business process to clean up the difference. Nobody at that bank chose a letter. They made a product decision and then made the system implement it.

That is what a real CAP decision looks like. It is almost never a database setting. It's a sentence like "during an outage, a customer may add to their basket but may not complete a purchase" — and that sentence belongs to your product manager as much as to you.

This is a lesson about a decision, so you should make the decision rather than read about it.

Below is a five-node cluster with a client on each side. Cut the link and the two halves stop being able to see each other — exactly as cap1 and cap3 did. Then send requests, and for each one pick the consistency level you want. That single flag is the whole of CAP, and here you get to hold it in your hand.

Try this first. Cut the link. Then, from the minority side, send a read at ONE — it answers. Send the identical read at QUORUM — it refuses. You just built a CP system and an AP system out of the same cluster, in the same partition, by changing one word.

Then go and do damage. Write to both sides at ONE, heal the network, and see whose write survived — and whose was silently eaten. Try to find a setting where nobody loses anything and everybody stays up. You will not find one. The proof from earlier says it isn't there, and the point of this widget is to let you fail to find it with your own hands, which is a much more durable form of knowing.

And watch the clock in the corner, because the last dial is the honest one: how long does a node wait before it decides the other side is dead? Turn it up and the system hangs on, choosing consistency, making your users stare at a spinner. Turn it down and it gives up early, choosing availability — and sometimes convicting a node that was merely slow.

None of this is useful unless it changes something you do. So:

Stop asking "are we CP or AP?" It's the wrong unit. Ask it per operation, because that's the granularity the machine actually works at. Add to basket should almost certainly stay available and risk a merge; take payment should almost certainly refuse rather than double-charge. Those are two different answers in the same request path, on the same database, and both are one flag away.

Go and look at your timeouts. Right now. Find the client-side request timeout, the failure-detector threshold, the health-check interval. Somebody set those, probably to the default, probably years ago. Those numbers are your real CAP policy — far more than whatever the vendor's marketing page claims about the letters — and I would bet a large sum that nobody has ever reviewed them as an architectural decision.

Write down your partition mode before you need it. When the split happens at 3am, the system will do something. The only question is whether that something was designed or accidental. Which operations degrade? Which refuse? Which invariants may be bent, and by how much (the ATM's $200)? What's the compensating action when you come back (the overdraft fee)? If you can't answer those, you don't have a CAP strategy — you have a CAP outcome, and you'll read about it in the incident review.

Place your replicas so the minority is the side you can afford to lose. If you go CP, some side stops serving during a split. Make sure it's the small one, and make sure you know which one it'll be.

"Pick two of the three." No. P is not on the menu — one dropped packet is a partition, and you don't get a vote on dropped packets. You have C and A on the good days; on the bad day you give up one of them. It's a bill, not a buffet.

"We're a CA system." No such thing once you replicate. CA is not a design, it's a bet that the network never fails, and it's a bet you will lose.

"MongoDB is CP, Cassandra is AP." Wrong shape. One Cassandra cluster served me a CP request and an AP request from the same node, in the same partition, seconds apart — I only changed a flag. CAP is a property of a request, not of a product.

"CAP-available means our site stays up." Different word, same spelling. CAP's A has no time bound at all (an answer next Tuesday counts) but demands that every non-failing node answer every request without error. Your uptime SLA is neither necessary nor sufficient.

"A partition means a cable got cut." A partition is anything that stops a node answering in time — and you cannot tell it apart from slowness. I froze a healthy node and the cluster declared it dead. It was fine the whole time.

"The system detects the partition." It guesses. After 2 · t_msg + t_local a node "concludes that the message was lost" — the paper's own word. Your timeout is your CAP choice.

"During a partition, the system goes down." The minority goes down, and only if it wanted consistency. The majority keeps both C and A — I measured it.

"Choosing availability just means slightly stale reads." It means a fully-acknowledged quorum write can be silently destroyed by a lonely node with a faster clock. Twelve times out of twelve. Availability is not free; it is paid for in other people's data.

• The real question is: answer, or wait? Answer from local state and risk being wrong; wait for the far side and risk being down. There is no third door — and the proof is that the read cannot tell the difference between "a write happened and nobody told me" and "no write happened."
• P is not a choice. "Any pattern of message loss can be modeled as a temporary partition." You get C and A almost always; the theorem only bills you on the bad days.
• CAP is a property of a request, not of a database. Measured: same cluster, same partition, same second — CL=ONE answered (AP), CL=QUORUM refused (CP). Choose per operation, not per vendor.
• Choosing consistency costs you the minority, not the system. The majority side kept C and A throughout the partition.
• Choosing availability costs you data, not freshness. A CL=ONE write from one isolated node destroyed a fully-acknowledged QUORUM write, 12 times out of 12, because a timestamp is not a vote.
• Nobody detects a partition; they give up waiting. A partition is indistinguishable from a slow node. Your timeout is your CAP policy, and it's currently set to whatever the default was.
• Stop picking letters. Detect, degrade deliberately, compensate — the ATM gives you $200 and charges you a fee. It didn't solve CAP; it priced it.

And notice the assumption we've been making all lesson: that this only matters when the network breaks. But a healthy network still has a width. Your replicas are still 70ms apart when everything is perfectly fine, and something still has to give. That's PACELC, and it's next.