Understanding CAP theorem and its relevance in distributed systems

Understanding CAP theorem and its relevance in distributed systems
Photo by Yevhen Rozhylo / Unsplash

In this guide, we will be analyzing the CAP theorem and its relevance in the development of distributed applications and in the choice of a NoSQL or relational data storage.

What is the CAP theorem?


Have you ever seen an ad for a landscaper, house painter, or some other tradesman that starts with the offer "Cheap, fast, and good: pick only two of these three options"?

The CAP theorem applies a similar type of logic to distributed systems, like a distributed system that can deliver only two of three desired features: consistency, availability, and partition tolerance (the "C," "A," and "P" in CAP).

A distributed system is a network that stores data on more than one node (physical or virtual machines) at the same time. Since all cloud applications are distributed systems, it is essential to understand the CAP theorem when designing an application in the cloud, so that you can choose a data management system that delivers the features your application needs the most.

The CAP theorem is also called Brewer's theorem, because it was first created by Professor Eric A. Brewer during a lecture he gave on distributed computing in the year 2000. Two years later, MIT professors Seth Gilbert and Nancy Lynch published evidence of "Brewer's Conjecture".

Details on the "CAP" of the CAP theorem


Let's take a deeper analysis on the three characteristics of the distributed system that the CAP theorem refers to.

Consistency

Consistency means that all clients see the same data at the same time, no matter which node they connect to. For this to happen, whenever the data is written to a node, it must be instantly forwarded or replicated to all other nodes in the system before the write is considered "successful."

Availability

Availability means that any client making a data request will get a response, even if one or more nodes are down. That is, all nodes operating in the distributed system return a valid response for any request, without exception.

Partition tolerance

Partition is a break in communications within a distributed system, a lost or temporarily slow connection between two nodes. Partition tolerance means that the cluster must continue to function even if one or more communication failures occur between the nodes in the system.

Types of NoSQL databases in the CAP theorem


NoSQL (non-relational) databases are ideal for distributed network applications. Unlike their vertically scalable SQL (relational) counterparts, NoSQL databases are horizontally scalable and were created to be distributed. It is possible to quickly adjust their scale in a growing network consisting of multiple interconnected nodes. (See "SQL vs. NoSQL Databases: What's the Difference?" for additional information).

Currently, NoSQL databases are classified based on the two CAP features they offer:

  • CP Database: A CP database delivers consistency and partition tolerance at the expense of availability. When a partition occurs between any two nodes, the system must disable the inconsistent node (i.e., make it unavailable) until the partition is resolved.
  • AP Database: An AP database delivers availability and partition tolerance at the expense of consistency. When a partition occurs, all nodes remain available, except those on the wrong side of a partition may return an older version of data than others. When the partition is resolved, AP databases usually resynchronize nodes to correct all inconsistencies in the system.
  • CA Database: A CA database delivers consistency and availability across all nodes. However, this is not possible if there is a partition between any two nodes in the system, and therefore, it cannot deliver fault tolerance.

We listed this type last for the following reason: in a distributed system, partitions cannot be avoided. Therefore, while we can discuss a distributed CA database in theory, for all practical purposes, a distributed CA database cannot exist.

Comparing NoSQL and Relational Databases

Relational databases, on the other hand, are vertically scalable and have been around for decades. They are based on the relational model, where data is organized into tables with defined relationships between them. They are ideal for applications that require data integrity and consistency.

One of the advantages of relational databases is that they provide ACID (Atomicity, Consistency, Isolation, and Durability) compliance. This means that transactions are guaranteed to be completed in full or not at all, and the data is always in a consistent state, even in the event of a system failure.

However, relational databases can be difficult to scale horizontally, which means they may not be the best choice for applications that require massive scalability. In addition, they may not be well-suited for applications that require flexibility in the schema, as changes to the schema can be complex and time-consuming.

Conclusion


When it comes to choosing between a NoSQL and a relational database, there is no clear winner. Both have their strengths and weaknesses, and the choice largely depends on the specific needs of the application.

If the application requires massive scalability, flexibility in the schema, and eventual consistency, a NoSQL database may be the best choice. On the other hand, if the application requires strong data integrity and consistency, and ACID compliance, a relational database may be the better option.

Regardless of the choice, it's important to understand the trade-offs involved and to choose a database that can deliver the necessary performance and functionality for the specific application.

Ref .:

  1. Martin Kleppmann's blog post "Please stop calling databases CP or AP": This post provides an in-depth explanation of the CAP theorem, why it is important, and why the common categorization of databases as "CP" or "AP" is not accurate. Link: https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
  2. Eric Brewer's original paper on the CAP theorem: In this paper, Eric Brewer presents the CAP theorem and its implications for distributed systems. Link: https://dl.acm.org/doi/10.1145/564585.564601
  3. Werner Vogels' blog post "Eventually Consistent - Revisited": This blog post by Amazon CTO Werner Vogels discusses the trade-offs between consistency and availability in distributed systems, and how to achieve the right balance. Link: https://www.allthingsdistributed.com/2008/12/eventually_consistent.html
  4. What is the CAP theorem? The CAP theorem maintains that a distributed system can deliver only two of three desired characteristics: consistency, availability, and partition tolerance. by IBM Link: https://www.ibm.com/topics/cap-theorem