CAP & PACELC Deep Dive
What the CAP theorem really proves, what PACELC adds for the time when the network is healthy, and how to choose consistency feature by feature, with Spanner, DynamoDB, Cassandra and Cosmos DB as worked examples.
Overview
The CAP theorem is the most quoted result in distributed systems and one of the most misquoted. It does not say 'pick any two of three'. It says something much narrower: while the network between replicas is broken, a system cannot both answer every request and keep every answer up to date. Outside that situation, it says nothing at all.
PACELC, set out by Daniel Abadi in a 2012 paper, fills that gap. Partitions are rare, but replication happens on every write, and waiting for other copies costs time on every request. So a design has two separate choices to make: what to give up during a partition, and what to give up on a normal day.
This chapter goes deeper than the short CAP and PACELC summary in Fundamentals. It covers the precise definitions and the proof, why labels such as CP, AP and CA mislead, how real databases let you pick consistency per request and what that costs, how Spanner uses TrueTime, and what actually happens on each side of a partition. For the menu of consistency models see Strong vs Eventual Consistency, and for quorum arithmetic see Quorum Consensus.
What you will be able to do
- State CAP precisely, sketch its proof, and say what it does not cover.
- Explain why 'pick two of three' and 'CA system' mislead, and what to say instead.
- Classify a database with PACELC, and show how its settings change the label.
- Tell linearizability, serializability and strict serializability apart, with an example.
- Choose consistency per feature in a design interview, and say what each choice costs during a partition and on a normal day.
Key concepts
- CAP theorem
- Linearizability
- CAP availability
- Network partitions
- PACELC
- Strict serializability
- Tunable consistency
- TrueTime
- Partition recovery
- Conflict resolution
Interview questions
- What does the CAP theorem actually prove, and what does it leave out?
- Why is 'pick two of three' misleading, and can you build a CA system?
- What does PACELC add, and how would you classify Cassandra, DynamoDB, MongoDB and Spanner?
- Explain linearizability, serializability and strict serializability with an example.
- Is ZooKeeper a CP system? Is etcd?
- How can Spanner claim to be 'effectively CA', and what does TrueTime actually do?
- A partition splits a five-node Raft cluster three to two, with the old leader on the small side. What happens?
- Two replicas accepted conflicting writes during a partition. How do you reconcile them?
- Apply CAP and PACELC to a ticket booking system.
- What does it cost to make every read strongly consistent, just to be safe?
Sign up free to read the full topic
More System Design topics
Start free on Cariara · Coding problems · System design studio