skip to content

Explain the CAP theorem and its PACELC extension, and how they shape architectural decisions about consistency, availability, and latency.

level: seniorimportance: must knowfreq 72%

answer

  1. P isn't optional — choose C or A during a partition
  2. PACELC: if P → A/C, else → L/C
  3. CAP-C = linearizability, not ACID's C
  4. R + W > N tunes the dial per query
  5. AP needs a merge story: version vectors, CRDTs

basics

~20 s

CAP: when the network splits a distributed system (a partition), you must choose between staying consistent (reject/block requests) or staying available (answer, possibly with stale data). PACELC adds: even with no partition, you still trade latency against consistency.

solid answer

~60 s

CAP applies to a replicated system: if a network **partition (P)** occurs, you can preserve **consistency (C — linearizability: every read sees the latest write)** or **availability (A — every non-failing node answers)**, not both. Partitions are a fact of networks, so CAP is really "during a partition, choose CP or AP". CP designs (quorum stores like ZooKeeper/etcd, single-leader RDBMS with synchronous replication) refuse or block on the minority side; AP designs (Dynamo-style stores, DNS, CRDT systems) keep answering and reconcile later. **PACELC** (Abadi) completes it: **if P then A-or-C, Else (normal operation) L-or-C** — latency versus consistency. This matters more day to day, because partitions are rare but every synchronous cross-replica ack costs latency. A cross-region quorum write is a PC/EC choice; an async-replicated read replica is PA/EL. Practically: CAP is not a system-wide badge but a **per-operation** decision. Payment authorization can be CP; a product-page view count can be AP. I'd express each as a quality-attribute scenario (what happens during the partition, what the user sees, what the recovery/reconciliation is) rather than debating labels.

code

text · 6 lines
text
PACELC:  if (Partition) A or C   else (E) L or C

quorum store, N = 3 replicas
  W=3, R=1   strong-ish reads, slow + fragile writes   (EC, PC-leaning)
  W=2, R=2   R+W>N: read-your-writes, balanced         (common default)
  W=1, R=1   fastest, most available, may read stale    (EL, PA)

go deeper

for a junior

State the partition scenario in plain words and that you must choose stale-but-answering versus correct-but-refusing. Avoid the 'pick two' phrasing.

for a middle

Define C as linearizability, explain why P is mandatory, give real CP and AP systems, and add PACELC's latency-versus-consistency point for normal operation.

for a senior

Argue per-operation rather than per-system, use quorum tuning (R+W>N), name consistency levels between strong and eventual (causal, read-your-writes, bounded staleness), and specify the conflict-resolution mechanism the AP choice obliges you to build.

for a principal

Drive it from business cost: what does a wrong answer cost versus a refused one, per journey; convert consistency needs into business processes (escrow, overbooking, compensation) where possible; write partition behaviour as a tested quality-attribute scenario; and account for the E-side latency cost, which is paid on every request while partitions are rare.

## The precise statement CAP (Brewer's conjecture, proved by Gilbert & Lynch) concerns a distributed system of replicas that must respond to reads and writes: - **C — Consistency**, here meaning **linearizability**: the system behaves as if there were a single copy; a read always returns the most recent completed write. Note this is *not* the C in ACID (which is about invariants inside a transaction). - **A — Availability**: every request to a **non-failing** node receives a non-error response, eventually. Note this is *not* the same as the operational "nines" availability — CAP-A is an absolute, per-node property. - **P — Partition tolerance**: the system continues operating despite arbitrary loss of messages between nodes. The theorem: you cannot have all three simultaneously. **The correct reading is not "pick two."** Partitions are not a design choice — networks drop packets, links flap, a switch fails, GC pauses look like partitions. Any system distributed across machines must tolerate P. So the real statement is: **when a partition occurs, choose between C and A.** When there is no partition, you can have both. ### Why the choice is forced Two replicas, R1 and R2, holding value x, with the link between them severed. A client writes x=2 at R1 and another reads x at R2. - If R2 answers with the old value, it was **available** but not **consistent**. - If R2 refuses to answer until it can reach R1, it was **consistent** but not **available**. There is no third option; no amount of engineering creates information that could not cross the broken link. ## PACELC — the part that matters every day Daniel Abadi's extension: > **if (P)** then **A or C**, **else (E)** then **L or C** Even with a healthy network, keeping replicas consistent requires coordination — a leader round trip, a quorum acknowledgment, a consensus round — and coordination costs **latency (L)**. So systems are labelled with two choices: | Class | Meaning | Typical examples | |---|---|---| | **PC/EC** | Consistent during partitions and normally, paying latency | ZooKeeper, etcd, Spanner, a single-leader RDBMS with synchronous commit, HBase | | **PA/EL** | Available during partitions, low-latency (weakly consistent) normally | Dynamo, Cassandra with low quorum settings, Riak, most DNS/CDN edges | | **PA/EC** | Available under partition, consistent when healthy | Some configurable stores; MongoDB is often placed near here depending on write concern | | **PC/EL** | Blocks under partition but is loose normally | Rare; e.g. certain configurations of PNUTS | PACELC's practical value: most systems never partition in a given month, but *every single request* pays the E-side cost. Choosing strong consistency across regions can add 50–150 ms per write — often the bigger business impact than the annual partition. ## Beyond the binary: the consistency spectrum CAP's C is the strongest rung. Real designs pick a level: 1. **Linearizable / strict serializable** — single-copy illusion; needs consensus (Raft/Paxos) or a leader with synchronous quorum. 2. **Sequential / causal+ consistency** — operations respect causality; achievable with high availability (causal consistency is the strongest model compatible with availability under partition). 3. **Read-your-writes, monotonic reads, bounded staleness** — session guarantees; cheap and often exactly what users perceive as "correct". 4. **Eventual consistency** — replicas converge if updates stop; needs conflict resolution. **Conflict resolution for the AP side** is where the real engineering lives: last-write-wins with clocks (lossy, clock-skew-prone), version vectors to detect concurrent updates, application-level merge, or **CRDTs** (conflict-free replicated data types — counters, sets, sequences that merge deterministically without coordination). Choosing AP means committing to a reconciliation story, not to "we'll sort it out later". Quorum arithmetic (Dynamo-style): with N replicas, W write acks and R read acks, `R + W > N` gives strong-ish read-your-writes behaviour at the cost of latency and reduced availability; `R + W ≤ N` is faster and more available but stale. This is a *tunable dial*, not a fixed property — the same store can be CP-ish or AP-ish per query. ## Business-level framing: what does "unavailable" cost vs "wrong"? The decision is not technical taste but the cost of each failure mode: | Operation | Cost of stale/conflicting answer | Cost of refusing | Reasonable choice | |---|---|---|---| | Debit an account / reserve the last seat | Overdraft, double-sold seat, regulatory issue | Customer retries in 30 s | **CP** | | Add to shopping cart | Two devices' carts merge (union) | Lost sale | **AP** + merge | | Product page view count, likes | Nobody notices | Page fails | **AP** | | Distributed lock / leader election | Split brain, data corruption | Wait | **CP** (never AP) | | Feature flag read, config | Slightly stale behaviour | Service can't start | **AP** with cached last-known-good | Note a subtlety: **many "we need strong consistency" cases are actually solvable by escrow/compensation.** Airlines overbook and compensate; warehouses reserve optimistically and cancel. That converts a consistency requirement into a business process, buying availability. ## Common misconceptions to correct out loud - **"Pick two."** No — P is not optional in a distributed system; you pick C or A *during a partition*. A single-node database is CA only in the trivial sense that it isn't distributed (and it is not available when it dies). - **"CAP-A means high availability."** CAP-A is an absolute liveness property; the operational availability you promise in an SLO is a percentage over time. A CP system can be 99.99% available in practice because partitions are rare. - **"CAP is a property of a database."** It is a property of a *configuration and an operation*. Cassandra with QUORUM reads/writes behaves differently from Cassandra with ONE. The same application can run CP and AP paths side by side. - **"NoSQL means AP, SQL means CP."** Orthogonal. Spanner is a SQL system that is effectively CP; MySQL with async replicas serves stale reads (AP-ish reads). - **"Spanner beats CAP."** No — Spanner chooses CP, and uses TrueTime plus enormous network investment to make partitions rare enough that its measured availability is very high. It reduces the frequency of the choice, not the theorem. - **Ignoring the microservices version.** CAP shows up not just in databases but whenever two services hold copies of a fact. Synchronous cross-service calls buy consistency and inherit each other's downtime; asynchronous events (outbox, saga) buy availability and accept a window of divergence with compensating actions. ## Turning it into a quality-attribute scenario Rather than arguing labels, write the scenario: > *Stimulus:* the link between region A and region B fails for 4 minutes. *Artifact:* the seat-reservation service. *Response:* the minority region rejects new reservations with a retriable error and serves read-only inventory marked "as of HH:MM"; the majority region continues. *Measure:* zero double-booked seats; ≤ 2% of reservation attempts rejected; full convergence within 60 s of the link recovering; users in the minority region see a clear message. That is testable — with a real partition drill — and it makes the trade-off visible to product stakeholders, which is the actual point of CAP in architecture work.

  • If you choose AP for a shopping cart, what must you build that a CP design would not need?
    A deterministic conflict-resolution story. Concurrent updates from two devices will exist, so you need version vectors or an OR-Set-style CRDT so that 'add' and 'remove' merge sensibly (typically union of adds, with tombstones for removes), plus idempotent operations, plus a UI decision about what the user is shown while replicas diverge. Last-write-wins by wall clock is the tempting shortcut and it silently loses items under clock skew.
  • Does using a single primary database make CAP irrelevant?
    No. It makes the trade explicit rather than absent: a single primary is CP-flavoured — during a partition the unreachable side simply cannot write, and if the primary is lost you must either wait (consistent, unavailable) or promote a possibly-behind replica (available, may lose writes — an RPO > 0). Add async read replicas and your reads are already eventually consistent, so you are running mixed modes whether or not you named them.
  • Where does CAP appear in a microservice architecture with no shared database?
    Whenever two services hold a copy of the same fact. A synchronous call to the owning service buys freshness and couples availability (you are now in series). Publishing domain events with an outbox and keeping a local read model buys availability and independence but accepts a staleness window and needs sagas/compensation for cross-service invariants. Same theorem, different packaging.

Two ticket offices connected by a phone line that just went dead. A customer wants the last seat. The clerk can sell it — fast and helpful, but the other office might sell it too (AP). Or refuse until the line is back — never double-sells, but sends customers away (CP). No clerk skill removes the choice; the only real decisions are which mistake you can afford and, when the line is up, whether you phone the other office before every sale (that call is PACELC's latency cost).

saying these in an interview costs you the question

  • Reciting "pick two of three" as if partition tolerance were an optional design choice.
  • Calling a single-node database "CA" and treating that as a real architectural option.
  • Equating CAP's consistency with the C in ACID, or CAP's availability with an uptime percentage.
  • Labelling a whole database CP or AP instead of recognizing it depends on configuration (quorum settings) and per-operation choice.
  • Claiming Google Spanner or any product "beats" or "solves" CAP.
  • Choosing AP with no conflict-resolution design, or defaulting to last-write-wins by wall clock despite clock skew.
  • Assuming eventual consistency is the only alternative to linearizability, ignoring causal, bounded-staleness, and read-your-writes models.
  • Using a distributed lock or leader election on an AP store, which invites split brain.

context

resolving links…