SyntaxPilot
Courses/System Design/Lesson 14

System Design · Lesson 14 of 40 · 12 min

CAP and PACELC

queued

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

  1. Cable cut: copies alive but can't talk = network partition.
  2. Keep answering → Rs 500 wallet, Rs 900 spent (available, not consistent).
  3. Refuse → ConnectionError, customers stuck (consistent, not available).
  4. CAP: during a partition, choose C or A. P is not optional; "2 of 3" is misleading.
  5. Middle path: offline limits with repair afterwards; choose per feature.
  6. 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

  1. Homework from the video: add a third city to Demo 1 and cut every link. How much is spent?
  2. Homework: in Demo 3, give Mumbai 3/4 of the balance and Delhi 1/4. Run Mumbai 250, Delhi 150, Delhi 100.
  3. Homework: in Demo 4, try a 5 ms and a 150 ms round trip.
  4. 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?").
  5. Put these systems in Abadi's PACELC labels from memory: Cassandra (default), HBase, MongoDB, PNUTS.
  6. 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.