Question

What does the CAP theorem state about distributed data stores?

Answer 1

The Short Answer (The TL;DR)

The CAP theorem states that in a distributed data store, it is impossible to simultaneously provide more than two out of the following three guarantees:

1. Consistency
2. Availability
3. Partition Tolerance

Because network failures are a given in any distributed system, Partition Tolerance (P) is a necessity. Therefore, the theorem effectively states that in the event of a network partition, a distributed system must make a trade-off between Consistency (C) and Availability (A).

---

Defining the Three Guarantees

To fully understand the theorem, let's break down what each guarantee means in the context of a distributed system (like a database cluster with multiple nodes).

1. Consistency (C)

This guarantee means that every read operation receives the most recently written data or an error. When data is written to one node, all subsequent reads from any node in the cluster will return that new value. All clients see the same view of the data at the same time.

• Example: A banking system. If you deposit money into your account, you expect every ATM or mobile app to immediately reflect that new balance. A system that shows your old balance after a successful deposit is not consistent.

2. Availability (A)

This guarantee means that every request receives a (non-error) response, without the guarantee that it contains the most recent write. The system is always operational and responsive. No request is ever dropped or ignored.

• Example: An e-commerce shopping cart. If you add an item to your cart, the system should always respond successfully ("Item Added!"), even if a background service that syncs the cart across devices is temporarily down. It's better to serve a slightly stale view than to return an error.

3. Partition Tolerance (P)

This guarantee means that the system continues to operate even if there is a network partition—a communication break or delay between nodes. In a distributed system, nodes communicate over a network, and networks are unreliable. Messages can be lost or delayed. A "partition" is when the cluster splits into two or more groups of nodes that cannot communicate with each other.

• Why it's essential: For any system that is truly "distributed" (i.e., running on more than one machine), you must assume network partitions will happen. You cannot choose to forfeit partition tolerance; you must design for it. This is why the CAP theorem's real-world choice is between C and A.

---

The Core Trade-off: C vs. A

The CAP theorem's critical insight comes into play when a network partition occurs.

Imagine a simple two-node database cluster, Node 1 and Node 2. A network failure happens, and they can no longer communicate. A user is connected to Node 1 and updates a value (e.g., x = 10).

Now, another user connects to Node 2 and tries to read the value of x. The system is now faced with a choice:

1. Choose Consistency over Availability (A CP System)
   To guarantee consistency, Node 2 must provide the absolute latest data. Since it cannot communicate with Node 1 to find out about the new write (x = 10), it must refuse to answer the read request.
   It will return an error or time out, thus making itself unavailable.
   * Result: The system is consistent but not fully available.

2. Choose Availability over Consistency (An AP System)
   To guarantee availability, Node 2 must respond to the read request. Since it can't get the latest data from Node 1, it will respond with the last version of the data it has (e.g., the old value, x = 5).
   This data is "stale," so the system is no longer consistent across all nodes.
   * Result: The system is available but not consistent. When the partition heals, the system will need a strategy to reconcile the conflicting data.

---

Classifying Distributed Systems using CAP

This trade-off forces architects of distributed systems to make a fundamental design choice.

CP (Consistent and Partition-Tolerant)

These systems sacrifice availability during a partition to ensure that data is never incorrect or stale.

• Use Cases: Financial systems, banking, e-commerce backends (e.g., order processing), or any application where data correctness is paramount.
• Example Systems: MongoDB, Redis, HBase, Zookeeper.

AP (Available and Partition-Tolerant)

These systems sacrifice consistency during a partition to ensure that the system always remains online and responsive. They often achieve "eventual consistency," where data is synchronized and reconciled after the network partition is resolved.

• Use Cases: Social media feeds, content delivery networks (CDNs), e-commerce shopping carts (where being able to add an item is more important than having a 100% accurate real-time stock count), and systems where uptime is the top priority.
• Example Systems: Amazon DynamoDB, Apache Cassandra, CouchDB, Riak.

What about CA (Consistent and Available)?

A CA system is one that is both consistent and available but cannot be partition-tolerant. This model only works for systems that run on a single node. Traditional relational databases like PostgreSQL or MySQL, when run on a single server, are CA systems. They are consistent and available, but since there is no network between distributed nodes, there is nothing to "partition."

In the context of distributed systems, CA is not a practical choice, as you cannot avoid the risk of network partitions.