PACELC: CAP's Grown-Up Sibling

I want to show you a stale read.

Not an interesting one. Not one caused by a severed cable or a dead node or a network partition — we spent the whole of the last lesson on those. This one happened on a completely healthy three-node cluster. Every node up. Every cable plugged in. Zero errors. Nothing in the logs.

Nothing went wrong here. This is the system working exactly as designed, on its best day, with a perfect network — and it still handed me data that was out of date.

And that should bother you, because everything we've built so far says the trade-off only shows up when the network breaks. CAP, Properly was entirely about the bad day: the partition happens, and you must choose. But partitions are rare — Brewer said so himself, and I quoted him.

So what's the excuse today? The network is fine. Nothing is broken. And I am still being handed stale data, and I am still apparently choosing between correctness and speed.

It turns out CAP was only ever telling you about the worst day of the year. There is a second trade-off, it runs every other day, and almost nobody talks about it — even though it is the one that has actually shaped the databases you use. It has a name, and it's the ugliest acronym in distributed systems: PACELC.

Daniel Abadi wrote the paper that names this thing, in 2012, and he opens by pointing at the gap:

"CAP only posits limitations in the face of certain types of failures, and does not constrain any system capabilities during normal operation."

Read that again with your operational hat on. CAP is a statement about failures. It has nothing whatsoever to say about what your database does on a Tuesday afternoon when everything is green.

Which is a strange gap, when you think about how you actually spend your time. Your partition budget for the year is, what, a few minutes? Maybe an hour, on a bad year. The other 364 days and 23 hours, your users are still waiting for responses, and your replicas are still disagreeing with each other — and CAP has offered you precisely no guidance about any of it.

So Abadi proposed an extension. Not a replacement — an extension, one that keeps CAP and then finishes the sentence:

PACELC (pronounced "pass-elk," which nobody enjoys):
if there is a Partition (P), how does the system trade off Availability and Consistency (A and C) — that's just CAP, and it's the lesson you've already had —
ELSE (E), when the system is running normally, in the absence of partitions, how does it trade off Latency (L) and Consistency (C)?

That second half is the whole point. The first half is a lesson you already know. The second half is running in your production system right now.

Here is the part that made this click for me, and it's a single sentence from Abadi's paper that I think is the most under-quoted line in the whole field. He is explaining why this second trade-off is unavoidable, and he puts it in a parenthesis, almost as an aside:

"(Note the important difference between this tradeoff and the CAP tradeoffs: while the occurrence of a failure causes the CAP tradeoffs, the failure possibility itself results in this tradeoff.)"

Sit with that for a second, because it's beautiful.

CAP is caused by the network breaking. PACELC is caused by the network existing.

Follow the chain. You want your system to survive a machine dying — of course you do, that's the entire job. Surviving a machine dying means you cannot keep the only copy of the data on that machine. So you replicate. You made that decision because a failure is possible, not because one happened.

And the instant you have a second copy, you have a question you cannot escape: when someone writes, do you wait for the other copy before you say "saved"?

Wait, and you are correct, and you are slow — because the other copy is somewhere else, and "somewhere else" costs milliseconds that the speed of light will not refund. Don't wait, and you are fast, and you are — as we just saw — occasionally wrong.

"As soon as a DDBS replicates data, a tradeoff between consistency and latency arises."

There is no third option. There is no clever protocol that escapes it, and Abadi is blunt about it: "For data replication over a WAN, there is no way around the consistency/latency tradeoff."

So you never needed a partition. You only needed to have made a copy — which you did, on purpose, on day one, for excellent reasons. And you have been paying for it every day since.

Now for the thing that turns two acronyms into one idea.

You might reasonably be thinking that this is all a bit convenient — that CAP handles failures, PACELC handles normal operation, and we've simply drawn a line between two different worlds. But there is no line. Watch what Abadi does next:

"Note that availability and latency are arguably the same thing: an unavailable system essentially provides extremely high latency."

And then he goes further, and just deletes the distinction:

"I will eventually drop this distinction and allow the low-latency requirement to subsume both cases. Therefore, the tradeoff is really just between consistency and latency."

Think about what a partition actually is, from the point of view of the machine trying to serve your request. It sent a message. It is waiting. Nothing has come back.

That is also exactly what "slow" looks like.

There is no moment where the system receives a telegram saying PARTITION HAS OCCURRED. There is only waiting — and, eventually, a decision to stop waiting. Which is precisely what we discovered last lesson: nobody detects a partition; they give up waiting. The failure detector doesn't know anything. It runs out of patience and reclassifies the node as dead.

A partition is not a different phenomenon from latency. A partition is latency = ∞.

CAP is just PACELC with the wait-dial turned all the way up.

And now the two lessons fuse into one, and I can tell you what that timeout in your config file really is. It is the line where "slow" gets legally reclassified as "down." Below the line, you call it latency and you put it on a p99 dashboard. Above the line, you call it a partition and you write an incident report.

It was one dial the whole time. We just have two different words for the two ends of it.

And once you see it that way, something that used to look like a coincidence stops being one. Why is it always the same systems that stay up during a partition and have the best p99 on a good day? Cassandra doesn't have two separate clever mechanisms, one for speed and one for outages.

An AP system survives a partition for exactly the same reason it's fast on a Tuesday: it never asks anyone. It answers out of the nearest copy and gets on with its life.

It isn't two behaviours. It's one behaviour, and we gave it two names because we were looking at it on two different days.

Enough theory. Let's find out what the E in PACELC actually costs, in milliseconds, on real hardware.

Three-node Cassandra, replication factor 3. I never partition it. I never kill anything. I never pause anything. The cluster is green from the first command to the last. The only thing I change is the width of the network — using tc netem to put 35 ms of delay on each node's outbound traffic, which makes a round trip between any two replicas 70 ms. Cross-continent, in other words. The kind of deployment you get the moment somebody says the word "multi-region."

First, the control: everything in one rack, the way it probably is on your laptop.

Look at that. Asking for a quorum costs you nothing. Strong consistency is, to within noise, free.

And this is why this lesson is such a hard sell. If you have only ever run a cluster inside one datacentre, you have never seen the bill, so you reasonably conclude there isn't one. Abadi flags this exact trap: researchers measuring consistent reads on Amazon's SimpleDB found they cost almost nothing extra — but only "as long as the read request comes from a location that is physically close to the master."

Now let me move the replicas 70 ms apart. Nothing else changes. Nothing breaks.

A fifty-times tax for consistency, and not a single thing was broken.

There's no failure to point at, no incident to declare, nobody to page. The cluster is green. It is just that QUORUM means "go and ask a machine on another continent," and another continent is 70 ms away, and physics is not negotiable.

This is the E branch of PACELC, and it is on right now, in your system, on your best day. Nobody will ever write an incident report about it. It will just quietly sit in your p99 for years.

This is the point where everybody has the same instinct, and it is wrong, and I want to kill it with a measurement rather than an argument.

The instinct: my writes can stay fast and cheap at ONE; I'll simply make my reads use QUORUM, and then I'll be reading from a majority, so I'll be safe.

So I did exactly that. Write at ONE. Read at QUORUM. On the healthy cluster.

Still stale. You bought a slower read and you got nothing at all for it.

And you already know why, because we did the counting two lessons ago in Quorums: N, R, W (#23). W(1) + R(2) = 3, and 3 is not greater than N(3). The write set and the read set are not forced to overlap, so the read is perfectly free to touch two replicas that both missed the write. Which is exactly what happened.

To actually be consistent you need R + W > N — for instance W=QUORUM (2) and R=QUORUM (2), giving 4 > 3. Which means:

The consistency bill is not a 73 ms read. It's a 73 ms read and a 73 ms write.

"Just read at quorum" is a half-fix. It leaves you exactly as stale as you were, and slower. If you are going to buy consistency, you have to pay for the whole thing.

Once you accept that there are two questions and not one, you get a two-by-two, and every database you've heard of lands somewhere in it.

The first letter answers "what do you do when the network breaks?" (PA or PC). The second answers "what do you do when it doesn't?" (EL or EC).

PA/EL — Cassandra, Dynamo, Riak (on their defaults). Abadi: "if a partition occurs, they give up consistency for availability, and under normal operation they give up consistency for lower latency." These systems are fast and loose, always, on purpose. That's the whole product.

PC/EC — VoltDB/H-Store, BigTable, HBase, Megastore (and Spanner belongs here too). Abadi: "they refuse to give up consistency, and will pay the availability and latency costs to achieve it." They will make you wait, and if they can't be sure, they'll refuse to answer. Both bills, paid in full, cheerfully.

PA/EC — MongoDB. Consistent in the baseline, because reads and writes go through one primary. But when a partition hits, the old primary's un-replicated writes get dumped into a rollback directory while a new primary is elected — and the two versions of history diverge.

PC/EL — PNUTS (Yahoo's system), and this is the interesting one. Slow down here.

PNUTS is PC/EL. Read that carefully, because it's a strange combination:

• PC — when the network partitions, it chooses consistency and gives up availability.
• EL — when the network is perfectly fine, it chooses latency and gives up consistency.

Now watch what happens when you try to describe PNUTS using CAP alone.

CAP looks at PNUTS, observes that it picks consistency during a partition, and confidently stamps it "CP." A consistent system! And in doing so, CAP has completely failed to mention that PNUTS is serving stale reads all day long, on a perfectly healthy network, deliberately, for speed.

For the few minutes a year that PNUTS is partitioned, CAP's label is accurate. For the other five hundred and twenty-five thousand minutes, it is not merely incomplete — it is actively misleading. It tells you the system is consistent. The system is not consistent. It has never been consistent. It was never trying to be consistent, because it would rather be fast.

That is the entire argument for PACELC's existence, in one system. CAP is not wrong about PNUTS. CAP is silent about PNUTS, at exactly the moment you needed it to speak.

One caveat, and Abadi insists on it, so I will too — otherwise you will misread the table above:

"PC does not indicate that the system is fully consistent; rather it indicates that the system does not reduce consistency beyond the baseline consistency level when a network partition occurs — instead, it reduces availability."

So the letters are relative to each system's own baseline, not absolute. PC doesn't mean "linearizable." It means "doesn't get worse when the network breaks." A system can be cheerfully sloppy at baseline and still be a PC system, which is exactly what PNUTS is.

Now the part that will change how you listen in design reviews.

You have heard this a hundred times, and you may well have said it: "We're eventually consistent — we're an AP system, because CAP says you can't have everything." It sounds rigorous. There's a theorem in it.

Abadi puts a pull-quote in the middle of his paper, and it is a demolition:

"It is wrong to assume that DDBSs that reduce consistency in the absence of any partitions are doing so due to CAP-based decision-making."

Think about the logic of what people are claiming. CAP only forces a choice during a partition. So if your system is eventually consistent right now, on a Tuesday, with a perfectly healthy network — CAP is not making you do that. CAP has no opinion about your Tuesday.

Something else is making you do it. And we both know what it is, because I measured it: the difference between 1.45 ms and 73.20 ms.

Amazon didn't build Dynamo eventually-consistent because of a proof about network partitions. They built it eventually-consistent because Dynamo serves the shopping cart, and Amazon has data showing that "an increase as small as 100 ms can dramatically reduce the probability that a customer will continue to interact or return in the future." Facebook built Cassandra for Inbox Search. LinkedIn built Voldemort for their site. These are latency decisions. They were always latency decisions.

"The obvious conclusion is that reduced consistency is attributable to runtime latency, not CAP."

CAP is the alibi. Latency is the motive.

And this genuinely matters, because it changes the conversation you should be having. "We're AP because of CAP" sounds like an engineering constraint you're forced to accept — a law of physics, nothing to be done. "We serve stale data because we want p99 under 10 ms" is a product decision, and it's one somebody should probably be asked to sign off on. Same architecture. Utterly different conversation.

This whole lesson is about one dial, so go and turn it.

Below is a cluster whose replicas you can move. Drag them next door and then to the far side of the planet, and watch what happens to the two numbers that matter: how long a request takes, and how stale an answer you might get. Choose your consistency level for reads and for writes, independently — because, as we just proved, that's the only way to actually buy consistency.

Try this first. Put the replicas in the same rack and turn consistency all the way up. Notice it costs you nothing — this is the trap. Now drag them across an ocean without changing anything else. You just watched a system that seemed perfectly well-designed become fifty times slower, without a single thing going wrong.

Then find the honest configurations. Try W=ONE, R=QUORUM — the half-fix — and confirm with your own eyes that it is still stale, because R + W is not greater than N. Then pay properly, and watch the bill arrive on both sides.

And when you're done, cut the network. The dial doesn't change. It just goes all the way to the end — and the word on the screen changes from slow to unavailable. That is the whole of CAP, sitting at the far end of the PACELC dial, and this is the clearest way I know to show you they were never two different things.

Stop asking what letters your database is. Start asking what letters your endpoint is. Abadi classifies defaults, and every one of these systems lets you override the default per request — we proved that in CAP, Properly (#25), where one flag turned the same Cassandra node from CP to AP and back. Your system's real PACELC letters are whatever your engineers typed into the client config, endpoint by endpoint, mostly without thinking about it. Go and read them.

Look at where your replicas physically are, and then look at your consistency levels. Those two facts multiply. A QUORUM read is nearly free in one rack (8.03 ms against 8.43 ms) and costs 50× across a continent (73.20 ms against 1.45 ms) — and the config file looks identical in both cases. The day somebody adds a region is the day every strongly-consistent read in your system gets quietly repriced, and nothing in your codebase will change to tell you.

If you buy consistency, pay for the whole thing. R + W > N, or you have bought nothing. A QUORUM read on top of a ONE write is the worst deal in distributed systems: the full latency of consistency, with none of the consistency.

And say what you actually mean. If you're serving stale data to keep p99 low, that's a legitimate, common, often correct decision — Amazon made it deliberately for the shopping cart. But say that. Don't say "CAP made us." CAP didn't make you. You wanted to be fast. Own it, write it down, and let the product decide whether the trade is worth it — because it is a product question, not a physics one.

"CAP covers this." No. CAP is a statement about failures — it "does not constrain any system capabilities during normal operation." It describes the worst day of the year and is completely silent about the other 364.

"We give up consistency because CAP forces us to." No. CAP only forces a choice during a partition. If you're eventually consistent on a healthy Tuesday, something else is making you do that — and it's the 1.45 ms vs 73.20 ms. "Reduced consistency is attributable to runtime latency, not CAP."

"PACELC is about failures too." Backwards. The occurrence of a failure causes the CAP trade-off; the possibility of one causes the PACELC trade-off — because the possibility is why you replicated. It's always on.

"I'll just read at QUORUM and I'm safe." Measured: still stale. W=1, R=2, N=3 → 1+2 is not greater than 3, so nothing forces the sets to overlap. You must pay on the write too.

"Strong consistency is expensive." Only sometimes, and that's the useful part. It cost me nothing in one rack and 50× across a continent. It's a question about your map, not your database — exactly as The Consistency Spectrum (#24) found.

"PC means the system is consistent." No — and Abadi explicitly warns about this. PC means "doesn't get worse under partition," relative to its own baseline. PNUTS is PC and serves stale reads all day.

"PACELC tells me which database to pick." It classifies defaults. Defaults are per-request overrides in every one of these systems. PACELC describes a database's personality, not its destiny.

"A partition and high latency are different problems." They are the same axis. "An unavailable system essentially provides extremely high latency." A partition is latency = ∞, and your timeout is the arbitrary line where you decide to start calling it by the other name.

• PACELC: if Partition → trade A vs C (that's CAP); Else → trade Latency vs Consistency (that's every other day).
• CAP is caused by the network breaking. PACELC is caused by the network existing. The occurrence of failure triggers CAP; the mere possibility of failure made you replicate — and replication is what starts the bill.
• A partition is just infinite latency. "Availability and latency are arguably the same thing." CAP is PACELC with the wait-dial turned all the way up, and your timeout is the line where slow gets renamed down. It was one dial the whole time.
• Measured, on a cluster where nothing was ever broken: in one rack, a QUORUM read costs nothing (8.03 vs 8.43 ms). With the replicas 70 ms apart, it costs 50× (73.20 vs 1.45 ms), and a QUORUM write costs 58×. Distance is the multiplier, and the config file looks identical either way.
• "Just read at QUORUM" is a half-fix that buys nothing. R + W > N or go home — you must pay on the write as well.
• PNUTS is PC/EL, which CAP would happily label "CP" while it serves stale reads every minute of every day. That single system is the argument for PACELC existing.
• "We're AP because of CAP" is almost always false. CAP has no opinion about your healthy Tuesday. CAP is the alibi; latency is the motive — so say what you mean, and let the product own the trade.

And notice what we have quietly left broken. Every experiment in this lesson had Cassandra's self-healing switched off — I disabled read repair and hinted handoff so the staleness would stay on screen long enough for you to see it. In a real cluster, those replicas do catch up, and there is a specific, rather clever set of machinery that does it. That's Read Repair & Hinted Handoff, and it's next.