CAP and ACID

Shane Keller
Jun 21, 2016 · 6 min read

The above two concepts are useful starting points for developing a solid understanding of core database concepts. I’m not going to reinvent the wheel, so first, read this quora post, which is the best summary of the above concepts that I’ve read. Now, let’s go a bit deeper.

Cap Theorem

The CAP Theorem is a useful way to consider the constraints on distributed systems. But it’s imperfect. First, the Quora post mentions that you can’t sacrifice partition tolerance in a reliable system. Let’s look at an example of why that’s the case. Consider the following system, in which each node is X, the master is X*, and a partition is |. The system involves a classic master-slave replication in which the master accepts writes and replicates to the read-only slaves.

Before the partition, everything is fine:

X X* X X X

After the partition, a subset of nodes must elect a new master in order to respond to write requests:

 X X* | X X X

Or otherwise, the system will be trapped in a split-brain state, in which each set of nodes is unaware of the other, and operates independently.

Partition Tolerance involves detecting a partition, entering a partition tolerant state (such as rejecting writes), and recovering from a partition after the partition has been repaired. So in order to detect that there’s been a partition, a system must have partition tolerance. Therefore, pure CA is not possible in a distributed system! Note that the above example describes a multi-node failure, which can be caused by any hardware failures in a data center. In a single-node failure, requests can fail over to a replica in a transactionally consistent way, and the system can still respond.

Second, CAP doesn’t explicitly address latency. While availability describes a binary outcome in which a request is responded to or not during a system failure, latency describes a continuous spectrum of a system’s delay in responding to a request under normal operations. Of course, latency could be so high that the system is effectively unavailable, and the client gives up in some way such as timing out the request. Professor Abadi at Yale gives a great explanation of how the latency vs. consistency tradeoff provides a more nuanced model of distributed system performance during normal system operations (other than a partition). The three alternatives for implementing replication, and their variations, each come with a consistency-latency tradeoff:

So, CAP is a great heuristic for thinking about distributed systems, but should not be interpreted too rigidly.

ACID

I’ll add some clarifications to ACID. First, “a transaction is a sequence of operations performed as a logical unit of work” (Microsoft TechNet). The concept of a transaction makes atomicity possible by grouping commands so that they either all succeed or all fail.

Next, while the “C” in the CAP Theorem refers to each node in the system having the same data, the “C” in ACID refers to a single node enforcing the same rules on every potential commit, such as the type of a field or a field not being null.

Also, isolation, which is a database property that guarantees that one transaction will not depend on the results of a transaction that has not yet been committed, can be implemented in multiple ways, with varying degrees of strictness. From wikipedia, in decreasing order of isolation level:

Image for post
Image for post

Source: Craig Freedman

“phantom reads” can occur in which the rows returned by two identical queries (aka “repeatable reads”) are different. For example:

/* Transaction 1, Query 1 */ 
SELECT * FROM users WHERE age BETWEEN 10 AND 30;
/* While Transaction 1 is still in progress, Transaction 2, Query 2 occurs */
INSERT INTO users(id,name,age) VALUES ( 3, 'Bob', 27 ); COMMIT;
/* Query 1 is executed again during Transaction 1, but its result will be different. */
SELECT * FROM users WHERE age BETWEEN 10 AND 30;

The tradeoff on all of these isolation levels is speed of database operations vs. consistency. Less locks means more transactions can read/write a particular row in a given period of time, but also means that there could be more variation in reads/writes from the same row. The loosest level of isolation, read uncommitted, has the additional downside of transactions potentially reading data that is not committed. This could occur of Transaction 2 reads rows that Transaction 1 has modified, and then Transaction 1 is rolled back.

Conclusion

Knowing a one-sentence definition for each of the terms in the CAP and ACID acronym is important. Depending on your job, you may not have to go any deeper than that. With that in mind, I’ll end with my own one-sentence definitions:

CAP — describes distributed systems

C — consistency — different nodes respond with the same data to the same request
A — availability — the system responds to a request, even if the system isn’t working or its data is outdated
P — partition tolerance — the system detects, remains operational during, and heals a partition caused by the failure of one or many nodes

ACID — describes databases

A — atomicity — either all of the operations in a transaction succeed, or none of them do
C — consistency — the database enforces rules about its fields and the relationships between fields
I — isolation — the extent to which rows that a transaction is affecting can be affected by other transactions
D — durability — the database writes its data to a permanent medium (hard drive) so that data is not lost during a power failure or other system failure


Originally published at www.shanemkeller.com, January 2016.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store