The CAP theorem and consistency models

Why can likes disagree, but my bank balance can’t?

The CAP theorem and consistency models

Words you’ll meet in this lesson

Where common systems sit (default settings)

CAP and consistency at three levels

CP, AP and the consistency ladder

The consistency ladder

A partition, handled two ways

1. Three copies, then the network splits

   replicas = {"A": 100, "B": 100, "C": 100}
   groups = [{"A"}, {"B", "C"}]           # the network splits
   majority = len(replicas) // 2 + 1
   for g in groups:
       print(sorted(g), "has majority" if len(g) >= majority else "minority")

   ['A'] minority ['B', 'C'] has majority
   A network fault separates A from B and C. Every node is still running; they just can’t talk. This is a partition, and in a big cluster it is a matter of when, not if.

2. CP: the minority refuses

   def cp_write(group, value, replicas, majority=2):
       if len(group) < majority:
           return "error: try again later"
       for n in group:
           replicas[n] = value
       return "ok"
   r = {"A": 100, "B": 100, "C": 100}
   print("via A:", cp_write({"A"}, 40, r), "| via B:", cp_write({"B", "C"}, 70, r), "|", r)

   via A: error: try again later | via B: ok | {'A': 100, 'B': 70, 'C': 70}
   Only the side with a majority may accept writes (and serve strongly consistent reads). Clients talking to A get errors, but no one ever sees two different balances.

3. AP: both sides answer

   r = {"A": 100, "B": 100, "C": 100}
   r["A"] = 40                      # AP: A accepts a write on its side
   r["B"] = r["C"] = 70             # B accepts a different write on the other side
   print("A answers", r["A"], "| B answers", r["B"], "-> both available, inconsistent")

   A answers 40 | B answers 70 -> both available, inconsistent
   Every request succeeds, but the two sides now disagree. When the network heals, the system must reconcile the two values, and some updates may need special merging.

4. Quorums: consistency you can tune

   N, W, R = 3, 2, 2
   print("R + W > N:", R + W > N, "-> every read overlaps the latest write")
   print("survives 1 node down for reads and writes:", N - W >= 1 and N - R >= 1)

   R + W > N: True -> every read overlaps the latest write survives 1 node down for reads and writes: True
   In leaderless stores like Cassandra, choosing W and R per query moves you along the scale: W = R = 1 is fast and AP-like; R + W > N gives strongly consistent reads while still tolerating one failed node.

5. When the network is fine: latency vs consistency

   Even without failures, a strongly consistent write must wait for a majority to confirm. If replicas are in Mumbai, Singapore and Frankfurt, that wait is one long network round trip.

   This is the “ELC” in PACELC: else, choose latency or consistency. Many systems keep strongly consistent data in one region and replicate asynchronously elsewhere.

6. Decide per piece of data

   In one food-delivery app: wallet balance → strong; restaurant stock of a limited dish → strong; cart → eventual with merge; ratings and view counts → eventual.

   Good designs mix models. The skill is matching each kind of data to the weakest guarantee that is still correct for the business.

Likes and a payment: what Riya sees, and what the copies do

Step through the six frames. Left: Riya’s reel likes and a UPI payment. Right: copies in three regions, eventually consistent for likes and strongly consistent for money.

Real-time scenarios: choosing consistency

Three live scenarios: the same network split handled by a CP and an AP design (real numbers), a shopping cart merged after a split, and an advanced look at the latency cost of consistency across regions.

One network split, two designs

A three-node cluster loses its network link to node A. Watch a CP bank balance and an AP like counter react to exactly the same failure. (These are the numbers from the program in “Run it on your PC”.)

Merging a shopping cart after a split

Shopping carts are a classic AP example: it is better to always accept “add to cart” than to show an error during a sale. Watch what merging two diverged carts really involves.

PACELC: consistency costs time even on good days

CAP talks only about partitions. But most of the time the network is fine, and there is still a trade-off: every strongly consistent write must wait for other replicas. Watch the latency of one write with replicas in three regions.

Consistency choices in real products

A network partition, handled CP and AP

Three replicas are split into {A} and {B, C}. In CP mode only the majority side accepts writes; in AP mode both sides accept and the values diverge. Run it, then try the challenges: quorum checks, read-your-writes, last-write-wins vs a CRDT counter, a cart merge and a PACELC latency estimate.

replicas = ["A", "B", "C"]
sides = [{"A"}, {"B", "C"}]
majority = len(replicas) // 2 + 1

def side_of(node):
    return next(s for s in sides if node in s)

def write(mode, node, value, store):
    side = side_of(node)
    if mode == "CP" and len(side) < majority:
        return "refused (minority side)"
    for n in side:
        store[n] = value
    return "accepted"

for mode in ["CP", "AP"]:
    store = {n: 100 for n in replicas}
    r1 = write(mode, "A", 40, store)
    r2 = write(mode, "B", 70, store)
    print(f"{mode}: via A {r1:24} via B {r2:9} -> {store}")

• majority = len(replicas) // 2 + 1With 3 replicas a majority is 2. Only a side with at least 2 nodes may make decisions in CP mode.
• if mode == "CP" and len(side) < majority:CP gives up availability on the minority side: it refuses rather than risk a conflicting value.
• for n in side:In AP mode each side updates its own copies, so after both writes the copies disagree.

Run it on your PC: CP, AP and merging after a split

This program splits three replicas into {A} and {B, C}. In CP mode it refuses writes on the minority side; in AP mode it lets both sides count likes, then merges them two ways: last-write-wins, which loses likes, and a CRDT counter, which keeps them all. Save it as cap_sim.py and run it.

"""Three replicas, then a network partition splits them {A} | {B, C}.
CP mode: only the side with a majority accepts writes.
AP mode: both sides accept writes, then merge when the network heals.
We merge a like-counter two ways: last-write-wins (loses likes) and a CRDT counter (keeps all)."""

REPLICAS = ["A", "B", "C"]
partition = [{"A"}, {"B", "C"}]


def side_of(node):
    return next(s for s in partition if node in s)


def cp_write(node, value, store):
    side = side_of(node)
    if len(side) > len(REPLICAS) // 2:
        for n in side:
            store[n] = value
        return "accepted"
    return "REFUSED (no majority on this side)"


print("CP mode (choose consistency):")
store = {n: 100 for n in REPLICAS}          # balance Rs 100 everywhere
print("  write via A:", cp_write("A", 40, store))
print("  write via B:", cp_write("B", 70, store))
print("  majority side (B, C) now holds:", store["B"], "| A must refuse reads and writes until the network heals")

print("\nAP mode (choose availability): a like counter")
likes = {"A": 1000, "B": 1000, "C": 1000}
# during the partition: 3 likes arrive at A, 5 likes at B
likes["A"] += 3
likes["B"] += 5
likes["C"] = likes["B"]                      # C is on B's side and syncs with it
print("  during partition:", likes, "-> different answers, but every request succeeded")

# merge 1: last-write-wins (keep the value written last, say B's)
lww = likes["B"]
print("  last-write-wins after healing:", lww, "(A's 3 likes are lost)")

# merge 2: a G-counter CRDT keeps a separate count per replica and adds them
increments = {"A": 3, "B": 5}
crdt = 1000 + sum(increments.values())
print("  CRDT counter after healing   :", crdt, "(every like kept)")

# In a terminal:  python cap_sim.py

Merging a G-counter, one line at a time

A G-counter (a CRDT) keeps one count per replica. Two replicas counted likes independently; merging takes the maximum for each replica's slot, then the total is the sum. Watch nothing get lost.

Worked examples: real problems, solved and traced in memory

Four consistency problems, from classifying data to merging concurrent updates. Each runs live and is traced.

wallet balance, like count, seat booking, product reviews, leader election

wallet balance   -> CP (refuse when unsure)
like count       -> AP (answer, reconcile later)
seat booking     -> CP (refuse when unsure)
product reviews  -> AP (answer, reconcile later)
leader election  -> CP (refuse when unsure)

levels ONE = 1, QUORUM = 2, ALL = 3

write ONE    read ONE   : consistent=False, write tolerates 2, read tolerates 2
write QUORUM read QUORUM: consistent=True, write tolerates 1, read tolerates 1
write ALL    read ONE   : consistent=True, write tolerates 0, read tolerates 2
write ONE    read QUORUM: consistent=False, write tolerates 2, read tolerates 1

A: address=Baner at 10:05 · B: address=Wakad at 10:03, phone=98xx at 10:04

merged: {'address': 'Baner', 'phone': '98xx'}
lost  : [('B', 'address', 'Wakad', '10:03')]

replica A: +4 −1 · replica B: +6 −2 · both start from the same state

merged: {'P': {'A': 4, 'B': 6}, 'N': {'A': 1, 'B': 2}}
likes: 7

Check yourself

Quick revision

Interview and viva questions

Practice problems

Consistency and quorum exercises. The last two are business tasks.

sides [1, 2]

['right']

sides = {"left": 1, "right": 2}
majority = 3 // 2 + 1
print([s for s, n in sides.items() if n >= majority])

3, 1, 2

False

N, W, R = 3, 1, 2
print(R + W > N)

balance, likes, seat, views

balance -> strong
likes -> eventual
seat -> strong
views -> eventual

for item in ["balance", "likes", "seat", "views"]:
    print(item, "->", "strong" if item in ("balance", "seat") else "eventual")

{A: 1008, B: 1008, C: 1005}

not yet

values = {"A": 1008, "B": 1008, "C": 1005}
print("converged" if len(set(values.values())) == 1 else "not yet")

a {A:5, B:2}, b {A:3, B:7}

{'A': 5, 'B': 7} 12

a, b = {"A": 5, "B": 2}, {"A": 3, "B": 7}
merged = {k: max(a[k], b[k]) for k in a}
print(merged, sum(merged.values()))

[12, 14, 13, 15]

went backwards at: [(14, 13)]

versions = [12, 14, 13, 15]
backwards = [(a, b) for a, b in zip(versions, versions[1:]) if b < a]
print("went backwards at:", backwards if backwards else "never")

[2, 45, 110] ms

W=1: 2 ms
W=2: 45 ms
W=3: 110 ms

rtts = sorted([2, 45, 110])
for W in [1, 2, 3]:
    print(f"W={W}: {rtts[W - 1]} ms")

2 lakh/min, 60 ms vs 3 ms

strong  : about 200 busy threads
eventual: about 10 busy threads

rate_per_s = 2_00_000 / 60
for name, ms in [("strong", 60), ("eventual", 3)]:
    print(f"{name:8}: about {rate_per_s * ms / 1000:.0f} busy threads")

500 stock, 2 s lag, 300/s

orders that could see stale stock near the end: 600
so up to ~ 600 phones could be oversold -> use strong consistency at checkout

lag, rate = 2, 300
print("orders that could see stale stock near the end:", lag * rate)
print("so up to ~", lag * rate, "phones could be oversold -> use strong consistency at checkout")

Real-world scenario questions (asked in company interviews)

Consistency questions from interviews and real designs. Decide your answer first, then open the model answer.