Why isn't RDBMS Partition Tolerant in CAP Theorem and why is it Available?

Question

Two points I don’t understand about RDBMS being CA in CAP Theorem :

1) It says RDBMS is not Partition Tolerant but how is RDBMS any less Partition Tolerant than other technologies like MongoDB or Cassandra? Is there a RDBMS setup where we give up CA to make it AP or CP?

2) How is it CAP-Available? Is it through master-slave setup? As in when the master dies, slave takes over writes?

I’m a novice at DB architecture and CAP theorem so please bear with me.

Melanie

Answer 1

It is very easy to misunderstand the CAP properties, hence I'm providing some illustrations to make it easier.

Consistency: A query Q will produce the same answer A regardless the node that handles the request. In order to guarantee full consistency we need to ensure that all nodes agree on the same value at all times. Not to be confused with eventual consistency in which the network moves towards having all data consistent but there are periods of time in which it is not.

Availability: If the distributed system receives query Q it will always produce an answer for that query. This should not be confused with "high-availability", this is not about having the capacity to process a higher troughput of queries, it is about not refusing to answer.

Partition Tolerance: The system continues to function despite the existence of a partition. This is not about having mechanisms to "fix" the partition, it is about tolerating the partition, i.e. continuing despite the partition.

Note that the following examples do not cover all possible scenarios. Consider the following caption:

An example for CP:

The system is partition tolerant because its nodes keep accepting requests despite the partition; it is consistent because the only nodes providing answers are those that maintain a connection to the master node that handles all the write requests; it is not available because the nodes in the other partition do not provide an answer to the queries they receive.

Examples for AP:

Either because (respectively) we have the slave nodes replying to requests regardless whether they able to reach master or because the slave nodes in the other partition elect a new master, or because we have a masterless cluster, availability is achieved because all questions are getting an answer - consistency is dropped because both partitions are replying while potentially yielding different states.

Examples for CA:

If we disconnect nodes when a partition occurs, we can ensure that we have at most one partition which ultimately means that the network is not partitioned anymore, or simply there is no service at all. This is the opposite of partition tolerance, because the system is avoiding the partition instead of functioning despite it. Consistency and availability holds in these partially or fully disconnected systems because all working nodes (if any) have the same state and all received queries (if any) will get an answer - shutdown nodes do not receive queries.

To answer the questions:

1. Under default configurations, databases such as Cassandra and MongoDB are partition tolerant because they do not shutdown nodes to cope with partitions, whereas RDBMS such as MySQL do.

2. Availability has very little to do with master/slave setup, e.g. Cassandra is masterless and very available because it doesn't really matter which node dies. As for availability in a master/slave setup, there is no reason to stop responding to all queries when master is dead, but you may need to suspend write operations while electing a new one.

Koziara

Thanks for these diagrams. I've been digging into this question for a while and your diagrams are finally helping me to make sense of it. I'm still confused though. Particularly about how you describe CP vs CA. Are you saying that in CP, the disconnected nodes receive a query and respond with some sort of "unavailable" error message, whereas in CA the request is re-routed away from the disconnected nodes and towards the connected nodes? If so, the former doesn't really sound like it's "handling" the partition, and the latter seems like it's strictly better (why would you choose CP over CA?). – Cartage

In CA the disconnected nodes get shutdown - they don't exist anymore, I don't I understand what you mean be re-route? There is no route in the first place – Thereafter

In CP, you say that the nodes accept requests despite a partition. But you also say that only the ones that are connected to the master node (top half of diagram) provide an answer to the query they receive. I don't see how accepting queries but not providing an answer to them is considered partition tolerant. – Cartage

In CA, consider the diagram you have on the left. The bottom half is shut down, and the top half continues to serve requests. Requests are ultimately routed to nodes in the network. Because the bottom half is shut down, the routing layer has to know not to route requests to them anymore, and to instead route the requests to the top half. To me, that sounds strictly better than the situation in CP, where requests arrive at nodes that are disconnected from the master node, but the query isn't answered. Wouldn't you rather have your query routed to a node that can answer it? – Cartage

To elaborate on what I mean by routing, I'm assuming that the client doesn't know the exact IP address of the machine they're trying to hit. Instead, the client says something like "get count of users", sends that request to some sort of routing layer, and that routing layer finds the right machine to hit. Imagine the router has an IP of 999, and DBs have IPs of 111, 222, 333, 444 and 555. I'm assuming the client sends their request to 999 and then 999 routes the request to one of the DBs. – Cartage

How is the first example(CP) tolerant towards partitions? There is a partition and we have upper half and lower half in your diagram. Only your upper half is tolerant since it will give results(since it can connect to master node). What about users in lower half(or lower geographical region)? How is this tolerant towards partitions? – Sebastien

@Sebastien because despite the partition (P) no two nodes will provide a different answer to the same question in any given moment (C) – Thereafter

@AdamZerner It seems to me that you are focusing too much on the practical side of things, don’t forget that the cap theorem is as the name implies a theoretical perspective that tries do explain that there is a trade-off iimplicit when choosing between different approaches – Thereafter

Allow me to provide an extra perspective. If no partitions occur then the theorem does not apply - all nodes are online and capable of providing a consistent answer to every query. The problem is when a node is unable to contact the rest of the cluster, then it has only three moves: 1) replies 2) does not reply 3) shutsdown. These three options lead to the three trade-offs exposed by the theorem – Thereafter

@JoãoMatos Thanks for the detailed explanation, After reading this my perspective towards CAP changed a lot. As you said, in case of failure cluster has 3 moves. 1) replies 2) does not reply 3) shuts down. I don't understand, How is do not reply different from shutdown? Even if few nodes are available and not replying, they are not contributing anything to the cluster. How are they useful? – Selfness

@JayantNarwani I) if all disconnected nodes shutdown then you are left with a fully connected cluster capable of providing you with a consistent response (CA) - in other words a request can only arrive at a connected node because there are no disconnected ones; ii) a disconnected node that does not reply while in that state is not useful but it regains usefulness once it reconnects - a partition can be temporary, e.g. the node is unable to reach other nodes for a few seconds and during that small window it chooses not to reply – Thereafter

@JoãoMatos thx for explanation, I think ur answer is better than the accepted one. But, like AdamZerner, am confused with the CA. In CP left diagram client connected to partitioned network, but not in CA left diagram. If there is client connected before partition happened, what happen to the client during partition? Does the client re-connect to the other partition or the client simply see the whole cluster as unavailable (which is not CA to that client)? I know it is a theorem but does it mean CA practically not exist? As shown here codahale.com/you-cant-sacrifice-partition-tolerance – Memnon

@verdy you are getting confused because using practical corner cases to disprove theorems is slippery. Consider an analogous example to attack AP instead: i) bring node failures to the table, because in practice node failures are like partitions -> you can’t guarantee that they won’t happen; ii) In an AP system a node receives a request right before a failure occurs which prevents the node from answering, thereby breaking availability; iii) does this mean that AP does not exist in practice? – Thereafter

My interpretation says no because breaking A is about refusing to answer and keep on working as if nothing happened, as opposed to not answering because we failed or because we shutdown. – Thereafter

Regarding CA not existing in practice: I disagree, IMHO you can implement CA - as explained above, if nodes shutdown when unable to reach their colleagues we have CA - the question is whether you want to. I don’t think anyone likes the idea of having their nodes potentially shutting down every time packages do not get delivered, hence I don’t think you’ll find many CA examples. Or to put it simpler, although it is a valid option it might not be a good one, so in practice you end up choosing between CP and AP alone. – Thereafter

Is there a use case for CP ? – Doerrer

@KamilDziedzic many. Let's say you have a bank account balance of N€ in an AP cluster, two concurrent withdraws of N€ each could potentially result in withdrawing twice as much you're allowed. Just a trivial example but in many cases eventual consistency is not enough and we need to ensure all nodes agree on a variable value at all times – Thereafter

Answer 2

A lot of databases now actually have different configurations and depending on the settings you set, it can be either CA, CP, AP, etc but can not achieve all three at the same time. Some databases actually make an effort to support all three but still prioritizes them in a certain way.

For example, MySQL can be CP and CA depending on the configurations. By default, it is CA because it follows a master slave paradigm which data is replicated to the slaves. Partition tolerance is sacrificed in the event that a set of the slaves loses the connection to the master and therefore decides to elect a new master creating two masters with their own set of slaves.

However, MySQL also has another configuration which is a clustered configuration. It prioritizes CP over availability eg. the cluster will shutdown if there are not enough live nodes to serve all the data.

There are probably more configurations for MySQL that makes it satisfy other CAP theorem combinations but overall, I just wanted say that it depends on what your system requires. Sometimes databases are better for one configuration vs another so its best to see what kinds of problems that may also occur in using a certain configuration.

As for implementing the CAP theorem, I would advise taking a further look into different databases and how they implement the priorities for the CAP theorem. There are just too many different ways of implementing them eg. generally, the master slave model is used for CA systems, the hash ring for AP systems, etc.

Profusion

you said Partition tolerance is sacrificed in the event that a set of the slaves loses the connection to the master and therefore decides to elect a new master creating two masters with their own set of slaves . I did not get, how creating two masters with their own set of slaves sacrifices the Partition tolerance ? – Hypersensitize

@Hypersensitize Sorry for getting back to this kind of late. It doesn't satisfy partition tolerance because a network partition will make the masters behave like individual clusters which they'll move forward with their own respective writes and updates without having the most updated data from the other master. – Profusion

@WillC you don't seem to understand what partition tolerance means, at all. Partition tolerance means that your cluster continues to work even if there's a partition. If there's no partition tolerance, that means that in the event of a network partition, the system stops working. – Graben

@hey_you Even if the system "functions" under partition, if the system doesn't have a way to resolve such situation where there are two masters, then it's definitely not partition tolerant - if you do claim that it is partition tolerant, then it wouldn't be consistent since the two masters would have their own versions of the database that cannot be resolved by the system. – Undercoat

@JohnSuh then it is an AP system, available, partition tolerant, but not consistent. Partition tolerance does not mean that the system has to be consistent. – Graben

@hey_you You're correct in theory. However, if there are no consistency guarantees(lowest being evenual), then you can have a "AP system" where you're just have two separate databases under one connection. Such system is useless. All AP systems have some way of resolving or minimizing conflicts in one way or another. – Undercoat

@JohnSuh : How's MySQL master slave CA ? when the master goes down and the slave takes over there is a small downtime that the system becomes unavailable right. please clarify – Pasto

@AarishRamesh I was stating that no database with replication can theoretically be CA, so the poster is incorrect in that master-slave is CA, in fact it is (or should be configured to be) CP. #29664145 refer to Average Joe's explanation. A master-slave that is CA would be a distributed system in disguise because it's acting like a single server system; fundamentally, distributed system should have a way to handle failover, otherwise it's not really a distributed "system". – Undercoat

@JohnSuh if the system “functions” under partition then by definition it is partition tolerant, period. ‘Resolving such situations’ is exactly what makes a system partition intolerant by definition. – Thereafter

In other words, a system that continues to operate despite the partition is partition tolerant, whereas a system that tries to fix the partition is partition intolerant – Thereafter

I have seen a lot of bad high-voted answers regarding the cap theorem, leading the readers to miss the point completely. Please take a look at my answer below which attempts to clarify some misconceptions – Thereafter

"So, while we can discuss a CA distributed database in theory, for all practical purposes, a CA distributed database can’t exist." ibm.com/cloud/learn/…. @JoãoMatos It seems like we're having a semantic issue. "continues to operate" is something that the client believes is happening, but the system should have a way of recognizing incongruity in the consistency (CP systems made w Raft, Paxos, etc.) or push the burden to the client (AP systems made w sloppy quorum). – Undercoat

There is no "System" that is not "partition tolerant", because a partition tolerant system is, by definition, a misnomer - such system is just independent set of nodes that perform CRUD operation. You can argue whether this makes sense on a semantic level, but the point is that there's no point discussing what a CA system is in the literature because it has no real meaning. Here, I am assuming that when we use the word "system", we're omitting (distributed) in front of it with multiple nodes. – Undercoat

@JohnSuh if nodes that are unable to reach the rest of the cluster decide to shutdown, how is this not CA? Since the shutdown nodes will not receive requests, then all requests received by the cluster will get a consistent answer. – Thereafter

@JoãoMatos Let me know if my example is the right setup: two node cluster(node A, node B), write comes to node A, partition occurs before write is replicated, A shuts down. In this case, the system does not satisfy availability because the write to node A fails. Assume A doesn't fail (returns a success response), then proceeds to shutdown. Then there is no consistency between node A and node B since client will not be able to read the write to node A. – Undercoat

In other words, given in a world where "partition" is a concept, you can't have both C and A. CA can only exist if there exists no partition in the system (i.e. you're using a single machine). – Undercoat

@JohnSuh If A gets the write and then shuts down, B is still up, although inconsistent because it doesn't have the latest write from A. The system is inconsistent. The service is still Available. How does it not satisfy availability? – Naturally

@Naturally reading my example again, I realize it is poorly put into words. I was really trying to point out that there is no point saying that there exists a "system" of multi-nodes that is CA, attempting to prove by showing two cases node failures (one before write to A succeeds, one after write to A succeeds). The only real CA that exist is when a single node is the entire system...in which case it is no longer a "distributed" system but just one server. So CA is not relevant in the discussion of distributed systems which is what CAP theorem (which isn't even a theorem) was made for. – Undercoat

@JohnSuh That part I agree. But I still don’t seem what it means for : one before writes to A succeeds and one after write to A succeeds. It looks like there is much less information bere to conclude anything about the clause. I agree that CA can’t be distributed. – Naturally

@Naturally I actually had a misunderstanding regarding availability I realize and it was a bad way of thinking of the two cases. – Undercoat

Answer 3

CAP theorem is problematic and it applies only to distributed database systems. When you have distributed databases then network partition and node crashes can happen. And when network partition happens you must have partition tolerance (the P of your CAP).

So to answer your question number 1) It’s either CP or AP. It can be configured as Will mentioned.

More about why partition tolerance is a must: https://codahale.com/you-cant-sacrifice-partition-tolerance/

More about problems around CAP theorem: https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html

Luggage

Answer 4

I agree that RDBMS can have all the properties of CAP. I have started studying noSQL DBs and had prior experience with IBM DB2.

Here is how IBM DB2 satisfies all the 3 CAP properties

1. C : Consistency : Every relational database satisfies this due to the transactional nature of RDBMS.

2. A : Availability : Availability means that when a query is made for a data that exists, it should be returned. Again, a relational database is designed to do this easily.

3. P : Partition Tolerance : This is the most interesting one. From DB2 stand point, in the application that I was working on, we had 2 databases spread across different data centres. One was the primary and communicated with the secondary via heartbeats. Each of these primary and secondary databases, had 12 physical instances where data was distributed on the basis of some predefined logic. If the primary goes down, the secondary detects this and takes the place of primary. Since the primary and secondary were always maintained in sync, data remains consistent as well.

This is how I think that RDBMS satisfies all 3 properties of CAP Theorem.

I may be wrong, and open to discussion on this.

Italia

How does it guarantee availability when one of the datacenters goes down? – Pashm

Your DB2 setup sounds like a Master-Slave setup. Which means, correct me if I'm wrong, that it should have some sort of downtime to promote the slave to master. Is that correct? Also, does Availability in CAP mean that there's absolutely no downtime when one node goes down? – Melanie

Sorry, but no distributed solution can have all 3 at any given time, that is just impossible. youtube.com/watch?v=K12oQCzjPxE&feature=youtu.be&t=183 You can have a system which is configurable to which of the two you have, You can have a system that tries to mitigate. But ultimately, you HAVE to make a choice on which you in the end sacrifices. – Markova