If you have a lot of money and are willing and able to build a private network with enough redundancy, you can have both C and A in practice, and P will be low enough not to practically affect the service.
Redundancy doesn't solve CAP. Even with a dozen connections you can end up with issues (A sent a packet, B received it, the connection you pick dropped the ack; what happens?)
"After some timeout" - exactly. During that time you effectively have a partition; you have either accepted the write, meaning you are no longer consistent, or you are blocking on the write, meaning you are no longer available.
If you have multiple, let's expand out to 3 instances (not necessary, but helps illustrate some of the issues better). A tells B something 10x. A also tells C something 10x. Even assuming you don't get inconsistent responses (i.e., B has both accepted and rejected the write), what happens if B accepts it, and C rejects it? Likewise, if you have high load, you're going to have race conditions leading to lack of consistency as well (A tells B and C x = 2, meanwhile C tells A and B that x = 3). You are favoring availability > consistency.
Spanner is a strongly consistent system leveraging Paxos. Yes, with sufficient redundancy you can reduce the likelihood of a partition. You still want to know what the guarantees of the system are. Spanner guarantees that if a transaction can't be agreed to by a quorum of nodes, it will be rejected. Ergo, favoring consistency. That guarantee matters, no matter how infrequent partitions are.
> Redundancy doesn't solve CAP. Even with a dozen connections you can end up with issues (A sent a packet, B received it, the connection you pick dropped the ack; what happens?)
If you really need things to arrive, you'd be sending them on more than one connection. Of course, the difficulty with redundant fiber connections is that really the only way to determine if redundant fiber connections are in the same bundle is with a backhoe.
Not sure why you got downvoted. I came here to say the same.
While it is in theory true that you cannot have a CA system, in practice if you control your H/W and data centers as well, you can build enough redundancy that a P is not more likely than (say) being hit by a meteor. So still not a CA system, but practically CA 99.9..% (add as many 9's as you have money).
99.9 isn't "A" though -- that's something like 10 hours of downtime per year. Even at 6 9s, 30 seconds is plenty of time to end up in a split brain situation!
> If you have a lot of money and are willing and able to build a private network with enough redundancy
Google has done this. Possibly AT&T also.
> Notice who the author is: Eric Brewer
Note that Professor Brewer is a teacher/academic, and CAP is intended for instructional purposes.
As a DBA, I find CAP totally inadequate for any business purpose.
Try explaining to a business owner, "Yeah, when our network partitioned, we couldn't accept purchases in both partitions." Their response will be, "So all that money you spent on HA was really based on a lie?"
If you built a highly redundant network, and it still partitioned, then the actual problem is that you somehow lost 80% of your lines to the internet at the same time. So your response back needs to be that your HA setup kept things running for a while but it would take actual magic to keep going once just about all the servers are unplugged simultaneously. That's not a problem with CAP, that's a problem with explaining the wrong part of the issue.
>>> "Yeah, when our network partitioned, we couldn't accept purchases in both partitions." Their response will be, "So all that money you spent on HA was really based on a lie?"
"All that money spent on HA was what allowed us to accept purchases -at all-"
> If you have a lot of money and are willing and able to build a private network with enough redundancy, you can have both C and A in practice, and P will be low enough not to practically affect the service.
Actually I'd say this is something that's correct in theory but not in practice. In theory you can build a network so redundant that you will never experience a partition. In practice you will always have bugs in your redundancy arrangement, operational errors by sysadmins, and so on.
> If you have a lot of money and are willing and able to build a private network with enough redundancy, you can have both C and A in practice, and P will be low enough not to practically affect the service.
You still have to choose whether to drop C, A, or both when P does happen. Five 9s means about an hour of downtime a year; maybe for some businesses that's small enough to be irrelevant, but by no means all.
You can make partition tolerance arbitrarily low in practice with enough work and resources. But you can never eliminate it. Note it is not just network failures here, because a dead machine and an inaccessible machine are both unavailable.
So in theory you have to choose in the event of P do you sacrifice A or C. That's CAP in a nutshell. You have to plan for P so choose your failure mode in that case.
And this is where people went wrong. They figured you can't sacrifice availability, so then you can't have consistency. If you can't have consistency in failure modes, you may as well not have it at all.
That's really dumb, because in reality you're always going to have some downtime. Most use cases can afford a little downtime, rather just work to keep it to acceptable levels. By sacrificing consistency you enter a realm where logic and cause and effect no longer apply - it's hell to program with that model - and the resulting bugs will cost you availability anyway.
> By sacrificing consistency you enter a realm where logic and cause and effect no longer apply - it's hell to program with that model - and the resulting bugs will cost you availability anyway.
Sacrificing strong consistency doesn’t mean your system won’t be eventually consistent. CRDTs are a great example of how you can get availability and simple consistency semantics.
Eventually consistent generally means things can be all over the place. You can temporarily see extremely weird and unintuitive things and then modify data based on that incorrect world view. That means eventually consistent turns into permanently inconsistent in unpredictable ways.
CRDTs are interesting, but over hyped. They only work for very simple situations and very limited data structures.
Eventual consistency is a stronger guarantee than you get with a remote git repo. It actually works fine for a large number of use cases.
CRDTs are just a way of implementing eventual consistency in provably predictable and 'reasonable' manners. I will agree they are very limited data structures, but I disagree that they only work for very simple situations. I'd liken them to an immutable list in FP. Very limited data structure, but can be used cleverly to create very complicated ones that maintain the same invariants.
If it's anything used by Netflix, Amazon Prime, Facebook, etc. it's inconsistent in practice. Maybe some of them does it right, but updates seems to be lost often. Perhaps something else than CRDTs is used though.
So, CRDTs are just a tool at the data layer to provide a way to resolve inconsistencies. A simple and easily understood example is an add-only set; in the event there is inconsistency it can be automatically resolved; the consistent state is just the union of the sets.
Now, while that model will give you predictable behavior to resolve inconsistencies, it's still eventually consistent (well, hopefully; CRDTs, being a data structure, also don't enforce that the system actually resolves those inconsistencies, just guarantees that it can do so in a correct way). And it doesn't tell you anything about the rest of the system.
I.e., even using CRDTs, if I have an internal netsplit, if you write to one partition, and read from the other, you will miss data (and if I try to read again, I might read from the partition I wrote to, so some reads return state T, and some reads return state T-1, until the consistency is resolved).
The benefit to CRDTs is that when the consistency is resolved (no guarantees on when that will be, or that the system as a whole ensures it!), I've definitely moved forward in time. Not all conflict resolution mechanisms provide that guarantee. For instance, Cassandra's (which came out of Facebook) old default (maybe current, I haven't used it in a while) of "Last Write Wins" meant that clock drift could lead to weirdness. I.e., at my time T I write X = 1. At my time T+1 I write X = 2. HOWEVER, the clock providing the timestamp of the change for the second is lagging, and thinks it's actually T-1. When the system deconflicts, T > T-1, so X will remain equal to 1, even though from a true temporal sense I know that X should be equal to 2.
I don't think that necessarily follows? I don't see why you can't have very intuitive and logical inconsistency.
To give a super simple example, imagine a database on two servers A and B. A is the canonical copy, and updates are streamed to B. All responses from A and B are of the form "the data as of <time> was x". During a partition B will simply serve increasingly stale data.
I'm not exactly sure what your point is. Inconsistent systems are not always horrible?
Mostly they behave well. It's really that they have edge cases that are unintuitive.
In your example of a user is switching between A and B all the time, imagine their confusion as their changes keep getting lost and reappearing. Now imagine they make other changes based on that situation.
This can also happen with different users communicating via a side channel.
In practice infrastructure is more complex than client-server, even if distributed. So inconsistencies may propagate in semi-random ways. Interestingly this happens in physical systems too, something accounting and banks provide means to mitigate.
What you're describing is a single writer distributed system, which is one way to achieve consistency.
Since you can't write directly to server B, the system is unavailable for writes when a writer happens to live on the side of the network partition where B is located.
Often when discussing "availability", it's very important to qualify for whom and for which operations.
> You can temporarily see extremely weird and unintuitive things and then modify data based on that incorrect world view.
No you can't, not without breaking the rules of the system, because as you say, that would lead to an actually inconsistent system.
> CRDTs are interesting, but over hyped. They only work for very simple situations and very limited data structures.
Nonsense. CPUs only work on very limited data structures (sequences of bits), but that's not a concern in practice because we can build up more complicated datastructures on top of them. The same is true for CRDTs.
> No you can't, not without breaking the rules of the system, because as you say, that would lead to an actually inconsistent system.
If you want to redefine eventually consistent to prohibit that behavior then you've just reclassified most real life AP systems as eventually inconsistent.
Eventually consistent systems allow stale reads of older data plus deleted data for an undefined period of time. If you turn around and issue a write based on that you get inconsistency. Eventually consistent systems do not prohibit this.
> Nonsense. CPUs only work on very limited data structures (sequences of bits), but that's not a concern in practice because we can build up more complicated datastructures on top of them. The same is true for CRDTs.
You're talking like there are no downsides to CRDTs. There are huge downsides to them, which is why they're rarely used in practice. Your analysis is only valid in theory.
I would appreciate some information specifically about the problems that cannot be solved by building abstractions on top of CRDTs. I don't don't they exist.
> Eventually consistent systems allow stale reads of older data plus deleted data for an undefined period of time. If you turn around and issue a write based on that you get inconsistency. Eventually consistent systems do not prohibit this.
An eventually consistent system does prohibit that, because as you say it would lead to inconsistency. If you want to do a write based on a read, you're supposed to express that using the system's abstractions, so that a change in the input will (eventually) be propagated to a change in the output.
> You're talking like there are no downsides to CRDTs. There are huge downsides to them, which is why they're rarely used in practice. Your analysis is only valid in theory.
In my experience the "downside" is that you have to actually take 5 minutes to think about your datamodel. They're very much effective in practice. I use them all the time.
Consistency requires more than just choosing the right database, but also design your overall distributed system with that in mind. You have to be very careful when it comes to caching, error handling, load balancing, etc.
Of course, if it's important enough for your use-case, there is always a way to get there.
It's not all or nothing, and it's not about the downtime. It has everything to do with what guarantees you need about your data. It turns out, there are various levels of consistency (strict, sequential, linearizable, etc), and the stronger the guarantees you need, both the harder it is to enforce at a system-wide level, AND the harder it is to have high throughput (both in the 'happy' case, and in any sort of negative event).
It's not a question, really, of "choosing" to be CP, but instead to figure out where on a spectrum of consistency vs availability you want to fall (and then that shade will fall into the 'consistent' or 'available' camp, as generally understood). Sometimes it's okay to just accept a best attempt at a write (such as a cache). Sometimes you REALLY need to ensure ONE view of the truth across the entire system (such as banking). Most cases fall somewhere in the middle, you can make tradeoffs. For instance, user metadata stores are great cases for eventual consistency. Very unlikely to get conflicts (a user isn't generally updating their data in two different locations), but could be fairly high throughput on reads; relaxing your consistency guarantees makes sense (easier to implement, fewer resources needed to maintain invariants, and allows for higher availability in the event of a partition).
Yeah, these all good points. The world is always more complex if you dig deeper. It does very much depend on your use case, and it can vary for different types of data.
I agree with you in general about matching consistency requirements to user/domain needs.
But given all the discussion about consistency in all the comments, just wanted to make sure to note that the CAP theorem is specifically about linearizability from the distributed systems literature (or strict serializability in the DB consistency hierarchy).
> By sacrificing consistency you enter a realm where logic and cause and effect no longer apply
The "C" in CAP refers to linearizable consistency, which is much stricter than causal consistency. You can build an AP system that is causally consistent.
> You can make partition tolerance arbitrarily low
I guess you mean 'the need for partition tolerance'. And that is honestly a better way of reading the P - effectively as 'partitionable'.
CAP says if you are making a partitionable system, it can't guarantee both consistency and availability. If you want consistency and availability, you will have to make the system unpartitionable - effectively, not distributed.
The idea of 'partition tolerance' just makes no sense, because it's not really possible to make a 'partition intolerant' partitionable system.
If the definition of a 'partition tolerant' system is one which actively determines, in the face of network partition, whether to stop answering requests because it can't communicate with other nodes, or to nonetheless answer requests in the knowledge that its answers might be inconsistent...
... how would a 'partition intolerant' node be able to do anything different? I suspect the most likely outcome for a system which can't tolerate partition is to lose both consistency AND availability.
How about: any time there's a network partition, each partition decides on a new identity for itself, and becomes a new cluster that will never join back into the original, larger cluster again. People pick sides and never interact with people on the other side again.
Consistency! (Because every node in each new smaller sub-cluster is now consistent with any other node said nodes will ever interact with again.) Availability! (Because all the nodes stay online.) Partition tolerance—in the sense of the partition ever being resolved? Nope.
I'm not just playing around, either; I'm describing non-unilaterally-assented hard forks in blockchains — e.g. the split between Ethereum and Ethereum Classic, or between Bitcoin and Bitcoin Cash.
You're also describing what Mnesia does in Erlang.
But of course, you ARE playing around here - you're shifting the system(s) you're talking about when defining consistency.
Consistency applies to the whole system, and just because you introduce a partition does not mean you now re-apply CAP considerations to the two systems independently, but still claim it applies to the original. You've changed your frame of reference. You either have one partitioned system that has given up consistency in favor of availability, or you have two systems, neither of which are partitioned (and which from the purposes of CAP are unrelated, since the initial source of seed data for the system is immaterial). Not some grammatical superposition of being both one and two systems.
> You're also describing what Mnesia does in Erlang.
Not quite. Mnesia doesn't have any algorithm for automatic reconciliation; but it does expect reconciliation — in the sense that the idiomatic default thing to do is to have the individual netsplit partitions just halt and wait for a sysop to remsh in and manually reconcile them.
(And this, because Mnesia is originally designed to be deployed in a leader/hot-standby setup, where only one node is ever accepting writes at a time, and there's automatic failover but no automatic failback if the original leader comes back up. The original leader just doesn't come back up, but rather comes up paused, waiting for a sysop to tell it what to do. Multi-master and/or automatic failback is out-of-design-scope for a DB designed for blades-on-a-shared-backplane network-switch control plane hardware.)
Certainly, you can add code that tells the partitioned sub-clusters that "this is your life now", such that each cluster then boots up and continues on separately — but that's an explicit choice you're making, external to Mnesia's design. An empty callback is very different code than no callback. :)
> or you have two systems, neither of which are partitioned (and which from the purposes of CAP are unrelated, since the initial source of seed data for the system is immaterial)
Right, this is what I meant. And, given this viewpoint, the system is never "partitioned": it just becomes new systems. So you have sacrificed partition-tolerance — or rather, you've sacrificed partitionability. Your system can never enter a state where it has nodes that are expecting to ever reconnect to other nodes that might have missed updates, so your system can never be "partitioned" per se (just like a system with a single node can never be "partitioned" per se.)
Correct, it doesn't have automatic reconciliation, but you're phrasing things ambiguously that each individual partition just halts. If a node is starting up, and Mnesia detects that it had partitioned from the cluster previously, you are correct that it will halt until it is told what to do, because it reasonably assumes that it had entered a netsplit before going down, and the data can't be assumed to be consistent across all nodes. However, when a network partition first happens, even on reconnect, writes are still accepted on both sides of the split; they're operating in split brain fashion. And this is because during the partition it wasn't clear whether the other node went down, or was partitioned, ergo, it will accept writes to ensure the system stays up. It also is why the system will wait for direction on the restart case - if it didn't allow for writes during a split brain, it would never be inconsistent. In fact, if a node goes down without a split brain being first detected, and comes back up and rejoins the Erlang cluster, it will rejoin the Mnesia cluster, because it CAN determine where it is; it's at checkpoint 1, the cluster it's rejoining is at checkpoint 2, it can just accept all the writes that bring it up to checkpoint 2 without issue.
And while, yes, the expectation generally is that you'll eventually heal the partition, the general expectation of that happening doesn't somehow change the CAP fundamentals. It's not even a universal expectation; depends what you're using Mnesia for; you could instead change the nodelist to enable each to function independently. The fact you have a use case for leaving them separate (as compared to the times it happens and you didn't, which still happens with a blockchain when a node shuts down or has network failure) doesn't change that.
"You have sacrificed partitionability"; no, you haven't. You've intentionally partitioned the original system, allowing them to be inconsistent, and choosing one side of the partition to promote to being a new system.
> You've intentionally partitioned the original system, allowing them to be inconsistent, and choosing one side of the partition to promote to being a new system.
I'm very confused.
If there's a new system, and the old system doesn't exist any more, then how is the old system partitioned? The old system is down. The new system just happens to contain nodes from the old system. (This is a crucial distinction: if you tried to introduce your new node to the sub-cluster on either side of the netsplit in this model, while advertising yourself as being a participant in the parent network they broke off from, all new sub-networks would refuse to connect to you. None of the sub-networks consider themselves a continuation of the parent. Each netsplit gives you two new networks.)
Saying this kind of permanent intended split is "partitioning", is like saying deallocated memory gets "corrupted" when new memory allocates over it. It only makes sense to say such a thing in a world where you didn't do the thing you did (deallocate the memory), because by doing so, you removed the semantics under which corruption makes sense to talk about. The allocated struct visible to your process is gone, and so there's no longer a requirement from your program that it be in any particular state. So, whatever state it's in, that's "just fine" as far as your program is concerned. Full of 0xdeadbeef? Valid! Because there's no longer any meaning to validity, past deallocation.
A partitioned system is a system that cares about being partitioned — and whose operators care about it being partitioned. Being partitioned is a state that exists in the context of the design goals of the architecture of the system, and an implementation as a control system that attempts to achieve those goals.
Two random nodes that have never talked to one-another aren't "partitioned" — they're just not part of a shared network-architecture design that would make partitioning between them a valid thing to talk about. They've never tried to communicate; they have no reified logic that says they should be communicating.
By designing a distributed system that can never care about nodes that leave it — that can never model other nodes as ever being able to rejoin, such that they could ever potentially introduce conflicting updates — you thereby design a system that exists outside the semantics for which being "partitioned" is well-defined as a concept. You're sacrificing "the ability to have partitions as part of your domain model", in the same sense that deallocation sacrifices "the ability to have structural validity as part of your domain model."
Yeah, that wasn't the best choice of wording. Much prefer how you phrased it.
It's really just about carefully defining the behavior of the system in the face of failures. Typically that means in a CP you tolerate some failures, but eventually you lose the majority and (perhaps only on one side of a network partition) and you have to sacrifice write availability at the minimum to maintain consistency - and reads might now be stale.
Google Spanner (and one other system I worked with) had this neat trick up its sleeve: Utilizing comparatively lighter witness replicas, that only participate in a quorums and keep a time-truncated (recent) un-materialized log necessary but answer no queries. Witnesses could, however, be used to bring other full nodes up-to-speed. This meant, availability of the cluster overall generally went up, assuming co-ordinated failure is rare and there's enough (hardware and software) heterogeneity in the cluster [0].
Regarding consistency in distributed systems, there's a lot to untangle here that even experts like Pat Helland are left lamenting the confusion both in the academia and in the engineering circles [1]
i wish that HN can actually aggregate these old threads together in the resubmission directly (and automagically?). And may be randomize the comment sorting so that the discussion can continue from the existing comments, rather than a rehash.
depends - but i often see a single, long thread of comments from the highest "voted" comment.
this makes it hard to discover lower ranked comments as it's now below the fold, and thus less likely to get votes either.
That's why i suggested a random sort, so that each top-level comment has a chance of getting visiblity and thus, remove groupthink and biases from discussion.
Of course, the top voted comments would have value - so that's why i suggested only doing this random sorting from aggregated old submissions, rather than for all submissions.
well... you can always page across the fold. intuitively I value the ranking of comments of olde higher than a potential contemporary re-evaluation of randomly presented previously less relevant content. a site keen on high engagement certainly would a/b test these hypotheses lol.
but the key is to make the previous content available without dang hand-picking it...
Good article but I'm still struggling to understand CAP in practice.
In general, the whole distributed system will include some kind of database and some kind of application servers. What would AP mean in this context? That application server nodes are able to respond meaningful (ie non failing) responses even if they are unable to communicate with the DB? Wouldn't that require every application node to have a whole local copy of the data it requires to work?
The CAP theorem applies whenever you have a distributed data store. This means a system you can write data to and read back from. This system is made of multiple nodes connected through a network and the clients can connect and make read/write requests from any node.
If you don't meet those conditions CAP doesn't apply to you. For example :
- an SQL database with master/slave replication but all the clients only ever access the database from the same nod (the clients will always have a consistent view of the one node they access)
- multiple processes on the same machine doesn't apply (it's a concurrent datastore but not a distributed one)
- a single SQL database instance doesn't apply (data is not distributed even if there are multiple clients. Confusingly enough if clients can keep some data and work in offline mode, then it would apply because the clients would be considered as a node of the system)
CAP was clearly created in the context of distributed database : SQL, noSQL, CDN,...
Can it apply to an entire system made of multiple components such as database, multiple services,... ? Things get muddier but I'd say yes as long as you check all the boxes: a system with data spread on multiple nodes that clients can access to where the connection can get severed.
Application servers with no local copy losing connection to the server : no. Where is the distribution of data? Where can a network failure partition the data? There is not much A or C choice to make when a partition occurs. Applying CAP wouldn't be very interesting here.
However application servers with local copy : yes CAP applies. In case of a partition there is a trade-off to be made between C and A.
To complicate things further, CAP has basically two versions. There is Brewer's version which talks in general terms is not formal and gets hazy when you drill down to the details. The other version is the one of Lynchs's Paper that provided a proof for the CAP theorem. In that version the definitions are very strict and consequently many real worlds aspects don't fit. Depending on who you ask you may get different answers.
For example, take the context of a database distributed on multiple servers in a datacenter with a reverse proxy that can detect partitions and always redirect read/write queries to non-partitioned nodes. In that context you could say that you have all three C, A and P because there is never going to be a request on a partitioned node. According to Lynch's version of CAP this is not C consistent because you have non-failing nodes that can read stale data (the question of whether there is going to be any request or not is outside the purview of the proof).
What's often missing from these discussions is that the trade off in the CAP theorem can change across the system and over time. If you have a cache on your client, you're trading off consistency for availability, same if you do an optimistic update on the client-side. But that does not change the consistency of your database core. You can also "downgrade" to eventual consistency if you detect a network problem.
I feel that a more principled way to navigate between these trade offs and awareness from the application and database of the current consistency guarantees of the data would help to make more robust systems. E.g. you'd want strong consistency by default, with a fallback to strong eventual consistency when the network is poor and the use-case allows it (e.g. not for changing your password, but ok for posting a comment). It needs to be reflected in the UI, and ideally you want the trade off to be decided at each level in a consistent way (client, local database, core database, ...).
The title should be more explicitly, "You can't sacrifice partition tolerance in a distributed system".
But you can if you don't have a distributed system. I think it is a good argument for monoliths, "real" non-cloud servers and mainframes.
In reality, there are usually backups, and hardware is not perfect so the whole system is most likely somewhat CP, but having everything on the same machine means you have less to worry about P in your application.
Edit: BTW, I know that monoliths don't scale, but you don't always need to scale, or not yet.
I think about this a lot. Amazon has (among others) the m5zn.12xlarge EC2 instance with 48 vCPUs, 192GB memory, 100gbps network and 19gbps EBS bandwidth... you could run a heck of a monolith before needing to scale horizontally.
64 comments
[ 3.7 ms ] story [ 38.1 ms ] threadIf you have a lot of money and are willing and able to build a private network with enough redundancy, you can have both C and A in practice, and P will be low enough not to practically affect the service.
See
https://cloud.google.com/blog/products/databases/inside-clou...
Notice who the author is: Eric Brewer
If you have multiple, let's expand out to 3 instances (not necessary, but helps illustrate some of the issues better). A tells B something 10x. A also tells C something 10x. Even assuming you don't get inconsistent responses (i.e., B has both accepted and rejected the write), what happens if B accepts it, and C rejects it? Likewise, if you have high load, you're going to have race conditions leading to lack of consistency as well (A tells B and C x = 2, meanwhile C tells A and B that x = 3). You are favoring availability > consistency.
If you really need things to arrive, you'd be sending them on more than one connection. Of course, the difficulty with redundant fiber connections is that really the only way to determine if redundant fiber connections are in the same bundle is with a backhoe.
While it is in theory true that you cannot have a CA system, in practice if you control your H/W and data centers as well, you can build enough redundancy that a P is not more likely than (say) being hit by a meteor. So still not a CA system, but practically CA 99.9..% (add as many 9's as you have money).
Edit: Spelling.
Google has done this. Possibly AT&T also.
> Notice who the author is: Eric Brewer
Note that Professor Brewer is a teacher/academic, and CAP is intended for instructional purposes.
As a DBA, I find CAP totally inadequate for any business purpose.
Try explaining to a business owner, "Yeah, when our network partitioned, we couldn't accept purchases in both partitions." Their response will be, "So all that money you spent on HA was really based on a lie?"
Teacher, academic, and vice president of infrastructure at Google. He wrote about the CAP implications of Spanner here as well:
https://storage.googleapis.com/pub-tools-public-publication-...
If you built a highly redundant network, and it still partitioned, then the actual problem is that you somehow lost 80% of your lines to the internet at the same time. So your response back needs to be that your HA setup kept things running for a while but it would take actual magic to keep going once just about all the servers are unplugged simultaneously. That's not a problem with CAP, that's a problem with explaining the wrong part of the issue.
"All that money spent on HA was what allowed us to accept purchases -at all-"
Actually I'd say this is something that's correct in theory but not in practice. In theory you can build a network so redundant that you will never experience a partition. In practice you will always have bugs in your redundancy arrangement, operational errors by sysadmins, and so on.
> If you have a lot of money and are willing and able to build a private network with enough redundancy, you can have both C and A in practice, and P will be low enough not to practically affect the service.
You still have to choose whether to drop C, A, or both when P does happen. Five 9s means about an hour of downtime a year; maybe for some businesses that's small enough to be irrelevant, but by no means all.
So in theory you have to choose in the event of P do you sacrifice A or C. That's CAP in a nutshell. You have to plan for P so choose your failure mode in that case.
And this is where people went wrong. They figured you can't sacrifice availability, so then you can't have consistency. If you can't have consistency in failure modes, you may as well not have it at all.
That's really dumb, because in reality you're always going to have some downtime. Most use cases can afford a little downtime, rather just work to keep it to acceptable levels. By sacrificing consistency you enter a realm where logic and cause and effect no longer apply - it's hell to program with that model - and the resulting bugs will cost you availability anyway.
CP should be the default choice.
Sacrificing strong consistency doesn’t mean your system won’t be eventually consistent. CRDTs are a great example of how you can get availability and simple consistency semantics.
CRDTs are interesting, but over hyped. They only work for very simple situations and very limited data structures.
CRDTs are just a way of implementing eventual consistency in provably predictable and 'reasonable' manners. I will agree they are very limited data structures, but I disagree that they only work for very simple situations. I'd liken them to an immutable list in FP. Very limited data structure, but can be used cleverly to create very complicated ones that maintain the same invariants.
Now, while that model will give you predictable behavior to resolve inconsistencies, it's still eventually consistent (well, hopefully; CRDTs, being a data structure, also don't enforce that the system actually resolves those inconsistencies, just guarantees that it can do so in a correct way). And it doesn't tell you anything about the rest of the system.
I.e., even using CRDTs, if I have an internal netsplit, if you write to one partition, and read from the other, you will miss data (and if I try to read again, I might read from the partition I wrote to, so some reads return state T, and some reads return state T-1, until the consistency is resolved).
The benefit to CRDTs is that when the consistency is resolved (no guarantees on when that will be, or that the system as a whole ensures it!), I've definitely moved forward in time. Not all conflict resolution mechanisms provide that guarantee. For instance, Cassandra's (which came out of Facebook) old default (maybe current, I haven't used it in a while) of "Last Write Wins" meant that clock drift could lead to weirdness. I.e., at my time T I write X = 1. At my time T+1 I write X = 2. HOWEVER, the clock providing the timestamp of the change for the second is lagging, and thinks it's actually T-1. When the system deconflicts, T > T-1, so X will remain equal to 1, even though from a true temporal sense I know that X should be equal to 2.
To give a super simple example, imagine a database on two servers A and B. A is the canonical copy, and updates are streamed to B. All responses from A and B are of the form "the data as of <time> was x". During a partition B will simply serve increasingly stale data.
Mostly they behave well. It's really that they have edge cases that are unintuitive.
In your example of a user is switching between A and B all the time, imagine their confusion as their changes keep getting lost and reappearing. Now imagine they make other changes based on that situation.
This can also happen with different users communicating via a side channel.
Since you can't write directly to server B, the system is unavailable for writes when a writer happens to live on the side of the network partition where B is located.
Often when discussing "availability", it's very important to qualify for whom and for which operations.
No you can't, not without breaking the rules of the system, because as you say, that would lead to an actually inconsistent system.
> CRDTs are interesting, but over hyped. They only work for very simple situations and very limited data structures.
Nonsense. CPUs only work on very limited data structures (sequences of bits), but that's not a concern in practice because we can build up more complicated datastructures on top of them. The same is true for CRDTs.
If you want to redefine eventually consistent to prohibit that behavior then you've just reclassified most real life AP systems as eventually inconsistent.
Eventually consistent systems allow stale reads of older data plus deleted data for an undefined period of time. If you turn around and issue a write based on that you get inconsistency. Eventually consistent systems do not prohibit this.
> Nonsense. CPUs only work on very limited data structures (sequences of bits), but that's not a concern in practice because we can build up more complicated datastructures on top of them. The same is true for CRDTs.
You're talking like there are no downsides to CRDTs. There are huge downsides to them, which is why they're rarely used in practice. Your analysis is only valid in theory.
An eventually consistent system does prohibit that, because as you say it would lead to inconsistency. If you want to do a write based on a read, you're supposed to express that using the system's abstractions, so that a change in the input will (eventually) be propagated to a change in the output.
> You're talking like there are no downsides to CRDTs. There are huge downsides to them, which is why they're rarely used in practice. Your analysis is only valid in theory.
In my experience the "downside" is that you have to actually take 5 minutes to think about your datamodel. They're very much effective in practice. I use them all the time.
Of course, if it's important enough for your use-case, there is always a way to get there.
It's not a question, really, of "choosing" to be CP, but instead to figure out where on a spectrum of consistency vs availability you want to fall (and then that shade will fall into the 'consistent' or 'available' camp, as generally understood). Sometimes it's okay to just accept a best attempt at a write (such as a cache). Sometimes you REALLY need to ensure ONE view of the truth across the entire system (such as banking). Most cases fall somewhere in the middle, you can make tradeoffs. For instance, user metadata stores are great cases for eventual consistency. Very unlikely to get conflicts (a user isn't generally updating their data in two different locations), but could be fairly high throughput on reads; relaxing your consistency guarantees makes sense (easier to implement, fewer resources needed to maintain invariants, and allows for higher availability in the event of a partition).
But given all the discussion about consistency in all the comments, just wanted to make sure to note that the CAP theorem is specifically about linearizability from the distributed systems literature (or strict serializability in the DB consistency hierarchy).
The "C" in CAP refers to linearizable consistency, which is much stricter than causal consistency. You can build an AP system that is causally consistent.
I guess you mean 'the need for partition tolerance'. And that is honestly a better way of reading the P - effectively as 'partitionable'.
CAP says if you are making a partitionable system, it can't guarantee both consistency and availability. If you want consistency and availability, you will have to make the system unpartitionable - effectively, not distributed.
The idea of 'partition tolerance' just makes no sense, because it's not really possible to make a 'partition intolerant' partitionable system.
If the definition of a 'partition tolerant' system is one which actively determines, in the face of network partition, whether to stop answering requests because it can't communicate with other nodes, or to nonetheless answer requests in the knowledge that its answers might be inconsistent...
... how would a 'partition intolerant' node be able to do anything different? I suspect the most likely outcome for a system which can't tolerate partition is to lose both consistency AND availability.
How about: any time there's a network partition, each partition decides on a new identity for itself, and becomes a new cluster that will never join back into the original, larger cluster again. People pick sides and never interact with people on the other side again.
Consistency! (Because every node in each new smaller sub-cluster is now consistent with any other node said nodes will ever interact with again.) Availability! (Because all the nodes stay online.) Partition tolerance—in the sense of the partition ever being resolved? Nope.
I'm not just playing around, either; I'm describing non-unilaterally-assented hard forks in blockchains — e.g. the split between Ethereum and Ethereum Classic, or between Bitcoin and Bitcoin Cash.
But of course, you ARE playing around here - you're shifting the system(s) you're talking about when defining consistency.
Consistency applies to the whole system, and just because you introduce a partition does not mean you now re-apply CAP considerations to the two systems independently, but still claim it applies to the original. You've changed your frame of reference. You either have one partitioned system that has given up consistency in favor of availability, or you have two systems, neither of which are partitioned (and which from the purposes of CAP are unrelated, since the initial source of seed data for the system is immaterial). Not some grammatical superposition of being both one and two systems.
Not quite. Mnesia doesn't have any algorithm for automatic reconciliation; but it does expect reconciliation — in the sense that the idiomatic default thing to do is to have the individual netsplit partitions just halt and wait for a sysop to remsh in and manually reconcile them.
(And this, because Mnesia is originally designed to be deployed in a leader/hot-standby setup, where only one node is ever accepting writes at a time, and there's automatic failover but no automatic failback if the original leader comes back up. The original leader just doesn't come back up, but rather comes up paused, waiting for a sysop to tell it what to do. Multi-master and/or automatic failback is out-of-design-scope for a DB designed for blades-on-a-shared-backplane network-switch control plane hardware.)
Certainly, you can add code that tells the partitioned sub-clusters that "this is your life now", such that each cluster then boots up and continues on separately — but that's an explicit choice you're making, external to Mnesia's design. An empty callback is very different code than no callback. :)
> or you have two systems, neither of which are partitioned (and which from the purposes of CAP are unrelated, since the initial source of seed data for the system is immaterial)
Right, this is what I meant. And, given this viewpoint, the system is never "partitioned": it just becomes new systems. So you have sacrificed partition-tolerance — or rather, you've sacrificed partitionability. Your system can never enter a state where it has nodes that are expecting to ever reconnect to other nodes that might have missed updates, so your system can never be "partitioned" per se (just like a system with a single node can never be "partitioned" per se.)
And while, yes, the expectation generally is that you'll eventually heal the partition, the general expectation of that happening doesn't somehow change the CAP fundamentals. It's not even a universal expectation; depends what you're using Mnesia for; you could instead change the nodelist to enable each to function independently. The fact you have a use case for leaving them separate (as compared to the times it happens and you didn't, which still happens with a blockchain when a node shuts down or has network failure) doesn't change that.
"You have sacrificed partitionability"; no, you haven't. You've intentionally partitioned the original system, allowing them to be inconsistent, and choosing one side of the partition to promote to being a new system.
I'm very confused.
If there's a new system, and the old system doesn't exist any more, then how is the old system partitioned? The old system is down. The new system just happens to contain nodes from the old system. (This is a crucial distinction: if you tried to introduce your new node to the sub-cluster on either side of the netsplit in this model, while advertising yourself as being a participant in the parent network they broke off from, all new sub-networks would refuse to connect to you. None of the sub-networks consider themselves a continuation of the parent. Each netsplit gives you two new networks.)
Saying this kind of permanent intended split is "partitioning", is like saying deallocated memory gets "corrupted" when new memory allocates over it. It only makes sense to say such a thing in a world where you didn't do the thing you did (deallocate the memory), because by doing so, you removed the semantics under which corruption makes sense to talk about. The allocated struct visible to your process is gone, and so there's no longer a requirement from your program that it be in any particular state. So, whatever state it's in, that's "just fine" as far as your program is concerned. Full of 0xdeadbeef? Valid! Because there's no longer any meaning to validity, past deallocation.
A partitioned system is a system that cares about being partitioned — and whose operators care about it being partitioned. Being partitioned is a state that exists in the context of the design goals of the architecture of the system, and an implementation as a control system that attempts to achieve those goals.
Two random nodes that have never talked to one-another aren't "partitioned" — they're just not part of a shared network-architecture design that would make partitioning between them a valid thing to talk about. They've never tried to communicate; they have no reified logic that says they should be communicating.
By designing a distributed system that can never care about nodes that leave it — that can never model other nodes as ever being able to rejoin, such that they could ever potentially introduce conflicting updates — you thereby design a system that exists outside the semantics for which being "partitioned" is well-defined as a concept. You're sacrificing "the ability to have partitions as part of your domain model", in the same sense that deallocation sacrifices "the ability to have structural validity as part of your domain model."
It's really just about carefully defining the behavior of the system in the face of failures. Typically that means in a CP you tolerate some failures, but eventually you lose the majority and (perhaps only on one side of a network partition) and you have to sacrifice write availability at the minimum to maintain consistency - and reads might now be stale.
Regarding consistency in distributed systems, there's a lot to untangle here that even experts like Pat Helland are left lamenting the confusion both in the academia and in the engineering circles [1]
[0] http://www2.cs.uh.edu/~paris/MYPAPERS/Icdcs86.pdf
[1] https://pathelland.substack.com/p/dont-get-stuck-in-the-con-...
You Can’t Sacrifice Partition Tolerance (2010) - https://news.ycombinator.com/item?id=11700856 - May 2016 (21 comments)
You Can’t Sacrifice Partition Tolerance (2010) - https://news.ycombinator.com/item?id=8214310 - Aug 2014 (4 comments)
You Can't Sacrifice Partition Tolerance (response to Stonebraker) - https://news.ycombinator.com/item?id=1821887 - Oct 2010 (13 comments)
You Can't Sacrifice Partition Tolerance - https://news.ycombinator.com/item?id=1768312 - Oct 2010 (50 comments)
this makes it hard to discover lower ranked comments as it's now below the fold, and thus less likely to get votes either.
That's why i suggested a random sort, so that each top-level comment has a chance of getting visiblity and thus, remove groupthink and biases from discussion.
Of course, the top voted comments would have value - so that's why i suggested only doing this random sorting from aggregated old submissions, rather than for all submissions.
but the key is to make the previous content available without dang hand-picking it...
In general, the whole distributed system will include some kind of database and some kind of application servers. What would AP mean in this context? That application server nodes are able to respond meaningful (ie non failing) responses even if they are unable to communicate with the DB? Wouldn't that require every application node to have a whole local copy of the data it requires to work?
If you don't meet those conditions CAP doesn't apply to you. For example :
- an SQL database with master/slave replication but all the clients only ever access the database from the same nod (the clients will always have a consistent view of the one node they access)
- multiple processes on the same machine doesn't apply (it's a concurrent datastore but not a distributed one)
- a single SQL database instance doesn't apply (data is not distributed even if there are multiple clients. Confusingly enough if clients can keep some data and work in offline mode, then it would apply because the clients would be considered as a node of the system)
CAP was clearly created in the context of distributed database : SQL, noSQL, CDN,... Can it apply to an entire system made of multiple components such as database, multiple services,... ? Things get muddier but I'd say yes as long as you check all the boxes: a system with data spread on multiple nodes that clients can access to where the connection can get severed.
Application servers with no local copy losing connection to the server : no. Where is the distribution of data? Where can a network failure partition the data? There is not much A or C choice to make when a partition occurs. Applying CAP wouldn't be very interesting here.
However application servers with local copy : yes CAP applies. In case of a partition there is a trade-off to be made between C and A.
To complicate things further, CAP has basically two versions. There is Brewer's version which talks in general terms is not formal and gets hazy when you drill down to the details. The other version is the one of Lynchs's Paper that provided a proof for the CAP theorem. In that version the definitions are very strict and consequently many real worlds aspects don't fit. Depending on who you ask you may get different answers.
For example, take the context of a database distributed on multiple servers in a datacenter with a reverse proxy that can detect partitions and always redirect read/write queries to non-partitioned nodes. In that context you could say that you have all three C, A and P because there is never going to be a request on a partitioned node. According to Lynch's version of CAP this is not C consistent because you have non-failing nodes that can read stale data (the question of whether there is going to be any request or not is outside the purview of the proof).
I feel that a more principled way to navigate between these trade offs and awareness from the application and database of the current consistency guarantees of the data would help to make more robust systems. E.g. you'd want strong consistency by default, with a fallback to strong eventual consistency when the network is poor and the use-case allows it (e.g. not for changing your password, but ok for posting a comment). It needs to be reflected in the UI, and ideally you want the trade off to be decided at each level in a consistent way (client, local database, core database, ...).
But you can if you don't have a distributed system. I think it is a good argument for monoliths, "real" non-cloud servers and mainframes.
In reality, there are usually backups, and hardware is not perfect so the whole system is most likely somewhat CP, but having everything on the same machine means you have less to worry about P in your application.
Edit: BTW, I know that monoliths don't scale, but you don't always need to scale, or not yet.