Consistency or Availability of databases?

Do you really understand the CAP theorem?

In this post, we will cover what CAP is, what PACELC is, why are they used? And how you can make better decisions on which distributed database to choose for your application. It’s one of the most confusing theorems on the internet with a lot of misleading articles. There are many articles that actually explain the CAP correctly but then use a lot of jargon like ‘Linearzability, Serializability, etc”. This is a humble attempt to understand the CAP theorem.

Content:

1. CAP theorem and the confusion around it.
2. Definition of Consistency, Availability and Partition Tolerance.
3. Difference between Consistency in CAP vs ACID.
4. Common ways to favor consistency or availability in case of a network partition.
5. Is CAP a good way of analyzing a distributed data store? Why and why not?
6. What is the PACELC theorem?
7. Conclusion
8. References and further readings.

1. CAP theorem and the confusion around it.

CAP theorem is used to analyze the behavior of the distributed data store in specific scenarios. Mind you, it’s applicable to only distributed data stores. I have been asked to analyze the behavior of a single node MySQL using the CAP theorem which is not possible.

This is what Wikipedia says about CAP theorem — “In particular, the CAP theorem implies that in the presence of a network partition, one has to choose between consistency and availability.”

A system has to trade-off between favoring Consistency and Availability in case of Network Partition. This behavior is what CAP theorem captures. So, knowing how a particular system is designed, can help you make a judicious choice of which distributed store to choose for your purpose.

The above diagram is the most common diagram used to explain the CAP theorem.

Thinking of CAP as a “You-Pick-Two” theorem is misguided and dangerous. First, “picking” AP or CP doesn’t mean you’re actually going to be perfectly consistent or perfectly available; many systems are neither. It simply means the designers of a system have at some point in their implementation favored consistency or availability when it wasn’t possible to have both.

If you see in the diagram, there are systems marked as CA. In the CAP theorem, this possibility simply doesn’t exist as it considers only the case when a network partition occurs. So, in the case of a network partition, it’s impossible for the system to guarantee both consistency and availability. A system has to trade-off between favoring Consistency and Availability in case of Network Partition.

2. Definition of Consistency, Availability and Partition Tolerance.

Let’s actually see what C, A and P in CAP have been defined. This is important as different words like Consistency has a very different meaning when used in a different context.

1. Consistency: All replicas of the same data will be the same value across a distributed system. You cannot apply an update to multiple nodes all at the same time. We will see Consistency in detail later. We will also differentiate between Consistency used in ACID properties vs Consistency in CAP.
2. Availability: For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. Node failure is outside the scope of the CAP theorem. It’s not equivalent to a Partition. A system is not considered for Availability in case of Node Failure or Crash. This is important as we assume that all nodes are up and doing their work.
3. Partition Tolerance: The network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. This may be due to multiple reasons like nodes are too busy and the heartbeats from each other times out, a network switch is down, etc. Let’s say a switch went down connecting the two components in the network. In that case, each component is a partition.

3. Difference between Consistency in CAP vs ACID.

Consistency in ACID — ACID consistency is all about database rules. Transactions must follow the defined rules and restrictions of the database, e.g., constraints, cascades, and triggers.

If a schema declares that a value must be unique, then a consistent system will enforce the uniqueness of that value across all operations. If a foreign key implies deleting one row will delete related rows, then a consistent system will ensure the state can’t contain related rows once the base row is deleted.

CAP Consistency is more like ‘Linearizability’. In plain English, under linearizability, writes should appear to be instantaneous. Imprecisely, once a write completes, all later reads (where “later” is defined by wall-clock start time) should return the value of that write or the value of a later write. Once a read returns a particular value, all later reads should return that value or the value of a later write. There is a good blog that explains the difference between Linearizability and Serializability.

CAP consistency promises that every replica of the same logical value, spread across nodes in a distributed system, has the same exact value at all times. Note that this is a logical guarantee, rather than a physical one. It’s not possible to have the same value at the same time across all the nodes in the cluster. The cluster can still present a logical view by preventing clients from viewing different values at different nodes.

4. Is CAP a good way of analyzing a distributed data store? Why and why not?

CAP gives a good view of how a system will behave under network partition but it says nothing about normal conditions.

Also, network partitions are a rare phenomenon. PACELC also includes the behavior of the system when there is no network partition. So, I prefer classifying systems using PACELC.

5. What is PACELC?

PACELC, is also used to analyze a distributed data store like CAP. It says: “In case of Network Partition a system can favor either Availability or Consistency Else you can favor either Latency or Consistency”. Now, this is important, in order to achieve a higher degree of consistency, a write operation should be successful once all the replica successfully process writes. This increases the latency of the system, as we wait for all the replicas to update their system in order to remain consistent. Or, else we can have read and write quorum, in which if 2 out of 3 replicas completes the write operation, then the write is marked as successful. And during the read operation, 2 out of 3 nodes must agree on the same value. This reduces the latency of the writes as we don’t wait for all the replicas to be updated. It’s a tradeoff that we need to take depending on the type of application. For, some applications, low latency is of prime concern, consistency can be traded off, for example, the “Search Systems” in E-commerce, Google, etc. If a document/item is not consistent immediately, it’s not a big deal. But for a banking/p2p system, let’s say you are expecting money from someone when you check the balance, you see money is added to your account and the very next moment when you hit the refresh button, the money suddenly disappears. It will create a really bad user experience and also panic among customers. In this case, we need high consistency.

6. Common ways to favor consistency or availability in case of a network partition.

It’s easy to favor availability, just allow the system to operate as it was operating earlier except that now data might not be consistent.

To favor consistency is a hard problem, it might not be possible to achieve completely, depends on the strategy. Like once a partition is identified, one of the partitions will only be allowed to operate and the rest will be shut down. This way only some of the updates which can guarantee consistency in that partition is allowed. The rest are discarded. Availability is traded.

In some systems like Hazelcast, you can configure the minimum number of nodes to be available for a cluster to be operational. Like out of 10 you may configure min 6 nodes to be present to allow a cluster formation. This way the other partitions can be avoided to form a cluster.

Another strategy is to completely shut down the whole cluster, this way no updates can be applied. Everything is consistent.

Conclusion:

1. CAP is only defined in the scenario of a distributed data store and not a single-node data store.
2. The only case which CAP handles is what happens during the case of Network Partition which is a rare thing. PACELC theorem addressed the tradeoff a system has to make even when there is no Network Partition.
3. CA systems don’t exist. Don’t confuse CAP as a “pick two” theorem.
4. Consistency in CAP is not the same as ACID consistency.
5. Node crash or failures is not considered when discussing Availability.
6. Choose your store based on your application requirements and know it beforehand as to how it will behave in case of network partitions. Also, you can tune the default values of consistency to meet your application requirements.

References and further readings:

1. https://www.voltdb.com/blog/2015/10/22/disambiguating-acid-cap/
2. CAP Wikipedia Page
3. Eric Brewer’s CAP Revisiting article at infoq.com from 2012
4. Coda Hale’s You Can’t Sacrifice Partition Tolerance from 2010
5. Dan Abadi’s post on PACELC from 2010
6. Martin Kleppmann’s post Please stop calling databases CP or AP from 2015
7. Henry Robinson’s CAP FAQ from 2013
8. Peter Bailis’s blog