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

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

🗳️ धडा 06 — Quorums: N पैकी W ला लिहा, R मधून वाचा

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

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

धडे 01–05, अधिक quorums सह leaderless replication: N प्रती ठेवा, W प्रतींकडे write पोहोचला की तो पूर्ण झाला असे धरा, आणि R प्रती वाचून सर्वात नवी ठेवा. जेव्हा R + W > N, तेव्हा प्रत्येक read सर्वात नवा write पाहतो. Read repair read दरम्यान जुन्या प्रती दुरुस्त करते; hinted handoff आणि anti-entropy त्या background मध्ये दुरुस्त करतात. dist/demo.py मधले quorums() आणि dist/sim.py मधले QuorumStore.

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

आता मुख्य नोंदवही नाही. तीन शाखा प्रत्येकी exam notice ची एक प्रत ठेवतात (N = 3). प्रत्येक प्रतीवर एक version number असतो.

दीपिका notice "exam on Monday" (version 1) वरून "exam moved to Tuesday" (version 2) करते. तिसऱ्या शाखेकडचा रस्ता तुटलेला आहे, म्हणून फक्त दोन प्रतींना बदल मिळतो (W = 2).

नंतर ऐश्वर्याला exam चा दिवस जाणून घ्यायचा आहे. ती एका शाखेवर विसंबत नाही, म्हणून ती त्यापैकी दोघींना विचारते (R = 2). एक सांगते "version 2: Tuesday". एक सांगते "version 1: Monday". ती मोठी version ठेवते — Tuesday — आणि जुन्या शाखेला नवे पान पाठवते (read repair).

इथे दोघींना विचारणे नेहमी का चालते? 3 प्रती आहेत. बदल 2 वर आहे. ऐश्वर्या 2 ना विचारते. 3 पैकी 2-2 च्या दोन गटांमध्ये किमान एक शाखा सामायिक असलीच पाहिजे. त्या सामायिक शाखेकडे नवे पान आहे. 🎯

🗺️ आकृती

flowchart LR
    w["✍️ write v2 'exam moved to Tuesday'<br/>W = 2"] --> c0["copy 0<br/>v2 Tuesday"]
    w --> c1["copy 1<br/>v2 Tuesday"]
    c2["copy 2<br/>v1 Monday — road was cut"]
    r["👀 read R = 2<br/>asks copies 1 and 2"] --> c1
    r --> c2
    c1 --> k["keep the biggest version: v2<br/>copy 1 is in both groups"]
    k -->|"read repair"| c2

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

❓ काय

N — प्रत्येक item च्या किती प्रती (replication factor).
W — write पूर्ण झाला असे धरण्याआधी किती प्रतींनी तो confirm करायला हवा.
R — read किती प्रतींना विचारतो; तो सर्वात नवी version असलेली value ठेवतो.
R + W > N — तेव्हा R प्रतींचा प्रत्येक संच W प्रतींच्या प्रत्येक संचाशी किमान एका प्रतीत एकमेकांवर येतो (overlap), त्यामुळे read मध्ये नेहमी सर्वात नवा write असतो. N = 3 सह, नेहमीची निवड W = 2, R = 2 (दोन्ही बाजूंनी बहुमत). W = 3, R = 1 ने reads जलद आणि writes हळू होतात; W = 1, R = 3 ने उलट.
R + W ≤ N — reads सर्वात नवा write चुकवू शकतात. जास्त जलद, आणि जास्त available, पण फक्त eventually consistent.
R + W > N काय वचन देत नाही — ते पूर्ण linearizability नाही (धडा 07). काही प्रतींवर अयशस्वी झालेला write इतरांवर राहू शकतो; दोन concurrent writes साठी अजूनही एक नियम लागतो (धडा 08); आणि "sloppy" quorums (खाली) मध्ये overlap ची हमी नसते.
Read repair — read ला जुनी प्रत दिसली की तो सर्वात नवी value तिच्यावर परत लिहितो.
Hinted handoff — एखादी प्रत बंद असेल तेव्हा दुसरा node तो write एका "hint" सह ठेवतो ("हे copy 2 चे आहे") आणि copy 2 परत आली की तिच्याकडे सोपवतो. Sloppy quorum अशा बदली nodes ना W मध्ये मोजतो.
Anti-entropy — background process प्रतींची तुलना करते (अनेकदा Merkle trees ने — hashes चे trees, त्यामुळे दोन nodes सगळे न पाठवता वेगळे असलेले भाग शोधतात) आणि कोणी न वाचणाऱ्या प्रती दुरुस्त करते.

🤔 का

कारण प्रत्येक write साठी एकच leader चालू असायला हवा, आणि पोहोचण्याजोगा असायला हवा. Quorums सह, कोणत्याही W प्रती write घेऊ शकतात आणि कोणत्याही R प्रती read चे उत्तर देऊ शकतात, त्यामुळे एक किंवा दोन हळू किंवा बंद पडलेल्या प्रती system थांबवत नाहीत. तुम्ही प्रत्येक request साठी R आणि W निवडता: सर्वात नवे हवे असेल तेव्हा मजबूत reads, थोडा जुनेपणा चालत असेल तेव्हा जलद reads. Amazon च्या Dynamo paper ने (2007) हे design प्रसिद्ध केले; Cassandra आणि Riak ते पाळतात.

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

dist/sim.py मधले QuorumStore(n) copies ठेवते, म्हणजे (version, value) ची list. write(version, value, w, reachable) reachable मधल्या पहिल्या w प्रतींवर लिहिते आणि ते w पर्यंत पोहोचले की नाही ते परत देते. read(r, order, repair=True) order मधल्या पहिल्या r प्रतींना विचारते, maximum (version, value) ठेवते, आणि — repair चालू असेल तर — ते जुन्या प्रतींवर परत लिहिते. ते (value, stale copy numbers) परत देते.

🧪 करून पाहा

python3 dist/demo.py quorums
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import QuorumStore
for w in (1, 2, 3):
    for r in (1, 2, 3):
        s = QuorumStore(3); s.write(1, "Monday", 3)
        s.write(2, "Tuesday", w, reachable=[0, 1, 2])      # the write lands on copies 0..w-1
        v, stale = s.read(r, order=[2, 1, 0], repair=False) # the read asks the far end first
        ok = "newest" if v == "Tuesday" else "STALE"
        print(f"W={w} R={r}  R+W={r+w} {'>' if r+w > 3 else '≤'} 3 → read {v!r:<10} {ok}")
EOF

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

quorums हे print करते:

── 3 copies, the change reached only W=2 of them: [(2, 'exam moved to Tuesday'), (2, 'exam moved to Tuesday'), (1, 'exam on Monday')]
   read R=2 from copies 1 and 2 → 'exam moved to Tuesday' · copy [2] was stale and got repaired → [(2, 'exam moved to Tuesday'), (2, 'exam moved to Tuesday'), (2, 'exam moved to Tuesday')]
   R + W > N (2 + 2 > 3): every read quorum overlaps every write quorum, so the newest version is always seen

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

W=1 R=1  R+W=2 ≤ 3 → read 'Monday'   STALE
W=1 R=2  R+W=3 ≤ 3 → read 'Monday'   STALE
W=1 R=3  R+W=4 > 3 → read 'Tuesday'  newest
W=2 R=1  R+W=3 ≤ 3 → read 'Monday'   STALE
W=2 R=2  R+W=4 > 3 → read 'Tuesday'  newest
W=2 R=3  R+W=5 > 3 → read 'Tuesday'  newest
W=3 R=1  R+W=4 > 3 → read 'Tuesday'  newest
W=3 R=2  R+W=5 > 3 → read 'Tuesday'  newest
W=3 R=3  R+W=6 > 3 → read 'Tuesday'  newest

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

Snippet write आणि read प्रतींच्या विरुद्ध टोकांवर ठेवतो — सर्वात वाईट परिस्थिती. R + W > 3 असलेल्या प्रत्येक ओळीने तरीही Tuesday वाचले; R + W ≤ 3 असलेल्या प्रत्येक ओळीने Monday वाचले. हा नियम नशिबावर नाही: तो मोजणीवर आहे. आणि demo मध्ये, जुनी copy 2 read नेच दुरुस्त केली.

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

"वेगासाठी" R = 1, W = 1, आणि मग स्वतःचा write वाचायला मिळेल अशी अपेक्षा ठेवणे
अयशस्वी write (W पेक्षा कमी प्रती) काही प्रतींवर तरीही असू शकतो हे विसरणे
बदली nodes मोजणे (sloppy quorum) आणि तरीही R + W > N overlap करते असे मानणे
anti-entropy repair कधीच न चालवणे, त्यामुळे क्वचित वाचला जाणारा data कायमचा जुना राहतो
machines पलीकडे "version" म्हणून wall-clock time stamps वापरणे (धडा 02)

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

Cassandra — consistency level म्हणजे R किंवा W, प्रत्येक request साठी निवडलेला. Replication factor 3 असेल तर QUORUM म्हणजे 2. On a real account, cqlsh मध्ये:

CREATE KEYSPACE school WITH replication = {'class': 'NetworkTopologyStrategy', 'pune_dc': 3};
CONSISTENCY QUORUM;                      -- this session's reads and writes use QUORUM (2 of 3)
INSERT INTO school.notices (id, body) VALUES ('exam', 'exam moved to Tuesday');
SELECT body FROM school.notices WHERE id = 'exam';
CONSISTENCY ONE;                         -- faster, may be stale

इतर levels: ALL, LOCAL_QUORUM (फक्त local data center मधले बहुमत — अनेक data centers असताना सामान्य), EACH_QUORUM, ANY (writes साठी; एक hint पुरेसा). Cassandra प्रती तीन प्रकारे दुरुस्त करते: read दरम्यान replicas जुळत नसतील तेव्हा read repair, hinted handoff (बंद replica साठी coordinator hints ठेवतो, जास्तीत जास्त max_hint_window पर्यंत — default नुसार 3 तास), आणि Merkle trees सह anti-entropy repair, जो तुम्ही ठरलेल्या वेळापत्रकावर चालवता:

nodetool repair school           # run on each node regularly — within gc_grace_seconds (10 days by default)
nodetool status                  # which nodes are up (UN = up/normal)

Amazon DynamoDB प्रत्येक item तीन Availability Zones मध्ये साठवते आणि ही निवड R आणि W म्हणून नव्हे, तर दोन read modes म्हणून देते (धडा 07). Riak तुम्हाला प्रत्येक bucket किंवा प्रत्येक request साठी r, w आणि n_val ठरवू देते.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक table साठी तुम्ही वापरता ते N, R आणि W लिहा आणि जिथे सर्वात नवी value हवी तिथे R + W > N तपासा. nodetool repair (किंवा तुमच्या store चे repair) ठरलेल्या वेळापत्रकावर ठेवा आणि ते पूर्ण झाले नाही तर alert द्या.

⏭️ पुढे

"Reads सर्वात नवे पाहतात" हे एक वचन आहे. आणखी अनेक आहेत, जास्त मजबूत आणि कमकुवत. पुढे: consistency models — प्रत्येक जण वाचणाऱ्याला काय वचन देतो.

git checkout lesson-07-consistency-models

🗳️ Lesson 06 — Quorums: write to W, read from R, out of N

📍 You are here: Lesson 06 of 12 · Previous: lesson-05-replication · Next: lesson-07-consistency-models

📦 What's in this branch

Lessons 01–05, plus leaderless replication with quorums: keep N copies, count a write as done when W copies have it, and read R copies and keep the newest. When R + W > N, every read sees the newest write. Read repair fixes stale copies during a read; hinted handoff and anti-entropy fix them in the background. quorums() in dist/demo.py and QuorumStore in dist/sim.py.

🧒 Explain like I'm 5

Now there is no main register. Three branches each keep a copy of the exam notice (N = 3). Each copy has a version number on it.

Dipika changes the notice from "exam on Monday" (version 1) to "exam moved to Tuesday" (version 2). The road to the third branch is cut, so only two copies get the change (W = 2).

Later Aishwarya wants to know the exam day. She does not trust one branch, so she asks two of them (R = 2). One says "version 2: Tuesday". One says "version 1: Monday". She keeps the bigger version — Tuesday — and sends the old branch the new page (read repair).

Why does asking two always work here? There are 3 copies. The change is on 2. Aishwarya asks 2. Two groups of 2 out of 3 must share at least one branch. That shared branch has the new page. 🎯

🗺️ Diagram

flowchart LR
    w["✍️ write v2 'exam moved to Tuesday'<br/>W = 2"] --> c0["copy 0<br/>v2 Tuesday"]
    w --> c1["copy 1<br/>v2 Tuesday"]
    c2["copy 2<br/>v1 Monday — road was cut"]
    r["👀 read R = 2<br/>asks copies 1 and 2"] --> c1
    r --> c2
    c1 --> k["keep the biggest version: v2<br/>copy 1 is in both groups"]
    k -->|"read repair"| c2

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

❓ What

N — how many copies of each item (the replication factor).
W — how many copies must confirm a write before it counts as done.
R — how many copies a read asks; it keeps the value with the newest version.
R + W > N — then every set of R copies overlaps every set of W copies in at least one copy, so the read always includes the newest write. With N = 3, the usual choice is W = 2, R = 2 (a majority each way). W = 3, R = 1 gives fast reads and slow writes; W = 1, R = 3 the reverse.
R + W ≤ N — reads can miss the newest write. Faster, and more available, but eventually consistent only.
What R + W > N does not promise — it is not full linearizability (lesson 07). A write that failed on some copies may stay on others; two concurrent writes still need a rule (lesson 08); and with "sloppy" quorums (below) the overlap is not guaranteed.
Read repair — when a read sees a stale copy, it writes the newest value back to it.
Hinted handoff — when a copy is down, another node keeps the write with a "hint" ("this belongs to copy 2") and hands it over when copy 2 is back. A sloppy quorum counts those stand-ins toward W.
Anti-entropy — a background process compares copies (often with Merkle trees — trees of hashes, so two nodes find the differing parts without sending everything) and repairs copies that nobody reads.

🤔 Why

Because a single leader must be up, and must be reachable, for every write. With quorums, any W copies can take a write and any R copies can answer a read, so one or two slow or dead copies do not stop the system. You choose R and W per request: stronger reads when you need the newest, faster reads when a little staleness is fine. Amazon's Dynamo paper (2007) made this design famous; Cassandra and Riak follow it.

🔧 How (in this repo)

QuorumStore(n) in dist/sim.py keeps copies, a list of (version, value). write(version, value, w, reachable) writes to the first w copies in reachable and returns whether it reached w. read(r, order, repair=True) asks the first r copies in order, keeps the maximum (version, value), and — when repair is on — writes it back to the stale copies. It returns (value, stale copy numbers).

🧪 Try it

python3 dist/demo.py quorums
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import QuorumStore
for w in (1, 2, 3):
    for r in (1, 2, 3):
        s = QuorumStore(3); s.write(1, "Monday", 3)
        s.write(2, "Tuesday", w, reachable=[0, 1, 2])      # the write lands on copies 0..w-1
        v, stale = s.read(r, order=[2, 1, 0], repair=False) # the read asks the far end first
        ok = "newest" if v == "Tuesday" else "STALE"
        print(f"W={w} R={r}  R+W={r+w} {'>' if r+w > 3 else '≤'} 3 → read {v!r:<10} {ok}")
EOF

✅ Verify — what you should see

quorums prints:

── 3 copies, the change reached only W=2 of them: [(2, 'exam moved to Tuesday'), (2, 'exam moved to Tuesday'), (1, 'exam on Monday')]
   read R=2 from copies 1 and 2 → 'exam moved to Tuesday' · copy [2] was stale and got repaired → [(2, 'exam moved to Tuesday'), (2, 'exam moved to Tuesday'), (2, 'exam moved to Tuesday')]
   R + W > N (2 + 2 > 3): every read quorum overlaps every write quorum, so the newest version is always seen

Your snippet prints:

W=1 R=1  R+W=2 ≤ 3 → read 'Monday'   STALE
W=1 R=2  R+W=3 ≤ 3 → read 'Monday'   STALE
W=1 R=3  R+W=4 > 3 → read 'Tuesday'  newest
W=2 R=1  R+W=3 ≤ 3 → read 'Monday'   STALE
W=2 R=2  R+W=4 > 3 → read 'Tuesday'  newest
W=2 R=3  R+W=5 > 3 → read 'Tuesday'  newest
W=3 R=1  R+W=4 > 3 → read 'Tuesday'  newest
W=3 R=2  R+W=5 > 3 → read 'Tuesday'  newest
W=3 R=3  R+W=6 > 3 → read 'Tuesday'  newest

🏁 What you just proved

The snippet puts the write and the read on opposite ends of the copies — the worst case. Every row with R + W > 3 still read Tuesday; every row with R + W ≤ 3 read Monday. The rule is not luck: it is counting. And in the demo, the stale copy 2 was fixed by the read itself.

⚠️ Common mistakes

R = 1, W = 1 "for speed", and then expecting to read your own write
forgetting that a failed write (fewer than W copies) may still be on some copies
counting stand-in nodes (sloppy quorum) and assuming R + W > N still overlaps
never running anti-entropy repair, so rarely read data stays stale for ever
using wall-clock time stamps as the "version" across machines (lesson 02)

🏭 In production

Cassandra — the consistency level is R or W, chosen per request. With a replication factor of 3, QUORUM means 2. On a real account, in cqlsh:

CREATE KEYSPACE school WITH replication = {'class': 'NetworkTopologyStrategy', 'pune_dc': 3};
CONSISTENCY QUORUM;                      -- this session's reads and writes use QUORUM (2 of 3)
INSERT INTO school.notices (id, body) VALUES ('exam', 'exam moved to Tuesday');
SELECT body FROM school.notices WHERE id = 'exam';
CONSISTENCY ONE;                         -- faster, may be stale

Other levels: ALL, LOCAL_QUORUM (a majority in the local data center only — common with several data centers), EACH_QUORUM, ANY (for writes; a hint is enough). Cassandra repairs copies three ways: read repair when replicas disagree during a read, hinted handoff (a coordinator keeps hints for a down replica, for up to max_hint_window — 3 hours by default), and anti-entropy repair with Merkle trees, which you run on a schedule:

nodetool repair school           # run on each node regularly — within gc_grace_seconds (10 days by default)
nodetool status                  # which nodes are up (UN = up/normal)

Amazon DynamoDB stores each item in three Availability Zones and exposes the choice as two read modes, not as R and W (lesson 07). Riak lets you set r, w and n_val per bucket or per request.

🏭 Why this matters in production: for each table, write the N, R and W you use and check R + W > N where you need the newest value. Put nodetool repair (or your store's repair) on a schedule and alert when it has not finished.

⏭️ Next

"Reads see the newest" is one promise. There are several others, stronger and weaker. Next: consistency models — what each one promises the reader.

git checkout lesson-07-consistency-models

← Previousreplication Next →consistency models

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