CAP Theorem & PACELC (Trade-off Framework)

1. What Is It?

The CAP theorem (Brewer's theorem) states that a distributed data store can only guarantee two of three properties simultaneously: Consistency, Availability, and Partition Tolerance. It provides a vocabulary and framework for reasoning about the fundamental tradeoffs in distributed systems.

PACELC extends CAP by adding a fourth dimension — latency — that is always present, even when there is no partition. CAP only applies during failure scenarios; PACELC applies all the time: even in normal operation, there is a latency/consistency tradeoff. PACELC was proposed by Daniel Abadi (2010 blog post, 2012 IEEE Computer paper).

These frameworks aren't just theoretical — every time you choose a database, choose a replication strategy, or design an API's behavior during failures, you're implicitly making CAP and PACELC choices. Understanding them lets you make those choices deliberately.

2. How It Works

The Three CAP Properties

Consistency (C): Every read receives the most recent write, or an error. All nodes in the cluster return the same data at the same time. This is linearizability — if a write succeeds, any subsequent read anywhere in the cluster reflects that write.

⚠️ CAP Consistency ≠ ACID Consistency: These are completely different concepts.

• CAP Consistency = all replicas agree on the current value (linearizability)
• ACID Consistency = a transaction leaves the database in a valid state (integrity rules, constraints, cascades — nothing to do with replicas)

Availability (A): Every request receives a non-error response — the response may not reflect the most recent write. All nodes always respond; none return errors due to unavailability. The system is always up, even if some reads return stale data.

Partition Tolerance (P): The system continues operating correctly even when network messages between nodes are dropped or delayed. In a distributed system, network partitions are not hypothetical — they are a fact of life.

The Practical Implication

In any real distributed system, you cannot give up P — you cannot design away network partitions. Therefore:

CAP reduces to: CP vs AP during a partition

CP (Consistency + Partition Tolerance):
  When a partition occurs, return an error or timeout rather than potentially stale data
  → Availability suffers during partition
  → Correct data guaranteed when the system is available

AP (Availability + Partition Tolerance):
  When a partition occurs, return potentially stale data rather than an error
  → Consistency suffers during partition
  → System always responds, but may return outdated values

"CA" (Consistency + Availability) without partition tolerance:
  → Only possible on a single-node system
  → Not a distributed system by definition

CAP During a Partition: What Actually Happens

-+ResetFullscreen

PACELC: Extending CAP with Latency

CAP only covers behavior during partitions. PACELC covers the always-present tradeoff:

PACELC = "If Partition, choose A vs C. Else, choose L vs C."

PA/EL system: During partition → Availability; During normal → Low Latency
PA/EC system: During partition → Availability; During normal → Consistency
PC/EL system: During partition → Consistency; During normal → Low Latency
PC/EC system: During partition → Consistency; During normal → Consistency

Why EL vs EC exists: To achieve strong consistency in normal operation, writes must be replicated synchronously to multiple nodes before acknowledging. That synchronous round-trip adds latency. To minimize latency, acknowledge the write to one node immediately (eventual consistency later). This tradeoff exists 100% of the time, not just during failures.

Database Classifications

-+ResetFullscreen

Full PACELC Classification Table

Nuances and Criticisms

Brewer's 2012 revision: CAP's binary "choose 2 of 3" is an oversimplification. All three properties are continuous, not binary. The real goal is to maximize the appropriate combination for the use case. During a partition, you don't permanently sacrifice one property — you temporarily degrade it and recover.

Kleppmann's critique: Martin Kleppmann (DDIA author) argues that CP/AP labels are so imprecise they should be abandoned. Example: ZooKeeper is CP by definition, but reads are not linearizable unless you use the sync command. Example: MongoDB is CP, but a replica can serve stale reads if secondary reads are enabled. The "CP" and "AP" labels collapse too much nuance into two letters.

The PACELC improvement: Abadi's key insight: "Ignoring the consistency/latency trade-off of replicated systems is a major oversight [in CAP], as it is present at all times during system operation, whereas CAP is only relevant in the arguably rare case of network partitions."

3. Variants & Comparisons

Consistency Models (Spectrum from Strongest to Weakest)

Distributed systems offer a range of consistency guarantees. Stronger consistency means all nodes agree more tightly on the current data, but costs more latency because nodes must coordinate before responding:

When "Eventual Consistency" Is Fine vs Dangerous

Fine for eventual consistency:

• Shopping cart items (user might add an item twice due to lag — can be deduped)
• Social media likes/views (approximate count is acceptable)
• DNS propagation (everyone eventually sees the same IP)
• Product catalog (a price being stale for 1 second is acceptable)

Dangerous for eventual consistency:

• Bank account balance (two concurrent withdrawals could both see sufficient balance → overdraft)
• Inventory reservation (two customers could both "buy" the last item)
• Distributed counter for rate limiting (counter may be stale → bypass the limit)
• Any operation that requires read-modify-write atomically

4. When to Use It (and When NOT To)

Choosing CP vs AP in Practice

Choose CP (Consistency over Availability) when:

• Financial transactions: A bank transfer must be atomic and consistent. A stale read that shows money that was already spent is unacceptable.
• Inventory with hard limits: Only 1 concert ticket left — two simultaneous purchases must not both succeed.
• Authentication/Authorization: A revoked token that still grants access is a security vulnerability.
• Distributed locks and coordination: etcd, ZooKeeper — used for leader election, distributed locks. Correctness requires consensus; availability loss during partition is acceptable.
• Metadata stores: Kubernetes control plane (etcd) — it's better to be unavailable than to have incorrect cluster state.

Choose AP (Availability over Consistency) when:

• User profiles and preferences: A user's display name being slightly stale is acceptable.
• Social media feeds: A post that doesn't appear immediately for 500ms is fine.
• Analytics and telemetry: Approximate counts are acceptable for dashboards.
• Globally distributed reads: Cassandra, DynamoDB — serve reads from nearest node, accept eventual consistency.
• Shopping carts: Amazon's famous Dynamo paper specifically used shopping carts to illustrate AP design — losing a cart item is a worse user experience than occasionally showing a duplicate item.

The "Default" Choice in Modern Systems

For most web applications, read-your-writes consistency (a middle ground) is the right target:

• The user always sees their own recent actions immediately
• Other users may see slightly stale data for a short window
• This is stronger than eventual consistency but weaker than linearizability

This is achievable with: primary-key reads going to the primary replica, with replica reads enabled for queries that don't need recency.

5. Real-World Usage

Amazon Dynamo (2007 Paper) — AP Design Choice

Amazon's famous "Dynamo: Amazon's Highly Available Key-Value Store" (SOSP 2007) documented the AP design choice for DynamoDB's predecessor. The core business rationale: for Amazon's shopping cart service, an available but possibly stale cart is better than an unavailable cart. A customer who can't add items to their cart during a network partition loses revenue. A customer who sees a slightly stale cart (missing one recently-added item) can easily re-add it. This business reasoning is why DynamoDB defaults to eventual consistency — availability was the higher priority.

Google Spanner — CP with Latency Cost

Google Spanner is designed as a globally-consistent distributed database (CP, PC/EC). The cost is explicit: TrueTime's commit wait adds 1–7ms to every transaction (the price of linearizability). Google's F1 team (AdWords) explicitly accepted this latency cost in exchange for global consistency — a wrong billing transaction is far more costly than an extra few milliseconds on a write.

etcd — CP for Kubernetes Coordination

Kubernetes uses etcd as its backing store for all cluster state (pods, services, deployments, configs). etcd uses Raft consensus: writes require a quorum — a majority of nodes (e.g. 2 of 3) must agree — before acknowledging. During a network partition where a minority of nodes are isolated, those nodes refuse to serve reads or writes — they'd rather be unavailable than serve incorrect cluster state. This is the canonical CP choice: the risk of acting on stale cluster state (scheduling a pod to a node that's already full, or missing that a service was deleted) is worse than temporary unavailability.

6. Interview Cheat Sheet

5 Sentences to Show Deep Understanding

1. "CAP reduces to CP vs AP in practice because no real distributed system can give up partition tolerance — you cannot design away network failures. CP systems sacrifice availability when a partition occurs (they return errors rather than stale data); AP systems sacrifice consistency (they return potentially stale data rather than errors)."

2. "CAP Consistency is linearizability — all nodes return the same data, and reads reflect the most recent write — which is completely different from ACID Consistency, which means a transaction preserves database integrity rules. Conflating them is a common interview mistake."

3. "PACELC extends CAP by observing that the latency/consistency tradeoff is always present, not just during partitions: synchronous replication to achieve strong consistency adds a round-trip latency cost to every write, even when there's no failure. Cassandra is PA/EL — it chooses availability AND low latency; HBase is PC/EC — it chooses consistency in both the partition and the normal-operation dimensions."

4. "The 'right' answer between CP and AP is domain-specific: financial systems and inventory with hard limits need CP (strong consistency); social media feeds, user preferences, and analytics can tolerate AP (eventual consistency). Choosing AP for a payment system or CP for a shopping cart are both wrong tradeoffs."

5. "Eventual consistency doesn't mean 'might be wrong forever' — it means 'given no new writes, all replicas converge to the same value.' The convergence time varies from milliseconds (same datacenter) to seconds (cross-region) — the key question is whether that convergence window creates a window for correctness violations in your specific use case."

Common Follow-Up Questions

Q: What is the difference between eventual consistency and strong consistency in Cassandra? A: Cassandra's consistency level is tunable per-query. QUORUM reads require a majority of replicas to respond with the same data — this gives you strong consistency at the cost of latency. ONE reads require only one replica to respond — fast, but potentially stale. ALL reads require all replicas — maximally consistent but least available (any node failure fails the read). The tradeoff: QUORUM + QUORUM for reads and writes ensures strong consistency while tolerating one replica failure.

Q: Is MongoDB CP or AP? A: MongoDB is CP by default — it uses a single primary that accepts all writes; during a partition, the minority partition becomes unavailable rather than accepting writes with potential inconsistency. However, MongoDB is configurable: enabling secondary reads makes it behave more like an AP system (stale reads, but always available). This is why Kleppmann argues the CP/AP label is too coarse — MongoDB's behavior depends on your read/write concern configuration.

Q: What is split-brain and how do systems prevent it? A: Split-brain occurs when a network partition causes a cluster to form two majorities that both think they're the leader and both accept writes — resulting in divergent data that's hard to reconcile. CP systems prevent it by requiring a quorum (majority of nodes) for any write. If a quorum can't be achieved (e.g., a 3-node cluster where 2 nodes are on each side of the partition — wait, that's 2+1, majority is 2), only the majority side accepts writes. The minority side becomes unavailable rather than risk split-brain.

Q: What is the W+R > N rule in Cassandra? A: In Cassandra, N = replication factor (number of copies). W = number of replicas that must acknowledge a write. R = number of replicas that must respond to a read. When W + R > N, you're guaranteed that reads and writes overlap — at least one replica that acknowledged the write will be in every read quorum. For N=3: W=2, R=2 → 2+2=4 > 3 → strong consistency. W=1, R=1 → 1+1=2 ≤ 3 → eventual consistency (fast but possibly stale).

Connections to Other Building Blocks

• Replication Strategies: The replication strategy (synchronous vs async, single-leader vs leaderless) directly determines where a database sits on the CAP/PACELC spectrum. Single-leader sync replication → CP; leaderless async replication → AP.
• Consensus (Raft/Paxos): Consensus algorithms are how CP systems achieve consistency — they ensure a quorum of nodes agrees before committing a write. etcd, ZooKeeper, and CockroachDB use consensus as their correctness mechanism.
• Wide-Column Store (Cassandra): Cassandra is the canonical AP/PA/EL system. Its tunable consistency levels (ONE, QUORUM, ALL) are a direct expression of the CAP tradeoff.
• NewSQL (Spanner, CockroachDB): These are CP/PC/EC systems — they achieve strong consistency across distributed nodes using consensus, at the cost of write latency.
• Message Queues (Kafka): Kafka's acknowledgment modes map to CAP tradeoffs: acks=0 (fire-and-forget, AP-like), acks=1 (leader acknowledges, eventual), acks=all (all replicas acknowledge, CP-like durability).