An Illustrated Proof of the CAP Theorem

https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/

by networked • 8 years ago

209 71 8 years ago

mwhittaker.github.io

spraak• 8 years ago

Is partition intolerance the only piece of the three that disproves it? I'm curious to know more about how partition intolerance is handled.

apengwin• 8 years ago

The proof only shows that you can't get all three CAP. You can get any two out of three though.

In practice, partition tolerance is the most important property to have, since there's no point in having a distributed system if it can't function if any part of the system is down (it has to be fault tolerant).

Chickenosaurus• 8 years ago

Partition tolerance isn't about a system's behavior when some part of the system is down. Partition tolerance is about preventing diverging state in multiple sets of nodes that can't reach the nodes in another set, usually because of networking problems.

MaxBarraclough• 8 years ago

partition tolerance is the most important property to have, since there's no point in having a distributed system if it can't function if any part of the system is down

This is really a question of definitions, no?

If partition-tolerance is a defining property of a distributed database system, then of course they all have it. Plenty of database systems don't have partition-tolerance: non-distributed database systems.

lucio4• 8 years ago

If partition tolerance is the most important property to have, you can have it, as long as you don't need "C", consistency.

fjsolwmv5• 8 years ago

There's no point in having a system if it's not available.

There's no point in having a system if it gives incorrect answers (inconsistent).

In the real world, you have to make tradeoffs.

Partition tolerant is "most important", it's awkwardly factored out of Availability -- "tolerant" is a variant of available. Your system can't be "partition intolerant "just because that means "not always unavailable".

Another way of looking at it is what you imply: "partition tolerant" is a synonym for "distributed".

std_throwaway• 8 years ago

Are there solutions that don't meet the formal definition but still perform just as good as if they did in practical situations?

(As in the formal definition is not what we actually need to get a consistent and reliable system for our real-world application. We need something a little less and then suddenly it's possible to get a similar solution that actually provides C A and P.)

fjsolwmv5• 8 years ago

Google Spanner

vortico• 8 years ago

Having never seen this theorem before, it seems so trivial that it's completely useless. If you have no guarantee of having connected systems, then of course you can't always have consistency between them if they're required to answer all requests. Am I missing something here? What are the applications of this idea, beyond assigning a name to a triviality?

mping• 8 years ago

The immediate application of it is that when you choose a DB, you should be able to tell if it's either CP or AP. The field is full of subtleties (eg Network is not 100% reliable so no system should be CA - it's way subtler but that is the gist of it. I'm no expert btw).

Lots of DB vendors have tried to circumvent the therorem by introducing their own concepts or stretching the definitions. "We can beat the CAP theorem"

amelius• 8 years ago

It would be nice to have an overview of existing/possible workarounds.

pdpi2• 8 years ago

is CA even possible in a distributed system though? I mean, it’s not like “the network never fails” is a design decision you’re allowed to make (short of removing the network altogether and therefore not being a distributed system at all)

lucio4• 8 years ago

What about partial partitions, let's say you have 7 nodes, and 4 of them can't see the other 3, while the client can see all of them?

There are systems tolerant to these partitions (see PAXOS)

vladf• 8 years ago

Your definition of tolerant is incompatible with availability from CAP. The Paxos 3/7 minority in your example can't make progress when partitioned from the other 4 machines.

Smaug123• 8 years ago

I'm not really a fan of that proof because it's a proof by contradiction in the least helpful sense. It doesn't tell you why the theorem is true; only that some assumption was wrong. Much better would be if the proof were accompanied by examples of systems that had CA but not P, CP but not A, and so on, to show that this result is best possible.

gregorygoc• 8 years ago

Proof by example or analogy is not a proof.

pdpi2• 8 years ago

Sure — but, given the proof by contradiction, the examples would then illustrate the trade offs that the theorem forces.

taeric• 8 years ago

This sounds wrong to me. Do visual proofs not count?

throwawaymath• 8 years ago

Proof by example can be a proof. It depends on the theorem statement.

federicoponzi2• 8 years ago

Proove that you can walk. Walk. Prooved by an example. Basically to prove that something exists or that a property is not valid for every element of a set, you can proove with an example.

posterboy2• 8 years ago

So you are saying that to show that less is the best you can do would be the next step, and by extension you could ommit the first step and go directly to show cp or ap was optimal. But showing the contradictiin us what motivates the first step. Going the other way around, "thus cap is not in the set of optimals" shows less and begets the question.

fjsolwmv5• 8 years ago

"begets the question" is a beautiful solution to the "begs the question" error, but I think in this case you meant "begs the question"?

otakucode2• 8 years ago

It doesn't tell you why the theorem is true; only that some assumption was wrong.

A proof establishes truth, it does not typically explain. And yes, some assumption was wrong. The assumed premise was wrong. A system which is consistent, available, and partition-resistant does not exist. The truth of the theorem that no such system can exist is proven. I imagine it's not the proof you dislike, but the article about it which you wish had more explanation which is reasonable. It would be a different matter to discuss which solution is "best possible", though, as that would vary greatly on the application. If you're running a bank, you would never want to sacrifice consistency. If you're running a blog, availability and partition-resistance is probably more important.

zzzcpan3• 8 years ago

If you're running a bank, you would never want to sacrifice consistency.

Banks do sacrifice CAP consistency. As it doesn't mean you don't have consistency at all or anything like that. Just that you don't wait for writes to become visible to all nodes.

jmd1• 8 years ago

Google’s Spanner database is very likely an example of overcoming CAP. There’s more details here: https://ai.google/research/pubs/pub45855. From what i’ve read, Google is able to do this because they control the physical data transfer infrastructure (the nuts, bolts, cables) which in many cases is the reason why CAP is defeated.

uluyol2• 8 years ago

The jist of the argument is that no DB gives 100% availability. That makes no sense. What if my client can't talk to anything? I'd still have to return a value.

So instead we talk about high availability. All sorts of things cause downtime besides network partitions. If the network is reliable enough, then you can still achieve high availability.

lucio4• 8 years ago

Does this mean that Spanner is a CA system as defined by CAP? The short answer is “no” technically, but “yes” in effect and its users can and do assume CA.
The purist answer is “no” because partitions can happen and in fact have happened at Google, and during (some) partitions, Spanner chooses C and forfeits A. It is technically a CP system. We explore the impact of partitions below.

...

Conclusion
---------
Spanner reasonably claims to be an “effectively CA” system despite operating over a wide area, as it is always consistent and achieves greater than 5 9s availability.

From the paper

Kenji• 8 years ago

Spanner is a CP system. Nobody can overcome proven theory that CAP is impossible to achieve all at once.

tlug2• 8 years ago

Is it just me, or the proof appears to be incorrect? In the last example, the write operation should simply block before returning "done" to the client, before it's able to replicate the state to the other server. In fact, in a fault-tolerant system there cannot be just two servers, because it would be impossible to achieve a majority vote.

DougBTX• 8 years ago

The example looks fine to me. If the writer blocks until the partition is resolved, then it isn’t Available for writes, so only meets CP.

tlug2• 8 years ago

OK, if you define the availability of writes in this way, that they must complete immediately, then indeed the availability part of CAP is not met.

However his definition reads: "every request received by a non-failing node in the system must result in a response"

It doesn't say anything about the timing of response. The network partition will be resolved eventually and thus the write operation will complete. Or it can time out and return an error, which is also fine based on the definition of availability (must result in a response).

j2kun2• 8 years ago

I was under the impression that the partition need never be resolved.

swagonomixxx• 8 years ago

Either the proof is incorrect or he/she set it up in a way to make it look extremely trivial.

The way I saw the proof go is: to satisfy CAP, you need replication, and you need high availability. To be consistent you need replication. But if you don’t have a reliable network, you don’t get reliable replication. Therefore you can’t be consistent. To me, this is a trivial result, and I’m not sure that this is what the CAP theorem intends to say?

It would be better to do, as you say, assume that a system is CA, And prove why it can’t be partition tolerant. Saying “network is unreliable” isn’t a suitable jump in argument IMO.

fjsolwmv5• 8 years ago

Trivial is subjective. The sketch of the proof is simple, but you skipped the details and it's not obvious to everyone at first.

j2kun2• 8 years ago

It's trivial because (when you say things like "high availability", which is not precise nor does it apply to CAP) you're ignoring the precision required for a valid proof.

dustingetz2• 8 years ago

"CP/AP: a false dichotomy" https://martin.kleppmann.com/2015/05/11/please-stop-calling-... . Martin Kleppman is the author of "Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems" https://www.amazon.com/Designing-Data-Intensive-Applications...

uluyol2• 8 years ago

I think that the CP/AP dichotomy is a good example of how we treat fundamental, but not hard tradeoffs as hard.

E.g. often we have a fundamental tradeoff between latency and throughput, and it's impossible to get 100% in both metrics. However, we can still do very well in both, and that's what matters in practice.

We have the same thing with CAP. You can build a CP system with high availability.

zzzcpan3• 8 years ago

Fundamental tradeoffs in CAP are latency/time for consistency, since real world networks are always partitioned. You are just using a different meaning of availability when talking about high availability, not the one from CAP.

dustingetz2• 8 years ago

When I speak about Datomic, my most frequent questions are about CAP theorem, which Datomic seemingly subverts to do seemingly impossible things (like aforementioned Spanner): http://www.dustingetz.com/:datomic-cap-theorem/

cconroy• 8 years ago

this proof is sound (for this simple structure) but does it imply you can never have all three (CAP) in some scheme where you can draw from many nodes and edges (not infinite) to handle partition failure while always being available and consistent? Perhaps a proof that you need to draw from infinite nodes and edges to achieve CAP would be interesting.

disclaimer: i am not well educated on the literature in Distributed systems :(

legacynl• 8 years ago

I was thinking the same thing. The ability to handle partition failure comes from having more nodes. This proves this is not possible when haviing just two nodes. Kind of makes sense as it stops being a distributed system if you disconnect all nodes.

y4mi• 8 years ago

The CAP Theorem thinks about guarantees, not probabilities.

There are various ways to reduce the impact and probability of partitions, but increasing the quantity of nodes does not make partitions impossible -- in fact, you now have to worry about n possible partitions (n being the number of nodes).

the only way to guarantee partition tolerance is by majority votum. If you do that, you can no longer guarantee availability. For example, a cluster of 11 nodes might be partitioned thrice. (2 + 4 + 5) None of the nodes are allowed to answer, breaking the availability guarantee.

gweinberg3• 8 years ago

If for any two nodes there is some path by which the nodes can communicate, the network is not partitioned. That's what partitioning means.

zzzcpan3• 8 years ago

In asynchronous networks you never have that. You never know whether you can communicate with the other nodes, until you try and get the response back. You can only reason whether you were able to communicate with other nodes about communications that already took place.

gweinberg3• 8 years ago

Once you understand exactly what is meant by the terms, the theorem seems immediately obvious. If your servers G1 and G2 cannot communicate with each other, of course you can't write data to G1 and read the updated data from G2.

gweinberg3• 8 years ago

Once it's clear what the terms mean, the theorem is so obvious as to scarcely need proof. If G1 and G2 can never talk to each other, of course you can't write data to G1 and read it back from G2.

I think the point is more about timing. If your client writes to G1, then you pretty much have to wait until the write has propagated to the entire network to acknowledge the write or accept some risk that some other client will read back stale data after the write has been acknowledged. I should think this would be obvious to coders also, but it is not at all obvious to managers.

I say "pretty much" above because there is technically a ridiculous third option where you essentially lock down the whole network with every read. But it still doesn't get you around CAP.

thanatos_dem• 8 years ago

The combination of partition tolerance being mandatory and the timing caveat is why I prefer to think in terms of an extended CAP theorem called PACELC[1].

The first part, PAC, is your traditional CAP theorem - in the presence of partitions (P), you can provide either availability (A), or consistency (C). The second part, ELC, describes the system characteristics during the normal, non-partition case. It reads as "else (E), you can provide either low latency (L) or consistency (C)".

Even tho apart from some curious outliers most systems are either PA/EL or PC/EC, I find the framing helpful for reasoning about a system in more than just the partition or failure case.

[1] https://en.wikipedia.org/wiki/PACELC_theorem

martincmartin• 8 years ago

Your first paragraph is spot on. The rest is overstating things though.

"If your client writes to G1, then you pretty much have to wait until the write has propagated to the entire network to acknowledge the write"

PAXOS, for example, just needs it to be written to a majority of nodes.

If you write it to node "key % n", where n is the number of nodes, then only that single node needs to be up & available to all writers / readers.

blt• 8 years ago

This proof is missing a step showing that the problem exemplified by the simple two-node system applies to all system topologies. This website only proves: "there exists a system for which CAP is impossible." I do not think the generalizing argument will be complicated, but it should be included.

curlypaul924• 8 years ago

I noticed this as well. Now I'm wondering -- how would one generalize this proof, keeping the same easy-to-grok style?

otakucode2• 8 years ago

I know this is probably a stupid question, but please humor me. Since the Client node has bidirectional communication with both servers, why can it not be used as a channel to facilitate communication between the two servers when a direct link is not available?

pram• 8 years ago

I think in that case the client would essentially be another broker. It would need to understand the cluster topology and manage replication awks etc. It would resemble a p2p protocol like BitTorrent.

I think that might also make split brain situations more likely if all the client brokers didn’t have the entire cluster topology known. You’d end up with different data in different places if the clients are partitioned in addition to the brokers.

akeck• 8 years ago

Is there a paper about proving whether or not an arbitrary system is subject to the CAP theorem?

mcintyre19942• 8 years ago

What if you added a rule that if 2 nodes lose communication then after some period T the lowest ID node kills itself? And you add a delay of 2T to all client/server communication to give that a chance to happen.

Then in the example, client writes to V1, V1 waits T time to communicate with V2, it doesn't manage to so it returns failure to the client and kills itself. Then the client writes + reads to V2 instead.

Does this break availability because returning an error that you can't act on a client request counts as ignoring it in this informal definition?

sobani• 8 years ago

Returning an error is basically saying "I'm not available", because there is no guarantee there is an alternative.

Your example can't deal with there being no path at all between V1 and V2. So even the client can't reach V2. In that case the entire system V is unavailable to the client.

Availability in CAP is about being able to reach a node, but not all of them and because of that the system doesn't function. I guess killing a node when a problem occurs can be argued to defeat CAP (all the nodes that are up can reach each other), but it definitely doesn't improve the situation.

Also what does you system do when V5 out of a 5 node cluster crashes? Do the nodes V1-V4 kill themselves, because they can no longer reach a higher ID node?

mcintyre19942• 8 years ago

Ah I see what you mean, fair point - I'd agree that doesn't really work!

TBH my 2-node system was a simplified version of Corosync which I've worked with a bit, in that you allow quorum if you have half+1 of nodes up - so 4/5 up will maintain quorum. The highest-node lives rule is just a tie breaker in the case of a half/half split which the 2 node system always has when one node goes down. Good point though, that rule alone is definitely not a good idea.

An Illustrated Proof of the CAP Theorem

Related Stories