CAP Theorem — Deep Dive

Level: Intermediate
Pre-reading: 01 · Architectural Foundations

The Theorem

In a distributed data store, you can only guarantee two out of three properties simultaneously:

graph TD
    subgraph CAP Triangle
        C[Consistency]
        A[Availability]
        P[Partition Tolerance]
    end
    C --- A
    A --- P
    P --- C

Why You Must Choose P

In any real distributed system, network partitions will happen. Machines fail, switches die, cables get unplugged, data centers lose connectivity. You cannot wish partitions away.

Partition tolerance is not optional. The real choice is: what do you sacrifice when a partition occurs — consistency or availability?

sequenceDiagram
    participant Client
    participant NodeA
    participant NodeB
    Note over NodeA,NodeB: Network partition occurs
    Client->>NodeA: Write X=5
    NodeA->>NodeA: Store X=5 locally
    NodeA--xNodeB: Cannot replicate (partition)
    Client->>NodeB: Read X
    Note over NodeB: What should NodeB return?

During a partition:

• CP system: NodeB returns an error (sacrifices availability to maintain consistency)
• AP system: NodeB returns stale data (sacrifices consistency to remain available)

CP Systems — Consistency over Availability

CP systems prioritize returning correct data. If they cannot guarantee the latest value, they refuse to respond.

When to Choose CP

AP Systems — Availability over Consistency

AP systems always respond, even if the response might be stale. They accept writes during partitions and reconcile later.

When to Choose AP

Conflict Resolution Strategies

When partitions heal, AP systems must reconcile divergent data:

PACELC — A More Complete Model

CAP only describes behavior during partitions. In practice, you also care about behavior during normal operation.

PACELC: If there's a Partition, choose Availability or Consistency; Else, when running normally, choose Latency or Consistency.

graph TD
    A[Network State] --> B{Partition?}
    B -->|Yes| C{Choose A or C}
    B -->|No| D{Choose L or C}
    C -->|A| E[AP: Stay available]
    C -->|C| F[CP: Reject requests]
    D -->|L| G[EL: Fast but eventual]
    D -->|C| H[EC: Slow but strong]

Consistency Levels — Tunable Trade-offs

Many distributed databases let you choose consistency level per operation:

Cassandra Consistency Levels

Read-Your-Writes Consistency

A common requirement: after writing, the same client must see their own write.

sequenceDiagram
    participant Client
    participant WriteNode
    participant ReadNode
    Client->>WriteNode: Write X=5
    WriteNode-->>ReadNode: Async replication
    Client->>ReadNode: Read X
    Note over ReadNode: May return X=old value

Solutions:

• Route reads to the same node that handled the write (sticky sessions)
• Include write timestamp in request; read waits until caught up
• Use quorum reads + writes

Practical CAP Trade-offs

Pattern: Strong Consistency for Writes, Eventual for Reads

Many systems use different consistency for different operations:

Pattern: CP for System of Record, AP for Read Replicas

graph LR
    W[Writes] --> P[(Primary DB - CP)]
    P -->|Async Replication| R1[(Read Replica 1)]
    P -->|Async Replication| R2[(Read Replica 2)]
    R[Reads] --> R1
    R --> R2

CAP Misconceptions

Designing for Partitions