Start practising

SYSTEM DESIGN · CONCEPTS · DISTRIBUTED SYSTEMS · EPISODE 25

CAP Theorem

What CAP actually says: during a network partition you choose consistency or availability. CP vs AP systems with real examples, why "pick two of three" is misleading, PACELC for the normal case, and how to answer the interview question.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 12

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

The setup

Start with replication from episode twenty. The same data lives on two nodes, say Mumbai and Frankfurt. A write lands on one and is copied to the other over the network. Normally that takes milliseconds and nobody notices.

The setup
  • data replicated on 2+ nodes
  • (episode 20: replication)
  • a write lands on one node
  • and is copied to the others
  • over the network
  • normally: milliseconds

C, A, P

The three letters, precisely. Consistency: every read returns the most recent write, as if there were one copy. Availability: every request to a node that's up gets a real answer, not an error. Partition tolerance: the system keeps operating when the network between nodes breaks. Note that C here is not the C in ACID; it's about copies agreeing.

The three letters
  • C, consistency:
  • every read sees the latest
  • write (linearizability)
  • A, availability:
  • every request to a live node
  • gets a non-error answer
  • P, partition tolerance:
  • keeps working when nodes
  • cannot talk to each other

Partition

Now the network between them breaks. A cable, a switch, a long garbage-collection pause; in large systems this is not rare. Both nodes are alive, but they can't talk. A user writes 'balance two hundred' to Mumbai. Frankfurt still says five hundred. Now another user reads from Frankfurt. What should Frankfurt do?

A partition happens
  • undersea cable cut, switch dies,
  • GC pause, misconfigured firewall
  • both nodes are alive
  • but cannot talk
  • A just took a write: 200
  • B still has: 500
  • now someone reads from B…

Choose C

Option one: choose consistency. Frankfurt can't confirm it has the latest value, so it refuses: an error, or it waits. Nobody ever sees a stale balance, but some requests fail until the network heals. In practice, only the side holding a majority of nodes keeps accepting writes. That's a CP system.

Option 1: consistency (CP)
  • B cannot confirm it is current
  • → returns an error or waits
  • no wrong answers
  • but some requests fail
  • usually: only the side with a
  • majority (quorum) keeps
  • accepting writes

Choose A

Option two: choose availability. Frankfurt answers with what it has, five hundred, and may even accept writes of its own. Every request succeeds, but some answers are stale, and when the link heals the two sides must reconcile conflicting writes: last-write-wins, merging, or data types designed to merge. That's an AP system.

Option 2: availability (AP)
  • B answers with what it has: 500
  • and may even accept writes
  • every request succeeds
  • but some answers are stale
  • when the link heals:
  • sync and resolve conflicts
  • (last write wins, merge, CRDTs)

The real choice

So why is 'pick two of three' misleading? Because you don't get to opt out of partitions; networks fail. Partition tolerance is a given for anything distributed. CAP really says: when a partition happens, you choose consistency or availability. And when there's no partition, you can have both. A so-called CA system is just a single machine.

Why not "pick 2 of 3"
  • partitions are not optional:
  • networks fail, so P is a given
  • CAP = when a partition happens,
  • choose C or A
  • no partition? you can have
  • both C and A
  • "CA" = single node, not distributed

In the wild

Real systems. CP: ZooKeeper, etcd and Consul, the coordination stores that hold locks and leader elections, where a wrong answer is worse than none; also Spanner and HBase. AP: Cassandra, DynamoDB by default, Riak, and DNS itself, where staying up matters more. Many are tunable: Cassandra with quorum reads and writes behaves much more like CP.

Real systems
  • CP (refuse when unsure):
  • ZooKeeper, etcd, Consul,
  • HBase, Spanner, MongoDB
  • (majority writes)
  • AP (always answer):
  • Cassandra, DynamoDB (default),
  • Riak, CouchDB, DNS
  • many are tunable per query

PACELC

CAP only talks about partitions, which are rare. PACELC covers the rest: if Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Waiting for every replica to confirm a write keeps copies consistent but adds latency; replying early is fast but briefly stale. Cassandra is P-A, E-L. Spanner is P-C, E-C, and pays for it with atomic clocks and extra milliseconds.

PACELC
  • if Partition:
  • choose Availability or Consistency
  • Else (normal operation):
  • choose Latency or Consistency
  • sync replication = consistent, slow
  • async = fast, briefly stale
  • Cassandra: PA/EL
  • Spanner: PC/EC

Decision

In practice you choose per feature, not per company. Bank balances, inventory counts, seat bookings, leader election: consistency, because showing a wrong value causes real damage. Likes, view counts, feeds, presence, shopping carts: availability, because a slightly stale number hurts nobody and an error page does. One application often uses both.

Pick per feature
  • bank balance, inventory count,
  • seat booking, leader election
  • → consistency
  • likes, view counts, feeds,
  • shopping cart, presence
  • → availability
  • one app can use both

Say it like this

The interview answer. Partitions will happen, so the question is what this feature should do during one. Compare the cost of a stale read with the cost of an error. Then choose: consistency with quorums or a single leader, or availability with async replication and a conflict-resolution plan. Mention PACELC for the normal case, and you've answered better than most.

In the interview
  • "Is your design CP or AP?"
  • 1. partitions will happen
  • 2. for <feature>, a stale read
  • costs X, an error costs Y
  • 3. so I choose C (quorum,
  • single leader) or A (async,
  • conflict resolution)
  • 4. normal case: PACELC latency

Interview questions

State the CAP theorem precisely.

In a distributed system with replicated data, when a network partition occurs, the system can guarantee either consistency (every read sees the latest write) or availability (every request to a live node gets a non-error response), but not both.

Why is "pick two of three" misleading?

Partition tolerance is not optional for a distributed system because networks fail. The real choice is between consistency and availability, and only while a partition is happening; without a partition a system can provide both.

What does a CP system do during a partition?

Nodes that cannot confirm they have the latest data refuse requests or block, typically allowing only the majority (quorum) side to keep serving writes. No stale reads are returned, but some requests fail.

What does an AP system do during a partition, and what happens afterwards?

Every live node keeps answering with the data it has, possibly stale, and may accept writes. When the partition heals, replicas sync and resolve conflicting writes using last-write-wins, application merges or CRDTs.

Give examples of CP and AP systems.

CP: ZooKeeper, etcd, Consul, HBase, Google Spanner, MongoDB with majority writes. AP: Cassandra and DynamoDB in their default modes, Riak, CouchDB, DNS. Many systems are tunable per query, for example Cassandra with QUORUM consistency.

What is PACELC?

An extension of CAP: if there is a Partition, choose Availability or Consistency; Else, in normal operation, choose Latency or Consistency. It captures that synchronous replication costs latency even when the network is healthy.

Is the C in CAP the same as the C in ACID?

No. ACID consistency means a transaction keeps the database within its integrity rules. CAP consistency means all replicas appear as a single up-to-date copy (linearizability).

For a ticket-booking system, CP or AP?

Seat booking needs consistency: selling the same seat twice is worse than asking a user to retry, so use a single leader or quorum writes. Browsing events and showing approximate seat counts can be served AP from caches or replicas.