These are the notes for System Design episode 14. In episodes 11 to 13 we copied ChaiNow's data to several machines and spread it across them. Today the network between those machines breaks. You'll see that during a network partition a system must choose between giving an answer (availability) and giving a correct, up-to-date answer (consistency): that's the CAP theorem. Then you'll find a middle path (offline limits, like ATMs), learn to choose per feature, and meet PACELC: even on a normal day, waiting for the other copy costs latency. Every demo is plain Python and runs as-is; outputs are real (Python 3.13).
The six problems
| Problem | What it teaches |
|---|---|
| The cable is cut | What a network partition is |
| Keep answering | Availability without consistency: a Rs 500 wallet spends Rs 900 |
| Refuse to answer | Consistency without availability: ConnectionError, customers wait |
| Why you can't have both | The CAP theorem, and why "pick 2 of 3" is misleading |
| A middle path | Offline limits (like ATMs) and choosing C or A per feature |
| No partition, still a price | PACELC: latency vs consistency on a normal day |
Problem 1: the cable is cut
ChaiNow has a wallet: you load Rs 500 and pay for chai from your phone. From episode 11, every wallet is replicated (copied) to two data centres, one in Mumbai and one in Delhi, so a dead machine doesn't lose anyone's money. Each copy is a replica.
One evening a construction crew cuts the fibre cable between the cities. Both data centres are fine and serving customers; they just can't talk to each other. That is a network partition: the network splits the machines into groups that can't reach each other. The machines are alive, but messages between them are lost.
| At a bank | In a distributed system |
|---|---|
| The phone line between two branches dies; both stay open | Network partition: nodes alive, messages lost |
| The branch keeps paying out cash from its own ledger copy | Available: every request gets an answer |
| The branch says "come back when the line works" | Consistent: never an out-of-date answer |
A node is one machine in the system. A distributed system is one where several nodes work together over a network.
Demo 1: keep answering (choose availability)
Each Replica is one city's copy of the wallet. It knows its peer (the other city) and whether the link is up. spend takes the money and, if the link is up, copies the new balance across. If the link is down, it carries on alone.
class Replica: # one copy of the wallet
def __init__(self, city):
self.city, self.wallet = city, 500
self.peer, self.link_up = None, True
def spend(self, amount):
if amount > self.wallet:
return f"{self.city}: declined"
self.wallet -= amount
if self.link_up: # copy to the other city
self.peer.wallet = self.wallet
return f"{self.city}: paid {amount}, wallet {self.wallet}"
mumbai, delhi = Replica("Mumbai"), Replica("Delhi")
mumbai.peer, delhi.peer = delhi, mumbai
print(mumbai.spend(100))
mumbai.link_up = delhi.link_up = False # the cable is cut
print(mumbai.spend(400))
print(delhi.spend(400))
print("loaded: Rs 500 | spent: Rs", 100 + 400 + 400)
Output:
Mumbai: paid 100, wallet 400
Mumbai: paid 400, wallet 0
Delhi: paid 400, wallet 0
loaded: Rs 500 | spent: Rs 900
Every customer got an answer, but the two copies now disagree (Mumbai's wallet is 0 after its payment, Delhi's is 0 after a different payment), and ChaiNow lost Rs 400. Staying available during a partition means accepting that answers may be wrong.
Demo 2: refuse to answer (choose consistency)
Now the replica refuses to spend unless it can confirm with the other city.
class Replica:
def __init__(self, city):
self.city, self.wallet = city, 500
self.peer, self.link_up = None, True
def spend(self, amount):
if not self.link_up: # can't confirm with the peer
raise ConnectionError(f"{self.city} can't reach "
f"{self.peer.city}, try later")
if amount > self.wallet:
return f"{self.city}: declined"
self.wallet -= amount
self.peer.wallet = self.wallet
return f"{self.city}: paid {amount}, wallet {self.wallet}"
mumbai, delhi = Replica("Mumbai"), Replica("Delhi")
mumbai.peer, delhi.peer = delhi, mumbai
print(mumbai.spend(100))
mumbai.link_up = delhi.link_up = False # the cable is cut
print(delhi.spend(400))
Output:
Mumbai: paid 100, wallet 400
Traceback (most recent call last):
File "main.py", line 20, in <module>
print(delhi.spend(400))
~~~~~~~~~~~^^^^^
File "main.py", line 8, in spend
raise ConnectionError(f"{self.city} can't reach "
f"{self.peer.city}, try later")
ConnectionError: Delhi can't reach Mumbai, try later
No money lost and the copies never disagree. But a Delhi customer with a perfectly good wallet was refused, and if the cable takes three hours to fix, every Delhi customer is stuck for three hours. ConnectionError is Python's built-in exception for network connection problems; here we raise it ourselves.
Problem 3: why you can't have both
Mumbai has spent the money, but that news can't cross the cut cable. Delhi only has its own copy. So Delhi can:
- answer now, and maybe be wrong (consistency lost), or
- wait for Mumbai, and give no answer (availability lost).
There is no third option, because the information Delhi needs is on the other side of the cut. During a partition, every system must pick: consistency or availability.
The CAP theorem
Eric Brewer stated this as a conjecture in an invited talk at the PODC conference (Principles of Distributed Computing) in July 2000. In 2002 Seth Gilbert and Nancy Lynch proved it ("Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services"). Their definitions:
| Letter | Property | Gilbert and Lynch's definition (in plain words) |
|---|---|---|
| C | Consistency (atomic, linearizable) | "there must exist a total order on all operations such that each operation looks as if it were completed at a single instant": as if there were one copy |
| A | Availability | "every request received by a non-failing node in the system must result in a response" |
| P | Partition tolerance | "the network will be allowed to lose arbitrarily many messages sent from one node to another" |
The theorem: "It is impossible in the asynchronous network model to implement a read/write data object that guarantees" availability and atomic consistency "in all fair executions (including those in which messages are lost)." An asynchronous network is one where messages can be delayed for any amount of time, so a node can't tell a slow message from a lost one.
Watch out: the C in CAP is not the C in ACID. ACID's "consistency" (from database transactions) means the data obeys its rules, like "balance never negative". CAP's C means every read sees the latest write, as if there were one copy.
"Pick any 2 of 3"? Not really
You'll often hear CAP as "pick any two of three: CP, AP or CA". Some teams then say "we'll be CA, we just won't have partitions". But you don't choose whether cables get cut; across a network, partitions happen. Brewer himself wrote in 2012 ("CAP Twelve Years Later: How the 'Rules' Have Changed", IEEE Computer):
- "The '2 of 3' formulation was always misleading because it tended to oversimplify the tensions among properties."
- "because partitions are rare, there is little reason to forfeit C or A when the system is not partitioned."
- "designers still need to choose between consistency and availability when partitions are present."
| The slogan | What it really says |
|---|---|
| Pick any 2 of C, A, P | No partition: you can have C and A |
| "We're CA, no partitions" | During a partition: choose C or A |
A system that chooses C during a partition is called CP; one that chooses A is called AP.
Problem 4: a middle path (offline limits, like ATMs)
Is it all or nothing? Brewer gives a real example: ATMs. When an ATM can't reach the bank, it doesn't have to refuse everyone. In his words, "modern ATMs limit the net withdrawal to at most k, where k might be $200." The bank accepts a small, bounded risk to stay useful, and when the line comes back the accounts are settled (reconciled).
| At an ATM | In our wallet |
|---|---|
| ATM can't reach the bank | Partition: Mumbai and Delhi cut off |
| Still pays out, up to a small limit | Offline limit: each side may spend part of the balance |
| Line back: settle the accounts | Merge after the partition: both sides report what they spent |
Demo 3: an offline limit
While the cable is cut, each city may spend half of the balance both cities last agreed on.
class Wallet: # one city's copy, cable cut
def __init__(self, city, balance):
self.city, self.spent = city, 0
self.limit = balance // 2 # each side may spend half
def spend(self, amount):
if self.spent + amount > self.limit:
return f"{self.city}: declined (limit {self.limit})"
self.spent += amount
return f"{self.city}: paid {amount}"
balance = 400 # both cities agreed on this
mumbai, delhi = Wallet("Mumbai", balance), Wallet("Delhi", balance)
print(mumbai.spend(150))
print(delhi.spend(400))
print(delhi.spend(200))
print("spent offline:", mumbai.spent + delhi.spent, "of", balance)
Output:
Mumbai: paid 150
Delhi: declined (limit 200)
Delhi: paid 200
spent offline: 350 of 400
We never overspent, and most customers were still served. The two halves can never add up to more than the balance, whatever the customers do. This is the real skill: not yes or no, but how much risk is acceptable during a partition, and how you'll repair things after.
Problem 5: choose per feature
You don't pick C or A once for the whole company; you pick per feature, by asking: what's worse, a wrong answer or no answer?
| Feature | Choice during a partition | Why |
|---|---|---|
| Wallet payments | C | A wrong answer loses real money |
| Last seat / last plate of biryani | C | Selling it twice is worse than asking someone to wait |
| Likes on a review | A | Off by a few for a minute? Nobody cares |
| Menu and photos | A | A slightly old menu beats an error page |
| Delivery rider's location | A | The next update fixes it in seconds |
Problem 6: no partition, still a price (PACELC)
The cable is fixed. For both copies to agree, every write in Mumbai has to send the change to Delhi and wait for Delhi to say "got it": a round trip across the country on every write. Or Mumbai doesn't wait: it answers at once and tells Delhi in the background (asynchronous replication, episode 11), so for a moment Delhi is behind.
Latency is how long one request takes (episode 4). A round trip is the time for a message to go and its reply to come back.
Demo 4: the price of waiting
The 40 ms round trip is a made-up number for the demo.
import time
ROUND_TRIP = 0.040 # pretend: 40 ms Mumbai <-> Delhi and back
def write(value, wait_for_delhi):
mumbai.append(value)
if wait_for_delhi:
time.sleep(ROUND_TRIP) # send, wait for "got it"
delhi.append(value)
for wait in [True, False]:
mumbai, delhi = [], []
start = time.perf_counter()
for order in range(25):
write(order, wait)
took = time.perf_counter() - start
print(f"wait for Delhi={wait!s:5}: 25 writes in {took:.2f} s,"
f" Delhi has {len(delhi)}")
Output (timings vary by a hundredth or so):
wait for Delhi=True : 25 writes in 1.00 s, Delhi has 25
wait for Delhi=False: 25 writes in 0.00 s, Delhi has 0
Waiting keeps Delhi in sync but costs a round trip per write. Not waiting is instant, but Delhi is behind until the background copy arrives. This trade exists every day, not only when cables break, and CAP says nothing about it, because CAP only talks about partitions.
PACELC
In 2012 Daniel Abadi wrote this up as PACELC (say "pass-elk") in "Consistency Tradeoffs in Modern Distributed Database System Design" (IEEE Computer, February 2012):
"if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?"
And: "This tradeoff exists even when there are no network partitions."
partition?
/ \
yes no (Else)
| |
A or C? L or C?
Real systems, real labels (from Abadi's paper)
| Label | Meaning | Systems Abadi lists |
|---|---|---|
| PA/EL | Partition: available. Else: low latency | Default versions of Dynamo, Cassandra, Riak |
| PC/EC | Always consistency first | VoltDB/H-Store, Megastore, BigTable, HBase |
| PA/EC | Partition: available. Else: consistent | MongoDB |
| PC/EL | Partition: consistent. Else: low latency | Yahoo's PNUTS |
Many databases let you change these choices per request (for example, how many replicas must answer), which is next episode's topic. Labels describe the default settings Abadi studied in 2012; products change, so check a system's current docs before relying on a label.
The whole chain
- Cable cut: copies alive but can't talk = network partition.
- Keep answering → Rs 500 wallet, Rs 900 spent (available, not consistent).
- Refuse →
ConnectionError, customers stuck (consistent, not available). - CAP: during a partition, choose C or A. P is not optional; "2 of 3" is misleading.
- Middle path: offline limits with repair afterwards; choose per feature.
- PACELC: else (no partition), choose latency or consistency.
Common mistakes (and the real errors)
| Mistake | Code | Error / result | Fix |
|---|---|---|---|
| Choosing C for everything | raise ConnectionError(...) for likes, menu, everything |
ConnectionError: Delhi can't reach Mumbai, try later |
Choose C or A per feature |
| Choosing A for money, no limit or repair | if self.link_up: self.peer.wallet = self.wallet (else carry on alone) |
loaded: Rs 500 \| spent: Rs 900 |
Limit offline spending; reconcile after |
| "We are CA" | assuming partitions won't happen | a partition happens anyway | Decide in advance what each feature does during P |
| Mixing up the two C's | "our DB is ACID so it's CAP-consistent" | stale reads from replicas | CAP's C = latest write, as if one copy |
| Ignoring the E in PACELC | every write waits for the far city | 25 writes take 1.00 s instead of 0.00 s | Wait only where consistency is needed |
Misconceptions
- "CAP means you always lose one of the three." No: when there's no partition you can have C and A. The choice is forced only during a partition.
- "An AP system is never consistent." It's usually consistent most of the time; it just may give stale answers during a partition (and for a short window after writes).
- "A CP system is always down." It refuses only the requests it can't answer correctly during a partition; the side with a majority can often keep working (episode 11's majority vote).
Mini project: per-feature C or A, with repair after the partition
A two-city store where the wallet is C (refuses during a partition) and likes are A (keep counting on both sides, then add both sides' changes together when the cable is fixed).
# Mini project: a two-city store that picks C or A per feature, and repairs itself after the partition
class City:
def __init__(self, name):
self.name, self.data, self.peer, self.link_up = name, {}, None, True
self.offline_log = [] # what we did while cut off (A features)
MODE = {"wallet": "C", "likes": "A"} # per feature: C or A
def write(city, feature, key, change):
"""change(old_value) -> new_value"""
if MODE[feature] == "C" and not city.link_up:
return f"{city.name}: {feature} unavailable during partition, try later"
old = city.data.get(key, 0)
city.data[key] = change(old)
if city.link_up:
city.peer.data[key] = city.data[key]
else:
city.offline_log.append((feature, key, change))
return f"{city.name}: {key} = {city.data[key]}"
def heal(a, b):
"""The cable is fixed: replay each side's offline changes on the other side."""
a.link_up = b.link_up = True
for src, dst in [(a, b), (b, a)]:
for feature, key, change in src.offline_log:
if feature == "likes": # counters: add what the other side added
dst.data[key] = change(dst.data.get(key, 0))
for src in (a, b):
src.offline_log.clear()
for key in a.data: # after replay, both sides must agree
assert a.data[key] == b.data[key], key
return {k: a.data[k] for k in sorted(a.data)}
mumbai, delhi = City("Mumbai"), City("Delhi")
mumbai.peer, delhi.peer = delhi, mumbai
print(write(mumbai, "wallet", "wallet:asha", lambda v: v + 500))
print(write(mumbai, "likes", "likes:review7", lambda v: v + 1))
mumbai.link_up = delhi.link_up = False # the cable is cut
print(write(delhi, "wallet", "wallet:asha", lambda v: v - 400))
print(write(mumbai, "likes", "likes:review7", lambda v: v + 1))
print(write(delhi, "likes", "likes:review7", lambda v: v + 1))
print("after heal:", heal(mumbai, delhi))
Output:
Mumbai: wallet:asha = 500
Mumbai: likes:review7 = 1
Delhi: wallet unavailable during partition, try later
Mumbai: likes:review7 = 2
Delhi: likes:review7 = 2
after heal: {'likes:review7': 3, 'wallet:asha': 500}
During the partition each side counted one more like (both showed 2). After healing, each side replays the other's change, so both agree on 3. Likes can be merged by adding, because adding is commutative (order doesn't matter). A wallet balance can't be merged so easily, which is exactly why it's C.
Extend it: add a menu feature in A mode where the last write wins (keep a timestamp with each value, and on heal keep the newer one).
Practice
- Homework from the video: add a third city to Demo 1 and cut every link. How much is spent?
- Homework: in Demo 3, give Mumbai 3/4 of the balance and Delhi 1/4. Run Mumbai 250, Delhi 150, Delhi 100.
- Homework: in Demo 4, try a 5 ms and a 150 ms round trip.
- For each, pick C or A during a partition, and say why: (a) a cricket score app, (b) UPI money transfer, (c) a shopping cart's "add item", (d) username sign-up ("is this name taken?").
- Put these systems in Abadi's PACELC labels from memory: Cassandra (default), HBase, MongoDB, PNUTS.
- Why can't a distributed system "choose CA"?
Solutions and hints
1. With three cities and every link cut, each spends 400 from the 400 it thinks it has:
class Replica:
def __init__(self, city):
self.city, self.wallet = city, 500
self.peers, self.link_up = [], True
def spend(self, amount):
if amount > self.wallet:
return f"{self.city}: declined"
self.wallet -= amount
if self.link_up:
for p in self.peers:
p.wallet = self.wallet
return f"{self.city}: paid {amount}, wallet {self.wallet}"
cities = [Replica(c) for c in ["Mumbai", "Delhi", "Chennai"]]
for c in cities:
c.peers = [p for p in cities if p is not c]
print(cities[0].spend(100))
for c in cities:
c.link_up = False # every link is cut
for c in cities:
print(c.spend(400))
print("loaded: Rs 500 | spent: Rs", 100 + 400 * 3)
Mumbai: paid 100, wallet 400
Mumbai: paid 400, wallet 0
Delhi: paid 400, wallet 0
Chennai: paid 400, wallet 0
loaded: Rs 500 | spent: Rs 1300
More copies that answer alone means more damage: Rs 1300 from Rs 500.
2.
class Wallet:
def __init__(self, city, balance, share):
self.city, self.spent = city, 0
self.limit = int(balance * share) # this city's part
def spend(self, amount):
if self.spent + amount > self.limit:
return f"{self.city}: declined (limit {self.limit})"
self.spent += amount
return f"{self.city}: paid {amount}"
balance = 400
mumbai, delhi = Wallet("Mumbai", balance, 3 / 4), Wallet("Delhi", balance, 1 / 4)
print(mumbai.spend(250))
print(delhi.spend(150))
print(delhi.spend(100))
print("spent offline:", mumbai.spent + delhi.spent, "of", balance)
Mumbai: paid 250
Delhi: declined (limit 100)
Delhi: paid 100
spent offline: 350 of 400
The shares just have to add up to at most 1. Give the bigger share to the city where the customer usually is.
3. Change ROUND_TRIP to 0.005 and 0.150:
wait for Delhi=True : 25 writes in 0.13 s, Delhi has 25
wait for Delhi=True : 25 writes in 3.77 s, Delhi has 25
(The "don't wait" line stays at 0.00 s.) The cost grows directly with distance: replicas far apart make waiting expensive.
4. (a) A: a score a few seconds old is fine. (b) C: money. (c) A is common: Vogels' article describes Amazon's shopping cart letting customers keep adding items during a partition and merging carts afterwards. (d) C: two people must not get the same username.
5. Cassandra: PA/EL. HBase: PC/EC. MongoDB: PA/EC. PNUTS: PC/EL.
6. Because over a real network, messages can be lost; when they are, the system must either answer without the other side (giving up C) or wait (giving up A). Only a single machine, with no network between copies, avoids the choice.
Quick quiz
# IRCTC Tatkal, a partition between
# two data centres. Feature:
book_last_seat(train=12951)
# keep answering (A),
# or refuse until synced (C)?
- A. A: keep answering
- B. C: refuse until synced
- C. Either, it doesn't matter
- D. Turn off partition tolerance
Answer
B. If both sides sell the last seat, two passengers turn up for one berth. A retry is annoying; a double booking is much worse. D is a trick: you can't turn off partitions.
Interview questions
- What is a network partition? (Nodes are alive but can't exchange messages.)
- State the CAP theorem precisely. (During a partition, a system can't guarantee both linearizable consistency and availability. Proved by Gilbert and Lynch, 2002.)
- Why is "pick 2 of 3" misleading? (Partitions aren't optional; without a partition you can have C and A. Brewer, 2012.)
- Give a feature you'd make CP and one you'd make AP, with reasons. (Payments CP; likes, menus, locations AP.)
- How do ATMs stay useful during a partition? (They allow a small, bounded withdrawal and reconcile later.)
- What does PACELC add to CAP? (Else, without a partition, the trade between latency and consistency.)
- Classify Cassandra and HBase in PACELC. (Cassandra default: PA/EL. HBase: PC/EC.)
- Is CAP's C the same as ACID's C? (No: CAP's C is about every read seeing the latest write; ACID's C is about data obeying its rules.)
Glossary
| Term | Meaning |
|---|---|
| Node | One machine (server) in a system |
| Distributed system | Several nodes working together over a network |
| Replica / replication | A copy of the data on another node; keeping copies in sync (episode 11) |
| Network partition | The network splits nodes into groups that can't reach each other; nodes are alive, messages are lost |
| Consistency (CAP's C) | Every read sees the latest write, as if there were one copy (also called atomic or linearizable) |
| Availability (CAP's A) | Every request to a live node gets a response (not an error or silence) |
| Partition tolerance (CAP's P) | The system keeps working even when messages between nodes are lost |
| CAP theorem | During a partition, you can't guarantee both C and A |
| Conjecture | A claim believed true but not yet proved; Brewer's in 2000, proved in 2002 |
| PODC | Principles of Distributed Computing, the conference where Brewer gave his 2000 talk |
| Asynchronous network | Messages can be delayed for any time, so a slow message looks like a lost one |
| CP / AP | A system that chooses consistency / availability during a partition |
| CA | "Consistent and available, no partitions": only possible without a network between copies |
| ACID | Atomicity, Consistency, Isolation, Durability: guarantees of database transactions (its C is a different idea) |
| Stale | Out of date: an older value than the latest write |
| Bounded risk | Accepting a limited, known worst case (like an ATM's withdrawal limit) |
| Reconcile / settle | After the partition, combine both sides' changes so they agree again |
| Commutative | Order doesn't matter: +1 then +1 equals the same either way |
| Latency | How long one request takes (episode 4) |
| Round trip | Time for a message to go and its reply to come back |
| Synchronous / asynchronous replication | Wait for the copy to confirm before answering / answer first, copy in the background |
| PACELC | If Partition: A or C; Else: Latency or Consistency (Abadi, 2012) |
| PA/EL, PC/EC, PA/EC, PC/EL | PACELC labels: what a system chooses in each case |
ConnectionError |
Python's built-in exception for connection failures |
time.perf_counter() |
A precise clock for measuring how long code takes |
time.sleep(s) |
Pauses the program for s seconds; here it pretends to be the network |
Summary
- A network partition means nodes are alive but can't talk. It isn't optional over a real network.
- Keep answering during a partition (AP) and copies disagree: Rs 500 loaded, Rs 900 spent.
- Refuse (CP) and answers are always right, but some customers get
ConnectionError: ... try later. - CAP (Brewer 2000, proved by Gilbert and Lynch 2002): during a partition, choose C or A. "2 of 3" is misleading (Brewer 2012).
- Middle paths exist: offline limits like ATMs, with reconciliation after. Choose C or A per feature.
- PACELC (Abadi 2012): else, on a normal day, choose latency or consistency; waiting for the other city made 25 writes take 1 s.
- Abadi's labels: Dynamo/Cassandra/Riak PA/EL, VoltDB/Megastore/BigTable/HBase PC/EC, MongoDB PA/EC, PNUTS PC/EL.
Next episode: consistent isn't a yes or no. There's a ladder, from strong to eventual, with useful steps in between, like read-your-writes: consistency models.