Skip to content

CAP & PACELC#

Problem statement (interviewer prompt)

Explain CAP and PACELC. Pick three real systems - one CP, one AP, one with tunable consistency - and contrast their behaviour during a network partition and during normal-mode latency-vs-consistency trade-offs.

Concept illustration

CAP: under a network partition, a distributed system can be either consistent or available - pick one.

PACELC extends it: even when no partition exists, you trade latency vs consistency.

CAP theorem Venn diagram showing consistency, availability, and partition tolerance
Source: Wikimedia Commons. CC BY-SA 4.0.
flowchart LR
  N[Network OK?]
  N -->|Partition| P[Choose: C or A]
  N -->|No partition| E[Choose: L or C]
  P --> CP[CP system<br/>HBase, Spanner, etcd]
  P --> AP[AP system<br/>Dynamo, Cassandra, Riak]
  E --> EL[EL low latency<br/>Dynamo, Cassandra]
  E --> EC[EC strong consistency<br/>Spanner, MongoDB majority]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class N,P,E service;
    class CP,AP,EL,EC datastore;

flowchart TB
  subgraph CAP[CAP Theorem - Brewer/Gilbert-Lynch]
    C1[Consistency<br/>linearizability]
    A1[Availability<br/>every request a non-error response]
    P1[Partition tolerance<br/>required in real networks]
  end

  subgraph PACELC[Abadi 2010 - PACELC]
    IfP[If Partition: pick A or C]
    Else[Else no partition: pick L or C]
  end

  subgraph Levels[Consistency Models]
    LIN[Linearizable]
    SS[Sequential]
    CS[Causal]
    RYW[Read-Your-Writes]
    MR[Monotonic Reads]
    EV[Eventual]
  end

  subgraph Examples[Systems]
    SP[Spanner<br/>CP / EC<br/>TrueTime]
    DY[DynamoDB / Cassandra<br/>AP / EL]
    MG[MongoDB majority<br/>CP / EC]
    CR[CockroachDB<br/>CP / EC]
    RD[Redis<br/>CP single-leader, AP cluster]
    RF[Raft / etcd / Consul<br/>CP / EC]
    KF[[Kafka<br/>CP within ISR]]
  end

  subgraph Mechanisms[Mechanisms]
    QR[Quorums R+W>N]
    HH[Hinted Handoff]
    AE[Anti-entropy / Merkle]
    CRDT[CRDTs]
    PAX[Paxos / Raft]
    LCK[Leases / Locks]
  end

  CAP --> PACELC
  PACELC --> Levels
  Examples --- Levels
  Mechanisms --- Examples

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class C1,A1,P1,IfP,Else,LIN,SS,CS,RYW,MR,EV,RF,QR,HH,AE,CRDT,PAX,LCK service;
    class SP,DY,MG,CR datastore;
    class RD cache;
    class KF queue;

Key clarifications#

  • "CA" systems do not exist in WAN - partitions are real.
  • "Consistency" in CAP = linearizability (strongest).
  • Most "AP" systems pick eventual consistency, often with knobs (Cassandra's ONE/QUORUM/ALL).
  • Spanner uses synchronized clocks (TrueTime) to give linearizable cross-region writes with 5-10 ms wait windows.

Choosing#

Need Pick
Money, ledger, secrets CP / EC (Spanner, CockroachDB, Postgres + Raft)
Shopping cart, session, social AP / EL (Dynamo, Cassandra)
Coordination (locks, config) CP / EC (etcd, ZooKeeper, Consul)
Analytics aggregations EL with eventual is fine

Practical tips#

  • Pick the weakest consistency you can tolerate per operation, not per system.
  • Read-your-writes is often sufficient and cheap (session pinning).
  • For cross-region, latency dominates → expect EL most of the time.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD Pub/Sub & message brokers topics, consumer groups, delivery semantics pub-sub-pattern
HLD CAP / PACELC C vs A under partition; L vs C otherwise cap-pacelc
HLD Raft / Paxos consensus replicated state machine via majority quorum consensus-raft-paxos
HLD Logical clocks Lamport, vector clocks, HLC, TrueTime logical-clocks
HLD CRDTs commutative replicated data types crdts
HLD Multi-region & DR RTO / RPO, active-active, failover multi-region-dr

Quick reference#

CAP precise statement (Gilbert & Lynch, 2002)#

For any read/write register replicated across nodes connected by an asynchronous network, you cannot simultaneously guarantee: - Linearizability (C) - Total availability (every non-failing node responds non-error) (A) - Tolerate network partitions (P)

In real networks P is unavoidable → pick CP or AP.

PACELC (Abadi 2010)#

If a Partition, choose A or C. Else, choose L (latency) or C.

This captures the normal-mode trade-off CAP misses: synchronous replication ≈ low-latency loss.

Consistency model lattice (strong → weak)#

  1. Linearizable
  2. Sequential
  3. Causal
  4. Read-your-writes / Monotonic reads
  5. Eventual

Common misconceptions#

  • "We're CA because no partitions in our DC" - partitions are still possible (rack switch, GC pause).
  • "Eventual = inconsistent forever" - usually converges in ms; bounded staleness is precise term.
  • Spanner is "CP" but with 99.999% availability - proving P doesn't always mean unavailable.

Refs#

  • Gilbert, Lynch (2002): "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services."
  • Abadi (2010): "Consistency Tradeoffs in Modern Distributed Database System Design."
  • Spanner OSDI '12 paper. Jepsen analyses (https://jepsen.io).

FAQ#

What is the CAP theorem in simple terms?#

During a network partition, a distributed system must choose between consistency (every read sees the latest write) and availability (every request gets a response). You cannot have both at once.

What is the difference between CAP and PACELC?#

CAP only describes behavior during a partition. PACELC extends it by saying that even without a partition, you trade latency versus consistency, which is the more common day-to-day choice.

Is MongoDB CP or AP?#

MongoDB with default settings is CP within a replica set. Reads from the primary are linearizable. Tunable read concerns let you trade toward AP when you want lower latency from secondaries.

Is Cassandra CP or AP?#

Cassandra is classically AP with eventual consistency. You can tune to stronger consistency per query using quorum reads and writes, but it defaults to availability under partition.

Can a system be both CP and AP?#

Not at the same time under a real partition, but modern databases like Spanner, CockroachDB, and YugabyteDB use synchronized clocks and quorum protocols to minimize partition windows so the tradeoff is rarely observed.

Further reading#

Curated, high-credibility sources for going deeper on this topic.

Video walkthrough

CAP Theorem Explained : via ByteByteGo