4 ms·

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 failure

by eloff 5y ago

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. CP should be the default choice.

zffr 5y ago
> 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.
- eloff 5y ago
  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.
  - lostcolony 5y ago
    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.
    - loopz 5y ago
      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.
      - lostcolony 5y ago
        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.
  - im3w1l 5y ago
    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.
    - eloff 5y ago
      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.
      - loopz 5y ago
        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.
    - ithkuil 5y ago
      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.
  - deleted 5y ago
    [deleted]
  - lmm 5y ago
    > 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.
    - eloff 5y ago
      > 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.
      - ledauphin 5y ago
        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.
        eloff 5y ago
        What data structures can't be implemented efficiently? Or what applications can't be architected differently to utilize CRDTs?
      - lmm 5y ago
analyst74 5y ago
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.
lostcolony 5y ago
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).
- eloff 5y ago
  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.
- mfreed 5y ago
  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).
jude- 5y ago
> 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.
jameshart 5y ago
> 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.
- derefr 5y ago
  > 'partition intolerant' partitionable system 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.
  - lostcolony 5y ago
    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.
ignoramous 5y ago
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] [0] http://www2.cs.uh.edu/~paris/MYPAPERS/Icdcs86.pdf http://www2.cs.uh.edu/~paris/MYPAPERS/Icdcs86.pdf [1] https://pathelland.substack.com/p/dont-get-stuck-in-the-con-game-v2 https://pathelland.substack.com/p/dont-get-stuck-in-the-con-...

by eloff 5y ago

zffr 5y ago

> 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.

eloff 5y ago
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.
- lostcolony 5y ago
  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.
  - loopz 5y ago
    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.
    - lostcolony 5y ago
      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.
- im3w1l 5y ago
  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.
  - eloff 5y ago
    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.
    - loopz 5y ago
      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.
  - ithkuil 5y ago
    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.
- deleted 5y ago
  [deleted]
- lmm 5y ago
  > 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.
  - eloff 5y ago
    > 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.
    - ledauphin 5y ago
      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.
      - eloff 5y ago
        What data structures can't be implemented efficiently? Or what applications can't be architected differently to utilize CRDTs?
    - lmm 5y ago

analyst74 5y ago

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.

lostcolony 5y ago

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).

eloff 5y ago
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.
mfreed 5y ago
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).

jude- 5y ago

> 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.

jameshart 5y ago

> 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.

derefr 5y ago
> 'partition intolerant' partitionable system 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.
- lostcolony 5y ago
  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.

ignoramous 5y ago

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] [0] http://www2.cs.uh.edu/~paris/MYPAPERS/Icdcs86.pdf http://www2.cs.uh.edu/~paris/MYPAPERS/Icdcs86.pdf [1] https://pathelland.substack.com/p/dont-get-stuck-in-the-con-game-v2 https://pathelland.substack.com/p/dont-get-stuck-in-the-con-...