CAP Theorem: Explained

CAP theorem is a concept relevant to distributed database systems. The letters in CAP stand for Consistency, Availability, and Partition Tolerance. It was first introduced by Eric Brewer in 2000 and has since become a fundamental principle in the design of distributed systems. The CAP theorem states that a distributed system can guarantee at most two out of these three properties simultaneously. In this article, we will discuss the three concepts enclosed in the CAP theorem, what trade-offs are, and how you should consider them to build robust systems that can handle network failures and scale efficiently. 

What Does CAP Mean in CAP Theorem?

The CAP in CAP theorem represents the three fundamental properties of a distributed system: Consistency, Availability, and Partition Tolerance. 

Imagine a group of friends keeping a shared notebook. You can call this shared notebook the database, and this database gets “distributed” among the friends.

• Consistency (C): Whenever someone reads the notebook, they all see the same latest entry. All the notes are up to date, and nobody is reading anything outdated.
• Availability (A): No matter when you ask to see the notebook, a friend always gives you something, even if it is not the most recent version.
• Partition Tolerance (P): Even if the friends are split into separate rooms and can’t talk to each other, each group can still use their copy of the notebook.

These concepts basically determine how a system will behave under normal operation and also in the event of network failures. Let us discuss each of these one by one in reference to a distributed database system. 

Stay Ahead with Excellence in Data Analytics

Learn Data Analytics with Confidence

Explore Program

1. Consistency (C)

Consistency makes sure that when a user queries the database of a distributed system for information, the most up-to-date and correct information is returned. In a distributed system, multiple nodes read and write data; therefore, consistency becomes a key factor one should consider.

For example, a system writes “1” in a particular server of the distributed system. If the system is consistent, then this update will be synced across all the other servers that are a part of that system. 

2. Availability (A) 

Availability, on the other hand, guarantees that every request receives a response. It doesn’t matter if the server is up-to-date or not and contains the latest data. Even if a node is unreachable, the system still responds to queries, ensuring that the service remains accessible. As long as the system returns something, it is available. 

3. Partition Tolerance (P)

When a node stops responding, the network gets divided into parts. Partition Tolerance makes sure that the system continues to operate even if there are network failures or communication issues between nodes. In other words, the system can handle partitions where some nodes cannot communicate with others, without crashing or becoming completely unavailable.

Now that we know what C-A-P means in the CAP theorem, let us understand what the CAP theorem states.

CAP Theorem Statement

CAP theorem was introduced by Eric Brewer in 2000, and it states that a distributed system can guarantee only two out of the three properties (Consistency, Availability, and Partition Tolerance) at the same time.

In practice, Partition Tolerance (P) is not up for debate in distributed systems since network interruptions and communication failures are unavoidable. Therefore, according to the CAP theorem, once a Partition occurs, the system has to choose between Consistency and Availability:

• If the system chooses Consistency, it may need to deny or delay requests to guarantee that all nodes return the same data.
• If the system chooses Availability, it will return when it can to each request, even if the node returns an older piece of data.

This tradeoff is at the core of the CAP theorem. It is the job of an engineer to carefully decide which property, between availability and consistency, they should choose. This decision is made depending on the system’s objective, whether it be accuracy (banking, transactions) or responsiveness (social media, DNS).

Let us now move on to the different pairs of trade-offs that can be made. In the sections above, we claimed that partition is unavoidable. You might wonder: are there really no systems that provide both consistency and availability while ignoring partitioning? All these doubts will be answered in the section below. 

Brief History of the CAP Theorem

In 2000, computer scientist Eric Brewer introduced the CAP theorem during his keynote speech at the Principles of Distributed Computing (PODC) conference. Brewer proposed that, in a distributed system, it is impossible to provide Consistency, Availability, and Partition Tolerance (even informal guarantees) at the same time.

At that time, it was referred to as Brewer’s Conjecture because it had not been formally proved.

Two years later, in 2002, computer scientists Seth Gilbert and Nancy Lynch published a formal proof, and it subsequently became known as the CAP Theorem. This work, mathematically, demonstrated that under network partition, a distributed system must necessarily trade off between consistency and availability.

Since then, the CAP theorem has been one of the core principles of distributed systems for engineers designing databases, cloud infrastructure, and large applications.

The Three Trade-Offs in the CAP Theorem

Depending on which properties are prioritized, systems are generally classified into three categories: CA, AP, or CP. 

1. CA (Consistency + Availability)

A CA system ensures that not only is the data up-to-date and reflects the recent changes, but every request gets a response, either success or failure. You might think that since this is the ideal case, every distributed system should incorporate this. But the thing is that CA systems are only possible if we ignore Partition Tolerance. This ultimately means they will only work well in single-node systems or tightly coupled monoliths where network partitions don’t exist.

Example:

• A traditional relational database running on a single machine appears to provide both consistency and availability.
• However, once the data is distributed across multiple nodes, network partitions become possible, and maintaining both consistency and availability simultaneously is no longer guaranteed.
• This is why CAP theorem considerations only apply to distributed systems.

When to choose CA systems?

CA systems do not truly exist in distributed contexts. CA systems are a theoretical concept. 

2. AP (Availability + Partition Tolerance)

An AP system ensures that a system responds to every request, even if it’s not the most recent data. And along with this, it also takes care of partition tolerance, that is system continues working even if communication fails between a few nodes. 

Here, in a trade-off, consistency gets sacrificed, which means that during a partition, different nodes might return different (possibly stale) versions of the data.

Some real-world examples include: 

• DNS Server: A DNS request must always respond with an IP address, even if the data is outdated. 
• Social Media Platforms (Twitter, Facebook): In case of social media as well, showing a slightly old timeline is better than not showing anything at all.

When to choose AP systems?

AP systems are great for user-facing applications where responsiveness is more important than absolute accuracy.

3. CP (Consistency + Partition Tolerance)

A CP system sacrifices availability to ensure consistency during network partitions. This means that if the system cannot guarantee consistent data during a partition, it may reject or delay requests until the partition is resolved. Let us look at some examples where CP is used in the real world.

Examples:

• Banking Systems: In banking systems, it is always better to block a transaction than allow an inconsistent exchange of balance.
• Google Bigtable & HBase: These databases prioritize strong consistency over availability. They ensure the correctness of data first, but sometimes at the cost of availability.
• MongoDB (in certain configurations): In certain settings, MongoDB can also behave like a CP system when set to ensure strong consistency.

When to choose CP systems?

CP systems are used in mission-critical applications where the accuracy of the data is absolutely non-negotiable.

CAP vs ACID and Consistency Models

In a database management system, there is another term for Consistency, which might be another concept you have learned before, that is, the consistency in ACID. One of the common questions for beginners is, what is the difference between CAP’s consistency and ACID’s consistency?

• CAP Consistency (C): Consistency, in this case, means that all nodes in a distributed system will see the data at the same time. For example, if a read occurs after a recent write request, the read will return the latest value. This is only about distributed systems.
• ACID Consistency (C): In a relational database, consistency means that the transaction has taken the database from one valid state to another with respect to all the rules, constraints, and integrity checks. This means it is a property of database correctness at the level of a single transaction and not the multiple-node level.

Eventual Consistency vs Causal Consistency

In distributed systems, strict consistency is not always needed, especially in an Availability-centered system (AP systems). It is also the motivation for relaxed consistency models, which accept that nodes can be temporarily inconsistent: 

• Eventual Consistency: Eventually, all updates will reach all nodes, and all nodes will eventually be in the same state. Eventual consistency is used by systems like DynamoDB, Cassandra, and Riak.
• Causal Consistency: All causally related updates (one update is caused by the other) will be seen by all nodes in the same order, while updates that are in parallel will be seen differently at each node. This is a stronger guarantee than eventual consistency but a weaker guarantee than strict consistency.

Knowing the differences between CAP consistency and ACID consistency is useful for engineers working with CAP theorem in distributed systems, in making informed choices on which system to use. This also helps them in designing applications that achieve the appropriate balance of correctness, performance, and fault tolerance.

Practical Design Patterns in CAP Theorem

Understanding the CAP theorem is one thing, but when it comes to implementing it in real distributed systems, you need to have practical strategies. Next, we will discuss some common design patterns for when engineers encounter the trade-offs between Consistency, Availability, and Partition Tolerance patterns:

1. Replication

• Replication is the process of storing data across multiple nodes to provide fault tolerance and high availability.
• In this way, after a single node fails or goes down, you may still be able to serve requests from another copy of the data.
• Trade-off: Replication can introduce a level of inconsistency since data updates must flow to every replica for concurrency.

2. Quorum-Based Reads/Writes

• Under this arrangement, a quorum, or a subset of nodes, must agree before a read or write can be successful. 
• The Quorum ensures a higher probability of consistency by requiring overlapping read and write sets. But the basic requirement is that sufficient nodes should respond.
• Trade-off: Quorum read and write must be determined experimentally. For example, R + W > N  (where R = number of nodes to read, W = number of nodes to write, and N = total number of nodes). A higher quorum means a more consistent result, which may slow down things or reduce availability.

3. Tunable Consistency

• Databases like Cassandra provide the option to set consistency levels for each write, read, or delete row-by-row method (i.e., ‘one’, ‘quorum’, ‘all’). 
• In each case, the developer has options that allow for optimization of the developer’s specific availability or consistency needs. 
• The trade-off is that tuning to higher levels of consistency will equate to higher latency or lower availability.

4. Graceful Degradation

• A system that fails will provide partial functionality instead of failing in its entirety. This is the graceful degradation method. 
• This improves the user experience, especially during a network partition or node failure, by keeping the system usable. 
• Trade-off: Social media could show slightly stale timelines instead of loading no data.

5. Consensus Algorithms (Paxos, Raft)

• Consensus algorithms refer to the prescribed norms to come to an agreement among nodes on a distributed system, in the presence of failures of some nodes.
• This type of algorithm has strong consistency in the system when a partition or node failure occurs.
• Trade-off: The trade-off is that the use of consensus has high latency and reduced availability under load and network constraints.

6. Eventual Consistency with Conflict Resolution

• A model that has temporary inconsistencies and conflicts between states, which will eventually resolve themselves. 
• This provides high availability to the users, and in the long run, all the nodes will be converged to a consistent state. 
• Trade-off: DynamoDB implements a last-write-wins conflict resolution, where vector clocks can often be used to resolve conflicts between nodes.

These are some patterns in theory that can be practiced to decide the trade-offs to go with. To see how these decisions have been made in the real world, let us see some of the real systems where these patterns are applied in practice.

Case Studies & Examples of CAP Theorem

Next, we will examine how large distributed systems utilize these patterns in practice and what trade-offs they make to achieve their performance and reliability objectives. CAP theorem in distributed systems is the foundation and at the core of their design.

AP vs CP vs CA Databases

The table below classifies popular distributed databases based on the CAP properties they prioritize. Use this as a quick reference when designing systems or preparing for system design interviews:

Beyond CAP Theorem – PACELC Theorem

The CAP theorem only focuses on the trade-offs during network failure, but distributed systems must also make trade-offs when the system is working absolutely fine. This is where the PACELC theorem comes into play. This theorem was proposed by computer scientist Daniel Abadi and provides a more comprehensive understanding.

PACELC stands for:

• P: Partition
• A: Availability
• C: Consistency
• E: Else (when there’s no partition)
• L: Latency
• C: Consistency

PACELC states that if a partition occurs (P), you must choose between Availability (A) and Consistency (C). Else (E), when the system is running normally, you must choose between Latency (L) and Consistency (C).
This is how the PACELC theorem takes care of both situations, when there is a network partition and also when the system runs smoothly. 

Why PACELC matters?

PACELC shows that design decisions are not only related to handling failures but also to how your system will behave under situations of daily life, so this lends to a more holistic way for architects to think about the trade-offs between user experience (latency) and data correctness (consistency), once one has a stable network.

CAP Theorem in System Design Interview

CAP theorem in distributed systems will be discussed a lot in system design interviews as a separate non-functional requirement. It helps the interviewer assess your trade-off understanding in distributed systems. The interviewer would want to see you not just code, but also balance consistency, availability, and partition tolerance according to the goals of the system. A banking application is an extreme case where correctness and consistency are the entire goal, so one would expect a CP approach (not AP). On the other hand, a social media feed emphasizes availability as the priority, so you would have an AP approach (not CP).

When discussing CAP in an interview, you can explain it in the following manner.

• First, examine the system’s requirements to decide whether consistency or availability is more important.
• Next, discuss the trade-offs, noting that no system can achieve all three during network partitions. 
• You can illustrate this with examples, like Twitter as an AP system or Amazon’s shopping cart leans towards CP for correctness, but the overall system mixes CP and AP approaches. If time allows, mention PACELC to show your understanding of latency-consistency trade-offs under normal operation. 
• Finally, clearly explain and justify why one choice is favored based on the system’s specific requirements.

Conclusion

Understanding the CAP theorem in distributed systems is essential for engineers to build reliable, scalable, and fault-tolerant applications. Understanding the requirements of distributed systems and the results of trade-offs supports engineers in building robust systems while prioritizing consistency or availability. There are many different examples of aligned trade-offs in systems such as Cassandra, banking systems, and social media apps, and their effect on performance and user experience. The understanding of the CAP theorem in distributed systems will also help engineers ace their System Design interviews.

CAP Theorem – FAQs