Pointer Walk

The CAP Theorem

When the network splits, a system must either refuse some requests or risk giving different answers. It cannot avoid both.

Distributed SystemsIntermediate8 min read

Three things you want

You store data on several servers so the system survives failures. You would like three properties.

  • Consistency: every read returns the latest write. All servers appear to agree at all times.
  • Availability: every request to a working server gets a real answer, not an error.
  • Partition tolerance: the system keeps working even when the network between servers fails.

The CAP theorem says that when the network does fail, you cannot have both of the first two. You must choose.

Partitions are not optional

A partition means some servers cannot reach others. Nobody has crashed. A cable, a switch or a router between them has failed.

You do not get to opt out. Networks fail. So "partition tolerance" is not really something you pick. It is a fact you must cope with.

That leaves a single real question: when a partition happens, what do my servers do?

The moment of choice

Two servers each hold a copy of a stock count. The link between them breaks. A client asks one of them to change the count.

That server cannot tell the other about the change. It has exactly two options.

Option 1: refuse

Choosing consistency: refuse when unsureInteractive
Client 1
Server A
stock = 5
Server B
stock = 5
Client 2

Two servers each hold a copy of the stock count: 5 items.

The server will not accept a change it cannot share. The client gets an error. No one ever reads a wrong number. The system stayed consistent and gave up availability.

Option 2: answer anyway

Choosing availability: always answerInteractive
Client 1
Server A
stock = 5
Server B
stock = 5
Client 2

Two servers each hold a copy of the stock count: 5 items.

The server accepts the change. The client is happy. The other server, cut off, goes on giving the old number. The system stayed available and gave up consistency.

There is no third option. Either the server answers, and risks being wrong, or it declines, and is unavailable. That is the entire theorem.

Choosing consistency: refuse when unsureInteractive
During a split
Client 1
Server A
stock = 5
Server B
stock = 5
Client 2

Two servers each hold a copy of the stock count: 5 items.

Which to choose

It depends on which mistake is worse for your data.

DataA wrong answer meansAn error meansUsually choose
Bank balanceMoney created or lostA customer retries laterConsistency
Seat or ticket bookingThe same seat sold twiceA customer retriesConsistency
Locks, leader electionTwo things both believing they are in chargeA short pauseConsistency
Shopping cartAn item reappears after removalA lost saleAvailability
Likes, view countsA slightly wrong number for a whileA broken pageAvailability
Social feedA post shows up a little lateA blank screenAvailability

Example

The same company, both answers

An online shop does not make one choice for everything.

The product catalogue and the cart stay available during a partition: showing a slightly old price is better than showing nothing.

The payment step chooses consistency: charging a card twice or selling stock that does not exist is worse than asking the customer to wait.

What CAP does not say

The theorem is often quoted as "pick two out of three". That is misleading in three ways.

  • It only applies during a partition. When the network is healthy, which is most of the time, a system can be both consistent and available.
  • It is not all or nothing. A system can refuse writes but still serve reads. It can be consistent for one kind of data and available for another.
  • It says nothing about speed. Even with a perfect network there is a trade between consistency and delay: waiting for every copy to confirm a write is safer and slower. See Replication and Replication Lag.

After the partition heals

A system that chose availability has a job to do when the link returns: the two sides may have accepted different changes, and they must be reconciled.

  • Last write wins. Keep whichever change has the later timestamp. Simple, and it silently throws away the other one.
  • Merge. For some data both changes can be kept. Two carts are combined. Two sets of likes are added together.
  • Ask. Keep both versions and let the application, or a person, decide.

A system that chose consistency has nothing to reconcile, because it never let the two sides drift apart. The mechanism for that is a majority vote. See Split Brain and Quorum.

Key takeaways

  • Consistency means everyone sees the latest data. Availability means every request gets an answer.
  • When the network splits, a server must either refuse requests or risk giving out-of-date answers.
  • Partitions happen whether you plan for them or not, so the real choice is between consistency and availability.
  • Choose consistency where a wrong answer is costly, and availability where an error is worse.
  • The trade-off only bites during a partition, and can be made differently for different data.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress