CAP and Consistency

The problem: the link between copies breaks

Say your app runs in two data centers, Europe and the US, each with a full copy of the data, so users get quick answers and the app survives losing one. Every change is copied to the other side over the link between them. When the link breaks, both still run and take requests, but no change gets across: a network partition.

Now Ana, in the US, claims the username neo. The US copy saves it, but Europe can't hear about it. A moment later Ben, in Europe, asks for neo too, and Europe's copy says it's free. Europe has exactly two choices:

• Answer from its own copy and give Ben the name. The system stays available, but two people now own neo, and when the link is back one of them loses a name they were promised. No sync can make both claims true.
• Refuse until it can reach the US again. The system stays consistent: every answer it gives is right, but Ben gets no answer for now.

Consistent or available: choose per kind of data

Refuse when a wrong answer can't be undone; answer when an old or clashing answer is cheap to fix later:

request                  during a partition   why
transfer money           refuse               money paid out twice
claim a username         refuse               two owners of one name
book the last seat       refuse               two passengers, one seat
show a like count        answer               a few likes behind is fine
add to a shopping cart   answer               merge both carts later
load the news feed       answer               it fills in later

Carts are the classic example: Amazon's Dynamo paper describes a cart that always accepts "add to cart" and merges the versions later, so an item you removed can come back. Real systems choose per kind of data, not once for everything.

The CAP theorem, and why "pick 2 of 3" misleads

The CAP theorem names three properties: consistency (every read sees the latest write), availability (every request to a working machine gets an answer) and partition tolerance (the system keeps running when the network between its machines splits). During a partition, you can't have both C and A.

"Pick 2 of 3", the usual summary, misleads. Cables get cut, routers fail, data centers lose their network: any system spread over machines will see partitions, so P is a given. The real choice is what each side does while one lasts: refuse (CP) or answer (AP). When the network is fine, a system can be both.

Quorums: how many copies to wait for

Many stores keep each value on N copies. A write is sent to all of them but waits for only W to confirm (ack); a read asks R copies and keeps the newest version. Say N = 3 and a flight has 10 seats left, version 1 on all three copies, and a booking writes 9 seats as version 2 with W = 2. Copies 1 and 2 ack; slow copy 3 still holds version 1. A read with R = 2 can ask three pairs:

copies asked   versions seen   returns
1 and 2        v2, v2          9 seats
1 and 3        v2, v1          9 seats
2 and 3        v2, v1          9 seats

Every pair includes copy 1 or 2, so every read sees 9 seats. Now try W = 1 and R = 1: a booking writing 8 seats as version 3 is confirmed once copy 1 acks, and a read of one copy lands on copy 2 or 3, which still say 9, in 2 cases out of 3. That read shows a seat that's already sold.

The rule: every read overlaps the last write when R + W > N, because then there aren't enough copies for the two groups to miss each other. For N = 3:

W   R   R + W   every read sees the last write?
1   1   2       no
1   2   3       no
2   1   3       no
1   3   4       yes, but one copy down stops reads
3   1   4       yes, but one copy down stops writes
2   2   4       yes, and one copy can be down

W = R = 2, a majority for both, is a quorum and the usual choice: reads and writes keep working with one copy down. With 5 copies, W = R = 3 (3 + 3 = 6, more than 5) survives two copies down. Lower settings are faster but can read stale data. Stores modeled on Amazon's Dynamo, such as Cassandra, let you choose how many copies each read and write waits for; DynamoDB lets each read ask for strong or eventual consistency. The rule covers finished writes; writes that fail halfway and two writes at once need more care.

PACELC: the cost when nothing is broken

CAP only covers partitions. PACELC adds the rest of the time: if there's a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Put the 3 copies in Europe, the US and Asia, to survive losing a region. A round trip inside a data center takes about 0.5 ms, between continents about 150 ms. A user in Europe books a seat:

setting   waits for                        about
W = 1     Europe's copy                    0.5 ms
W = 2     Europe's and the first far one   150 ms

The write goes to all copies at once, so W = 2 waits for the second ack, one round trip across an ocean: about 150 ms, 300 times longer than W = 1. A read with R = 2 pays the same. A store tuned to answer from the nearest copy is called PA/EL; one that waits for a majority, PC/EC.

Consistency levels

• Strong: every read sees the latest write. Needed for a bank balance before a transfer, or the seats left when you pay for the last one. It costs the most: every read and write waits for enough copies to agree, far ones included.
• Read-your-writes: you always see your own changes; others may see them a moment later. Right for your own profile photo or comment, so it doesn't seem to vanish; one way is to read from the copy you wrote to for a while.
• Eventual: the copies agree soon after the writes stop. Fine for view counts and other people's follower counts; the fastest, and it keeps answering during a partition.

Where it shows up in system design interviews

CAP comes up whenever a design keeps copies in more than one place, often as "what happens if the link between your regions breaks?" Don't answer with one letter for the whole system. Name the data, choose for each, and say why: in a shop, payments and stock counts stay consistent and refuse during a split, because selling the last item twice or charging twice can't be undone; carts and the catalog stay available and catch up after. Then add the cost: consistent data waits for far copies, even with no partition.

Common interview questions

Is your system CP or AP?

Usually both, per kind of data. Money, stock and unique names are CP: during a partition, the cut-off side refuses. Feeds, counts and carts are AP: they answer from the local copy and catch up later, because a stale read there is cheap.

What does R + W > N guarantee?

That the copies a read asks include at least one that the last finished write reached, so the read, which keeps the newest version, sees it. With 3 copies, W = R = 2 is the common quorum.

Why is "pick 2 of 3" wrong?

Partitions happen whether you plan for them or not, so a system spread over machines can't drop P. CAP only forces a choice during one; otherwise the trade is latency against consistency (PACELC).

Summary

• Partition: the link between copies breaks; each side answers (available) or refuses (consistent).
• Per kind of data: refuse when a wrong answer can't be undone.
• CAP: partitions happen, so the choice is C or A while one lasts, not "2 of 3".
• Quorums: R + W > N means every read sees the last write.
• PACELC: with no partition, you trade latency for consistency.
• Levels: strong, read-your-writes or eventual: the cheapest each piece of data can live with.