I. Introduction to the CAP Theorem
First, let’s briefly explain what the CAP theorem is:
- C: Consistency
Consistency means that all nodes should return the same data when accessed. It’s important to note that this refers to strong consistency—after data is updated, all nodes must display identical data immediately. This differs from weak consistency or eventual consistency.
- A: Availability
Availability means all nodes remain highly available. High availability here also implies no delays; for example, if node B blocks requests while waiting for data synchronization, it fails to meet the availability requirement.
In other words, any non-failing service must return a valid result within a finite time.
- P: Partition Tolerance
Partition tolerance refers to network partitions. Since networks are unreliable, nodes may lose communication with each other. A system with partition tolerance continues to function normally even when nodes cannot communicate.
In practical terms, partition tolerance imposes a timeout on communication. If the system cannot achieve data consistency within the timeout, a partition is considered to have occurred, and a choice must be made between Consistency (C) and Availability (A) for the current operation.
The CAP theorem states that a distributed data system cannot simultaneously satisfy all three conditions (C, A, and P). Thus, system architects should not waste effort trying to design a “perfect” distributed system that meets all three; instead, they must make trade-offs. Due to the unreliability of networks, most open-source distributed systems prioritize Partition Tolerance (P) and then choose between Consistency (C) and Availability (A).
Common Misconceptions About the CAP Theorem
Many online articles describe the CAP theorem as the “cornerstone of distributed systems,” but it actually applies specifically to distributed data storage systems. For example, if a distributed system’s nodes all read from and write to the same MySQL instance, discussing the CAP theorem is irrelevant. In this case:
- Nodes do not need to communicate for data replication, satisfying Partition Tolerance (P).
- They can respond to requests at any time, satisfying Availability (A).
- Since all access a single database instance, data consistency (C) is inherently guaranteed.
Thus, the CAP theorem is primarily discussed in the context of distributed storage systems with data replication—such as the NoSQL databases we are familiar with.
Most of us do not design new NoSQL databases but use existing open-source systems like HBase, MongoDB, or Cassandra. Therefore, we rarely directly apply the CAP theorem in practice.
Nevertheless, understanding it is still valuable. Below is a brief proof of the CAP theorem.
II. A Simple Proof of the CAP Theorem
Suppose there are two nodes, data1 and data2, initially storing a value number = 1. Later, an update is submitted to data1 to set number = 2. data1 then needs to propagate this update to data2 so both nodes have the new value.
We analyze three scenarios:
- Guaranteeing C and P
To ensure consistency, data1 must replicate data to data2, requiring communication between them. However, due to network unreliability, the system’s partition tolerance means it must tolerate such issues. data2 may not receive the update from data1 promptly. When a request queries number from data2, maintaining consistency forces data2 to block until synchronization completes—violating availability.
Thus, C and P cannot coexist with A.
- Guaranteeing A and P
To ensure availability, data1 and data2 must return results within a finite time. Due to network unreliability, data2 might not receive the update from data1 in time, returning stale data (number = 1) while data1 returns number = 2—violating consistency.
Thus, A and P cannot coexist with C.
- Guaranteeing A and C
Ensuring both availability and consistency is only possible if the network is perfectly reliable, allowing data1 to instantly send updates to data2. However, networks are inherently unreliable (prone to packet loss). To achieve immediate, reliable updates, data1 and data2 would need to be in the same network partition, sacrificing partition tolerance (P). In this case, the system is no longer truly distributed.
The simplest way to understand the CAP theorem is to imagine two nodes separated by a partition. Allowing at least one node to update its state causes inconsistency (losing C). To maintain consistency, making one side of the partition unavailable loses A. Only if nodes can communicate can both C and A be guaranteed—but this loses P.
III. Applications of the CAP Theorem in Systems
IV. Summary
A key point about the CAP theorem: while a system cannot satisfy all three conditions, satisfying two does not mean completely abandoning the third. Trade-offs are relative. For example:
- A CP system cannot guarantee perfect availability but can be designed to maximize availability (approaching 100%).
- An AP system can prioritize weak consistency or eventual consistency to approximate strong consistency.
