CAP Theorem Explained

The CAP theorem is the foundational trade-off in distributed systems. It states that a distributed system can guarantee at most two of three properties: Consistency, Availability, and Partition Tolerance. Understanding this theorem is critical for designing any distributed system.

1. The Three Properties

graph TD
    C["Consistency (C)
Every read returns the most recent write"]
    A["Availability (A)
Every request receives a response"]
    P["Partition Tolerance (P)
System works despite network failures"]

    C --- A
    A --- P
    P --- C

    style C fill:#D97A2B,stroke:#B86418,color:#fff
    style A fill:#D97A2B,stroke:#B86418,color:#fff
    style P fill:#D97A2B,stroke:#B86418,color:#fff

Consistency (C)

Every read receives the most recent write or an error. All nodes see the same data at the same time. There are no stale reads.

Example: You update your profile picture. Every subsequent request returns the new picture : not the old one.

Availability (A)

Every request receives a non-error response (no timeout), but it may not contain the most recent write. The system is always operational and responsive.

Example: You update your profile picture. Even if the new picture hasn't propagated to all servers, the system still serves profile requests : just showing the old picture temporarily.

Partition Tolerance (P)

The system continues to operate despite network partitions (communication breaks between nodes). In a distributed system, network partitions are inevitable : machines crash, cables get cut, switches fail. Partition tolerance is non-negotiable in distributed systems.

2. The Trade-off: You Must Pick Two

graph LR
    subgraph "During Network Partition"
        CP["CP: Consistency + Partition Tolerance
Reject requests, serve stale data"]
        AP["AP: Availability + Partition Tolerance
Serve requests, potentially stale data"]
    end

    style CP fill:#FAF6EE,stroke:#D97A2B
    style AP fill:#FAF6EE,stroke:#D97A2B

Since network partitions are unavoidable, you must choose between consistency and availability during a partition:

CP Systems (Consistency + Partition Tolerance)

During a partition, reject requests rather than serve stale data. The system sacrifices availability to maintain consistency.

• HBase : Strong consistency, but requests fail during partitions.
• MongoDB (with majority write concern) : Guarantees consistency but may reject writes.
• ZooKeeper : Consensus-based, sacrifices availability during leader election.
• Google Spanner : Globally consistent database, uses TrueTime for consistency.

AP Systems (Availability + Partition Tolerance)

During a partition, serve requests with potentially stale data. The system sacrifices consistency to maintain availability.

• Cassandra : Always writable, but eventual consistency.
• DynamoDB : Highly available, but eventual consistency by default.
• CouchDB : Multi-master replication with eventual consistency.
• DNS : Always resolves, but may return stale records.

CA Systems (Consistency + Availability)

No network partitions allowed. This only works in single-node systems or when the network is perfectly reliable : which doesn't exist in distributed systems. Traditional relational databases (PostgreSQL on a single node) are CA.

3. Real-World Decision Framework

graph TD
    Q1{"Is stale data
acceptable?"}
    Q2{"Is downtime
acceptable?"}
    AP["Choose AP
(Cassandra, DynamoDB)"]
    CP["Choose CP
(ZooKeeper, HBase)"]
    CA["Choose CA
(PostgreSQL single node)"]

    Q1 -->|"Yes"| Q2
    Q1 -->|"No"| CP
    Q2 -->|"Yes"| AP
    Q2 -->|"No"| CA

    style Q1 fill:#D97A2B,stroke:#B86418,color:#fff
    style Q2 fill:#D97A2B,stroke:#B86418,color:#fff
    style AP fill:#D4EDDA,stroke:#28A745
    style CP fill:#FFF3CD,stroke:#FFC107
    style CA fill:#F8D7DA,stroke:#DC3545

• Banking system: Choose CP. You cannot show an incorrect balance. Reject the transaction rather than serve stale data.
• Social media feed: Choose AP. Showing a feed that's a few seconds stale is fine. Users care about always being able to see their feed.
• Shopping cart: Choose AP (Amazon Dynamo paper). Better to have an item appear in the cart twice than to lose it entirely.
• DNS resolution: Choose AP. A stale IP address is better than no resolution.
• Leader election: Choose CP. Only one leader must be elected, even if it means temporary unavailability.

4. PACELC: The Extension to CAP

PACELC adds another dimension: if Partition, choose A or C; Else (normal operation), choose Latency or Consistency.

• PA/EL: Cassandra, DynamoDB : prioritize availability during partitions, low latency during normal ops
• PA/EC: MongoDB : prioritize availability during partitions, consistency during normal ops
• PC/EL: PNUTS (Yahoo) : consistency during partitions, low latency during normal ops
• PC/EC: Google Spanner : consistency always, higher latency

5. Common Interview Mistakes

• Thinking you can achieve all three: You cannot. During a partition, you must choose C or A.
• Confusing consistency with consensus: Consistency is about data freshness; consensus is about agreement on a value.
• Ignoring that most systems are AP: In practice, most web applications prioritize availability over strong consistency.
• Not discussing PACELC: The extension shows deeper understanding of the trade-offs beyond just partitions.
• Forgetting about single-node systems: A single PostgreSQL instance is CA : it has no partitions to worry about.

6. Summary Table