CAP Theorem

As soon as data is copied to more than one machine, a question appears: what should the system do when those machines cannot talk to each other? The CAP theorem answers it. It says that while the network between the copies is broken, a system cannot both answer every request and guarantee that every answer is up to date. It must choose. This topic explains the choice, what it really means, and how real systems make it.

The three properties

Consistency (C): every read returns the most recent write. The system behaves as if there were a single up-to-date copy of the data.
Availability (A): every request to a working node receives an answer, without waiting indefinitely.
Partition tolerance (P): the system keeps operating even when the network splits the nodes into groups that cannot reach each other.

Normal operation: no conflict

Two nodes keeping a copy of the same data in step while the network works

A user writes x = 2 to node A, and node A copies it to node B. Another user reads x from node B and gets 2. While the network works, the system is both consistent and available. Nothing has to be given up.

A partition: the choice

During a partition, node B must either refuse the read or return a possibly old value

Now the link between the nodes fails. A user writes x = 3 to node A, but the update cannot reach node B. Another user asks node B for x. Node B has two options:

Choose consistency (CP). Refuse to answer, or return an error, because it cannot be sure its value is the latest. The data is never wrong, but some requests fail until the network recovers.
Choose availability (AP). Answer with the value it has, x = 2, knowing it may be out of date. Every request is answered, but some answers are stale, and the copies must be reconciled once the network recovers.

It cannot do both. To return the latest value it would need to reach node A, and it cannot.

The common misreading: "pick two of three"

CAP is often summarised as "choose any two of consistency, availability and partition tolerance". Eric Brewer, who proposed it, wrote in 2012 that this "2 of 3" formulation "was always misleading because it tended to oversimplify the tensions among properties". Two points matter:

Partitions are not optional. Networks do fail, so a distributed system has to tolerate partitions. The real choice is between C and A, and only while a partition is happening.
Most of the time there is no conflict. Brewer notes that partitions "are rare", and that "there is little reason to forfeit C or A when the system is not partitioned". A well-designed system can be both consistent and available almost all of the time, and decides in advance what to give up during the rare failure.

He also points out that "all three properties are more continuous than binary". Real systems choose degrees: how stale a read may be, how long to wait before giving up.

Real systems

Amazon Dynamo: availability first

Amazon's Dynamo paper describes a key-value store built for services such as the shopping cart, where "customers should be able to view and add items to their shopping cart even if disks are destroyed by tornados". To achieve that, the paper states, "Dynamo sacrifices consistency under certain failure scenarios". It is "an eventually consistent data store; that is all updates reach all replicas eventually", and conflicting versions are detected and reconciled later. Rejecting a customer's update was judged worse than briefly showing an older cart.

Google Spanner: consistency first

Google describes Spanner as its "highly available global-scale distributed database" that "provides strong consistency for all transactions". Brewer's 2017 paper on Spanner notes that this combination "is generally considered impossible due to the CAP Theorem", and sets out to show "how Spanner achieves this combination and why it is consistent with CAP". The paper is the best place to read how it is done.

The lesson

Neither choice is better in general. It depends on what a wrong answer costs compared with no answer:

Prefer consistency where stale data causes real harm: bank balances, stock counts during checkout, seat bookings, usernames that must be unique.
Prefer availability where a slightly old answer is acceptable: social feeds, like counts, product reviews, shopping carts.

Many systems choose per operation. Cassandra and DynamoDB, for example, let each request choose how many replicas must respond, trading consistency against availability and speed.

How to use this in an interview

When data is replicated, say explicitly what happens during a network partition.
Justify the choice from the product: "a stale like count is fine; a double-booked seat is not".
Avoid "this system is CA". With replication across machines, partitions must be tolerated; say instead which of C or A you keep when one occurs.

Implementing it in your project

Most databases let you choose where you sit between consistency and availability:

PostgreSQL replication: asynchronous replicas (the default) keep the primary available if a replica is down, but a failover can lose the last few transactions. Synchronous replication makes the primary wait for a replica to confirm each commit, which is safer but stalls writes if no synchronous replica is reachable.
Cassandra: each request chooses a consistency level, such as ONE for availability and speed, or QUORUM for consistency.
DynamoDB: reads are eventually consistent by default; a strongly consistent read can be requested per call, at a higher cost.

Decide per kind of data: strict for money, stock and unique names; relaxed for feeds, counters and recommendations.

Sources and credibility

Everything above is written from scratch; the only quotes come from the sources below, attributed where used.

Primary (highest confidence)

CAP Twelve Years Later: How the "Rules" Have Changed, Eric Brewer, 2012 (first published in IEEE Computer). Source of the definitions and the quotes on "2 of 3", rare partitions and continuous properties.
Spanner, TrueTime and the CAP Theorem, Eric Brewer, Google, 2017. Source of the Spanner description; the quotes are from its abstract.
Dynamo: Amazon's Highly Available Key-value Store, DeCandia et al., SOSP 2007. Source of the shopping cart example and the quotes on consistency.

Academic (the origin of the idea)

Brewer proposed the conjecture in a keynote at the ACM PODC conference in 2000; Gilbert and Lynch published a formal proof in 2002.

On copyright: the diagrams on this page were drawn for this article, and the explanations are original. Quoted phrases are short and attributed.