PROGRAMMING
CAP Theorem and Distributed Database Management Systems
Consistency, Availability, Partition Tolerance
This article aims to review CAP Theorem and its relevance when designing a distributed application and choosing the most suitable relational or non-relational database.
The ‘CAP’ in the CAP Theorem stands for consistency, availability and partition tolerance. In short, the theorem applies a simple logic that a distributed system can only deliver two of these characteristics. When designing a distributed application, it is essential to understand the CAP theorem and pick the data management system that delivers the most suitable two characteristics, depending on your needs, with the trade-off in the third term which should have a lower priority in our application.
“The CAP theorem is also called Brewer’s Theorem named after Professor Eric A. Brewer. He is the first person to mention the CAP theorem in a distributed computing talk back in 2000.” ¹
‘CAP’ in the Cap Theorem
Consistency
Consistency means that every replica of the same logical value spread across nodes in a distributed system has the same value at all times. For a successful write operation, each data that is written into one node must be successfully forwarded to each replica before a read operation starts. Thus guaranteeing that all reads receive the most recent write or an error.
Availability
Availability means that all non-failing nodes are available for queries at all times. The response must contain data (a non-error response), but it might not be the most recent data.
Partition Tolerance
To understand partition tolerance, the semantic of “partition” must be clarified. A partition is a communications break within a distributed system (nodes remain up, but the network between some of them does not work). In other words, this is a delay or a drop in messages between nodes communicating over an asynchronous network. Partition tolerance, also called Robustness, means that the cluster continues to function even if there is a partition.
The CAP Tradeoff
NoSQL databases are ideal for distributed network applications. Their ability to scale horizontally (unlike most SQL relational databases which can only scale vertically) makes them a perfect fit for applications with multiple interconnected nodes.
CA (Consistency and Availability)
Systems providing consistency and availability do so at the expense of sacrificing partition tolerance and the ability of distribution. If your needs match a database that returns the same data for each node at any time and is always aligned even if the instance of a partition, CA databases are the right choice.
Most relational databases like MySQL, PostgreSQL and Oracle are consistent and available (CA). They cannot provide partition tolerance hence they can only scale vertically (scale-up) and not horizontally (scale-out). They perform transactions referring to ACID properties, therefore, guaranteeing that the database transactions process reliably. Banking and finance applications require the data to be consistent and available thus they mostly prefer CA databases.
AP (Availability and Partition Tolerance)
All distributed systems must retain partition tolerance. AP databases trade off consistency for availability. They cannot guarantee consistency in the data between nodes but they provide eventual consistency. Prioritizing availability, these types of systems allow write operations on one node of the system without waiting for other nodes to become up to date thus it makes sense to use them with applications that favor writes over reads.
Dynamo from Amazon, Cassandra, CouchDB and Riak are some examples of AP-type databases.
Eventual Consistency is a guarantee that when an update is made in a distributed database, that update will eventually be reflected in all nodes that store the data, resulting in the same response every time the data is queried. ²
CP (Consistency and Partition Tolerance)
AP databases trade off availability for consistency. They ensure that data is always up to date and aligned, even in the instance of a partition. Having strong consistency on distributed systems comes with a trade-off of availability. When a write operation is performed, the database locks down all nodes until they are up to date. After all nodes are consistent, the system becomes available again.
MongoDB, Redis and HBase are some examples of CP-type databases.
Strong Consistency means the data must be strongly consistent at all times. All the server nodes across the world must contain the same value as an entity at any point in time. The only way to implement this behavior is by locking down the nodes when the database is being updated.
Limitations of the CAP Theorem
The Cap theorem gives us a basic understanding and perspective when looking at the classification of database system types. However, as it is inevitable with every theorem, The Cap theorem will eventually become outdated. Since 2000, many comments have been made on the CAP theorem and the CAP theorem has been struggling to cover important points on rapidly growing distributed systems (Big Data systems).
It is criticized for oversimplifying important concepts which leads to a misunderstanding of its original meaning. Furthermore, in its original definition, the CAP theorem ignores time delays, although in practice latency and partitioning are deeply connected. In 2012, twelve years after Professor Eric A. Brewer first mentioned the CAP Theorem, he wrote;
“Although designers still need to choose between consistency and availability when partitions are present, there is an incredible range of flexibility for handling partitions and recovering from them. The modern CAP goal should be to maximize combinations of consistency and availability that make sense for the specific application. Such an approach incorporates plans for operation during a partition and for recovery afterward, thus helping designers think about CAP beyond its historically perceived limitations.” ³
So, the idea was to think of the consistency and availability trade-off in a more advanced way such that we wouldn’t pick one of them but try to balance them most efficiently. However, there were also more criticisms of the Cap Theorem. Software engineer Martin Kleppman wrote an article mentioning “Please stop calling databases CP or AP” back in 2015. A short section in his article goes as follows;
“If you want to refer to CAP as a theorem (as opposed to a vague hand-wavy concept in your database’s marketing materials), you have to be precise. Mathematics requires precision. The proof only holds if you use the words with the same meaning as they are used in the proof. And the proof uses very particular definitions.”
“Also, the CAP theorem says nothing about latency, which people tend to care about more than availability. In fact, CAP-available systems are allowed to be arbitrarily slow to respond, and can still be called “available”. Going out on a limb, I’d guess that your users wouldn’t call your system “available” if it takes 2 minutes to load a page.” ⁴
Partitions in a network are very common and they absolutely do happen but it is not the only kind of problem that may occur. Nodes can crash or be rebooted, you can run out of disk space and so on. When building a distributed system, all of these trade-offs and complications should be taken into consideration. Focusing only on the issues mentioned in the CAP theorem may lead to ignoring other important issues. Thus as described in Brewer’s piece from 2012, system requirements should be considered and trade-offs should be thought after in detail. Furthermore, without being completely bound by the Cap Theorems terms but rather having one’s own approach to each term, developers may find their ideal database system.
The PACELC Theorem
The PACELC theorem described by Daniel J. Abadi is considered an alternative approach to the design of distributed systems. The PACELC Theorem is an updated version of the CAP model. In addition to consistency and availability, it also includes latency. The ‘E’ stands for ‘else’ meaning that while you have to choose between consistency and availability when a partition occurs, there will still be a trade-off between consistency and latency (LC) even if there is no partition.
Conclusion
The CAP Theorem might seem a little outdated but it still gives developers a way to think about database types when designing a distributed system. Not only does it provide a basic understanding of distributed system design but also a lot of developers started studies after The CAP theorem was first mentioned in 2000.
People criticized the theorem and started to think out of the box, improving the theorem even further. They concluded that a system should not be limited to two parameters and then sought solutions that provide more balance.
The CAP theorem is a theorem that applies to distributed systems in general but it is ill-advised to categorize systems based on it. PACELC Theorem extends the CAP Theorem by adding the latency and consistency trade-off into consideration and therefore it functions better when it comes to designing modern distributed databases and Big Data Applications. It is an undeniable fact that both theorems have their limitations. As they cannot cover every possible situation, they have to simplify the problem. On top of that, new requirements will constantly arise in the future, giving us even more parameters to take into consideration when building our distributed systems.
For More Information
- About CAP Theorem [1]
- About Eventual Consistency [2]
- About CAP Twelve Years Later [3]
- About Dr. Martin Kleppmann’s article [4]
