CAP theorem - Availability and Partition Tolerance

Question

While I try to understand the "Availability" (A) and "Partition tolerance" (P) in CAP, I found it difficult to understand the explanations from various articles.

I get a feeling that A and P can go together (I know this is not the case, and that's why I fail to understand!).

Explaining in simple terms, what are A and P and the difference between them?

Solution 1

Consistency means that data is the same across the cluster, so you can read or write from/to any node and get the same data.

Availability means the ability to access the cluster even if a node in the cluster goes down.

Partition tolerance means that the cluster continues to function even if there is a "partition" (communication break) between two nodes (both nodes are up, but can't communicate).

In order to get both availability and partition tolerance, you have to give up consistency. Consider if you have two nodes, X and Y, in a master-master setup. Now, there is a break between network communication between X and Y, so they can't sync updates. At this point you can either:

A) Allow the nodes to get out of sync (giving up consistency), or

B) Consider the cluster to be "down" (giving up availability)

All the combinations available are:

• CA - data is consistent between all nodes - as long as all nodes are online - and you can read/write from any node and be sure that the data is the same, but if you ever develop a partition between nodes, the data will be out of sync (and won't re-sync once the partition is resolved).
• CP - data is consistent between all nodes, and maintains partition tolerance (preventing data desync) by becoming unavailable when a node goes down.
• AP - nodes remain online even if they can't communicate with each other and will resync data once the partition is resolved, but you aren't guaranteed that all nodes will have the same data (either during or after the partition)

You should note that CA systems don't practically exist (even if some systems claim to be so).

Solution 2

Considering P in equal terms with C and A is a bit of a mistake, rather '2 out of 3' notion among C,A,P is misleading. The succinct way I would explain CAP theorem is, "In a distributed data store, at the time of network partition you have to chose either Consistency or Availability and cannot get both". Newer NoSQL systems are trying to focus on Availability while traditional ACID databases had a higher focus on Consistency.

You really cannot choose CA, network partition is not something anyone would like to have, it is just an undesirable reality of a distributed system, networks can fail. Question is what trade off do you pick for your application when that happens. This article from the man who first formulated that term seems to explain this very clearly.

Solution 3

Here is how I'm discussing CAP, regarding P particularly.

CA is only possible if you are OK with a monolithic, single server database (maybe with replication but all data on one "failure block" - servers are not considered to partially fail).

If your problem requires scale out, distributed, and multi-server --- network partitions can happen. You're already requiring P. Few problems I approach are amenable to single-server-always paradigms (or, as Stonebraker said, "distributed is table stakes"). If you can find a CA problem, solutions like a traditional non-scale-out RDBMS provides a lot of benefits.

For me, rare: so we move on to discussing AP vs CP.

You only choose between AP and CP operation when you have a partition. If the network & hardware is operating correctly, you get your cake and eat it too.

Let's discuss the AP / CP distinction.

AP - when there is a network partition, let the independent parts operate freely.

CP - when there is a network partition, shut down nodes or disallow reads and writes so there are deterministic failures.

I like architectures that can do both, because some problems are AP and some are CP - and some databases can do both. Among the CP and AP solutions, there are subtleties as well.

For example, in an AP dataset, you have the possibility of both inconsistent reads, and generating write conflicts - these are two different possible AP modes. Can your system be configured for AP with high read availability but disallows write conflicts? Or can your AP system accept write conflicts, with a strong and flexible resolution system? Will you need both eventually, or can you pick a system that only does one?

In a CP system, how much unavailability do you get with small partitions (single server), if any? Greater replication can increase unavailability in a CP system, how does the system handle those tradeoffs?

These are all questions to ask with CP vs AP.

A great read in this area right now is Brewer's "12 years later" post. I believe this moves forward the CAP debate with clarity, and recommend it highly.

http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed

Solution 4

Consistency:

A read is guaranteed to return the most recent write(like ACID) for a given client. If any request comes during that time it has to wait till data sync completed across/in the node(s).

---

Availability:

every node (if not failed) always executes queries and should always respond to requests. It does not matter whether it returns the latest copy or not.

---

Partition-tolerance:

The system will continue to function when network partitions occur.

---

Regarding AP, Availability(always accessible) can exist with(Cassendra) or without(RDBMS) partition tolerance

pic source

Solution 5

I have gone through lot of links, but none of them could give me satisfactory answer, except one.

Hence I am describing CAP in very simple wordings.

• Consistency: Must return same Data, regardless to from which node is it coming.

• Availability: Node should respond (must be available).

• Partition Tolerance: Cluster should respond (must be available), even if there is a a partition (i.e. network failure) between nodes. ( Also one main reason it confuses more is bad naming convention of it. If I had right, I might have given DNC theorem instead: Data Consistency, Node Availability, Cluster Availability, where each corresponds to Consistency, Availability and Partition Tolerance respectively )

CP database: A CP database delivers consistency and partition tolerance at the expense of availability. When a partition occurs between any two nodes, the system has to shut down the non-consistent node (i.e., make it unavailable) until the partition is resolved.

AP database: An AP database delivers availability and partition tolerance at the expense of consistency. When a partition occurs, all nodes remain available but those at the wrong end of a partition might return an older version of data than others. (When the partition is resolved, the AP databases typically resync the nodes to repair all inconsistencies in the system.)

CA database: A CA database delivers consistency and availability across all nodes. It can’t do this if there is a partition between any two nodes in the system, however, and therefore can’t deliver fault tolerance. In a distributed system, partitions can’t be avoided. So, while we can discuss a CA distributed database in theory, for all practical purposes, a CA distributed database can exist but should not exist.

Hence, this doesn’t mean you can’t have a CA database for your distributed application if you need one. Many relational databases, such as PostgreSQL, deliver consistency and availability and can be deployed to multiple nodes using replication.

Source: https://www.ibm.com/cloud/learn/cap-theorem

View more solutions

Comments

[Maiden]

don't go for the readymade anslwers . Read , visualize and understand each C , A , P separately . Design a distributed cluster architecture (maybe 3 DB) and now apply your understanding . See what happens to C,A,P when failures of the distributed (DB's) happens . Once you understand , then check for answers and apply with your logic . Remember - Even if you understand , it might not be clear . so, think and apply your understanding . Thanks

[vivek.m]

Somehow the above ksat.me link goes to 404 url because it ends with '/'. ksat.me/a-plain-english-introduction-to-cap-theorem This works fine and is very detailed explanation of each of 'C', 'A', 'P'

[Ram Ghadiyaram]

my answer here which describes what should be considered before choosing hbase?

[grep]

In AP why we do not have guaranteed that all nodes will have the same data? Ok, because of we do not have "C" but.. this is not clear for me... I want to know why this happens...

[Chris Heald]

@grep Sorry for the late answer. If you have both availability (the cluster doesn't go down) and partition tolerance (the database can survive nodes being unable to communicate), then you can't guarantee that all nodes will always have all the data (consistency), because nodes are up and accepting writes, but can't communicate those writes to each other.

[bitinn]

Late to the party, but it's worth showcasing some examples in each category, eg. blog.nahurst.com/visual-guide-to-nosql-systems

[shrotavre]

it'd really help to include a simple illustration/example about node-clusters meant here. is it a system or a data table/collections spread across different system or something else?

[Chris Heald]

Pragmatically, nodes are most often individual systems (or software running on those systems) connected by some networking mechanism.

[Gadam]

“Availability means the ability to access the cluster ..”— this should be ‘extent of access to the cluster’. The cluster is still up, but only few nodes are accessible.

[chaooder]

CA system is indeed confusing, I have a question regarding your CA example of a monolithic database. If it is just a single server, where does the "A" come from, since it appears to me that the failure of the said server will result in no service being available?

[Zippon]

For this statement: B) Consider the cluster to be "down" (giving up availability), doesn't it mean we lost both A and P? The cluster doesn't function now...

[Brian Bulkowski]

Good question. Servers can have a disk fail, or even have DIMMs fail, or have power supplies fail if they are designed for high availability. Even imagine being on multiple power grids. You get higher and higher availability, but there is never a "network" inside that has the capability to partition and run with components disagreeing. While more esoteric hardware exists ( look up SQL NON-STOP ), examples of RAID arrays with failing and resuming components are still common these days, and provide very high availability in a single server.

[Vigneswaran Rk]

This is a relevant read. Google Cloud Spanner claims to be CA system in practice (not technically) for most use cases : cloud.google.com/blog/products/gcp/…

[Ashish Ranjan]

This is what I also understand from CAP theorem. On network partition, you can either chose consistency or availability.

[Prashanth Debbadwar]

B) Consider the cluster to be "down" (giving up availability) In this case, how does the system is partition tolerant?

[Chris Heald]

You can remain "partially available" in something like a master-slave setup by making slaves unavailable during a partition, while leaving the master online. You just can't keep the whole cluster available during a partition - only the parts capable of declaring what authoritative state is.

[Bishnu]

If it makes sense to ask, How availability works in the AP system? Consider 3 nodes A, B, C system, with RF=3, and B & C are down. Any write to node A with consistency ALL/QUORUM would fail as B, C is down. How availability is achieved here?

[Chris Heald]

Requiring ALL is essentially CP, not AP. QUORUM works by ensuring that writes only go to the majority cluster in a partition, but if no cluster of a majority of nodes can be formed, it can't continue. No system can maintain availability with a critical number of nodes being offline.

[Adam Zerner]

Hm, my read of your response @BrianBulkowski is that the "A" is saying "it'll still be available even if there's a network partition", not "it'll still be available if the node goes down". Is that accurate?

[Varun Garg]

Agree, traditional SQL databases are CA, but they don't have any partitioning, only failover for HA. Can a system without P be even considered distributed?

[matrix]

You didn't answer the question. Actually, what you're saying is exactly the thing that made the OP confused.