The author’s argument relies on the assumption that split-brain scenarios don’t occur in cloud services, which doesn’t match the theory or my personal experience.
What I’m saying is that well-designed and well-implemented systems can avoid split-brain scenarios by ensuring that writes only happen on the majority/quorum side of any split. This ensures correctness, while still practically offering high availability to clients in a large number of cases. The cases where this can’t happen - when the network is too broken - are rare and not a particularly large contributor to real-world availability.
Alternatively, systems can choose to allow split brain to happen, allow monotonic writes and weak read guarantees, and still have well-defined properties in the case of network partitions. This is less useful in cloud architectures, where establishing a quorum is generally a better architecture, but more useful in IoT, mobile, space, and similar applications.
As I say in the post, I’m not saying the CAP theorem is wrong, merely that it’s one of the least interesting things one can say about distributed systems tradeoffs (and that’s its irrelevant to thinking through the real tradeoffs in large classes of cloud architectures).
CAP is the trivial observation that if you have a database implemented by two servers, and the connection between the two servers is lost, then if you write to server 1 and then read from server 2, you won’t see the newly written value. I think at least some of the opposition to CAP comes from naming this “The CAP theorem” or here, “CAP Theory” (capital T).
Right. The “CAP Theorem” is either trivial (as you say), or just wrong (if we try use the “common sense” definition of A).
The best version I could state is probably “there exist network partitions that force a trade-off to be made between consistency and availability”, and even that’s more clunky than the flow-chart I borrowed from Bernstein and Das.
The way you wrote that made me realize that the CAP theorem is a deepity in the sense of Dennett: “A deepity involves saying something with two meanings—one trivially true, the other profound sounding but false or nonsensical.”
It may be trivial, but it’s still a theorem, since it’s not an axiom. Even easy theorems deserve proof and recognition when they have profound consequences.
I would disagree here. The pretentiousness around “The CAP Theorem” has had negative value, by obfuscating a trivial concept. The success of CAP in the memetic sense relies on NOT clearly explaining what it really means. If its purveyors clearly explained what it means and then called it “The CAP Theorem” afterward, that would be ok, but it also would look silly, which is why that doesn’t happen.
I don’t think this is is a fair assessment of CAP.
CAP says that if you have a distributed system over N nodes, then, in the presence of a partition (P) that system can be either correct (C) or available (A) — from the perspective of nodes/clients — but not both.
It is unclear what those words mean and when others have tried to pin it down they have ended up with that. See the paper that “proved” the CAP theorem (previously “Brewer’s conjecture”): https://users.ece.cmu.edu/~adrian/731-sp04/readings/GL-cap.pdf If you read the proof of Theorem 1 you’ll see lots of fancy words, but those words say nothing more than the sentence I wrote.
Personally I’ve never found the theorem or its terminology particularly confusing, but, to each their own, I guess! Mostly, I like CAP as a way to push back on overly optimistic engineering managers who want to insist on having both C and A in the data system(s) they commission from their engineers ;)
I’m not saying it’s confusing. I’m saying that if you pin the meaning down then you end up with the triviality that I wrote above. See the paper I referenced above, or the blog post mentioned by Corbin below, if you do not believe me.
I don’t think that “a system can be either consistent or available but not both” is a triviality. But, different strokes for different folks, I suppose.
If you prefer pictures, there is an illustrated proof using diagrams. Out of curiosity, which language would you use if you wanted a formal proof of CAP? I might be able to oblige.
Right, that is a pictorial way of saying “if you have a database implemented by two servers, and the connection between the two servers is lost, then if you write to server 1 and then read from server 2, you won’t see the newly written value”. If you think it is valuable to formalize this, Lean seems to be popular these days.
well-designed and well-implemented systems can avoid split-brain scenarios by ensuring that writes only happen on the majority/quorum side of any split
How would you convince someone this is well-designed without first explaining that it’s a CP system, and what that means?
I don’t think, from the client’s perspective, it’s particularly interesting to talk about partitions (rather than talking about the larger set of failures of infrastructure, software, and operations).
So what do we talk about? There are three options I find more interesting than CAP:
Talk specifically about client guarantees (e.g. “strict serializability”, “bounded staleness”, “linearizability”) offered to clients. This needs to consider the whole world of failure modes.
Talk about specific distributed systems problems and their safety and liveness definitions (e.g. “consensus”, “atomic commitment”). You can talk about these problems in context of a particular failure model (e.g. fail-stop, byzantine, etc) and what the achievable system properties are.
Talk about lower-level results with more specific an useful predictions and properties. Even of the well-known ones (e.g. FLP, CALM, etc), CAP is the least interesting of these.
The problems with CAP are the goofy definition of “availability”, the overly-broad assumptions people make based on that definition, and the over focus on partitions at the cost of more interesting failure models.
What would be a non-goofy definition of availability?
I agree that “partition” is, in practice, often just a synecdoche for a much broader class of failure modes. My experience has been that the specific details of those failure modes are rarely interesting to users. All that users really care about is that such failure modes exist; or, more precisely, that those failure modes are unavoidable, and the downstream consequences of that realization.
While I agree with you that such breakages are rare, they affect millions of people, as in an outage earlier this year disconnecting millions from the Internet. Affected countries are known for their commerce and financial-service providers would have had to fall back to eventual consistency rather than pause transactions.
I imagine it’s similar to describing a boolean value without covering the fact that radiation can cause bitflips. In actual hardware, for most systems, these are so rare that the flips can be detected and corrected by ECC memory, and you probably don’t care about double flips unless you’re in space. So is it really relevant for us to talk about radiation bitflips? Does it impact the semantics of our program?
The article points out that in some networked services we already have a mitigation (routing to the majority) and scenarios where this isn’t viable are rare. The argument is that it’s so rare that you don’t even need to think about it.
As it says, it’s not that it’s wrong, it just isn’t interesting. Similarly, I could use booleans that use redundant bits to avoid radiation, but I don’t, because it’s not really important to me even if I understand that there’s a real scenario where I could really end up in trouble.
What is doing the detection/coordination here? A load balancer? Can you describe maybe a little bit more about the specifics of what cloud products would allow this kind of transactional awareness of network failures?
DNS, multi-cast, or some other mechanism directs them towards a healthy load balancer on the healthy side of the partition
These are not transactional mechanisms in my experience so would need a loss of A?
That depends a lot on what you mean by A. But yes, the mechanisms (e.g. LB health checks) are not transactional, and depend on the fact that the database replicas use consensus for replication (in my particular example). This is a common pattern, and is the same fundamental idea as DynamoDB, Aurora, S3, and wide array of other cloud systems.
What I’m saying is that well-designed and well-implemented systems can avoid split-brain scenarios by ensuring that writes only happen on the majority/quorum side of any split
One property of CAP is that the only way that a writer can know if it’s writing into a majority/quorum or minority/non-quorum partition of a distributed system, is if that system is CP.
ensuring that writes only happen on the majority/quorum side of any split. This ensures correctness, while still practically offering high availability to clients in a large number of cases.
The only way to ensure that writes only happen on the majority/quorum side of a split, is to use some kind of consensus protocol (Paxos, Raft, etc.) which necessarily make the overall system a CP system, in the CAP sense.
This ensures correctness,
Yes.
while still practically offering high availability to clients in a large number of cases
You’re weakening the definition of availability, here, beyond what CAP requires.
Alternatively, systems can choose to allow split brain to happen…
Split brain is always a possibility, the only question is how a system behaves when it occurs.
…allow monotonic writes and weak read guarantees, and still have well-defined properties in the case of network partitions.
Yes! And CRDTs are basically the only way to do it!
I like the CALM and PACELC shout outs. I wish those were as talked about as CAP. If I talk about a CAP problem people feel like I’m being reasonable. If I try to talk about a CALM problem all of a sudden I’m going to be burning innovation tokens in someone’s brain.
I like PACELC a lot. Unfortunately I think it’s definition of “A” is still broken (at least in as far as it’s a statement about real-world trade-offs, and not bounds on worst-case behavior).
I like the CALM and PACELC shout outs. I wish those were as talked about as CAP.
I agree with you, PACELC is especially valuable in the SLO-driven world of commercial software.
If I talk about a CAP problem people feel like I’m being reasonable. If I try to talk about a CALM problem all of a sudden I’m going to be burning innovation tokens in someone’s brain.
This sounds very familiar and is no less disheartening to hear from another. Learning new concepts shouldn’t be considered a bad thing. While the operational costs of “unfamiliar technology” remain non-trivial, why compare them to the cognitive load of a new mindset which could simplify solutions?
You aren’t doing distributed system pedagogy a favor with posts like these. They come off as condescending and insular, which is already a problem in DS, they attract people that want to be seen as the smartest guy in the room.
Consider the … system [with] seven [where] six are on the majority side [and can both read and write to each other] … [and the seventh is partitioned]
OK! So you have a system of 7 nodes, which is partitioned into 2 partitions. One partition of 6 fully-connected nodes, and 1 partition of 1 fully-disconnected node.
The formalized CAP theorem would call this system unavailable, based on their definition of availability:
I’m pretty sure this is not true.
Assuming this network topology, a CP system with a two-thirds majority quorum requirement, would show to any client connecting to any of those 6/7 nodes in the majority partition that the system is available; and would show to any client connecting to that 1/7 node in the minority partition that the system is unavailable.
An AP system would maybe allow clients submitting write operations to that 1/7 minority node to see success responses, but only partial successes, which would be overridden if and when that 1/7 minority partition re-joined and re-synced with the majority cluster quorum. And that caveat in data consistency would necessarily be reflected in the API of overall system.
None of the clients [to the overall system] need to be aware that a network partition exists (except a small number who may see their connection to the bad side drop, and be replaced by a connection to the good side).
Huh? The whole point of the P in CAP is that client connecting to nodes in the minority side of the P don’t know that they’re in the minority side of the P!
If the partition extended to the whole big internet that clients are on, this wouldn’t work.
Correct!
But they typically don’t.
Er, what? — CAP (and PACELC and all that stuff) is about guaranteeing data consistency all of the time, not most of the time.
edit: I think maybe the disconnect here might be in the expectation of what a node in a system represents. I think maybe the author believes it represents any arbitrary client to the system, whereas I think most of the time it represents a well-defined server in the system. Maybe? Maybe not.
Yeah, that thing really is true, which creates the whole confusion. A in CAP is a very specific formal property, that doesn’t at all relate to practical meaning of availability. To quote CAP paper:
For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response.
…
The availability requirement (§2.2) implies that every node receiving a request from a client must respond,
This is a formal definition that means what it says, rather what you’d intuitively think it means.
If there are 7 servers in the system, one is partitioned, you direct a write request to the partitioned one and don’t receive a reply, then your system is not CAP-paper-available.
In Gilbert and Lynch’s specific formalization of the CAP theorem it is true (by their definition of ‘A’). I’m not aware of another formalization that makes sense (and doesn’t come down to a restatement FLP, or some other fundamental result).
Er, what? — CAP (and PACELC and all that stuff) is about guaranteeing data consistency all of the time, not most of the time.
Yes, of course. Worst-case system properties are important, and CAP is one framing of those worst-case system properties. I’m not claiming it’s false, I’m just saying it’s not the first (or most interesting) distributed systems trade-off to teach or learn. For nearly all builders of nearly all classes of multi-datacenter cloud-style systems, it’s not a particularly relevant trade-off at all (one reason is that p(two partitions|one partition) is so low that it doesn’t tend to really factor into the real-world availability of three replica systems on modern networks).
There are two interesting points in this post: 1) that the “eventual consistency” flowchart should be widely known and understood, and 2) that CALM etc. are more directly relevant to solving engineering problems than the CAP theorem. I found this very useful.
I would add that CAP is about framing the problem and constraining the solution space, not about solving the problem, and then lead into the discussion of what the solution space really looks like, which is the area in which the author seems to know quite a bit more than I do.
There are some mild inaccuracies here about partitioning which, combined with the overall tone, seems to have nudged us into a more critical mode rather than a receptive one. I would recommend that the author be less hyperbolic and rhetorically bombastic so that the good ideas here get wider coverage, rather than being lost in somewhat insipid debates about whether CAP is good or bad or more or less useful and so forth.
What alternative formalization would you propose? I’m not aware of another one that really fixes the problems with Gilbert and Lynch’s, and Brewer’s informal statement is either trivial (Gilbert and Lynch) or wrong (“real world” definition of ‘availability’).
The author’s argument relies on the assumption that split-brain scenarios don’t occur in cloud services, which doesn’t match the theory or my personal experience.
That’s not what I’m saying, no.
What I’m saying is that well-designed and well-implemented systems can avoid split-brain scenarios by ensuring that writes only happen on the majority/quorum side of any split. This ensures correctness, while still practically offering high availability to clients in a large number of cases. The cases where this can’t happen - when the network is too broken - are rare and not a particularly large contributor to real-world availability.
Alternatively, systems can choose to allow split brain to happen, allow monotonic writes and weak read guarantees, and still have well-defined properties in the case of network partitions. This is less useful in cloud architectures, where establishing a quorum is generally a better architecture, but more useful in IoT, mobile, space, and similar applications.
So, you traded off consistency.
CAP Theory remains.
As I say in the post, I’m not saying the CAP theorem is wrong, merely that it’s one of the least interesting things one can say about distributed systems tradeoffs (and that’s its irrelevant to thinking through the real tradeoffs in large classes of cloud architectures).
CAP is the trivial observation that if you have a database implemented by two servers, and the connection between the two servers is lost, then if you write to server 1 and then read from server 2, you won’t see the newly written value. I think at least some of the opposition to CAP comes from naming this “The CAP theorem” or here, “CAP Theory” (capital T).
Right. The “CAP Theorem” is either trivial (as you say), or just wrong (if we try use the “common sense” definition of A).
The best version I could state is probably “there exist network partitions that force a trade-off to be made between consistency and availability”, and even that’s more clunky than the flow-chart I borrowed from Bernstein and Das.
The way you wrote that made me realize that the CAP theorem is a deepity in the sense of Dennett: “A deepity involves saying something with two meanings—one trivially true, the other profound sounding but false or nonsensical.”
It may be trivial, but it’s still a theorem, since it’s not an axiom. Even easy theorems deserve proof and recognition when they have profound consequences.
I would disagree here. The pretentiousness around “The CAP Theorem” has had negative value, by obfuscating a trivial concept. The success of CAP in the memetic sense relies on NOT clearly explaining what it really means. If its purveyors clearly explained what it means and then called it “The CAP Theorem” afterward, that would be ok, but it also would look silly, which is why that doesn’t happen.
I don’t think this is is a fair assessment of CAP.
CAP says that if you have a distributed system over N nodes, then, in the presence of a partition (P) that system can be either correct (C) or available (A) — from the perspective of nodes/clients — but not both.
It is unclear what those words mean and when others have tried to pin it down they have ended up with that. See the paper that “proved” the CAP theorem (previously “Brewer’s conjecture”): https://users.ece.cmu.edu/~adrian/731-sp04/readings/GL-cap.pdf If you read the proof of Theorem 1 you’ll see lots of fancy words, but those words say nothing more than the sentence I wrote.
Personally I’ve never found the theorem or its terminology particularly confusing, but, to each their own, I guess! Mostly, I like CAP as a way to push back on overly optimistic engineering managers who want to insist on having both C and A in the data system(s) they commission from their engineers ;)
edit: my bad —
s/correct/consistent/gI’m not saying it’s confusing. I’m saying that if you pin the meaning down then you end up with the triviality that I wrote above. See the paper I referenced above, or the blog post mentioned by Corbin below, if you do not believe me.
I don’t think that “a system can be either consistent or available but not both” is a triviality. But, different strokes for different folks, I suppose.
If you prefer pictures, there is an illustrated proof using diagrams. Out of curiosity, which language would you use if you wanted a formal proof of CAP? I might be able to oblige.
Right, that is a pictorial way of saying “if you have a database implemented by two servers, and the connection between the two servers is lost, then if you write to server 1 and then read from server 2, you won’t see the newly written value”. If you think it is valuable to formalize this, Lean seems to be popular these days.
How would you convince someone this is well-designed without first explaining that it’s a CP system, and what that means?
I don’t think, from the client’s perspective, it’s particularly interesting to talk about partitions (rather than talking about the larger set of failures of infrastructure, software, and operations).
So what do we talk about? There are three options I find more interesting than CAP:
The problems with CAP are the goofy definition of “availability”, the overly-broad assumptions people make based on that definition, and the over focus on partitions at the cost of more interesting failure models.
What would be a non-goofy definition of availability?
I agree that “partition” is, in practice, often just a synecdoche for a much broader class of failure modes. My experience has been that the specific details of those failure modes are rarely interesting to users. All that users really care about is that such failure modes exist; or, more precisely, that those failure modes are unavoidable, and the downstream consequences of that realization.
While I agree with you that such breakages are rare, they affect millions of people, as in an outage earlier this year disconnecting millions from the Internet. Affected countries are known for their commerce and financial-service providers would have had to fall back to eventual consistency rather than pause transactions.
How does that make them irrelevant for describing the semantics of the system?
I imagine it’s similar to describing a boolean value without covering the fact that radiation can cause bitflips. In actual hardware, for most systems, these are so rare that the flips can be detected and corrected by ECC memory, and you probably don’t care about double flips unless you’re in space. So is it really relevant for us to talk about radiation bitflips? Does it impact the semantics of our program?
The article points out that in some networked services we already have a mitigation (routing to the majority) and scenarios where this isn’t viable are rare. The argument is that it’s so rare that you don’t even need to think about it.
As it says, it’s not that it’s wrong, it just isn’t interesting. Similarly, I could use booleans that use redundant bits to avoid radiation, but I don’t, because it’s not really important to me even if I understand that there’s a real scenario where I could really end up in trouble.
What is doing the detection/coordination here? A load balancer? Can you describe maybe a little bit more about the specifics of what cloud products would allow this kind of transactional awareness of network failures?
These are not transactional mechanisms in my experience so would need a loss of A?
That depends a lot on what you mean by A. But yes, the mechanisms (e.g. LB health checks) are not transactional, and depend on the fact that the database replicas use consensus for replication (in my particular example). This is a common pattern, and is the same fundamental idea as DynamoDB, Aurora, S3, and wide array of other cloud systems.
One property of CAP is that the only way that a writer can know if it’s writing into a majority/quorum or minority/non-quorum partition of a distributed system, is if that system is CP.
The only way to ensure that writes only happen on the majority/quorum side of a split, is to use some kind of consensus protocol (Paxos, Raft, etc.) which necessarily make the overall system a CP system, in the CAP sense.
Yes.
You’re weakening the definition of availability, here, beyond what CAP requires.
Split brain is always a possibility, the only question is how a system behaves when it occurs.
Yes! And CRDTs are basically the only way to do it!
I like the CALM and PACELC shout outs. I wish those were as talked about as CAP. If I talk about a CAP problem people feel like I’m being reasonable. If I try to talk about a CALM problem all of a sudden I’m going to be burning innovation tokens in someone’s brain.
I like PACELC a lot. Unfortunately I think it’s definition of “A” is still broken (at least in as far as it’s a statement about real-world trade-offs, and not bounds on worst-case behavior).
I agree with you, PACELC is especially valuable in the SLO-driven world of commercial software.
This sounds very familiar and is no less disheartening to hear from another. Learning new concepts shouldn’t be considered a bad thing. While the operational costs of “unfamiliar technology” remain non-trivial, why compare them to the cognitive load of a new mindset which could simplify solutions?
I think you’re right.
You aren’t doing distributed system pedagogy a favor with posts like these. They come off as condescending and insular, which is already a problem in DS, they attract people that want to be seen as the smartest guy in the room.
OK! So you have a system of 7 nodes, which is partitioned into 2 partitions. One partition of 6 fully-connected nodes, and 1 partition of 1 fully-disconnected node.
I’m pretty sure this is not true.
Assuming this network topology, a CP system with a two-thirds majority quorum requirement, would show to any client connecting to any of those 6/7 nodes in the majority partition that the system is available; and would show to any client connecting to that 1/7 node in the minority partition that the system is unavailable.
An AP system would maybe allow clients submitting write operations to that 1/7 minority node to see success responses, but only partial successes, which would be overridden if and when that 1/7 minority partition re-joined and re-synced with the majority cluster quorum. And that caveat in data consistency would necessarily be reflected in the API of overall system.
Huh? The whole point of the P in CAP is that client connecting to nodes in the minority side of the P don’t know that they’re in the minority side of the P!
Correct!
Er, what? — CAP (and PACELC and all that stuff) is about guaranteeing data consistency all of the time, not most of the time.
edit: I think maybe the disconnect here might be in the expectation of what a node in a system represents. I think maybe the author believes it represents any arbitrary client to the system, whereas I think most of the time it represents a well-defined server in the system. Maybe? Maybe not.
Yeah, that thing really is true, which creates the whole confusion. A in CAP is a very specific formal property, that doesn’t at all relate to practical meaning of availability. To quote CAP paper:
This is a formal definition that means what it says, rather what you’d intuitively think it means.
If there are 7 servers in the system, one is partitioned, you direct a write request to the partitioned one and don’t receive a reply, then your system is not CAP-paper-available.
In Gilbert and Lynch’s specific formalization of the CAP theorem it is true (by their definition of ‘A’). I’m not aware of another formalization that makes sense (and doesn’t come down to a restatement FLP, or some other fundamental result).
Yes, of course. Worst-case system properties are important, and CAP is one framing of those worst-case system properties. I’m not claiming it’s false, I’m just saying it’s not the first (or most interesting) distributed systems trade-off to teach or learn. For nearly all builders of nearly all classes of multi-datacenter cloud-style systems, it’s not a particularly relevant trade-off at all (one reason is that p(two partitions|one partition) is so low that it doesn’t tend to really factor into the real-world availability of three replica systems on modern networks).
There are two interesting points in this post: 1) that the “eventual consistency” flowchart should be widely known and understood, and 2) that CALM etc. are more directly relevant to solving engineering problems than the CAP theorem. I found this very useful.
I would add that CAP is about framing the problem and constraining the solution space, not about solving the problem, and then lead into the discussion of what the solution space really looks like, which is the area in which the author seems to know quite a bit more than I do.
There are some mild inaccuracies here about partitioning which, combined with the overall tone, seems to have nudged us into a more critical mode rather than a receptive one. I would recommend that the author be less hyperbolic and rhetorically bombastic so that the good ideas here get wider coverage, rather than being lost in somewhat insipid debates about whether CAP is good or bad or more or less useful and so forth.
I don’t think it’s irrelevant, I think things need to be redefined (e.g. “any” available node meaning any that’s in quorum).
What alternative formalization would you propose? I’m not aware of another one that really fixes the problems with Gilbert and Lynch’s, and Brewer’s informal statement is either trivial (Gilbert and Lynch) or wrong (“real world” definition of ‘availability’).