Building Blocks10 min read

CAP Theorem

You can't have it all — pick two out of three

scope:Building Blockdifficulty:Intermediate

The Impossible Triangle

Imagine you're running a chain of ice cream shops across the country. You want three things:

Every shop has the exact same menu at all times (Consistency)
Every shop is always open, no matter what (Availability)
Shops keep working even when the phone lines between them go down (Partition Tolerance)

The CAP Theorem says: you can only guarantee two of these three at the same time.

This was proven by Eric Brewer in 2000 and formally proved by Gilbert and Lynch in 2002. It's one of the most important theorems in distributed systems, and it comes up in almost every system design interview.

▸ The three CAP properties

C, A, and P — Explained

Consistency (C) — Every read receives the most recent write. If Alice updates her profile picture on Server 1, and Bob reads from Server 2 one millisecond later, Bob sees the new picture. Everyone sees the same data at the same time.

Availability (A) — Every request receives a response (not an error), even if it might not contain the most recent data. The system is always "open for business." No request goes unanswered.

Partition Tolerance (P) — The system continues to operate even when network communication between servers breaks. Messages between nodes get lost or delayed. In the real world, network partitions always happen — cables get cut, switches fail, data centers lose connectivity.

Since network partitions are unavoidable in distributed systems, you must always choose P. The real choice is between C and A during a partition:

CP system: When a partition occurs, the system sacrifices availability. Some requests will fail or wait, but you'll never get stale data.
AP system: When a partition occurs, the system sacrifices consistency. All requests get a response, but some might return outdated data.

Note: Here's the key insight most people miss: CAP only applies DURING a network partition. When the network is healthy, you CAN have all three. The theorem is about what you sacrifice when things go wrong — and in distributed systems, things ALWAYS eventually go wrong.

▸ Network partition happens

Proof Intuition

Let's make this concrete. You have two database servers, Server A and Server B, that replicate data between each other. A network partition cuts the connection between them.

A client writes x = 5 to Server A. Now a different client reads x from Server B.

Option 1 (Choose Consistency): Server B knows it can't verify it has the latest value (it can't reach Server A). So it refuses the read request — returning an error. The data is consistent, but the system is unavailable for reads on Server B.

Option 2 (Choose Availability): Server B returns whatever value it has for x (maybe the old value, x = 3). The system is available — the client got a response — but the data is inconsistent (Server A says 5, Server B says 3).

There's no magic third option. You must choose.

▸ Choose CP — consistency over availability

The CAP decision tree: the real choice is between CP and AP when a network partition strikes

CP vs AP System Behavior

class CPDatabase:
    """Consistency + Partition Tolerance.
    During a partition, rejects requests rather than serve stale data."""

    def __init__(self):
        self.data = {}
        self.can_reach_leader = True

    def write(self, key, value):
        if not self.can_reach_leader:
            raise Exception("503 Service Unavailable — cannot confirm write")
        self.data[key] = value

    def read(self, key):
        if not self.can_reach_leader:
            raise Exception("503 Service Unavailable — cannot guarantee consistency")
        return self.data.get(key)


class APDatabase:
    """Availability + Partition Tolerance.
    During a partition, serves potentially stale data but never rejects."""

    def __init__(self):
        self.data = {}
        self.can_reach_leader = True

    def write(self, key, value):
        self.data[key] = value  # Write locally, sync later
        if self.can_reach_leader:
            pass  # Replicate to other nodes
        else:
            pass  # Queue for later replication (eventual consistency)

    def read(self, key):
        # Always return something, even if it might be outdated
        return self.data.get(key, None)


# Simulate partition
cp = CPDatabase()
cp.data["balance"] = 100
cp.can_reach_leader = False  # Partition!
try:
    print(cp.read("balance"))  # Raises error — refuses to serve
except Exception as e:
    print(f"CP: {e}")

ap = APDatabase()
ap.data["balance"] = 100
ap.can_reach_leader = False  # Partition!
print(f"AP: balance = {ap.read('balance')}")  # Returns 100 (maybe stale)

Output

CP: 503 Service Unavailable — cannot guarantee consistency
AP: balance = 100

▸ Choose AP — availability over consistency

Real-World Examples

CP Systems (Consistency over Availability):

ZooKeeper — Used for coordination in distributed systems. If it can't guarantee consistent data, it refuses to serve. Better to be unavailable than wrong.
HBase — A consistent column-family store. Writes go to a single leader; if the leader is unreachable, writes fail.
MongoDB (with majority write concern) — Can be configured to prioritize consistency by requiring writes to be acknowledged by a majority of nodes.
Banking systems — Your bank balance must be correct. If the system can't guarantee accuracy, it's better to show "temporarily unavailable" than a wrong balance.

AP Systems (Availability over Consistency):

Cassandra — Always accepts writes, even during partitions. Uses consistent hashing for data distribution. Uses eventual consistency to sync later.
DynamoDB — Amazon's key-value store, one of many NoSQL databases. Designed to always be writable. "Add to cart" should never fail, even if the cart might be briefly inconsistent.
DNS — The internet's phone book. It caches old values and eventually updates. A slightly outdated DNS record is better than no DNS at all.
Social media feeds — If your Instagram feed is 5 seconds behind, nobody notices. But if Instagram is down, everyone notices.

▸ Real-world CP and AP systems

Eventual Consistency

Many AP systems use eventual consistency as a compromise. The idea: after a partition heals, all nodes will eventually converge to the same data. There might be a window of inconsistency, but it's temporary.

How does this work in practice?

Read repair: When a read detects inconsistency between replicas, it triggers a background update to bring them in sync.
Anti-entropy (Merkle trees): Nodes periodically compare their data using hash trees and exchange any differences.
Conflict resolution: When two nodes have conflicting writes, the system resolves them. Last-write-wins (LWW) is the simplest strategy. Vector clocks or CRDTs are more sophisticated approaches.

The key question for eventual consistency: how eventual is eventual? In practice, it's usually milliseconds to seconds. But during severe partitions, it could be minutes or hours.

Beyond CAP: PACELC

CAP only describes behavior during partitions. But what about normal operation? That's where PACELC comes in (pronounced "pass-elk").

PACELC says: If there's a Partition (P), choose between Availability (A) and Consistency (C). Else (E), when the system is running normally, choose between Latency (L) and Consistency (C).

PA/EL — During partition: choose availability. Normally: choose low latency. Example: Cassandra, DynamoDB. These are fast and always available, with eventual consistency.
PC/EC — During partition: choose consistency. Normally: still choose consistency (even at the cost of latency). Example: Traditional RDBMS like PostgreSQL, ZooKeeper.
PA/EC — During partition: choose availability. Normally: choose consistency. Example: MongoDB (default config). This is a common practical trade-off.

PACELC gives you a more complete picture of how a system actually behaves in both good times and bad.

Note: Interview tip: When someone asks about CAP, don't just recite the definition. Explain that the REAL choice is between CP and AP during partitions (since P is mandatory in distributed systems). Then go further and mention PACELC to show you understand the normal-operation trade-offs too. This demonstrates deep understanding.

Key Metrics

CP read (during partition)Refuses stale reads

Error / timeout—

AP read (during partition)Returns potentially stale data

~1-5 ms\(O(1)\)

Eventual consistency windowVaries by system and load

~10-1000 ms—

Strong consistency latencyMust confirm with quorum

+5-50 ms—

Quorum read (N=3, R=2)Wait for 2 of 3 replicas

~5-20 ms—

Quick check

In a distributed system, a network partition occurs. Your system continues to serve all requests but some responses may have stale data. What type of system is this?

Databases: SQL vs NoSQL

Choosing the right home for your data

→

Consistent Hashing

Adding a server shouldn't reshuffle everything

→

Message Queues

Don't do everything right now — put it in line

→

Scalability

From one user to one billion — how systems grow

→