CAP Theorem

TL;DR

• CAP Theorem says a distributed system can guarantee at most two of three properties simultaneously: Consistency, Availability, and Partition Tolerance — never all three.
• In practice, partition tolerance is non-negotiable: network partitions happen in every production distributed system. The real choice collapses to C (return an error rather than serve stale data) or A (return whatever data you have, even if stale).
• CP systems (HBase, ZooKeeper, etcd, Spanner) sacrifice availability during a partition — they return errors rather than serve potentially inconsistent data.
• AP systems (Cassandra, DynamoDB, CouchDB, Riak) sacrifice consistency during a partition — they return possibly stale data rather than fail requests.
• Consistency in CAP means linearizability — every read returns the most recent write or an error — completely unrelated to ACID consistency and far stronger than eventual consistency. The CP vs AP decision is the real engineering choice in every distributed system.

The Problem It Solves

It is 11:42 PM on Cyber Monday. Your e-commerce platform runs in two data centers: US-East and EU-West. A BGP routing issue between AWS and a European telecom corrupts the inter-datacenter link.

For 90 seconds, neither data center can reach the other. Both regions keep running independently.

A user in Frankfurt clicks "Place Order." EU-West has their cart data. But their loyalty reward balance — updated by a purchase 30 seconds earlier in the US — hasn't replicated yet.

The EU-West node holds an outdated balance.

Your system must now make a choice it may never have consciously designed for:

Option A: Refuse to process the checkout until connectivity restores. The user sees an error. You lose the sale. Your data is correct.

Option B: Process the checkout using the stale balance. The loyalty discount is wrong. You make the sale. Your data is wrong.

There is no third option. Every distributed system picks one of these behaviors — whether the engineering team planned for it or not. The mistake I see most often is teams that discover their default behavior at 3 AM during an incident, not at the design whiteboard.

For every data store you sketch, the first question to answer is: CP or AP? This is the core of CAP Theorem — not an academic abstraction, but a specific operational decision that every distributed database makes, silently, the first time a network fails.

What Is It?

CAP Theorem, proposed by Eric Brewer in 2000 and formally proved by Gilbert and Lynch in 2002, states that any distributed data store can provide at most two of three guarantees simultaneously:

• Consistency (C): Every read returns the most recent write, or returns an error. No node ever serves stale data. This means linearizability — the strongest possible consistency model. This is entirely different from the "C" in ACID (which refers to constraint enforcement) and has nothing to do with eventual consistency.

• Availability (A): Every request to a non-failed node gets a non-error response. Not necessarily the most recent data — just a response, always. Note: CAP Availability is an absolute guarantee, not an SLA percentage. A system is either available in the CAP sense (responds to all requests) or it is not.

• Partition Tolerance (P): The system continues operating even when network messages between nodes are lost, delayed, or reordered. The system does not require a perfectly reliable network to function.

Analogy: Think of two bank branches in different cities that share a central ledger via overnight courier. If the courier van breaks down (partition), each branch faces the same choice:

• Consistency: Neither branch processes any transactions until the courier van is repaired and the ledger is re-synced. Customers are turned away. The ledger is never wrong.
• Availability: Each branch keeps processing transactions from their last-known ledger copy. When the courier van is fixed, the branches reconcile. During the outage, some customers get incorrect balances.

The bank's choice depends on which outcome is worse: turning customers away, or occasionally showing wrong balances. Neither is zero-cost. My recommendation: before selecting any data store, explicitly state which failure mode your system can tolerate — and document that decision.

How It Works

The Proof: Why You Can't Have All Three

The proof is short and worth understanding once — after it, CAP becomes intuitive rather than received wisdom. I find most engineers understand CAP conceptually but can't explain why you can't have all three — this proof closes that gap in about 30 seconds.

Imagine the simplest possible distributed system: two nodes, N1 and N2, both storing a variable x. Initially, x = 0 on both nodes.

Step 1: A client writes x = 1 to N1.
        N1 persists x = 1 locally.
        N1 tries to send the update to N2.
        But the network is partitioned — N2 never receives the write.

Step 2: Another client reads x from N2.

Now you must pick:
  If you want AVAILABILITY:
    N2 must respond. It returns x = 0.
    That is stale. Inconsistent. Wrong.

  If you want CONSISTENCY:
    N2 must return an error (or block until partition heals).
    It cannot return x = 1 — it hasn't received that write.
    So it cannot serve a response without violating consistency.

You cannot return x = 1 (correct) AND serve a response (available)
without N2 somehow knowing about the write — which requires
a working network. The network is broken. That's the partition.

Partition Tolerance means the system works despite this.
Given P is required, C and A cannot co-exist.

That is the complete proof. The partition is the forcing function. P is not optional in any real system running across multiple nodes, so the choice reduces to: sacrifice C or sacrifice A during a partition.

// Simplified: the binary branch every distributed system implements
async function read(key: string): Promise<Value | PartitionError> {
  const localValue = await localDb.get(key);
  const partitionDetected = !(await canReachQuorum());

  if (partitionDetected) {
    // CP BRANCH: sacrifice availability to guarantee correctness
    if (systemMode === "CP") {
      throw new PartitionError(
        "Quorum unreachable — cannot confirm data freshness"
      );
    }

    // AP BRANCH: sacrifice consistency to guarantee a response
    if (systemMode === "AP") {
      return {
        value: localValue,
        stale: true,
        lagMs: estimatedReplicationLag(),
      };
    }
  }

  // Normal path: no partition — quorum read guarantees strong consistency
  return await quorumRead(key);
}

The TypeScript above is a mental model — but the binary C-or-A branch it exposes is the actual decision your distributed system makes on every request during a partition. Name that choice explicitly in your design.

Key Components

Types / Variations

The real-world expression of CAP is two families of distributed systems, each optimized for their side of the partition decision.

CP Systems: Refuse Rather Than Lie

A CP system's contract: "I would rather turn you away than give you wrong information."

ZooKeeper is the canonical CP system. ZooKeeper is a coordination service used for distributed locking, leader election, and configuration distribution. If ZooKeeper's quorum is disrupted and a minority of nodes cannot confirm the latest state, those nodes stop serving reads entirely — they return ConnectionLossException.

The reasoning: a stale leadership result is worse than no result at all. If two nodes both believe they are the leader because ZooKeeper served a stale election result, both execute critical sections simultaneously — a race condition that causes data corruption. ZooKeeper powers distributed coordination in Kafka, HBase, Hadoop, and every Kubernetes cluster.

When candidates list ZooKeeper in a design, I always follow up: "what happens to your service when ZooKeeper loses quorum?" If they can answer that, they understand CP.

When CP is the right call:

• Distributed locks — a stale lock state means two processes enter a critical section simultaneously
• Payment confirmation — a stale "payment succeeded" that hasn't propagated is a silent double-charge
• Inventory decrements at point-of-sale — a stale "1 item in stock" at true zero inventory oversells
• Auth token revocation — a stale "token valid" for 200ms after revocation is a security vulnerability
• Leader election — split-brain leadership causes duplicate task execution and data corruption

AP Systems: Return and Reconcile

An AP system's contract: "I would rather give you something than make you wait. We will sort out any conflicts later."

Cassandra is the canonical AP system. Cassandra writes to any available node without waiting for quorum confirmation. Reads also return immediately from any available replica.

During a partition, each side accepts writes independently. When the partition heals, Cassandra's anti-entropy repair process reconciles divergent data using Last Write Wins (LWW) timestamp-based conflict resolution.

When AP is the right call:

• User activity feeds and timelines — stale posts are invisible to users; the next refresh catches up
• Recommendation engines — a ~500ms-stale recommendation is indistinguishable from fresh
• View, like, and share counts — approximate counts are acceptable; counters merge cleanly after partition
• Shopping cart contents — slightly stale cart data is annoying but not irreversible
• DNS — responses can be cached (stale) for minutes without meaningful consequences to end users

Pick CP when stale data costs more than downtime. Pick AP when a timeout costs more than stale data. Most production systems use both — the choice is per data type, not per system.

PACELC: The Tradeoff Beyond Partitions

Ok, but here's the thing most people miss. CAP only defines system behavior during a partition — a relatively rare event. But real systems have an equally important tradeoff on the normal, no-partition path: latency vs. consistency for every single request.

PACELC (proposed by Daniel Abadi, 2012) extends CAP:

Partition → choose A (Availability) or C (Consistency)

Else (normal operation) → choose L (Latency) or C (Consistency)

flowchart LR
  subgraph PartitionPath["⚡ During a Partition (P)"]
    P{"Network\nPartition?"}
    AP_side["📬 Availability (A)\nReturn stale data\nSystem stays up"]
    CP_side["🔒 Consistency (C)\nReturn error\nSystem partially down"]
    P -->|"Sacrifice consistency"| AP_side
    P -->|"Sacrifice availability"| CP_side
  end

  subgraph NormalPath["🟢 Normal Operation (EC)"]
    EC{"No Partition\n— Choose trade-off"}
    EL_side["⚡ Latency (L)\nAsync replication\nFast writes · stale reads"]
    EC_side["✅ Consistency (C)\nSync quorum write\nSlow writes · fresh reads"]
    EC -->|"Optimize for speed"| EL_side
    EC -->|"Optimize for correctness"| EC_side
  end

Understanding PACELC helps you answer the follow-up most candidates can't: "What is your system's latency vs. consistency tradeoff on the happy path — when there is no partition?" I've seen this exact question stump senior engineers who had a confident CP vs. AP answer just thirty seconds earlier.

Trade-offs

The fundamental tension here is data correctness vs. service availability — every replica you add to improve availability introduces a new window where that replica's data might diverge from the primary. The right answer is almost always different per data type: AP for feeds and analytics where stale data is invisible, CP for money and locks where stale data has real-world consequences. My recommendation: build a two-column table for your design — data type on the left, CP or AP on the right — and be ready to defend every row.

When to Use It / When to Avoid It

So when does this actually matter? Here's the decision in plain terms.

Choose CP (sacrifice availability during partitions) when:

• Data correctness is more expensive than downtime: financial balances, inventory counts, session tokens, distributed locks
• The downstream action is irreversible: shipping an order, charging a card, sending a legal document, dispatching emergency services
• Regulatory compliance requires accurate data at all times: banking, healthcare (patient records), payment processing
• Your system coordinates distributed behavior: leader election, task scheduling, configuration management

Choose AP (sacrifice consistency during partitions) when:

• Stale data is invisible or inconsequential to end users: social feeds, recommendations, personalization, activity logs
• You need multi-region active-active write throughput: global gaming leaderboards, content delivery, analytics ingestion
• Your data naturally handles eventual consistency: counters that merge, sets that union, strings where last-write-wins is correct
• Your consistency requirement can tolerate a bounded staleness window (e.g., "never more than 5 seconds behind")

If a data type doesn't map cleanly onto either list, default to CP — a wrong AP choice is often irreversible, while a wrong CP choice is merely slower.

Real-World Examples

Here's how the best engineering teams actually apply this. In every case below, the CP vs. AP decision was made deliberately, per data type — not as a blanket system choice.

Amazon DynamoDB — AP with tunable consistency by design

Amazon built Dynamo after a 2004 incident where a shopping cart service became unavailable due to a cascading consistency failure. The original Dynamo paper (DeCandia et al., 2007) explicitly chose AP: "Dynamo targets applications that need to be highly available and whose designers are willing to accept stale data." DynamoDB returns stale data during partitions and offers eventually consistent reads (fastest, cheapest) and strongly consistent reads (slower, 2× the cost).

At peak, DynamoDB handles over 89.2 million requests per second globally. Amazon uses DynamoDB for shopping carts, user sessions, and recommendation data — but uses Aurora or custom transactional stores (CP semantics) for financial transaction finality. The lesson: Amazon consciously operates a mixed CAP architecture — AP for volume, CP for money.

Google Spanner — CP at planetary scale

Google Spanner, launched in 2012, achieves external consistency — effectively global linearizability across distributed transactions — across data centers worldwide. It uses TrueTime — GPS-disciplined atomic clocks in every Google data center — to bound clock uncertainty to ±4ms. Every write waits for TrueTime's uncertainty window to close before committing, guaranteeing that any subsequent read from any datacenter on Earth sees the write.

The cost: each write adds a mandatory ~7ms of latency — the TrueTime uncertainty window. Spanner sacrifices those 7ms to guarantee that a read anywhere in the world, at any time after a write confirmation, will see the write. Google uses Spanner for AdWords billing and Google Fi subscriptions — billions of dollars in transactions per day held at global CP guarantees with 99.999% availability.

What I find remarkable about Spanner is that it doesn't escape CAP — it's still CP. It just makes the availability sacrifice so small that the cost of correctness becomes nearly imperceptible.

Netflix on Cassandra — AP with intentional staleness bounds

Netflix migrated from Oracle to Cassandra for user activity data in 2011. At peak, Netflix writes over 1 million events per second to Cassandra. They explicitly chose AP: "We accept stale data in the recommendation engine to never see errors. A user seeing a recommendation 500ms behind reality is invisible. A user seeing a 503 error in the recommendation engine is not."

Netflix tunes Cassandra's consistency levels per query type: QUORUM for user preferences (few writes, correctness matters) and ONE for activity events (high volume, staleness acceptable). The Cassandra cluster spans 3+ AWS regions active-active — a topology that would be physically impossible with a CP system, where quorum across 3 continents would add ~200ms of write latency per event. The pattern across Amazon, Google, and Netflix is the same: CP for money and coordination, AP for everything else at scale.

How This Shows Up in Interviews

The most common interview error on this topic is confusing CAP Consistency (linearizability) with ACID Consistency (constraint enforcement) — they are completely unrelated. Get that distinction locked down before anything else.

Depth expected at senior/staff level:

• Know the difference between CAP Consistency (linearizability) and ACID Consistency (constraint enforcement) — they are unrelated; confusing them is the most common interview error on this topic
• Identify real partitions that happen in production: BGP flaps, AZ isolation, hot-spot congestion dropping packets, kernel networking bugs
• Choose CP vs AP per data type, not per system — explain which of your design's data is CP and which is AP
• Know PACELC as the extension of CAP — the consistency-latency tradeoff matters on the normal path too, not only during partitions
• Explain conflict resolution in AP systems (LWW, vector clocks, CRDTs) and when each breaks down

When an interviewer asks "can we avoid CAP with a better network?" — that's your cue. Address it directly: improving network reliability reduces partition frequency, not partition possibility.

Common follow-up questions and strong answers:

Test Your Understanding

Quick Recap

1. CAP Theorem states a distributed system can guarantee at most two of: Consistency (linearizability), Availability (always respond), and Partition Tolerance (survive network failures) — never all three simultaneously.
2. Partition Tolerance is non-negotiable in any real distributed system — network failures happen at every scale, in every cloud, on every hardware — the true choice is always CP vs AP.
3. CP systems (ZooKeeper, HBase, etcd, Spanner) sacrifice availability during partitions — they return errors rather than serve data that might be stale, because in their domains (locks, coordination, financial records), wrong data is worse than no data.
4. AP systems (Cassandra, DynamoDB, CouchDB, Riak) sacrifice consistency during partitions — they return their local view of data and converge after the partition heals via LWW or vector clock conflict resolution.
5. CAP Consistency (linearizability) is completely unrelated to ACID Consistency (constraint enforcement) — confusing the two is the most common and most costly interview error on distributed systems topics.
6. PACELC extends CAP: even without a partition, every distributed replication strategy trades latency for consistency on the normal path — synchronous quorum writes are consistent but slow; async replication is fast but stale.
7. The right answer is almost always per-data-type: CP for money, locks, auth tokens, and safety-critical data; AP for feeds, counts, recommendations, and telemetry where bounded staleness is acceptable.

Related Concepts

• Consistency Models — CAP Consistency is one point on a full spectrum. Eventual, monotonic, session, causal, and linearizable consistency are the complete model — reading this article next shows how to select the right model per data type rather than defaulting to the strongest or weakest.
• Replication — The mechanical reality behind CP vs AP choices: how primary-replica setups implement replication lag, semi-sync replication, quorum writes, and WAL-based consistency — the actual system behavior that embodies the CAP tradeoff.
• Databases — SQL vs NoSQL framing maps directly onto CAP choices: most NoSQL databases explicitly chose AP for horizontal scale; SQL databases historically chose either CA (single-node) or CP (distributed, strict quorum). Understanding CAP makes database selection principled.
• Sharding — Sharding distributes writes horizontally, but each shard is itself a distributed system making its own CAP choice. Understanding CAP per-shard is necessary for designing correct sharded architectures where cross-shard transactions need explicit consistency models.
• Microservices — In a microservices architecture, each service's data store makes its own CAP choice independently. Cross-service eventual consistency (saga pattern) emerges from composing AP-style services — CAP understanding is prerequisite to understanding saga correctness and failure compensation.