CAP theorem simulator

The simulator keeps three copies, or replicas, of a single value called x. Client 1 talks to replica R1 and client 2 talks to replica R3. While the network is working, every write is copied to all three replicas, so both clients always read the same value.

Press Cut the network to separate R3 from R1 and R2, then write and read from both clients:

• With Prefer consistency (CP), a replica answers only if it can reach a majority of the replicas, which here means two of the three. R1 and R2 can, so client 1 keeps working. R3 cannot, so client 2's requests are refused.
• With Prefer availability (AP), every replica answers. Client 2 can keep writing to R3, but its reads may return an old value, and the two sides drift apart.

Press Repair the network to see how the replicas catch up. In AP mode, if both sides accepted writes, the simulator keeps the most recent one, a rule called "last writer wins", and the writes from the other side are lost even though they were acknowledged. The counters at the top count what happened.

The model is deliberately small. Real systems add leaders, timeouts, retries and more replicas, and many use smarter ways of merging conflicting writes than "last writer wins". They still face the same choice whenever replicas cannot reach each other.

The CAP theorem says that a distributed data store cannot guarantee all three of the following properties at the same time:

• Consistency: every read returns the most recent write, or an error;
• Availability: every request to a working node gets a response;
• Partition tolerance: the system keeps working even when the network loses messages between nodes.

Network failures cannot be ruled out in a system that runs on more than one machine, so the theorem is usually read like this: when the network splits, a system has to choose between consistency and availability. It can refuse some requests so that it never gives an out-of-date or conflicting answer, or it can answer every request and accept that some answers may be out of date.

The idea was put forward by Eric Brewer in 2000 and proved by Seth Gilbert and Nancy Lynch in 2002. It is also known as Brewer's theorem.

Gilbert and Lynch's proof uses precise definitions, and these differ from the everyday meaning of the words.

Consistency

Consistency in CAP means linearizability. The system behaves as if there were a single copy of the data, and each operation takes effect at one instant between the moment it starts and the moment it finishes. Once a write has completed, every later read, from any client and any node, returns that value or a newer one.

Availability

Availability means that every request received by a node that has not failed eventually gets a response that is not an error. This is a strict requirement. A system that answers only from the side of a partition that holds a majority of the nodes is not available in this sense, even if most clients never notice the difference.

Partition tolerance

Partition tolerance means the system keeps working even if the network loses any number of messages between nodes. A partition is a period in which some nodes cannot communicate with others, for example because a switch fails, a firewall rule is wrong or the link between two data centres is cut. The nodes themselves are still running.

The argument needs only two replicas. Suppose replicas G1 and G2 cannot communicate. A client writes a new value to G1. To be available, G1 must accept the write and reply. Another client then reads from G2. To be available, G2 must also reply, but it has had no way of learning about the write, so it returns the old value, and consistency is broken.

No algorithm can avoid this, because G2 cannot tell this situation apart from one in which no write happened at all. That is the core of Gilbert and Lynch's proof. In practice, each side of a partition has two options:

• refuse requests until it can be sure it has the latest data, which gives up availability (a CP choice); or
• keep answering, and reconcile the differences once the network recovers, which gives up consistency (an AP choice).

Here is one sequence of steps run through the simulator above twice, once in each mode. Client 1 writes before the network is cut, so all three replicas hold x = a1. The network is then cut, leaving R1 and R2 on one side and R3 on the other. Both clients write, then both read, then the network is repaired.

"Pick any two of three"

The popular summary is misleading. Partition tolerance is not optional for a system that runs on more than one machine, because networks do fail. The choice applies only while a partition lasts, and only between consistency and availability. When the network is working, a system can be both consistent and available. Brewer made this point himself in 2012.

"CA" systems

A database on a single server is sometimes called CA. It has no network between replicas that could split, so the question does not arise. But if that server, or its own network connection, fails, the database is simply unavailable. The label is only meaningful for systems that do not replicate across a network.

Every system is either CP or AP

Many real systems are neither in the strict sense of the theorem. A database with one leader and asynchronously updated followers can lose acknowledged writes when the leader fails, so it is not consistent; and clients that cannot reach the leader cannot write, so it is not available either. In 2015 Martin Kleppmann argued that it is more useful to describe the guarantees a system offers than to label it CP or AP. Many databases also let each request choose its own trade-off.

Consistency means the same as in ACID

The C in ACID means that a transaction leaves the database in a valid state that satisfies its rules and constraints. The C in CAP means linearizability. They are unrelated properties that happen to share a word.

CAP describes performance

The theorem says nothing about how fast a system is when the network is healthy. That trade-off is the subject of PACELC, described below.

Eric Brewer, a professor at the University of California, Berkeley and a co-founder of the search company Inktomi, presented the idea as a conjecture in his keynote at the ACM Symposium on Principles of Distributed Computing (PODC) in July 2000. In 2002 Seth Gilbert and Nancy Lynch of MIT published a formal proof in SIGACT News, in a paper titled Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services.

In 2012 Brewer published CAP Twelve Years Later: How the "Rules" Have Changed in IEEE Computer. He argued that the "two of three" formulation is misleading and that designers should think instead about how a system behaves during a partition and how it recovers afterwards. In 2017 he described Google's Spanner database as technically CP but "effectively CA": Google's private network makes partitions rare enough that Spanner is almost always available in practice.

A related but different result is the FLP impossibility proof of 1985 by Fischer, Lynch and Paterson, which shows that agreement between processes cannot be guaranteed in a fully asynchronous network if even one process may crash.

The CAP theorem only describes what happens during a partition. Daniel Abadi pointed out that replicated systems face a second trade-off all the time: even when the network is working, keeping replicas consistent means waiting for messages between them, and that adds latency. He described the idea in a blog post in 2010 and in an article in IEEE Computer in 2012, using the name PACELC:

If there is a partition, the system trades availability against consistency; else, when the system is running normally, it trades latency against consistency.

In Abadi's article, Dynamo, Cassandra and Riak are PA/EL: they favour availability during a partition and low latency otherwise. VoltDB/H-Store and Megastore are PC/EC. MongoDB was classed as PA/EC and Yahoo's PNUTS as PC/EL. Many of these systems can now be configured to behave differently, so the labels describe default designs, not fixed rules.

Most production systems do not fit neatly into one category, and many can be configured per request. These are their usual behaviours during a partition. Check each system's documentation for the version and settings you use.

The question to ask is what is worse for this piece of data: a request that fails, or an answer that is wrong or later undone. The same application often answers it differently for different data.

The consistency in CAP is linearizability, defined by Maurice Herlihy and Jeannette Wing in 1990. It is about individual operations on individual objects, and it respects real time: once a write has completed, every later read sees it.

Serializability, which comes from database transaction theory in the 1970s, is a different guarantee. It says that concurrent transactions produce the same result as if they had run one at a time in some order, but that order does not have to match real time. Strict serializability combines the two; Spanner and FoundationDB are examples of databases that offer it.

Many systems offer weaker models, such as causal consistency, read-your-writes or eventual consistency, which allow more availability or lower latency. The Jepsen project's consistency-models page shows how these models relate to each other.

A node cannot see a partition directly. It only notices that messages from another node have stopped arriving, and that could also mean the other node has crashed or is just slow, for example during a long garbage-collection pause. Systems therefore rely on heartbeats and timeouts.

Choosing the timeout is a trade-off. A short timeout causes unnecessary failovers when a node is merely slow; a long one leaves the system waiting for a node that has died. etcd's defaults, for example, are a 100 ms heartbeat interval and a 1,000 ms election timeout. Cassandra and Akka use the φ accrual failure detector (Hayashibara and others, 2004), which reports a level of suspicion that grows the longer a heartbeat is overdue, instead of a simple yes or no.

Split brain happens when both sides of a partition believe they are in charge and accept writes independently, so the data diverges. Consensus protocols such as Raft and Paxos prevent this by requiring a majority to agree on a leader; only one side of a partition can contain a majority. An old leader on the minority side may still think it is the leader for a short time, but it cannot get a majority to accept its writes.

For locks and leases, a common extra safeguard is a fencing token: a number that increases each time the lock is granted. The storage system rejects any request carrying an older token, so a client whose lease has expired cannot overwrite newer data. Martin Kleppmann described the technique in 2016, and Google's Chubby lock service uses a similar mechanism called sequencers.

GitHub's outage of 21 October 2018 shows what can go wrong. A loss of connectivity of 43 seconds between its US East Coast network hub and its main data centre led its failover tooling to promote database servers on the West Coast. Writes ended up in both places, and reconciling them took GitHub a little more than 24 hours of degraded service.

Jepsen, a project started by Kyle Kingsbury in 2013, tests distributed databases by cutting the network, skewing clocks and crashing nodes while a workload runs, then checking whether the results match the guarantees the database claims. Its analyses have found problems in many systems, including Redis Sentinel and early versions of MongoDB, and vendors often fix the issues it reports. The published analyses are one of the best public records of how databases behave during partitions.

The CAP theorem comes up whenever a design replicates data across machines or data centres. Naming it is not enough; what an interviewer wants to hear is a decision for each kind of data and what it costs. A good answer:

• Treats partitions as given. The choice is between consistency and availability while the network is split, not “two of three”.
• Chooses per data type. Payments and inventory on a consistent store; carts, sessions, feeds and caches on an available one.
• Names the mechanism. Majority quorums or a consensus protocol such as Raft for CP; replication with conflict resolution (last writer wins, version vectors or CRDTs) for AP.
• Covers the normal case too. Synchronous replication across regions adds round trips to every write even with no partition. That is the latency side of PACELC.
• Says what happens on recovery. How diverged copies are merged, and which acknowledged writes can be lost.