The CAP Theorem

Replication, in the previous module, creates copies of your data for safety and read scale. It also raises a new question: what happens when the copies cannot talk to each other, even briefly? Cables get cut, switches fail, and a link between two regions can drop for seconds or minutes. The CAP theorem is the precise answer, and it is one of the most quoted ideas in system design, so it is worth understanding properly rather than as a slogan.

A couple share an account with $100 in it. The account is kept in two branches, and the branches keep each other up to date by phone. Then the phone line between the branches goes down. The wife asks Branch A for $100, and at the same moment the husband asks Branch B for $100. Each branch has two options. It can refuse until the phone line is back, so that it never gives out money the other branch may already have paid. Or it can go ahead with its last known balance, so the customer is served, and sort out any overdraft later.

• -The two branches are two replicas of the same data.
• -The broken phone line is a network partition: the replicas are alive but cannot reach each other.
• -Refusing until the line is back keeps the data correct (consistent) but turns a customer away (not available).
• -Serving from the last known balance keeps every customer served (available) but the two branches may now disagree, so the account could go to minus $100 (not consistent).

The CAP theorem says that when a network partition happens, a distributed data store has to choose between consistency and availability. Its three letters mean:

• -Consistency (C): every read returns the most recent write, or an error. All clients see the same data at the same time.
• -Availability (A): every request to a node that is working gets a real response, not an error, even though it might not be the latest data.
• -Partition tolerance (P): the system keeps working even when messages between nodes are lost or delayed.

CAP is often shown as pick any two of three, which makes it sound like a menu. It is not. The moment your data lives on more than one machine, a partition is something that will happen: a failed switch, a congested link, a long pause that makes a healthy node look dead. You cannot promise it never occurs, so partition tolerance is not something you can choose to drop. A system that claims to be CA is really one that runs on a single machine, or one that simply stops working when a partition happens. The real decision is what to do when the partition arrives: protect consistency, or protect availability.

The diagram shows the situation: the link between the leader and its replica in another region has been cut.

Say a user's balance is 100 on both replicas, and then the link is cut. A client asks the isolated replica to withdraw 100, while another client asks the leader to withdraw 100.

• -A CP system protects consistency. The isolated replica cannot confirm it has the latest data, so it returns an error (or waits) for the withdrawal. No overdraft is possible, but some requests fail until the partition heals. ZooKeeper and etcd lean this way.
• -An AP system protects availability. Both sides accept the withdrawal, so everybody is served. When the partition heals, the balance has become minus 100 and the system must merge the two histories using some rule. Cassandra and DynamoDB lean this way, and both let you tune the behavior per request.

The choice is not made once for a whole product. It is made for each kind of data, by asking which is worse: an error, or a wrong answer for a while?

• -Account balances, the last seat on a flight, a unique username: a wrong answer causes real harm, so choose consistency and accept some errors during a partition.
• -Like counts, view counts, a shopping cart, a social feed: a slightly stale answer harms nobody, but an error loses a sale or annoys a user, so choose availability and reconcile later.

One more thing the theorem does not say: even with no partition, there is a trade-off. Keeping replicas strictly in step means waiting for them, which costs latency. This extension is sometimes called PACELC: if there is a partition, choose availability or consistency; else, choose latency or consistency. The Wiki card below walks through CAP with real systems: