Back to System design

CAP Theorem and PACELC

easy
Scale: Consistency dictates per-op latency Storage: Replication factor × dataset Google, Meta, Amazon
FundamentalsDistributed SystemsConsistency

The CAP theorem says a distributed data store can guarantee at most two of Consistency, Availability, and Partition tolerance. Because partitions are unavoidable in the real world, the practical choice is between Consistency and Availability during a partition.

ScaleConsistency dictates per-op latency
StorageReplication factor × dataset

Key Concepts

1
1. The three properties. Consistency here means linearizability — every read returns the latest successful write, as if there were a single copy. Availability means every non-failing node returns a non-error response in finite time. Partition tolerance means the system keeps operating despite arbitrary message loss between nodes.
1. The three properties.
2
2. The forced choice. When a partition happens, you cannot have both C and A: either the minority side refuses writes to stay correct (CP), or both sides keep accepting writes and reconcile later (AP). Partitions are not optional in practice — packets drop, links fail, regions get isolated.
2. The forced choice.
3
3. PACELC extends CAP. Most of the time there is no partition, and PACELC (Abadi, 2010) captures the day-to-day trade-off: if Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Async replication across regions is cheap but stale; sync replication is consistent but pays a cross-region round trip on every write.
3. PACELC extends CAP.iE
4
4. Pick CP or AP per data class, not per system. Ledgers, orders, inventory want CP — rejecting a write is better than lying. Feeds, like counts, recommendations want AP — never show the user a 500. Many stores let you mix: Cassandra has per-query consistency (ONE / QUORUM / ALL); DynamoDB exposes both eventual and strongly-consistent reads.
4. Pick CP or AP per data class, not per system.
5
5. In production. Spanner is CP using TrueTime to bound clock skew. CockroachDB is CP with Raft per range. DynamoDB defaults to AP, opt-in strong reads. Cassandra is AP with tunable quorum (R+W>N → linearizable). etcd / ZooKeeper are CP coordination services — fine for config, wrong for high-throughput data.
5. In production.

Related Problems

Load Balancing: L4 vs L7, Algorithms, Health CheckseasyCaching Strategies: Cache-aside, Write-through, Write-backeasySQL vs NoSQL: When to Pick WhicheasySharding Strategies: Range, Hash, Directory, GeomediumConsistent Hashingmedium

Approach

  1. Pin down the consistency model in plain language: linearizable, serializable, snapshot, causal, read-your-writes, eventual.
  2. Identify the partition pattern. Same rack? Same AZ? Cross-region? Long-lived netsplit?
  3. Decide per-data-class, not per-system. Orders and inventory want CP; counters and recommendations want AP.
  4. Pick a store that supports the chosen mode. CP options: Spanner, CockroachDB, etcd, HBase. AP: Cassandra, DynamoDB, Riak. Tunable: Cassandra, DynamoDB, Couchbase.
  5. Decide quorum settings. For Dynamo-style: R + W > N gives strong reads. R=W=1 = eventual; R=W=N = full agreement, low availability.
  6. Handle the AP case explicitly: conflict resolution (LWW, vector clocks, CRDTs), read repair, anti-entropy.
  7. Now layer in PACELC. Async replication for cheap reads; sync only where staleness is unacceptable.

Components

  • Replication protocol — sync, semi-sync, async, quorum-based.
  • Replica placement — same AZ, cross-AZ, cross-region, with proximity rules.
  • Conflict resolution — Last-Write-Wins timestamps, vector clocks, CRDTs (G-counters, OR-sets), domain merge functions.
  • Failure detection — heartbeats, gossip (SWIM), phi-accrual.
  • Leader election or coordinator — Raft, Paxos, single-master with promotion.
  • Client-side routing knowledge — which replica owns this key, which is leader, fall-back order.
  • Anti-entropy — Merkle tree compare, read repair, periodic full sync.

Trade-offs

CP: simpler app code, fewer surprises, but a partition or leader loss means the minority side returns errors. Acceptable if your SLO is correctness over uptime.

AP: never tells the user 'no', but conflict resolution and read repair complexity bleed into the application. Stale data is a UX problem unless you compensate (read-your-writes, session stickiness).

Latency vs consistency in the no-partition case (PACELC): sync replication = correct + slow tail; async = fast + potentially stale. Most products land on async cross-region replication with strong consistency only on the primary region.

Hybrid is the real answer: ledger CP, derived views AP, search index eventually consistent on a separate path.

Real-world systems

  • Spanner: CP system using TrueTime to bound clock uncertainty; achieves external consistency globally at the cost of write latency tied to the TT interval.
  • CockroachDB: Raft per range; CP with tunable transactional isolation.
  • DynamoDB: AP by default with eventual reads; opt into strongly-consistent reads at 2x cost and higher latency.
  • Cassandra: tunable per-query consistency; QUORUM reads + QUORUM writes give linearizability under R+W>N.
  • etcd / ZooKeeper: CP coordination services; never use for high-throughput data, only for config and leases.

Common interview pitfalls

  • Treating CAP as a static label for the whole system. Real systems mix per-table.
  • Forgetting that 'P' is not optional — partitions will happen.
  • Claiming a system is 'CA' — that just means no partitions are tolerated, which is unrealistic for distributed systems.
  • Confusing eventual consistency with weak consistency. Eventual = converges if writes stop; weak = no guarantees.
  • Ignoring PACELC and missing the day-to-day latency trade-off, which dominates user-perceived performance.