CAP and consistency

  • Lesson 16 of 40
  • 12 min
  • Intermediate
  • 11 steps

While the network works, keeping several copies is almost free. The day it breaks, each copy must decide: answer with what it knows, or refuse so it is never wrong.

Failed requests
0%
Conflicts
0
Copies
3
Under partition
—
South regionNorth regiondatadatasouth usersnorth usersclientcopy 1copy 2copy 3left: 1left: 1replicationleft: 1can't reach the southnetwork partitionleft: 1rejects purchases and readserrornetwork partitionleft: 0 · sold to Lucíaleft: 0 · sold to Marknetwork partitionleft: 0 · Lucíaleft: 0 · LucíaMark: refundedexchanging what they missed10:15:06 · 8 Elm10:15:04 · 18 Elmhighest stamp winsWhich clock rules?10:15:02 realnorth saves "8 Elm"stamp 10:15:06its clock runs 4 s fast10:15:04 realsouth saves "18 Elm"stamp 10:15:04clock on time10:15:06 winsthe old addressexample timesleft: 0left: 0replicationDuring a partition, chooseC: refusenever gives old datagood forpayments, stock, bookingsA: answermay give old datagood forlikes, carts, feedsno partition: latency or consistencyv2v2v1 · oldN = 3, W = 2, R = 2writewaits for 2 of 3readasks 2, uses the newestW + R = 4 > 3they always overlapv2v2v2Choose per operationlikeW = 1, R = 1 · fast, eventualpaymentW = 2, R = 2 · slower, safedecideswhat being wrong costsv2v2v1 · oldStrongest to weakestlinearizableeveryone sees the latest writecausalcause before effectread your writesyou see your own changesmonotonicyou never go back in timeeventualcopies converge… laterread your writes and monotonic are not rankedv2v2v1 · oldN = 3, W = 2, R = 2writewaits for 2 of 3readasks 2, uses the newestW + R = 4 > 3they always overlap
  • request
  • response
  • slow request

Step 1 of 11

Concept

One copy on each continent

An online shop stores its data in two regions: one in South America and one in North America. Each user talks to the nearest one and gets fast answers. Every write is replicated to the other region.

A console is on sale and there is 1 unit left. Both copies know it and agree.

Step 2 of 11

Problem

The network splits in two

The link between the regions fails. The servers on each side are still healthy and their users reach them fine, but the two regions can no longer talk to each other. That is a network partition.

Right then, someone in North America wants to buy the last console. The northern copy cannot ask the southern one whether it is still available. What should it do?

What changed

  • The link between regions goes down

Step 3 of 11

Technique

Option 1: never be wrong

Refuse whatever you cannot confirm. The primary copy lives in South America, so that side keeps serving. The northern side rejects purchases, and also reads that could be out of date, until the link is back.

Nobody sees wrong data, but northern users get errors for as long as the partition lasts. In this example each region receives half of the traffic, so 50 % of requests fail.

What changed

  • The northern side rejects requests
  • Errors for northern users

Step 4 of 11

Technique

Option 2: always answer

Answer with what you have. Both regions keep accepting writes. Lucía, in Lima, buys the last console. Mark, in Toronto, also buys the last console.

Everyone gets an answer and there is not a single error, but the copies no longer match. When the link returns there will be two sales of a single unit.

What changed

  • Both regions accept writes
  • The same unit, sold twice

Step 5 of 11

Solution

When the network returns: eventual consistency

The link is repaired and each copy sends the other the writes it missed. If no new writes arrive, they end up equal: that is eventual consistency. But someone has to decide what to do with the conflict.

You can keep the latest write (last write wins: simple, but it drops one sale without telling anyone) or let the application settle it: keep one sale, refund Mark and apologise.

What changed

  • The link is back
  • The copies exchange what they missed
  • Conflict resolved: Mark refunded

Step 6 of 11

Problem

"Last" by which clock?

To know which write came last, each server stamps it with the time on its own clock, and clocks drift. In this example, the northern server's clock runs 4 seconds fast.

A customer saves her delivery address, "8 Elm St", at 10:15:02 through the northern copy, which stamps it 10:15:06. Two seconds later she corrects it to "18 Elm St" through the southern copy, which stamps it 10:15:04.

The correction is newer, but its stamp is smaller. On sync, 10:15:06 wins: the old address stays and the correction vanishes without anyone noticing.

What changed

  • The northern clock runs 4 s fast
  • The newest write carries the oldest stamp
  • The wrong address is kept

Step 7 of 11

Concept

What the CAP theorem really says

The CAP theorem says that, when there is a network partition (P), a replicated system has to give up either consistency (C: every read sees the latest write, as if there were a single copy) or availability (A: every request that reaches a working server gets a response that is not an error).

It is not about "picking two of three". Partitions will happen, so the real question is what your system does when they do.

CAP's "C" is what database people call linearizability. It is not the C in ACID, which is about a transaction respecting your data's rules.

Step 8 of 11

Technique

Quorums: a dial between the two extremes

With N = 3 copies, a write waits until W copies confirm it, and a read asks R copies and keeps the newest version.

If W + R > N, any read group shares at least one copy with the latest write group. Here W = 2 and R = 2: even though one copy still holds v1, every read reaches a v2.

What changed

  • 3 copies (N = 3)
  • Writes wait for 2 (W = 2)
  • Reads ask 2 (R = 2)

Step 9 of 11

Technique

A like and a payment, in the same app

A like can be confirmed by a single copy and spread later (W = 1, R = 1): fast, always available, and nobody minds if a counter lags for a moment.

A payment uses a majority to write and to read (W = 2, R = 2): it is slower and fails if two copies cannot be reached, but nobody will read an old "payment pending".

What changed

  • Likes: W = 1, R = 1
  • Payments: W = 2, R = 2

Step 10 of 11

Concept

Consistency comes in degrees

"Consistent" is not yes or no. Between the strongest end (linearizable: everyone sees the latest write) and the weakest (eventual) there are useful promises: read your writes (you always see your own changes), monotonic reads (you never see data older than what you already saw) and causal (a reply never shows up before the question it answers).

The weaker the promise, the cheaper and more available it is. Pick the weakest one your users will not notice.

Step 11 of 11

Summary

Summary

A partition separates copies that keep serving their users.

During a partition you choose: consistency (refuse) or availability (answer, maybe with old data).

Available systems converge eventually and settle conflicts without trusting clocks.

Quorums (W + R > N) tune the balance on each request.

Use the weakest consistency each operation can tolerate.

You will learn

  • Recognise a network partition
  • Choose between consistency and availability
  • Reconcile copies with eventual consistency
  • Distrust clocks for ordering writes
  • State CAP without "pick two of three"
  • Tune the balance with quorums: W + R > N
  • Choose consistency per operation
  • Tell the consistency models apart