# CAP Theorem

The CAP Theorem (also known as Brewer's Theorem) states that it is impossible for a distributed data store to simultaneously provide more than two out of the following three guarantees: **Consistency**, **Availability**, and **Partition Tolerance**.

## 1. The Three Pillars

### Consistency (C)
Every read receives the most recent write or an error.
*   **Meaning:** All nodes see the same data at the same time. If you write data to Node A, a read from Node B immediately afterwards returns that new data.

### Availability (A)
Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
*   **Meaning:** The system stays up and responsive, even if some nodes are down. You might get stale data, but you get *some* data.

### Partition Tolerance (P)
The system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes.
*   **Meaning:** The system works even if the network connecting the nodes fails (a "partition").

## 2. The "Pick Two" Reality

In a distributed system (where data is stored on multiple nodes), network partitions are inevitable. You cannot guarantee the network will never fail. Therefore, **Partition Tolerance (P) is mandatory**.

This leaves you with a binary choice when a partition occurs:

### CP (Consistency + Partition Tolerance)
*   **Behavior:** If the network breaks, the system stops accepting writes (or reads) to ensure data doesn't diverge. It sacrifices Availability to ensure Consistency.
*   **Use Case:** Banking systems, inventory management (don't sell the same item twice).
*   **Examples:** MongoDB, HBase, Redis, HDFS.

### AP (Availability + Partition Tolerance)
*   **Behavior:** If the network breaks, the system keeps accepting writes and reads, even if the nodes cannot talk to each other. Data will diverge (become inconsistent) temporarily. It sacrifices Consistency to ensure Availability.
*   **Use Case:** Social media feeds, shopping carts (better to let a user add an item and fix conflicts later than show an error page).
*   **Examples:** Cassandra, DynamoDB, CouchDB.

### CA (Consistency + Availability)
*   **Behavior:** This is only possible if you assume the network never fails. This essentially describes a **single-node database** (like a standalone MySQL server). It is not applicable to distributed systems.

## 3. Beyond CAP: PACELC Theorem

The CAP theorem only describes what happens *during a partition*. But what about when the system is running normally?

The **PACELC** theorem extends CAP:
> If there is a partition (**P**), how does the system trade off availability and consistency (**A** and **C**)?
> **E**lse (when the system is running normally), how does the system trade off **L**atency and **C**onsistency?

*   **Example:** DynamoDB is an **PA/EL** system. During a partition, it chooses Availability. Else, it chooses Latency (fast reads/writes) over strong Consistency (eventual consistency).

[[programming/distributed-systems]]
[[programming/database-basics]]
[[programming/system-design-interview-basics]]