CAP Theorem¶

Prerequisites: Replication basics, Network fundamentals

← Distributed Systems Overview | Next: Consistency Models →

Why This Exists¶

In 2000, Eric Brewer observed that distributed systems face an unavoidable tension. You cannot simultaneously guarantee all three of:

• Consistency — a single-copy / linearizable view: every operation appears to occur on one up-to-date copy of the data, respecting real-time ordering. (This is a much stronger guarantee than "eventually correct" — see Consistency Models for the weaker variants: causal, read-your-writes, sequential.)
• Availability — every request sent to a non-failing node eventually receives a response, even though that response may not reflect the latest write
• Partition Tolerance — the system keeps operating even when network messages are lost/delayed between nodes

The CAP theorem formalizes this: in the presence of a network partition, you must choose between consistency and availability.

Abstraction Levels¶

The Unavoidable Choice¶

graph TD
    P["Network Partition\n(cable pulled)"] --> Q{What does Node A do?}
    Q -->|Accept write| A["Available ✓\nConsistent ✗\n(nodes diverge)"]
    Q -->|Reject write| C["Consistent ✓\nAvailable ✗\n(returns error)"]
    style P fill:#b71c1c,color:#fff
    style A fill:#f57f17,color:#fff
    style C fill:#1565c0,color:#fff

CAP Categories¶

Typical interview shorthand — not a permanent product identity. The same database can look CP-like or AP-like depending on topology and consistency settings.

CP/AP here describes the behavior of a specific operation under a specific configuration during a partition — not a database's permanent identity. Cassandra, DynamoDB, and MongoDB are tunable per the table in How Real Databases Behave. etcd/ZooKeeper writes are not optional CP knobs.

How Real Databases Behave¶

"CP" and "AP" are configuration defaults, not fixed identities — most of these systems let you dial the trade-off per-query. What matters in an interview is knowing the default, why it was chosen, and — critically — that what actually determines partition behavior is topology, quorum/fencing policy, and which reads/writes are allowed during a partition, not replication mode alone. Sync vs. async replication changes acknowledgement durability and latency; it doesn't by itself decide what happens when nodes can't reach each other.

Architecture Diagram¶

sequenceDiagram
    participant Client
    participant NodeA
    participant NodeB
    Note over NodeA,NodeB: Normal operation — replication working
    Client->>NodeA: Write x=5
    NodeA->>NodeB: Replicate x=5
    NodeB-->>NodeA: ACK
    NodeA-->>Client: OK
    Note over NodeA,NodeB: ⚠️ Network Partition — replication broken
    Client->>NodeA: Write x=10
    Note over NodeA: CP system: reject to stay consistent
    NodeA-->>Client: Error (unavailable)
    Note over NodeA: AP system: accept, diverge from NodeB
    NodeA-->>Client: OK (stale data risk)

How It Works Internally¶

What is a Partition?¶

A network partition is when messages between nodes are lost or significantly delayed — not when a node crashes. Partitions can be:

• A switch failure isolating one rack
• High packet loss on an inter-datacenter link
• A firewall rule change
• Network congestion dropping packets
• Elevated latency that crosses a timeout threshold — nodes are technically reachable, but slow enough that the system must treat them as partitioned anyway (a "gray failure," often harder to detect than a clean disconnect)

The dangerous case isn't the partition itself — it's what happens if both sides keep accepting writes without realizing the other side is still alive: split-brain, where two nodes each believe they're the leader, both accept writes, and the histories diverge in a way that isn't a simple merge. This is precisely what quorum-based consensus (Raft, ZAB) is designed to prevent — see Consensus & Raft for the mechanism.

Why Can't We Have All Three?¶

Proof sketch: 1. Two nodes, A and B. A receives write W1. 2. Before A replicates to B, a partition occurs. 3. Client queries B for the same key. 4. If we want Consistency: B must return W1 → B must wait → not Available 5. If we want Availability: B responds immediately → returns stale data → not Consistent

PACELC — The More Practical Model¶

CAP only covers the partition case. PACELC extends it:

If Partition (P): choose Availability (A) or Consistency (C). Else (E) — no partition: choose Latency (L) or Consistency (C).

Typical interview shorthand / common configuration — not a fixed product identity:

Read & Write Trade-offs¶

The PACELC "EL" axis isn't abstract — it shows up directly as a knob on every read and write:

Stronger consistency  ──────────────────────────────  Higher availability
  Slower writes                                          Faster writes
  Higher read latency                                     Lower read latency
  (wait for quorum/replica ack                          (ack immediately, replicate
   before returning)                                      in the background)

This is why "consistency level" is usually a per-request parameter (Cassandra's ONE/QUORUM/ALL, DynamoDB's ConsistentRead) rather than a database-wide setting — a single system routinely runs both ends of this trade-off simultaneously: strong reads for a payment total, eventual reads for a "people also viewed" widget, against the same cluster.

Realistic Example¶

Designing a bank balance system:

Requirements: - Must always show correct balance (never show more money than exists) - Read/write the same account from multiple DCs

Choice: CP — we reject writes during partition rather than risk showing incorrect balances.

Implementation — and why quorum reads/writes alone are not enough: Quorum (write to 2/3, read from 2/3, overlapping majorities) guarantees a read sees the most recent acknowledged write — that's freshness, and it's genuinely useful. It does not guarantee a read-modify-write is atomic. Two overlapping quorum reads can both see balance=100, both compute "100 − 30 = 70" independently, and both quorum-write 70 — a classic lost update, even though every individual read and write was itself quorum-consistent (this is exactly the gap between quorum reads/writes, which are not linearizable by themselves, and true linearizability). A bank balance mutation needs one of:

• Compare-and-swap / conditional writes (Cassandra's IF balance = :expected, a lightweight transaction) — the write only applies if the value hasn't changed since it was read, so a concurrent lost update fails the CAS and must retry instead of silently overwriting.
• Consensus-backed writes (Raft/Paxos-replicated state machine — etcd, Spanner-style) — the whole read-modify-write goes through a single linearizable log, so concurrent mutations serialize correctly by construction.
• A ledger design instead of a mutable balance — append immutable debit/credit entries (each one an independent, idempotent write) and compute balance as a sum/fold over entries, rather than mutating a single balance field at all. This sidesteps the lost-update problem entirely, because there's no shared mutable value for two writers to race on.

Plain quorum reads/writes are the right foundation for freshness and durability during a partition, but "CP + quorum" is not by itself a safe answer for a concurrent balance mutation — say so explicitly in an interview, because reaching for quorum alone here is exactly the mistake this example is warning against.

Designing a shopping cart:

Requirements: - Must always be accessible (losing a cart abandonment is expensive) - Slight staleness acceptable (cart merge on reconnection is fine)

Choice: AP — accept writes during partition, merge conflicts on reconnection (Last Write Wins or semantic merge).

Designing a chat/messaging system:

Requirements: - Users must always be able to send a message, even if a data-center link is degraded - Messages must eventually be delivered and ordered correctly per-conversation, but a few seconds of delay is invisible to the user

Choice: AP for the send path — accept the message locally, replicate and reorder asynchronously (this is exactly the trade-off WhatsApp-style messaging systems make: never block "send" on cross-region replication). Note the nuance: within a single conversation, causal/session consistency still matters — a reply shouldn't appear before the message it's replying to — so "AP" here means available-with-ordering-guarantees-per-conversation, not "anything goes."

Failure Modes¶

CP system during partition¶

• Symptom: Clients receive errors / timeouts on writes
• Impact: Revenue impact if the partitioned component handles customer-facing traffic
• Detection: Error rate spike, timeout alerts
• Mitigation: Multi-AZ deployment to reduce partition probability; circuit breakers to fail fast

AP system during partition¶

• Symptom: Stale reads, conflicting writes, data anomalies post-partition
• Impact: Inventory overselling, duplicate orders, lost updates
• Detection: Read-your-writes violations, conflict resolution logs
• Mitigation: Design for conflict resolution upfront; use CRDTs where possible

Production Debugging¶

When investigating consistency issues in a distributed system:

Symptom: User sees stale data after a write

1. Check replication lag
   → replica_lag metric, binlog position
2. Check if partition occurred
   → network error rate between nodes, packet loss
3. Check read routing
   → is the read going to a replica vs primary?
4. Check consistency level
   → Cassandra: QUORUM vs ONE, DynamoDB: strong vs eventual
5. Check for split-brain
   → are two nodes both accepting writes thinking they're primary?

Key metrics to monitor: - Replication lag (p50, p99) - Network packet loss between nodes - Write acknowledgment rate - Read-your-writes violation rate (application-level)

Scaling Limits¶

• CP systems sacrifice availability during partitions → harder to scale writes globally
• AP systems scale writes globally easily but require conflict resolution strategy
• Spanner achieves global CP using TrueTime (atomic clocks + GPS) — extreme engineering cost

Trade-offs¶

Interview Questions¶

Reasoning Exercises¶

1. E-commerce inventory: 100 warehouses, each can decrement stock. Items should never go negative. Is this CP or AP? What's the conflict resolution strategy?

2. Social media likes: Instagram shows like counts. Exact count matters less than availability. CP or AP? What consistency model do you use?

3. Distributed config service (like etcd): Used by hundreds of microservices to read feature flags. CP or AP? What happens if the config cluster has a partition?

4. DNS: You query a DNS server for an IP. The answer might be cached and 30 minutes stale. CP or AP? Why is this the right choice?

Key Takeaways¶

Previous: Distributed Systems Overview | Next: Consistency Models