🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

✂️ धडा 08 — CAP & PACELC: जेव्हा रस्ता तुटतो

📍 तुम्ही इथे आहात: 12 पैकी धडा 08 · मागे: lesson-07-consistency-models · पुढे: lesson-09-raft

📦 या ब्रँचमध्ये काय आहे

धडे 01–07, आणि network partition भाग पाडते ती निवड: consistent राहा (उत्तर देण्यास नकार द्या) किंवा available राहा (उत्तर द्या, कदाचित जुन्या data सह) — हा CAP theorem — आणि PACELC, जो सामान्य दिवसांतली निवड जोडतो: latency की consistency. शिवाय: फुटीच्या दोन्ही बाजूंनी केलेले दोन बदल कसे मिटवायचे. dist/demo.py मधील cap() आणि dist/sim.py मधील partition_choice() + resolve().

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

वादळामुळे रस्ता तुटतो. ⛈️ पुणे आणि नाशिक एकमेकांशी बोलू शकतात. नागपूर आणि कोल्हापूर एकमेकांशी बोलू शकतात. पण हे दोन गट एकमेकांपर्यंत अजिबात पोहोचू शकत नाहीत.

पुण्याने नुकताच परीक्षेचा दिवस बदलला आहे (version 2). नागपूरकडे अजून version 1 आहे.

नागपूरमधील एक पालक विचारतात: "परीक्षेचा दिवस कोणता?" नागपूरकडे दोन पर्याय आहेत:

🔒 नकार द्या: "माफ करा, मी पुण्याशी तपासू शकत नाही, म्हणून मी उत्तर देणार नाही." पालक नाराज होतात, पण त्यांना चुकीचा दिवस कधीच सांगितला जात नाही. (CP — consistent)
📣 उत्तर द्या: "सोमवार" — जुना दिवस, नागपूरकडे असलेला एकमेव. पालकांना उत्तर मिळते, पण कदाचित चुकीचे. (AP — available)

रस्ता तुटलेला असेपर्यंत तिसरा पर्याय नाही. Version 2 अस्तित्वात आहे हे नागपूरला कळूच शकत नाही.

त्याहून वाईट: वादळाच्या काळात दोन्ही बाजू वर्ग 3A च्या सहलीतील एक बदल स्वीकारतात. पुण्याची बाजू शुक्रवार म्हणते. नागपूरची बाजू शनिवार म्हणते. रस्ता पुन्हा उघडल्यावर कोण जिंकणार? मोठा क्रमांक ठेवायचा आणि दुसरा फेकून द्यायचा? की दोन्ही ठेवून एखाद्या व्यक्तीला विचारायचे?

🗺️ आकृती

flowchart LR
    subgraph left["Pune + Nashik"]
      p["🏫 Pune<br/>latest: v2"]
      n["🏫 Nashik"]
    end
    subgraph right["Nagpur + Kolhapur"]
      g["🏫 Nagpur<br/>holds v1"]
      k["🏫 Kolhapur"]
    end
    p -.-x|"✂️ road cut"| g
    g --> cp["CP: refused<br/>no answer rather than a wrong one"]
    g --> ap["AP: answered v1 (stale!)"]

🗺️ रेखाटलेली आवृत्ती + एक lab: https://school-edh.pages.dev/distributed-systems/lesson-diagrams.html#l08

❓ काय

CAP theorem (Eric Brewer यांचे 2000 मधील अनुमान; Seth Gilbert आणि Nancy Lynch यांनी 2002 मध्ये सिद्ध केले) — प्रती असलेली system या तिन्ही गोष्टींची एकाच वेळी हमी देऊ शकत नाही:
- C, Consistency — इथे याचा अर्थ linearizability (धडा 07), ACID मधला "C" नव्हे
- A, Availability — बंद न पडलेल्या node ला आलेल्या प्रत्येक request ला (error नसलेले) उत्तर मिळते
- P, Partition tolerance — network ने nodes मधले messages टाकून दिले तरी system काम करत राहते
खरा अर्थ — partitions होणारच (धडा 01), म्हणून P ऐच्छिक नाही. CAP म्हणते: partition च्या काळात, C निवडा (काही requests ना errors मिळतात किंवा थांबावे लागते) किंवा A निवडा (प्रत्येक request ला उत्तर मिळते, कदाचित जुने, आणि दोन्ही बाजूंचे मत वेगळे असू शकते). Partition नसताना तुम्हाला दोन्ही मिळू शकतात. Network वर पसरलेल्या system साठी "CA" हा खरा पर्यायच नाही.
CP systems — अल्पसंख्य बाजूला नकार देतात: etcd, ZooKeeper, consensus-आधारित databases (धडा 09). Locks, leader election, bookings, balances साठी योग्य.
AP systems — दोन्ही बाजूंना उत्तर देतात आणि नंतर मेळ घालतात: Cassandra आणि DynamoDB त्यांच्या default modes मध्ये, DNS, caches. Carts, likes, presence, feeds साठी योग्य.
PACELC (Daniel Abadi, 2010) — Partition असेल तर A किंवा C निवडा; Else (सामान्य कामकाज) Latency किंवा Consistency निवडा. Partition नसतानाही consistent read किंवा write ला इतर प्रतींसाठी थांबावे लागते; वेगवान read/write थांबत नाही. या रोजच्या किंमतीबद्दल CAP काहीच सांगत नाही; PACELC सांगतो.
फुटीनंतर मेळ घालणे — दोन्ही बाजूंनी writes स्वीकारले असतील (AP), तर रस्ता पुन्हा जुळल्यावर:
- last-writer-wins (LWW) — मोठा time stamp किंवा version असलेला write ठेवा; दुसरा गुपचूप टाकून दिला जातो
- merge — दोन्ही ठेवा (siblings), CRDT ने merge करा, किंवा एखाद्या व्यक्तीला ठरवू द्या (धडा 03)

🤔 का

कारण प्रती असलेल्या प्रत्येक system समोर तुटलेला रस्ता येणारच, आणि ही निवड एकतर जाणूनबुजून (design मध्ये) केली जाते किंवा अपघाताने (code च्या defaults मध्ये, जी outage च्या वेळी उघडकीस येते). "आमचा database highly available आणि strongly consistent आहे" हे network फुटेपर्यंतच खरे असते. ही निवड माहीत असली की तुम्ही data च्या प्रत्येक तुकड्यासाठी वेगळी निवडू शकता: seat booking साठी CP, like counter साठी AP.

🔧 कसे (या repo मध्ये)

dist/sim.py मधील partition_choice(mode, local_version, latest_version) 'CP' साठी नकार परत करते, किंवा 'AP' साठी "answered v…" परत करते, आणि local version मागे असेल तर सोबत (stale!). resolve(a, b, rule) दोन (version, value) writes मिटवते: 'lww' मोठी version असलेला ठेवतो; बाकी काहीही ('merge') दोन्ही values परत करते, क्रमाने लावून आणि duplicates शिवाय.

🧪 करून पाहा

python3 dist/demo.py cap
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import partition_choice, resolve
for mode in ("CP", "AP"):
    for local in (1, 2):
        print(f"{mode} · Nagpur holds v{local}, latest v2 → {partition_choice(mode, local, 2)}")
print("lww, versions 7 vs 6 →", resolve((7, "trip on Friday"), (6, "trip on Saturday"), "lww"))
print("lww, a tie 6 vs 6    →", resolve((6, "trip on Friday"), (6, "trip on Saturday"), "lww"))
print("merge, same text     →", resolve((5, "trip on Friday"), (6, "trip on Friday"), "merge"))
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

cap हे print करते:

── the road between Pune+Nashik and Nagpur+Kolhapur is cut (a partition); Nagpur holds v1, the latest is v2
   CP: Nagpur is asked the exam day → refused — cannot reach a majority, so no answer rather than a wrong one
   AP: Nagpur is asked the exam day → answered v1 (stale!)
── both sides accepted a change during the split: (5, '3A trip on Friday') and (6, '3A trip on Saturday')
   last-writer-wins → '3A trip on Saturday' (the other write is silently dropped) · merge → ['3A trip on Friday', '3A trip on Saturday'] (a person decides)
   PACELC: during a Partition choose A or C; Else (normal days) choose Latency or Consistency

तुमचा snippet हे print करतो:

CP · Nagpur holds v1, latest v2 → refused — cannot reach a majority, so no answer rather than a wrong one
CP · Nagpur holds v2, latest v2 → refused — cannot reach a majority, so no answer rather than a wrong one
AP · Nagpur holds v1, latest v2 → answered v1 (stale!)
AP · Nagpur holds v2, latest v2 → answered v2

नंतर:

lww, versions 7 vs 6 → trip on Friday
lww, a tie 6 vs 6    → trip on Friday
merge, same text     → ['trip on Friday']

🏁 तुम्ही आत्ताच काय सिद्ध केले

CP node त्याची प्रत योगायोगाने अद्ययावत असली तरीही नकार देतो — दुसऱ्या बाजूशिवाय त्याला हे कळू शकत नाही. AP node नेहमी उत्तर देतो, आणि तो बरोबर असतो तो फक्त नशिबाने. Tie झाल्यास last-writer-wins तरीही एक निवडतो (इथे, फक्त पहिला argument) आणि दुसरा टाकून देतो, कोणत्याही error शिवाय. Merge दोन्ही ठेवतो — आणि दोन सारखे writes एक होतात.

⚠️ नेहमीच्या चुका

system ला "CA" म्हणणे — network वरील कोणत्याही system ला partitions हाताळावेच लागतात
data च्या प्रत्येक तुकड्यासाठी निवड करण्याऐवजी संपूर्ण product साठी एकच अक्षर निवडणे
CAP मधला C म्हणजे ACID मधला C असे समजणे (त्या वेगळ्या कल्पना आहेत)
वेगवेगळ्या machines वरील wall-clock time stamps सह last-writer-wins वापरणे (धडा 02)
PACELC विसरणे: बहुतेक वेळा partition नसतो, आणि खरी किंमत latency असते

🏭 प्रत्यक्ष वापरात

नेहमीच्या systems कुठे बसतात (defaults; अनेक बदलता येतात):

System	Partition च्या काळात (PAC)	सामान्य दिवशी (ELC)
etcd, ZooKeeper	C — अल्पसंख्य बाजू writes नाकारते	C — writes बहुमतासाठी थांबतात
Cassandra, DynamoDB (default reads)	A — दोन्ही बाजू उत्तर देतात	L — वेगवान reads, कदाचित जुने
`QUORUM` सह Cassandra	ज्या keys च्या replicas बहुमतापासून तुटल्या आहेत त्यांच्यासाठी C	latency ची किंमत देऊन C

On a real account — etcd मध्ये CP वर्तन पाहा: 3 members असताना 2 बंद करा, मग उरलेल्या एकावर write करून पाहा:

etcdctl --endpoints=http://nagpur:2379 put exam-day Tuesday
# Error: context deadline exceeded   (no leader: the minority cannot commit)

DynamoDB global tables (अनेक AWS Regions मध्ये replicate केलेली एक table) — default नुसार प्रत्येक Region writes स्वीकारतो आणि asynchronously replicate करतो; एकाच item वरील एकाच वेळचे updates last writer wins ने मिटवले जातात. ही AP / EL निवड आहे. नवा multi-Region strong consistency mode दुसरी निवड करतो: writes दुसऱ्या Region साठी थांबतात.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक data item साठी दोन रिकाम्या जागा भरा: "partition च्या काळात आम्ही ___ (नकार देतो / जुने उत्तर देतो)" आणि "सामान्य दिवशी आम्ही ___ (प्रतींसाठी थांबतो / लगेच उत्तर देतो)". मग store च्या settings त्याच्याशी जुळतात का ते तपासा.

⏭️ पुढे

भाग 2 पूर्ण झाला. CP systems ना शाखांनी एका leader वर आणि बदलांच्या एका क्रमावर एकमत करायला हवे, काही बंद असल्या तरीही. भाग 3 याची सुरुवात करतो: consensus आणि Raft.

git checkout lesson-09-raft

✂️ Lesson 08 — CAP & PACELC: when the road is cut

📍 You are here: Lesson 08 of 12 · Previous: lesson-07-consistency-models · Next: lesson-09-raft

📦 What's in this branch

Lessons 01–07, plus the choice a network partition forces: stay consistent (refuse to answer) or stay available (answer, maybe with old data) — the CAP theorem — and PACELC, which adds the choice on normal days: latency or consistency. Also: how to settle two changes made on both sides of the split. cap() in dist/demo.py and partition_choice() + resolve() in dist/sim.py.

🧒 Explain like I'm 5

A storm cuts the road. ⛈️ Pune and Nashik can talk to each other. Nagpur and Kolhapur can talk to each other. The two groups cannot reach each other at all.

Pune has just changed the exam day (version 2). Nagpur still has version 1.

A parent in Nagpur asks: "What is the exam day?" Nagpur has two choices:

🔒 Refuse: "Sorry, I cannot check with Pune, so I will not answer." The parent is unhappy, but never told a wrong day. (CP — consistent)
📣 Answer: "Monday" — the old day, the only one Nagpur has. The parent gets an answer, but maybe a wrong one. (AP — available)

There is no third choice while the road is cut. Nagpur cannot know version 2 exists.

Worse: during the storm, both sides accept a change to the class 3A trip. Pune's side says Friday. Nagpur's side says Saturday. When the road opens, which one wins? Keep the bigger number and throw the other away? Or keep both and ask a person?

🗺️ Diagram

flowchart LR
    subgraph left["Pune + Nashik"]
      p["🏫 Pune<br/>latest: v2"]
      n["🏫 Nashik"]
    end
    subgraph right["Nagpur + Kolhapur"]
      g["🏫 Nagpur<br/>holds v1"]
      k["🏫 Kolhapur"]
    end
    p -.-x|"✂️ road cut"| g
    g --> cp["CP: refused<br/>no answer rather than a wrong one"]
    g --> ap["AP: answered v1 (stale!)"]

🗺️ Drawn version + a lab: https://school-edh.pages.dev/distributed-systems/lesson-diagrams.html#l08

❓ What

CAP theorem (Eric Brewer's conjecture in 2000; proved by Seth Gilbert and Nancy Lynch in 2002) — a system with copies cannot guarantee all three of these at once:
- C, Consistency — here it means linearizability (lesson 07), not the "C" of ACID
- A, Availability — every request to a node that is not failed gets a (non-error) answer
- P, Partition tolerance — the system keeps working when the network drops messages between nodes
The real reading — partitions will happen (lesson 01), so P is not optional. CAP says: during a partition, choose C (some requests get errors or wait) or A (every request gets an answer, possibly stale, and the two sides may disagree). When there is no partition, you can have both. "CA" is not a real option for a system that spans a network.
CP systems — refuse on the minority side: etcd, ZooKeeper, consensus-based databases (lesson 09). Right for locks, leader election, bookings, balances.
AP systems — answer on both sides and reconcile later: Cassandra and DynamoDB in their default modes, DNS, caches. Right for carts, likes, presence, feeds.
PACELC (Daniel Abadi, 2010) — if Partition, choose A or C; Else (normal operation), choose Latency or Consistency. Even with no partition, a consistent read or write must wait for other copies; a fast one does not. CAP says nothing about this everyday cost; PACELC does.
Reconciling after the split — if both sides accepted writes (AP), when the road heals:
- last-writer-wins (LWW) — keep the write with the bigger time stamp or version; the other is silently dropped
- merge — keep both (siblings), merge with a CRDT, or let a person decide (lesson 03)

🤔 Why

Because every system with copies will face a cut road, and the choice is made either on purpose (in the design) or by accident (in the code's defaults, found during an outage). "Our database is highly available and strongly consistent" is only true until the network splits. Knowing the choice lets you pick per piece of data: CP for a seat booking, AP for a like counter.

🔧 How (in this repo)

partition_choice(mode, local_version, latest_version) in dist/sim.py returns a refusal for 'CP', or "answered v…" for 'AP' with (stale!) when the local version is behind. resolve(a, b, rule) settles two (version, value) writes: 'lww' keeps the one with the bigger version; anything else ('merge') returns both values, sorted and without duplicates.

🧪 Try it

python3 dist/demo.py cap
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import partition_choice, resolve
for mode in ("CP", "AP"):
    for local in (1, 2):
        print(f"{mode} · Nagpur holds v{local}, latest v2 → {partition_choice(mode, local, 2)}")
print("lww, versions 7 vs 6 →", resolve((7, "trip on Friday"), (6, "trip on Saturday"), "lww"))
print("lww, a tie 6 vs 6    →", resolve((6, "trip on Friday"), (6, "trip on Saturday"), "lww"))
print("merge, same text     →", resolve((5, "trip on Friday"), (6, "trip on Friday"), "merge"))
EOF

✅ Verify — what you should see

cap prints:

── the road between Pune+Nashik and Nagpur+Kolhapur is cut (a partition); Nagpur holds v1, the latest is v2
   CP: Nagpur is asked the exam day → refused — cannot reach a majority, so no answer rather than a wrong one
   AP: Nagpur is asked the exam day → answered v1 (stale!)
── both sides accepted a change during the split: (5, '3A trip on Friday') and (6, '3A trip on Saturday')
   last-writer-wins → '3A trip on Saturday' (the other write is silently dropped) · merge → ['3A trip on Friday', '3A trip on Saturday'] (a person decides)
   PACELC: during a Partition choose A or C; Else (normal days) choose Latency or Consistency

Your snippet prints:

CP · Nagpur holds v1, latest v2 → refused — cannot reach a majority, so no answer rather than a wrong one
CP · Nagpur holds v2, latest v2 → refused — cannot reach a majority, so no answer rather than a wrong one
AP · Nagpur holds v1, latest v2 → answered v1 (stale!)
AP · Nagpur holds v2, latest v2 → answered v2

then:

lww, versions 7 vs 6 → trip on Friday
lww, a tie 6 vs 6    → trip on Friday
merge, same text     → ['trip on Friday']

🏁 What you just proved

A CP node refuses even when its copy happens to be up to date — it cannot know that without the other side. An AP node always answers, and is right only by luck. On a tie, last-writer-wins still picks one (here, simply the first argument) and drops the other, with no error. Merge keeps both — and two identical writes become one.

⚠️ Common mistakes

calling a system "CA" — any system on a network must handle partitions
choosing one letter for the whole product instead of per piece of data
reading CAP's C as ACID's C (they are different ideas)
last-writer-wins with wall-clock time stamps from different machines (lesson 02)
forgetting PACELC: most of the time there is no partition, and the real cost is latency

🏭 In production

Where common systems sit (defaults; many are tunable):

System	During a partition (PAC)	Normal days (ELC)
etcd, ZooKeeper	C — the minority side refuses writes	C — writes wait for a majority
Cassandra, DynamoDB (default reads)	A — both sides answer	L — fast reads, possibly stale
Cassandra with `QUORUM`	C for keys whose replicas are cut off from a majority	C at the cost of latency

On a real account — see CP behaviour in etcd: with 3 members, stop 2, then try a write on the one left:

etcdctl --endpoints=http://nagpur:2379 put exam-day Tuesday
# Error: context deadline exceeded   (no leader: the minority cannot commit)

DynamoDB global tables (one table replicated across AWS Regions) — by default each Region accepts writes and replicates asynchronously; concurrent updates to the same item are settled by last writer wins. That is an AP / EL choice. A newer multi-Region strong consistency mode makes the other choice: writes wait for another Region.

🏭 Why this matters in production: for each data item, fill two blanks: "during a partition we ___ (refuse / answer stale)" and "on normal days we ___ (wait for copies / answer fast)". Then check that the store's settings match.

⏭️ Next

Part 2 is done. CP systems need the branches to agree on one leader and one order of changes, even when some are down. Part 3 starts with how: consensus and Raft.

git checkout lesson-09-raft

← Previousconsistency models Next →raft

This page is the lesson's README from the lesson-08-cap-pacelc branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.