In a distributed data store, what does the CAP theorem actually force you to choose between, and how does PACELC extend that framing?
answer
- P is given — real choice is CP vs AP
- CAP C = linearizability, not ACID's C
- A = every non-failing node answers, not uptime %
- PACELC: Else → Latency vs Consistency
- Decide per operation: cart AP, payment CP
basics
~20 sCAP says that when the network splits (a partition), a distributed store must choose: keep answering with possibly-stale or conflicting data (availability), or refuse some requests to stay correct (consistency). PACELC adds: even with no partition, you still trade latency against consistency.
solid answer
~40 sCAP applies only during a network partition (P). Partitions are imposed by the world, not chosen, so the real choice is CP vs AP: when nodes cannot talk, either reject/block requests to preserve linearizable consistency (CP), or keep serving from reachable replicas and accept divergence you must reconcile later (AP). CAP's 'C' is linearizability — not the C in ACID — and 'A' means every non-failing node answers, not '99.99% uptime'. PACELC (Abadi) completes the picture: *if Partition then A-or-C, Else then Latency-or-Consistency*. The 'else' branch matters far more day to day, because partitions are rare but every synchronous quorum or cross-region acknowledgement costs latency on every request. So a store is classified like PA/EL (Dynamo-style), PC/EC (consensus-backed strict systems) or PC/EL. Modern systems are increasingly tunable per operation rather than globally.
go deeper
State that during a network split you must choose between answering with possibly stale data or refusing to answer, and give one example of each.
Define C, A and P precisely, explain that P is a given so the choice is CP vs AP, and state PACELC's else-branch: latency vs consistency on every normal request.
Apply it per operation, discuss quorum tuning (R + W > N), session guarantees, bounded staleness, and the reconciliation strategy for anything left AP.
Tie the choice to business cost of a stale read versus a rejected request, discuss multi-region topology and the latency floor imposed by geography, and set organisation-wide defaults with explicit escape hatches.
## Definitions first A **distributed data store** keeps copies (**replicas**) of data on several machines. A **network partition** is any condition where some replicas cannot exchange messages in time — a cut cable, an overloaded switch, a stalled process, a firewall rule. From the outside, an arbitrarily slow node is indistinguishable from a partitioned one. The **CAP theorem** (Brewer's conjecture, proved by Gilbert & Lynch in 2002) uses precise, narrow meanings: - **C = Consistency = linearizability.** Every read sees the most recent completed write; the system behaves as if there were a single copy. This is *not* the C (integrity constraints) of ACID. - **A = Availability.** *Every* request to a *non-failing* node gets a non-error response, eventually. It is not a percentage-uptime SLA. - **P = Partition tolerance.** The system keeps functioning despite arbitrary message loss between nodes. ## What the theorem really forces The popular phrasing "pick two of three" is misleading. You do not choose partitions — the network does. Any system that spans machines will experience partitions, so **P is a given**, and the theorem becomes: *during a partition, choose C or A.* - **CP behaviour:** the minority side stops serving (or blocks) so no client can read stale or write conflicting data. Cost: some clients see errors/timeouts even though the process is alive. Typical of consensus-backed stores (Raft/Paxos), strongly-consistent metadata services, ledgers. - **AP behaviour:** every reachable replica keeps serving. Cost: replicas diverge and must be reconciled afterwards — last-write-wins, vector clocks, CRDTs, or application-level merge. Typical of Dynamo-style stores, DNS, shopping carts, caches. A single system can pick different answers per operation: 'add to cart' can be AP while 'take payment' is CP. ## Why PACELC exists CAP describes only the rare partitioned case and says nothing about normal running. Daniel Abadi's **PACELC** (2010) reads: > **if (P)artition then (A)vailability or (C)onsistency, (E)lse then (L)atency or (C)onsistency.** The 'else' half is the one you pay for on every single request: to guarantee a read sees the latest write you must contact a quorum or the leader, possibly across regions, which adds round trips. Relaxing to a local or follower read removes those round trips and reintroduces staleness. So the everyday trade-off is **latency vs consistency**, and it is continuous, not binary: you can tune quorum sizes (R + W > N), read-your-writes sessions, bounded staleness, monotonic reads. Common classifications: PA/EL (available under partition, latency-optimised otherwise — Dynamo-style), PC/EC (consistency always — consensus/externally-consistent systems), PC/EL (consistent under partition but latency-favouring locally). ## Frequent misreadings to avoid - "We're AP because we have three nodes." Node count is not a CAP choice; behaviour during partition is. - "CAP's C is ACID's C." No — CAP's C is linearizability; ACID's C is constraint preservation, and ACID's I (isolation) is the closer cousin. - "CP systems are down." They are *unavailable for some requests on the minority side*, which is a deliberate correctness choice, not an outage of the whole service. - "Choose two of three." You choose one of two, and only while partitioned. - "Eventual consistency means data is wrong." It means replicas converge once messages flow again, given no new writes; correctness comes from the merge strategy and from designing operations to be commutative or idempotent where possible. ## How to use this in an interview or design Do not classify the whole system. Walk operation by operation: what is the cost of a stale read here, and what is the cost of an error here? Payment capture and uniqueness constraints want CP; feeds, catalogues, recommendations, presence and analytics happily take AP/EL. Then pick the storage guarantee (and quorum settings) per data set, and write down the reconciliation rule for anything you left AP.
- Give an operation in an e-commerce system you would run AP and one you would run CP, with reasons.Browsing the catalogue and adding to a cart can be AP — a stale price or a merged cart is recoverable and cheap. Reserving the last unit of stock or capturing a payment should be CP — double-selling or double-charging costs money and trust, so refusing under partition is cheaper than reconciling.
- What does the quorum rule R + W > N buy you, and what does it cost?With N replicas, requiring W acknowledgements on write and R on read so that R + W > N guarantees the read set overlaps the write set, giving strong-ish reads. It costs latency (more nodes to wait for) and availability (fewer node failures tolerated) — exactly PACELC's else-branch trade.
- Why is 'we are highly available, so we are AP' a weak statement?CAP availability is a formal per-request property during a partition, not an uptime figure. A CP system can have five-nines uptime; an AP system can be badly engineered and flaky. The question is only what happens to requests on the minority side of a split.
Two bank branches lose their phone line. Policy A: keep paying out from local records and reconcile the ledgers tonight (available, may overdraw). Policy C: refuse withdrawals until the line is back (correct, some customers turned away). Even when the line works, checking with head office before each payout adds delay — that is PACELC's 'else' branch.
saying these in an interview costs you the question
- 'Pick any two of C, A and P' — partition tolerance is not optional in a distributed system
- Equating CAP's consistency with ACID's consistency
- Reading availability as an uptime SLA percentage
- Classifying an entire product as CP or AP instead of per operation
- Ignoring the everyday latency-vs-consistency trade-off because partitions are rare
- Assuming eventual consistency needs no reconciliation design