Distributed systems · 15 min

CAP theorem

When the network between two copies of your data breaks, each side must either refuse some requests or risk a wrong answer. You choose which, ahead of time.

Two data centres lose their link. A fan in each city taps Buy for the last ticket at the same moment. What should each server say?

Here are the details. Your ticket site runs in two data centres, one in Tokyo and one in Osaka, so customers get quick answers and one fire can’t take the whole site down. Each keeps its own copy of the ticket count for tonight’s concert. Both copies say 1.

At 20:00 a construction crew cuts the cable that connects Osaka’s data centre to the company’s other sites. Each data centre still talks to its own customers, but not to the other. Aiko, in Tokyo, taps Buy. Two milliseconds later Ren, in Osaka, taps Buy. Decide what you would have each server say before you read on.

Bad answer one: both say yes

Tokyo checks its copy, sees 1, sells to Aiko and sets its copy to 0. It tries to tell Osaka, but the message can’t get through.

Osaka checks its own copy. It still says 1, because nothing from Tokyo has arrived. Osaka sells to Ren. Both fans see “It’s yours!” within a millisecond.

At 20:40 the cable is fixed and the two copies compare notes. There are two sales and one seat. One of those fans is about to get an email they will not enjoy.

Bad answer two: Osaka says “try again”

Osaka can’t know whether Tokyo has sold the ticket. The only way to be sure it never sells the seat twice is to refuse: “We can’t confirm right now. Please try again.”

Now nobody is double-booked, but Ren gets an error from a server that is working perfectly. If the cut lasts 40 minutes, every Osaka customer gets errors for 40 minutes.

The rule, said precisely

Eric Brewer put this forward in 2000, and Seth Gilbert and Nancy Lynch proved it in 2002. It is named after three properties, and two of them mean something stricter than their everyday words.

The CAP theorem: during a network partition, a system that keeps copies of data in more than one place can’t be both consistent and available. Each side must either refuse some requests (keep C, give up A) or answer from its own copy (keep A, give up C).

A system that refuses is called CP: consistent during a partition. A system that answers is called AP: available during a partition. Bad answer one was AP. Bad answer two was CP.

The proof is the puzzle you just did. Osaka has no way to learn what Tokyo did. If Osaka answers, Tokyo may have done something that makes the answer wrong. If Osaka must never be wrong, it must not answer. No clever code fixes this, because no message gets through.

When the cable is fine, you get both

With the link up, Tokyo sells to Aiko and copies the sale to Osaka a few milliseconds later. When Ren taps Buy, Osaka says “Sorry, sold out.” That is a real answer (available) and a correct one (consistent).

So CAP doesn’t say your system is always broken in one way. It says what happens in the rare minutes the network splits, and you decide that in advance, in code.

Who refuses, and who keeps selling?

First, how the CP version sells at all. Tokyo is the leader, the one server allowed to make sales. When Ren taps Buy in Osaka, Osaka passes the order to Tokyo and relays the answer. Osaka keeps a copy, like the followers in the Replication article on this site. With the link up, Tokyo waits for Osaka to confirm each sale, so Osaka’s copy is always exact and it can answer “how many left?” on its own.

During a cut, refusing on both sides would be safe and useless. So the servers vote on who may keep selling, and only a side with a majority (more than half the votes) may. With just Tokyo and Osaka, each side has 1 of 2 votes, and neither has more than half.

So designers add a third voter: a small tie-breaker server in a third city, say Nagoya, that stores no tickets and only votes. MongoDB calls this an arbiter. It does nothing while the link is up; it only matters during a cut.

Our cut isolated Osaka, so Tokyo can still reach Nagoya. Tokyo has 2 of 3 votes and keeps selling; before each sale it checks with Nagoya that it still has them (4 ms there and back), so nobody else can have taken over. Osaka has 1 of 3 and refuses. When the link heals, Osaka copies the sales it missed from Tokyo. Had the cut isolated Tokyo instead, Osaka and Nagoya would hold the majority, Osaka would take over as leader, and Tokyo would refuse. The Raft article on this site shows how servers run such votes safely.

If both say yes, someone cleans up later

An AP system sells to Aiko and Ren. When the link comes back, the copies swap notes and find a conflict.

There are two common ways to settle it:

• Last write wins (LWW): keep the change with the later timestamp and throw the other away. Ren tapped 2 ms later, so Ren keeps the ticket. Aiko was told “It’s yours”, and her sale silently disappears unless you add code to tell her. Cassandra settles conflicting writes this way by default.
• Compensate: keep one sale by a rule you choose (here, the first tap wins), then make the other customer whole in the real world: a refund, an apology, maybe a voucher. Airlines do this when a flight is overbooked.

So AP does not make the problem go away. It moves it from “an error now” to “an apology later”. That is a good trade when the apology is cheap.

The price you pay every day: waiting

Partitions are rare. A CP system pays something on every request, even when nothing is broken: to be sure Osaka’s copy is right before Aiko hears “It’s yours”, Tokyo sends the sale to Osaka and waits for “got it”.

Tokyo and Osaka are about 400 km apart. Cables follow roads and railways, so call it 500 km of fibre. Light in fibre covers about 200 km per millisecond, so one way takes 500 ÷ 200 = 2.5 ms and there and back takes 5 ms. Cables don’t run straight and every router on the way adds a little delay, so measured round trips between the two cities come out at about 8 ms.

A system built to answer during a cut (AP) usually doesn’t wait in normal times either: it answers from its own copy and sends the change across afterwards. That is why the demo’s CP sale takes 9 ms (1 ms of work plus 8 ms of waiting) and its AP sale takes 1 ms. A checkout that makes 20 such writes one after another pays 20 × 8 = 160 ms in CP. Between Tokyo and London, where a round trip is about 220 ms, every confirmed write would cost a quarter of a second.

In a 2012 paper, Daniel Abadi called this PACELC, read in two halves. P-A-C: if there is a Partition, choose Availability or Consistency. E-L-C: Else, choose Latency (speed) or Consistency. CAP is only the first half; the second is the one you live with most days.

Who leans which way

Real systems pick per kind of data, based on which hurts more: an error now or a wrong answer later.

• Bank balances and payments lean CP. A transfer that says “try again” is annoying; money that exists twice is a disaster.
• Leader-based databases lean CP. etcd and ZooKeeper, small databases other systems use to store settings and choose leaders, use majority voting, so the side of a split without a majority stops taking writes.
• Shopping carts lean AP. Amazon’s 2007 Dynamo paper describes a cart that always accepts “add to cart” and merges copies later. The merge keeps every item any copy has, so if only one copy saw you remove an item, it comes back.
• DNS (the system that turns a name like kizukulab.com into a server address) and like counts lean AP. An address a few hours old, or 1,203 likes when the truth is 1,205, beats an error.

Choosing for the ticket site

Now you can answer the puzzle as a designer instead of guessing:

• The step that takes payment and assigns the seat: CP, with a tie-breaker in a third city. During a rare cut, Osaka’s buyers see “please try again” and Tokyo’s don’t notice anything.
• The “3 tickets left” badge on the event page: AP. Osaka shows its own copy, and a count a few seconds old is fine.
• The 8 ms wait per sale in normal times: acceptable, because a purchase happens once and a correct answer matters more than 8 ms.
• For a 10,000-seat show, give each city its own block of seats, say 5,000 each. Neither side has to ask the other before selling, so there is nothing to conflict, until one side runs out and has to ask for more.

The last ticket is the hard case because it can’t be split. Somewhere a cable will be cut. CAP doesn’t let you avoid the choice; it lets you make it on purpose, before Aiko and Ren tap Buy.