System design deep dive
CAP Theorem: deep dive
The CAP theorem says that when a network partition splits a distributed system, each node must either refuse some requests to stay consistent or answer them and risk returning stale data. Understanding what CAP does and does not claim, and its PACELC extension, separates strong candidates from those reciting a slogan.
What the three letters actually mean
- Consistency in CAP means linearizability: every read sees the most recent completed write, as if there were one copy of the data. This is not the C in ACID.
- Availability means every request to a non-failed node gets a non-error response, eventually. A node that times out or returns try later is not available in this sense.
- Partition tolerance means the system keeps operating when messages between nodes are lost or delayed indefinitely.
Because partitions happen in any real network (switch failures, misconfigured firewalls, long GC pauses that look like partitions), you cannot opt out of P. So CAP is really a choice made at the moment of a partition: preserve consistency or preserve availability.
How a partition forces the choice, step by step
- A key
stock:sku1with value 5 is replicated across three nodes: A and B in Mumbai, C in Singapore. - The link between the regions fails. A and B can talk to each other; C is isolated.
- A client in Singapore sends a write
stock:sku1 = 4to node C. - A CP system requires a majority (2 of 3). C cannot reach a majority, so it rejects the write or times out. Data stays consistent, but Singapore users see errors.
- An AP system lets C accept the write locally and return success. Meanwhile, a Mumbai client may read 5 from A. Both sides stay available, but they disagree.
- When the link heals, the AP system must reconcile divergent versions using last-write-wins timestamps, vector clocks, or application-specific merges; the CP system simply resumes.
PACELC: the trade-off that matters day to day
Partitions are rare, but latency is constant. PACELC says: if there is a Partition, choose Availability or Consistency; Else, even when everything is healthy, choose Latency or Consistency. Waiting for a cross-region replica to confirm every write costs tens of milliseconds even with no failure at all. Many systems are tuned for low latency in the normal case and accept weaker consistency, which is a choice CAP alone does not describe.
| System | During partition (PA/PC) | Normal operation (EL/EC) | Typical use |
|---|---|---|---|
| Cassandra, default settings | PA | EL | High write volume, time-series, feeds |
| DynamoDB, eventually consistent reads | PA | EL | Key-value at massive scale |
| MongoDB, majority writes and reads | PC | EC | General documents needing correctness |
| Google Spanner, CockroachDB | PC | EC | Global transactions, financial data |
| ZooKeeper, etcd | PC | EC | Leader election, configuration, locks |
Choosing CP or AP in a design
Decide per feature, not per company. A payment ledger, inventory decrement at checkout, or a username uniqueness check should be CP: a short outage is better than double-spending or two users with the same handle. A like counter, a news feed, a shopping cart, or presence indicators can be AP: showing slightly stale data is harmless, and errors would hurt the experience. One product often uses both, for example strongly consistent orders alongside an eventually consistent product catalog. See ACID vs BASE for how this shows up in transaction models.
Common mistakes in interviews
- Saying pick any two, as if you could choose CA for a distributed system. Without partitions you do not need CAP at all.
- Confusing CAP consistency (linearizability) with ACID consistency (constraints and invariants hold).
- Labelling a database as permanently CP or AP when most are tunable per request through quorum settings.
- Ignoring latency, which is the trade-off you pay every second, not just during rare partitions.
Interview questions
›Why is a CA distributed system not possible?
A system spread over a network will experience partitions eventually, and at that moment it must either reject requests or risk inconsistency. A single-node database can be consistent and available, but only because it has no network between replicas to partition.
›How do quorums relate to CAP?
With N replicas, writes acknowledged by W nodes and reads consulting R nodes, choosing R + W > N ensures every read overlaps the latest write, giving strong reads. During a partition, a side that cannot gather W or R nodes must refuse requests, which is the CP choice. Lowering R or W favours availability and latency.
›Is DynamoDB CP or AP?
It is tunable. By default reads are eventually consistent, an AP and low-latency choice, but you can request strongly consistent reads for a key, which go to the leader replica and may fail during certain failures. Transactions add stronger guarantees at higher cost.
›What is eventual consistency, precisely?
If no new writes are made to an item, all replicas will eventually converge to the same value. It says nothing about how long that takes or what reads return in the meantime, so practical systems add guarantees like read-your-writes or monotonic reads on top.
›Which would you choose for a chat application's message store?
Mostly AP with per-conversation ordering. Users expect to send messages even during degraded network conditions, and a short delay before another region sees a message is acceptable. Ordering within a conversation can be preserved with per-conversation sequence numbers rather than global consistency.