CAP theorem · Commitwise

The link between two data centers goes down for four minutes. Both sides are healthy and both keep getting requests. A customer in Frankfurt and a customer in Virginia both try to buy the last concert ticket. The system has exactly two options: let both purchases go through and sort out the double sale later, or refuse one side’s requests until the link is back. There’s no third option where both sides answer correctly and immediately, because neither side can know what the other is doing.

That forced choice is the CAP theorem. It’s one of the most quoted and most misquoted ideas in system design interviews.

New to some of these? Open what you need, or skip ahead.

Basics:What is a network partition?

A network partition is when machines that are all running can’t reach each other: a broken switch, a misconfigured firewall, a cut cable between data centers. Each side still works and still gets requests, but can’t tell whether the other side crashed or is just unreachable.

Basics:What is replication?

Replication means keeping copies of the same data on several machines, so the service survives one of them failing and can answer reads from more places. The Replication and consistency lesson covers how copies are kept in sync.

Part Not started

What CAP actually says

Two friends share a paper calendar for booking a meeting room, each keeping a copy, and they phone each other to sync every booking. One day the phone line is down. Someone asks Ana to book the room for 3 pm. Ana can:

refuse (“I can’t confirm right now, try later”), so the calendars never disagree, or
accept the booking, knowing that Marko might be booking the same slot for someone else at this very moment.

That’s the whole theorem. The three letters:

Consistency: every read sees the latest write, as if there were only one copy.
Availability: every request to a working server gets a (non-error) answer.
Partition tolerance: the system keeps working when the network between servers fails.

Brewer’s conjecture, proved by Gilbert and Lynch (2002): an asynchronous networked system with replicated data cannot simultaneously guarantee linearizability (C), availability of every non-failing node (A) and tolerance of arbitrary message loss between nodes (P). Since partitions happen in any real network, the meaningful reading is: when a partition occurs, each operation either sacrifices linearizability or sacrifices availability on at least one side. CAP says nothing about behavior without partitions, about latency, or about weaker consistency models (causal and session guarantees remain achievable while available), and the C and A are much stricter than the everyday meanings of “consistent” and “up”.

Two behaviors during a partition

Situation: replicas EU and US can't reach each other. A client in the EU writes x = 2 (was 1).
Then a client in the US reads x.

CP behavior (choose consistency):
  EU write   → refused or blocked: can't reach a majority / the leader is on the other side
  US read    → x = 1 is the last confirmed value; or refused if the US side can't confirm it's current
  Result: nobody sees conflicting data; some requests get errors or wait

AP behavior (choose availability):
  EU write   → accepted locally: x = 2
  US read    → answered locally: x = 1 (stale)
  US write   → accepted locally: x = 3 (now a conflict)
  Result: everyone gets answers; the copies disagree until the partition heals and they reconcile

“Pick two of three” is misleading. You can’t choose to give up P: networks fail whether you like it or not. The real choice is what to do when they do: refuse (CP) or answer with possibly stale data (AP).
When the network is fine, a well-built system can be both consistent and available. CAP is about the bad minutes, not every second.
A mobile app offline is a partition too: the app either refuses to act until it’s online (CP) or lets the user act and syncs later (AP).

Predict the output

A CP database runs 5 replicas: 3 in Frankfurt, 2 in Virginia. The transatlantic link fails. What do clients in Virginia get when they try to write?

Partitions are inevitable; CAP = under partition, each operation gives up linearizability or availability (on some side).
CAP’s C is linearizability and its A is “every non-failing node answers”: both stricter than everyday usage. It says nothing about the no-partition case or latency.
Consensus systems are CP: the minority side loses writes and linearizable reads. Replica placement decides who stays up.
Weaker models (causal, session) remain achievable while available.

Check this part

Why is "pick two of C, A and P" misleading?
You don't get to opt out of network failures.
During a partition, what does an AP system do?
It stays available and reconciles later.
In a 5-replica consensus cluster split 3/2, which side keeps accepting writes?
Only a majority can commit.

With data replicated across machines, a network partition forces a choice: refuse some requests until it heals (consistency) or answer everything from local data that may be stale or conflicting (availability). Partitions aren't optional, so 'pick two of three' really means 'pick C or A when the network fails'.

Part Not started

Choosing per feature

“Is our system CP or AP?” is the wrong question. A shop has many kinds of data, and each one has its own answer. Ask for each operation: if two sides disagreed for a few minutes, what would it cost?

Two people get the same username: support nightmare. Consistency.
The last ticket is sold twice: an angry customer and a refund. Consistency (or a deliberate overselling policy).
A like count is off by three for a minute: nobody notices. Availability.
A cart can’t be updated while the network is flaky: lost sales. Availability, and merge later.

Real systems mix both: CP stores (consensus databases, a single leader with synchronous replication) for invariants that can’t be violated (uniqueness, balances, seat inventory, idempotency keys, leader leases), and AP stores or local-first designs for data where convergence is enough (carts, presence, counters, feeds, analytics, offline edits). AP data needs explicit conflict semantics; CP data needs a degraded-mode UX (queue the action, show “try again”, fall back to a read-only view). Many “consistency” requirements can also be met with compensation instead of coordination: accept, then detect and fix (overselling with cancellation, fraud review after authorization).

Data	During a partition	Why
Usernames, emails	CP: refuse sign-up	Duplicates break login and are painful to undo
Payments, balances	CP: refuse or queue	Double spending costs money
Seat / ticket inventory	CP, or AP with an oversell-and-refund policy	A business decision, not a technical one
Shopping cart	AP: accept, merge later	Refusing a cart update loses sales
Likes, view counts	AP	Approximate is fine; use a mergeable counter
Chat messages	AP for sending (queue), ordered per conversation	Users expect to send offline; order matters within a chat
Notes and drafts in an offline app	AP with merge or CRDTs	Users must be able to type without signal

Spot the bugTwo accounts named ana

Tap the line with the bug.

fun signUp(username: String, password: String): User {
    val taken = replica.query("SELECT 1 FROM users WHERE username = ?", username).isNotEmpty()
    if (taken) throw UsernameTaken(username)
    return leader.insert(User(username = username, passwordHash = hash(password)))
}

User signUp(String username, String password) {
    boolean taken = !replica.query("SELECT 1 FROM users WHERE username = ?", username).isEmpty();
    if (taken) throw new UsernameTaken(username);
    return leader.insert(new User(username, hash(password)));
}

async function signUp(username: string, password: string): Promise<User> {
  const rows = await replica.query("SELECT 1 FROM users WHERE username = $1", [username]);
  if (rows.length > 0) throw new UsernameTaken(username);
  return leader.insert({ username, passwordHash: await hash(password) });
}

The uniqueness check reads from a replica, which may not have the other sign-up yet, and even on the leader, check-then-insert is a race: two requests both see “free” and both insert. Uniqueness is the textbook case for consistency: it needs one authoritative place that decides atomically.

Let the database enforce it on the leader with a unique constraint, and treat the violation as “taken”:

// CREATE UNIQUE INDEX users_username ON users (lower(username));
fun signUp(username: String, password: String): User =
    try {
        leader.insert(User(username = username, passwordHash = hash(password)))
    } catch (e: UniqueViolation) {
        throw UsernameTaken(username)
    }

The pre-check can stay, for a friendly “already taken” message while typing, but it’s only a hint; the constraint is the guarantee. In a multi-region setup, usernames need a single home (one region, or a consensus database), because two regions accepting writes can’t both enforce uniqueness during a partition.

Exerciseeasy

CP or AP?

A food-delivery app has: (1) the restaurant menu, (2) the order a customer is placing, (3) the courier’s live location on the map, (4) the restaurant’s “accepting orders” switch, (5) promo codes limited to one use per customer. For each, say what should happen during a partition and why.

›

For each one, imagine two sides disagreeing for five minutes. Who is hurt, and how badly? Can it be fixed afterwards?

SolutionTry it yourself first

Menu: AP. A menu a few minutes old is fine; serve cached data.
Placing an order: accept the request (AP from the user’s view) but confirm only when the order service has it durably; queue it on the device and show “sending…” if offline. Never show “confirmed” for an order the restaurant can’t see.
Courier location: AP. Show the last known position with its age; newer updates simply replace older ones.
“Accepting orders” switch: prefer consistency for turning it off (a closed restaurant shouldn’t get orders), with a short delay acceptable; if in doubt, the order flow re-checks before confirming.
One-use promo codes: CP. Redemption must be checked and recorded atomically in one place; during a partition, refuse the code (“can’t apply right now”) rather than allow double use, or accept it and claw back afterwards if the business prefers.

Production puzzles

Spot the bugDeleted items come back

Tap the line with the bug.

// Cart replicas accept writes during partitions; on reconnect they merge.
fun merge(a: Cart, b: Cart): Cart =
    Cart(items = a.items union b.items)

// Cart replicas accept writes during partitions; on reconnect they merge.
Cart merge(Cart a, Cart b) {
    Set<Item> items = new HashSet<>(a.items());
    items.addAll(b.items());
    return new Cart(items);
}

// Cart replicas accept writes during partitions; on reconnect they merge.
function merge(a: Cart, b: Cart): Cart {
  return { items: new Set([...a.items, ...b.items]) };
}

A plain union can’t tell “removed on A” from “never added on B”. After the merge, the cart is {shoes, hat} again: deleted items reappear, and users who checked out quickly may buy them. (Amazon’s Dynamo paper describes exactly this behavior for carts and accepted it as the lesser evil; most teams wouldn’t.)

Merging needs to know about removals. Use an observed-remove set (OR-Set CRDT): each add gets a unique tag, a remove records the tags it has seen, and the merge keeps an item only if it has an add tag that no remove covered. Concurrent add and remove of the same item then resolve deterministically (add wins), and a remove of something both sides saw sticks.

data class OrSet<T>(val adds: Map<T, Set<String>> = emptyMap(), val removes: Map<T, Set<String>> = emptyMap()) {
    fun add(item: T) = copy(adds = adds + (item to (adds[item].orEmpty() + UUID.randomUUID().toString())))
    fun remove(item: T) = copy(removes = removes + (item to (removes[item].orEmpty() + adds[item].orEmpty())))
    val items: Set<T> get() = adds.filter { (item, tags) -> (tags - removes[item].orEmpty()).isNotEmpty() }.keys
    fun merge(other: OrSet<T>) = OrSet(
        adds = (adds.keys + other.adds.keys).associateWith { adds[it].orEmpty() + other.adds[it].orEmpty() },
        removes = (removes.keys + other.removes.keys).associateWith { removes[it].orEmpty() + other.removes[it].orEmpty() },
    )
}

(Tombstones grow forever in this naive version; real implementations compact them.)

Decide per operation: invariants (uniqueness, balances, inventory, one-time codes) CP; convergent data (carts, counters, presence, feeds, offline edits) AP.
Enforce invariants in one authoritative place (unique constraints on the leader, consensus stores), never by check-then-act on replicas.
AP needs merge semantics that handle deletes (OR-Sets, tombstones), not unions; CP needs degraded-mode UX.
Compensation (oversell and refund) is sometimes cheaper than coordination; it’s a business decision.

Check this part

Which data most clearly needs consistency during a partition?
Duplicates are hard to undo.
Why is checking a username on a replica and then inserting it unsafe?
Let a unique constraint on the leader decide.
Why does a union merge make deleted cart items reappear?
Track removals, e.g. with an OR-Set.

Choose per operation, not per database: uniqueness, inventory and money need consistency (refuse when unsure); carts, likes, feeds and drafts prefer availability (accept and reconcile). AP data needs a plan for merging conflicts; CP data needs a plan for what users see when requests fail.

Part Not started

PACELC: the trade-off you pay every day

Partitions are rare: minutes per year in a good setup. But even when the network is fine, keeping copies in agreement costs time: a strongly consistent write has to wait for other replicas, possibly in other cities, to confirm. So there’s a second, everyday question: wait for agreement (consistency), or answer right away from the nearest copy (low latency)?

PACELC names both: if Partition, choose A or C; Else, choose Latency or Consistency.

Abadi’s PACELC captures that the consistency/latency trade-off exists without failures and dominates day-to-day behavior. Systems classify as PA/EL (Dynamo-style stores by default, Cassandra at low consistency levels: available and fast, eventually consistent), PC/EC (Spanner, CockroachDB, etcd, single-leader synchronous setups: consistent, paying coordination latency always), and mixes (MongoDB and DynamoDB are tunable per operation: majority vs local reads, strongly consistent vs eventually consistent reads). Cross-region consensus costs at least one inter-region round trip per write (60 to 150 ms between continents), which is often the deciding factor.

Predict the output

A team moves its user database to a consensus-based store with replicas in Frankfurt, Virginia and Singapore, for 'consistency everywhere'. Before, writes went to a single-region database in ~5 ms. Roughly how long do writes from Frankfurt take now?

Tuning per request

Reads: “strongly consistent” or majority reads go to the leader or wait for confirmation; “eventual” or local reads are cheaper and faster. Choose per screen.
Writes: write concern (w=majority vs w=1), synchronous replica count, and quorum levels (Cassandra QUORUM vs ONE) set the latency/durability point per operation.
Data placement: most data has a natural home (a user’s region, a tenant’s region). Keeping it there gives consistent, low-latency access for its owner, and pushes cross-region consistency to the rare operations that span homes.

Practice: saying it in an interview

Don’t open with “I’ll pick CP” or “AP”. Name the data and what a disagreement would cost.
For invariants (uniqueness, money, inventory), say where the single source of truth lives and what users see if it’s unreachable.
For everything else, say it’s eventually consistent, how lag shows up, and which session guarantee you add (usually read-your-writes).
Mention the everyday cost: strong consistency across regions adds a round trip to every write.

PACELC: under Partition, A or C; Else, Latency or Consistency. The E-branch is the everyday cost.
PA/EL (Dynamo-style), PC/EC (Spanner, CockroachDB, etcd), tunable per operation (MongoDB, DynamoDB, Cassandra).
Cross-region consensus = inter-region RTT per write; prefer home-region placement and per-request consistency levels.

Check this part

What does the "ELC" part of PACELC describe?
Agreement between copies costs time even when nothing is broken.
How do you keep most writes fast while some data needs global consistency?
Most operations stay within one region.

PACELC extends CAP: if there's a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Most of the time there's no partition, and the everyday trade-off is how long a request waits for other replicas to agree.

Key takeaways

CAP: when the network between copies fails, a system must either refuse some requests (consistency) or answer with possibly stale data (availability).
Partitions aren’t optional; “pick two of three” really means “choose C or A when the network fails”.
Decide per feature: usernames and money need consistency; carts, likes and feeds prefer availability.
PACELC adds the everyday cost: consistency across copies takes time even when nothing is broken.

CAP’s C is linearizability, its A is total availability; it says nothing about the no-partition case.
Enforce invariants in one authoritative place; give AP data real merge semantics, including deletes.
Replica placement decides which side survives a partition.
Choose consistency levels per operation, and keep data in a home region to avoid cross-region round trips.