CAP theorem - System Design Guide

Overview

The CAP theorem states that when a network partition happens, a distributed data system must choose between consistency (every read sees the latest write) and availability (every request to a working node gets a non-error response).

Partitions are not optional in real networks, so the practical choice is CP or AP during a partition. The PACELC extension adds that even without a partition, systems trade latency against consistency.

Two bank branches with a broken phone line

Two branches share account balances by phone. The line goes down. Either they stop accepting withdrawals until the line is back (consistent, unavailable), or they keep serving customers and reconcile later, risking an overdraft (available, inconsistent).

Why it matters

Choosing a database for data that spans multiple nodes or regions.
Deciding what the product should do when replicas cannot communicate.
Explaining why a system shows stale data or rejects writes during failures.

Where it shows up in interviews

Choosing consistency per feature

Recognize it when: what happens during a network partition?

Design a shopping cart
Design a banking system
Design a distributed key-value store

Multi-region design

Recognize it when: regions can lose connectivity.

Design a global social network
Design global inventory

Where it is used in real software

Cassandra and DynamoDB (AP-leaning)

Stay available during partitions with tunable consistency and later reconciliation.

etcd, ZooKeeper, Spanner (CP)

Reject writes on the minority side of a partition to preserve consistency.

PACELC

Daniel Abadi's extension: even without partitions, systems trade latency against consistency.

Key terms

Consistency (C): Linearizability: every read returns the most recent write or an error.
Availability (A): Every request to a non-failed node receives a non-error response.
Partition tolerance (P): The system continues operating despite lost or delayed messages between nodes.
PACELC: If Partition then Availability vs Consistency, Else Latency vs Consistency.

Reasoning through a partition

1
Normal operation
A write to node 1 is replicated to node 2 before or shortly after acknowledgement.
2
The network splits
Node 1 and node 2 can no longer exchange messages, but both still receive client requests.
3
A write arrives at node 1
Node 2 cannot learn about it until the partition heals.
4
A read arrives at node 2
A CP system rejects or blocks the read because it cannot confirm freshness. An AP system returns the value it has, which may be stale.
5
The partition heals
AP systems reconcile conflicting writes (last-write-wins, vector clocks, CRDTs). CP systems resume full operation.

Common systems and their default choice

Behavior during a network partition

System	Choice	Partition behavior
ZooKeeper, etcd	CP	Minority side rejects writes; majority keeps quorum
HBase, MongoDB (majority writes)	CP	Writes require the primary and a majority
Cassandra, DynamoDB (default)	AP	Accepts reads/writes; resolves conflicts later
DNS	AP	Serves cached, possibly stale records
Single-node PostgreSQL	CA*	No partition possible, but no tolerance to node loss

NOWSystem: ZooKeeper, etcd | Choice: CP | Partition behavior: Minority side rejects writes; majority keeps quorum

Many databases are tunable. Cassandra with QUORUM reads and writes (R + W > N) behaves more consistently at the cost of availability and latency.

Implementation

1// N replicas, W replicas must ack a write, R replicas are read.2// If R + W > N, every read set overlaps the latest write set.3function isStronglyConsistent(n: number, w: number, r: number): boolean {4  return r + w > n;5}6 7isStronglyConsistent(3, 2, 2); // true:  QUORUM / QUORUM8isStronglyConsistent(3, 1, 1); // false: fast, but reads may be stale9isStronglyConsistent(3, 3, 1); // true:  fast reads, writes fail if any replica is down

Complexity and performance

Quorum writeslowest of W

Latency is set by the W-th fastest replica.

Majorityfloor(N/2) + 1

3 nodes tolerate 1 failure; 5 nodes tolerate 2.

Trade-offs

Choose CP for

Payments, inventory decrements, unique usernames, leader election, and configuration: correctness matters more than answering during a partition.

Choose AP for

Shopping carts, social feeds, likes, view counters, and product catalogs: showing slightly stale data is better than showing an error.

Per-operation choices

One product can mix both: AP for browsing the catalog, CP for checkout.

Variants and related techniques

Eventual consistency

If writes stop, all replicas converge to the same value eventually.

Read-your-writes

A user always sees their own updates, often by routing their reads to the primary briefly.

Causal consistency

Operations that depend on each other are seen in order by everyone.

Common mistakes

Claiming a distributed system is CA.
Fix: Partitions happen; the real question is what the system does during one.
Treating CAP availability as uptime percentage.
Fix: CAP availability is a strict per-request property, not a 99.9% SLA.
Picking one model for the whole product.
Fix: Decide per data type and per operation.

Interview questions

Is your design CP or AP?

State it per component: for example, the order ledger is CP using a primary database with synchronous replication, while the product catalog is AP with cached, eventually consistent replicas.

What does PACELC add?

Even without partitions, stronger consistency needs more coordination and therefore higher latency. It explains why systems like DynamoDB offer both eventually and strongly consistent reads.

Practice problems

Problem	Difficulty	What it trains
Design a global shopping cart	Medium	AP with conflict resolution.
Design a ticket booking system	Hard	CP for seat allocation.