Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › System Design

CAP Theorem and Consistency

In a distributed system (data stored on several machines), the network between machines can fail. The CAP theorem says what you can and cannot promise when it does.

The three letters

The theorem

During a network partition, a distributed system must choose between Consistency and Availability.

Partitions will happen in real networks, so P is not optional. The real choice is:

Choice During a partition Example behaviour
CP refuse or wait on some requests to avoid wrong data "Service unavailable, try again"
AP answer every request, possibly with stale data; fix differences later shows an old like count
When there is no partition, a system can be both consistent and available.

Picture it

   Node A  ──✂── (link broken) ──  Node B
   x = 1                            x = 1
User writes x = 2 to A.  Another user reads x from B.
CP: B refuses (or waits) — it can't confirm the latest value.
AP: B answers x = 1 — available but stale.

Examples

System Usually classed Notes
Single-node PostgreSQL/MySQL CA (not distributed) no partition to worry about
MongoDB (default, majority writes) CP minority side can't elect a primary
HBase, ZooKeeper, etcd, Consul CP used for config, leader election, locks
Cassandra, DynamoDB, Riak AP (tunable) quorum settings move them toward C
CouchDB, DNS AP eventually consistent
Google Spanner CP uses atomic clocks; is practically highly available
Many databases are tunable — the label depends on configuration.

Which to choose

Prefer CP Prefer AP
bank balance, payments, stock/inventory reservation, seat booking social feed, likes, view counts, product catalogue, shopping cart, DNS
wrong data is worse than an error an error is worse than slightly old data

PACELC — the fuller picture

If Partition → choose A or C; Else (normal operation) → choose Latency or Consistency. Even without failures, waiting for replicas to agree costs time.

System PACELC
Cassandra, DynamoDB PA/EL — available, low latency
MongoDB PC/EC (default)
Spanner, HBase PC/EC
PNUTS (Yahoo) PC/EL

Consistency models (strongest → weakest)

Model Guarantee Example
Strong / linearizable everyone sees the latest write immediately bank balance in a single-leader DB with sync reads
Sequential everyone sees operations in the same order —
Causal if B depends on A, everyone sees A before B a reply never appears before its comment
Read-your-writes you always see your own updates your edited profile
Monotonic reads you never see older data after newer refreshing a feed
Eventual if writes stop, all replicas eventually agree like counts, DNS
Stronger = simpler to reason about but slower and less available.

How AP systems reconcile

Quorums

With N replicas: write to W, read from R. W + R > N → every read overlaps the latest write.

N, W, R Result
3, 2, 2 consistent reads, tolerates 1 failure
3, 1, 1 fastest, eventually consistent
3, 3, 1 fast reads, any failure blocks writes

ACID vs BASE

ACID (traditional SQL) BASE (many NoSQL)
Atomic, Consistent, Isolated, Durable Basically Available, Soft state, Eventually consistent
correctness first availability and scale first
See Transactions and ACID.

Common interview mistakes

Interview one-liners

More System Design notes