8 ms·
The CAP theorem. The Bad, the Bad, & the Ugly
- jph 3y agoThe CAP theorem expands to the PACELC theorem. PACELC stands for Partition, Availability, Consistency, Else, Latency, and Consistency. The theorem states that in the event of a network partition, a distributed system must choose between availability and consistency; otherwise, it must choose between latency and consistency. https://en.wikipedia.org/wiki/PACELC_theorem https://en.wikipedia.org/wiki/PACELC_theorem
- peterbell_nyc 3y agoIt seems like people make this really complicated. There will occasionally be network partitions. When there are, a given node can either respond (potentially inconsistently) or not. So you pick some balance between consistency and availability. Latency is really just a proxy for availability - as latency tends towards infinite, availability tends towards zero. Of course you can wait until the network partition is resolved and the nodes are caught up - but I think it's simpler to consider that as not being available for a period of time rather than as having a high latency at that time. Consistency or Availability - you don't have to pick one, but the more consistent you want to be (in the case of network partitions) the less available you'll be.
- pachico 3y agoIf your decision between Consistency and Availability has business implications, you definitely aren't making this "really complicated" but rather a business logic to adhere to. Failing to understand the implications of one over the other is often sign of immature architecture.
- justin_hancock 3y agoDisagree on latency, for certain classes of applications it really matters. Latency can be caused by a myriad of things, but if that thing is your means for cut over, you haven't failed to respond, you've failed to respond in a timely way. The telco space has strict latency requirements. If you have a failure which results in erratic behaviour on the network due to the database taking time to handle a node failure you aren't in a good place, it has a financial impact. There are databases that can provide high consistency and availability.
- harkinian 3y agoWas going to say, latency doesn't need to be in there.
- AtlasBarfed 3y agoWhenever I see questions about CAP as a useful thought exercise in distributed systems, it seems to originate from people trying to defend database systems that don't respond well to the realities of partition inevitably. That is people doing implicit or explicit marketing of some enterprise data landgrab telling you things like they can scale arbitrary SQL joins across distributed tables. Because large data sets do not teleport across the wire for merging. Foundation db, Cassandra, and kinda dynamo (I don't trust their new global replication) actually scale, but I've never used gcps db techs. CAP is imo one of the best distributed systems principles ever stated. It is simply state, compare to say the nitty gritty of say paxos vs raft. It is a very useful first principles exercise for deconstructing whatever harebrained claim some marketroid is foisting upon you.
- justin_hancock 3y agoVolt is another good example of solving this well. It's consistency guarantees are strong, and offers very high availability through it's replication which commits transactions to replicas simultaneously. In theory it's weaker on the partition side, but in practise with modern hardware and networks it's impact is not felt. It also offers multi data centre replication, with all sites being active.
- _dark_matter_ 3y agoIn my opinion this dead horse is beat. Anyone working on distributed systems knows that CAP is not useful in isolation. See Eric Brewer's followup article from 2012: https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/ https://www.infoq.com/articles/cap-twelve-years-later-how-th...
- _visgean 3y agoI had an interview question about it, I tried to cite Kleppmann from the distributed systems book and the interview manager got quite offended.
- adhamsalama 3y agoSame, but I actually forgot why he didn't like it, so I didn't.
- 12345hn6789 3y agocare to elaborate? Not picking apart anything you said but am curious. I am slowly making my way through DDIA. Nothing he says is particularly egregious (so far).
- _visgean 3y agothe guy interviewing me just wanted a definition. I guess I should have started with that and then point out why its a bad concept.
- swyx 3y agosounds like you dodged a bullet.
- jameshart 3y agoThe ‘network partitions are not optional’ interpretation of CAP is forgetting about the fact that non-distributed-systems are a thing. Sure, as soon as you decided to distribute your system across a network you opted into a world where partition can happen, and you will have to give up consistency or availability. Mainframes, though, provide consistency and availability by being unpartitionable except through use of a chainsaw.
- valenterry 3y agoThey don't provide availability, because if they go down, they are down. For example, if there is a fire, the whole thing is gone. That's a choice you make.
- jameshart 3y agoMainframes have a ton of internal redundancy that enables insanely high avaialability, absent destruction. All ‘availability’ rests on some assumed radius of safety. A nuclear blast in northern Virginia can take out all the availability zones for AWS US-East-1 - that doesn’t invalidate the availability claims of a system that is distributed across three AZs, it just puts an upper limit on it.
- largbae 3y ago"All availability rests on some assumed radius of safety", thank you for that! If this is not a named law could you name it? I have needed this statement in the past but it never came together like that.
- anyonecancode 3y agoI agree it's a good point. A nuclear blast is extrinsic to the system. I think what something like CAP gets us to think about is failures/limitations that are _intrinsic_ to the system. Someone walking around the data center and unplugging all the machines, then flying to the next data center and unplugging them, etc, would also cause all of CAP to fail. Though, thinking about it more, what it also tells us is that we need to be clear about what "the system" is. There are, after all, some systems that _do_ take nuclear blasts into account, or systems that take "physical breach by a hostile actor" into account. Less dramatically, we make trade-offs all the time as to what we consider "in" system vs "out", and it's good to be conscious and explicit about them. We see this a lot in UI, especially web UI in terms of things like what browsers to support, whether we care about users' battery life or data cap limits, if we foresee ourselves running the system in a jurisdiction with different regulations around data collection and usage, etc.
- zer00eyz 3y agoThis conflict comes up everywhere: Newtonian physics/mechanics: good enough in a lot of cases. Einstein accurate, but unnecessary in most cases. In many cases CAP is good enough for us to have the conversation about how the system works. One can then formulate plan for when it doesn't. The fact that it's imperfect at a formal level is academically interesting, but technically irrelevant for a LOT of conversations where it has utility.
- sgift 3y agoAgreed. Sure, you can expand it with PACELC, but the important part is that you have something which starts the conversation/thinking about the fact that distributed systems have specific requirements and challenges. And CAP is sufficient for that.
- throw0101d 3y agoTIL: > In theoretical computer science, the PACELC theorem is an extension to the CAP theorem. It states that in case of network partitioning (P) in a distributed computer system, one has to choose between availability (A) and consistency (C) (as per the CAP theorem), but else (E), even when the system is running normally in the absence of partitions, one has to choose between latency (L) and loss of consistency (C). * https://en.wikipedia.org/wiki/PACELC_theorem https://en.wikipedia.org/wiki/PACELC_theorem
- tootie 3y agoMy first thought was The Structure of Scientific Revolution. CAP was a very useful theory on top of which years of research were done until the paradigm was broken and replaced. That's how progress works. It doesn't mean CAP was a scam it was our very good first draft at formalizing distributed database theory. And the fact that we still talk about it is proof of that.
- jameshart 3y agoFundamental principles often just formally state the obvious. People who want CAP to be profound and useful are missing the point - it just tells you some things that you might want to try to achieve are provably impossible. Just like Newton’s first law tells you things can’t accelerate without a force (duh) and the first law of thermodynamics tells you you can’t get energy out of a perpetual motion machine (duh) and the pigeonhole principle tells you if you put n things in less than n groups, at least one group has more than one thing in it (duh); CAP tells you you can’t build a distributed, partitionable data system that is 100% consistent and 100% available (duh). It’s not that deep or profound but it is proven and it eliminates a whole class of ideas from meriting further thought because they’re demonstrably impossible. That lets us get on with making the most of what is possible.
- willsmith72 3y agoI don't find this position particularly helpful, unless you're talking to someone who takes CAP literally as a law and picks only 2. That's never been the case in discussions I've had. It's still extremely useful as a mental model for tradeoffs in designing a system. All it's telling you is there's a pendulum from availability to consistency and generally. The more you want of one, generally the less you get of the other, so choose the amounts you want of each deliberately. People take things too literally and seriously. Has anyone in their company really argued that, "we should choose availability instead of consistency"? It's way more nuanced than that, and as far as I know, everyone knows that
- deathanatos 3y ago> Has anyone in their company really argued that, "we should choose availability instead of consistency"? It's way more nuanced than that, and as far as I know, everyone knows that … I'm usually experiencing the CP/AP split from the seat of a user, using the system. From where I sit … yes, it certainly feels like people are, somewhere, saying "we should choose availability", given the number of systems I've had to interact with that are trivially not CP. Specifically, refer to https://jepsen.io/consistency https://jepsen.io/consistency — these are better, more specific terms, IMO; the number of systems that don't obey "Read Your Writes" (at the very bottom of the tree!) is pretty stark. Many Azure services, for example, are not read-your-writes; this means I'm perpetually wrapping things in loops that attempt to wait for the upstream system to become consistent, which is impossible to do in any manner that's foolproof, prior to moving on to the next API call (which would otherwise fail, if it depends on a write from the prior API call, but can't read it, because read-your-writes). Off the top of my head, I've seen empirical violations of read-your-writes in all of ARM, AAD, ACR. My latest container registry is also not read-your-writes. S3 used to fail read-your-writes, in certain circumstances. (That have since been fixed.)
- IgorPartola 3y agoI worked on a wide-area distributed system on 2010-2012. CAP and NoSQL was all the rage then (MongoDB is webscale, after all). The approach we took was to have a single database node be the primary and another replicating from it asynchronously. When a node went offline, a third monitoring node made a decision to promote the backup to primary and communicate this decision to all clients. The three nodes were located in three different cities and as such the possibility of all three having issues at once was reduced. By doing this, we could literally pull the plug on the primary node and within 30 seconds the clients were talking to the backup-now-primary. If the monitoring node failed, of course we had no way of automatically switching database nodes but again it had to be a major issue for a node in Seattle to get cut off at the same time as the nodes in Dallas or DC. This worked because of the kinds of data we processed so that our 30 second failover time was acceptable AND a small window of lost writes was also OK. I think another interesting approach is to have your nodes explicitly communicate write status when responding. Basically when you write(node1, key, val) and expect node1 to normally propagate the write to node2, in the case of a network partition node1 would respond with ack(key, nodes_written=[node1]) explicitly excluding node2 from nodes_written if it was unable to push the write to node2 in a timely fashion. Similarly, read(node1, key) could have node1 return resp(key, val, inconsistent=true) or again spelling out which nodes do or do not know this value. This would give the application a way to decide if the write should be considered successful or not based on what key represents. For example, updating the current position of a fast moving object that sends updates all the time could easily lose a write or two without it being a problem for the user, but a financial transaction could not. Lastly, the approach I never explored but was curious about is the idea of the client being responsible for pushing all values to all nodes rather than replication happening in the background. This would effectively allow the write to happen simultaneously and also know if the write was a fail, a partial success, or a full success. Then a read could be done from just one node, but before returning it would poll other nodes and return the value that is consistent amongst the majority of the nodes or a failure if it could not reach any of them.
- cybereporter 3y agoYeah, the post doesn't go into quorum decision making with the "monitoring node", which helps either enforce eventual or strong consistency. I've found that you typically want minimum 3 nodes + a monitoring node (or could be client side) to have a read quorum (at least 2 nodes have consistent data).
- taneq 3y agoYep, seems reasonable. Kind of like Carnot efficiency for heat engines, it’s old and boring and we should stop talking about it.
- super_mario 3y agoI view CAP theorem as statement about the universe we live in (information travels at speed of light, "instantaneous" is observer dependant etc), and not as a consequence of information theoretic definitions we chose to adopt (strength of consistency or availability). Yes, when stated simplistically (you have 3 properties C, A, P choose 2) can be extremely misleading, since you can't really choose P, you can only decide what to do in case of P. But like any mathematical theorem one has to understand the preconditions when the theorem applies, understand the various computing model assumptions etc. to actually use it. Notwithstanding, I still find it very useful as a general guide when designing distributed systems.
- fl0ki 3y agoA very common failure mode I see even among experienced senior engineers is to talk about the availability only of their endpoint, not the user experience of the system to meaningfully address user requests. Well-intentioned SLOs around error rate, 99th latency, etc. become meaningless if you don't understand how they affect the various objectives of various production clients. We generally accept that clients may have to perform retries, definitely jittered and hopefully bounded. Given that's the case, what does it matter whether a single instance takes 5 seconds to come back online after failure (possibly rescheduled on a new node), or multiple instances take the same 5 seconds to recognize leader failure and elect a new leader? Sure, they're unlikely to be identical numbers, but say they're within an order of magnitude and both have error margins so it's a wash. An architecture astronaut will put forward a design with complex leader election, endpoint discovery, distributed locking, strong consistency, etc. for the latter solution and pat themselves on the back for their expertise and professionalism. They'll waste a lot of time for both dev and SRE as long as the service lives. A reasonable person should be able to acknowledge that, given either solution will have the client retrying about the same amount of time, the simplest solution that delivers that experience is sufficient from the client's point of view and vastly preferable from a maintainer's or operator's point of view. Of course not every scenario will be like this. Sometimes startup is unavoidably a lot slower than re-election. It's just rare you see this evaluated in terms of client-facing numbers before a very costly architecture decision is made.
- senderista 3y agoLatency eventually becomes availability eventually becomes durability. The difference is only quantitative not qualitative.
- margorczynski 3y agoDoesn't strong consistency always imply some form of explicit locking that collides with availability? As in a distributed system it needs to go something like: 1. Get write request to a node 2. Node sends lock on that updated data to rest of nodes 3. After they send back OK the write happens 4. Propagate to rest of nodes 5. After receiving OK on the update from all of the nodes send notification to nodes to lift the lock So if a partition happens the system fails if it is CA while with e.g. CA it cannot guarantee strong consistency without resolving the split brain (killing of one of the partitions based on e.g. quorum)?
- senderista 3y agoIf by "strong consistency" you mean "linearizability" then no, you can build a distributed atomic register without locking (ABD algorithm[0][1]). The trick is to force readers to complete a possibly-incomplete write returned from a read quorum by writing it to a write quorum before they can return their result (in practice you can elide the write-on-read in the common case where the result from the read quorum already is written to a write quorum). Similarly, writers must find the latest possibly-written version from a read quorum to obtain the version number for their write. If you need stronger primitives than atomic read/write (e.g. CAS), then ABD is insufficient and you need consensus in the asynchronous model (although synchronized clocks can allow even CAS to be implemented with ABD + leader election with leases[2]). [0] https://dl.acm.org/doi/pdf/10.1145/200836.200869 https://dl.acm.org/doi/pdf/10.1145/200836.200869 [1] https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-notes.pdf https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-n... [2] https://arxiv.org/pdf/1702.04242.pdf https://arxiv.org/pdf/1702.04242.pdf
- dtornow 3y agoMy favorite mental framework to reason about consistency in distributed systems, Invariant Confluence, was formulated by Peter Bailis at al in Coordination Avoidance in Database Systems (overview and link to paper http://www.bailis.org/blog/when-does-consistency-require-coordination/ http://www.bailis.org/blog/when-does-consistency-require-coo...) Invariant confluence, determines whether an application requires coordination for correct execution. You can tailor the invariants to your requirements making invariant confluence a much better tool than CAP
- stevefan1999 3y ago> On the other hand, given a non-permanent partition and the requirements that a request receives a response eventually, that is, in unbounded time, both strong consistency as well as weak consistency can be achieved. Is that why S3 works so well?
- rubiquity 3y agoThe point they're trying to make is that the A in CAP is ambiguous. If your timeout is unbounded and a request completes an hour/day/month/year or more later is the system available?
- j-pb 3y agoThere is a theorem called CALM[1] (Consistency as Logical Monotonicity) that shows that systems are eventually consistent iff they are monotonic. I find that reasoning about consistency is much easier from that perspective, for example it immediately gives you an intuition on why individual CRDTs work. 1: https://arxiv.org/abs/1901.01930 https://arxiv.org/abs/1901.01930
- klabb3 3y agoSounds interesting. Is there an intuitive definition of monotonicity for the purposes of distributed systems? I mean, I thought I knew what it means, but I’m not too sure now.
- j-pb 3y agoYou never take something back. A grow set for example only ever grows. A monotonic counter only ever grows. Even a set where you can insert and delete once is like a set of counters that only ever grow (nothing: 0, added:1, removed:2). Forgetting for example is fine, but deletion is not.
- samatman 3y ago> Since you have to account for network partitions, you have to choose between consistency and availability if and when a partition occurs. In other words, the CAP divides the world into CP and AP systems. No, it's two out of three. CA systems don't use a network. Consider a database and a work queue which communicates with the database, where they run on the same server. You can achieve consistency and availability in such a system, but only by eliminating partitioning, and there's only the one way to do that: don't run the systems on a network. Nor is this an unrealistic architecture! Far from it, it is in fact the one you should choose if you need both consistency and availability. The parts of the article about the CAP theorem and its consequences are on fairly solid ground as I see it. But the observation about the CAP conjecture is bootless, the conjecture that CAP is "pick two" holds up to scrutiny. Not that it proves the conjecture, just that all three of the "pick two" options describe meaningful systems.
- rufius 3y agoThis blog post felt unsatisfying. I’m not sure I’ve talked to anyone in the last decade about distributed systems where: - CAP came up - all parties immediately agreed that CA was impossible I still think it’s a useful model for forcing people to think about their failure modes though. Systems, largely, tend to fall into either CP or AP or be horrendously expensive. You have to choose your trade offs. I wish the author had expounded a little further on better options. I’ll read the paper linked, but there’d be more punch with more inline content.
- mbfg 3y agoMy understanding of [[The “Pick 2 out of 3” interpretation implies that network partitions are optional, something you can opt-in or opt-out of.]] is you can choose to not have a distributed system.
- kqr 3y agoThis is also how I understand it. You choose networked or not networked, and if you choose networked you get a 2-for-1 with partitions.