Acid transactions, ACID properties, and the CAP theorem are two important concepts in data management and distributed systems. It’s unfortunate that in both acronyms the “C” stands for “Consistency,” but actually means completely different things. What follows is a primer on the two concepts and an explanation of the differences between the two “C”s.
Table Of Contents
What is ACID?
The idea of acid transactions, their semantics and guarantees, evolved with data management itself. As computers became more powerful, they were tasked with managing more data. Eventually, multiple users shared data on a machine. This led to problems where data could be changed or overwritten while other users were in the middle of a calculation. Something needed to be done; so the academics were called in.
The “ACID” rules were originally defined by Jim Gray in the 1970s; the acronym was popularized in the 1980s. ACID transactions solve many problems when implemented to the letter but have been engaged in a push-pull with performance trade-offs ever since. Still, simply understanding these rules can educate those who seek to bend them about the dragons they may encounter.
A transaction is a bundling of one or more operations on database state into a single sequence. Databases that offer transactional semantics offer a clear way to start, stop, and cancel (or roll back) a set of operations (reads and writes) as a single logical meta-operation.
But transactional semantics do not make a “transaction.” A true acid transaction must adhere to the ACID properties. ACID transactions offer guarantees that absolve the end user of much of the headache of concurrent access to mutable database state.
The value of ACID transactions is argued in the seminal Google F1 paper:
The system must provide ACID transactions, and must always present applications with consistent and correct data. Designing applications to cope with concurrency anomalies in their data is very error-prone, time-consuming, and ultimately not worth the performance gains.
WHAT DOES ACID STAND FOR?
- Atomic: All components of a transaction are treated as a single action. All are completed or none are; if one part of a transaction fails, the database’s state is unchanged.
- Consistent: Transactions must follow the defined rules and restrictions of the database, e.g., constraints, cascades, and triggers. Thus, any data written to the database must be valid and any transaction that completes will change the state of the database. No transaction can create an invalid data state. Note that this is different from “consistency” as it’s defined in the CAP theorem.
- Isolated: Fundamental to achieving concurrency control, isolation ensures that the concurrent execution of transactions results in a system state that would be obtained if transactions were executed serially, i.e., one after the other. With isolation, an incomplete transaction cannot affect another incomplete transaction.
- Durable: Once a transaction is committed, it will persist and will not be undone to accommodate conflicts with other operations. Many argue that this implies the transaction is on disk as well; most formal definitions aren’t specific.
Many also argue the acronym itself is a bit forced. Specifically, the “C” is not like the others. These critics are right, but it seems hard to deny that the quality of the acronym has, in part, driven the success of ACID as a concept.
What is CAP?
CAP is a tool to explain trade-offs in distributed systems. It was presented as a conjecture by Eric Brewer at the 2000 Symposium on Principles of Distributed Computing and formalized and proven by Gilbert and Lynch in 2002.
WHAT DOES CAP STAND FOR?
- Consistent: All replicas of the same data will be the same value across a distributed system.
- Available: All live nodes in a distributed system can process operations and respond to queries.
- Partition Tolerant: The system is designed to operate in the face of unplanned network connectivity loss between replicas.
The typical CAP definition says: You can’t have all three. Here’s a more practical way to think about CAP: In the face of network partitions, you can’t always have both perfect consistency and 100% availability. Plan accordingly.
To be clear, CAP isn’t about what is possible, but rather, what isn’t possible. 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.
Second, of the three pairs, CA isn’t a meaningful choice. The designer of distributed systems does not simply make a decision to ignore partitions. The potential to have partitions is one of the definitions of a distributed system. If you don’t have partitions, then you don’t have a distributed system, and CAP is just not interesting. If you do have partitions, ignoring them automatically forfeits C, A, or both, depending on whether your system corrupts data or crashes on an unexpected partition.
Must Read: 5G and Its Impact on BSS
HOW IS CAP CONSISTENCY DIFFERENT FROM ACID CONSISTENCY?
ACID consistency is all about database rules. If a schema declares that a value must be unique, then a consistent system will enforce 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 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. Due to the speed of light, it may take some non-zero time to replicate values across a cluster. The cluster can still present a logical view by preventing clients from viewing different values at different nodes.
The most interesting confluence of these concepts occurs when systems offer more than a simple key-value store. When systems offer some or all of the ACID properties across a cluster, CAP consistency becomes more involved. If a system offers repeatable reads, compare-and-set or full transactions, then to be CAP consistent, it must offer those guarantees at any node. This is why systems that focus on CAP availability over CAP consistency rarely promise these features.
Further reading:
The internet is full of blog posts on CAP (I apologize for adding one more). They range from educational to editorial. Some are great. Many are terrible. Be careful not to rely too much on one source. Below is a collection of links interesting to me. I don’t endorse every word written, but each adds something useful to the discussion.
- CAP Wikipedia Page
- Eric Brewer’s CAP Revisiting article
- Coda Hale’s You Can’t Sacrifice Partition Tolerance
- Dan Abadi’s post on PACELC
- Martin Kleppmann’s post Please stop calling databases CP or AP
- Henry Robinson’s CAP FAQ
- Peter Bailis’s whole blog
