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

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

🔀 धडा 03 — Ordering & causality: आधी, नंतर, की एकाच वेळी

📍 तुम्ही इथे आहात: 12 पैकी धडा 03 · मागे: lesson-02-clocks · पुढे: lesson-04-failure-detection

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

धडे 01–02, अधिक vector clocks: प्रत्येक चिठ्ठीवर असणारा, प्रत्येक शाखेसाठी एक counter. त्यांच्यामुळे दोन घटना एकतर before, after, same, किंवा concurrent असतात — आणि "concurrent" म्हणजे खरा conflict, उशीर नव्हे. dist/demo.py मधले ordering() आणि dist/sim.py मधले VectorClock + compare().

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

आता प्रत्येक शाखा चार खाने असलेले एक छोटे कार्ड ठेवते: पुणे, नाशिक, नागपूर, कोल्हापूर. 🗂️ प्रत्येक खाना मोजतो "त्या शाखेकडून आलेल्या किती गोष्टी मी पाहिल्या आहेत".

पुण्यातली कतरिना काही लिहिते तेव्हा ती पुणे खान्यात 1 मिळवते.
तिच्या चिठ्ठीवर तिच्या कार्डची एक प्रत असते.
नाशिकमधली ऐश्वर्या ती चिठ्ठी वाचते तेव्हा ती प्रत्येक खान्यातला मोठा आकडा घेते, आणि मग नाशिक खान्यात 1 मिळवते.

आता दोन कार्डांची तुलना करा. कार्ड A वरचा प्रत्येक खाना कार्ड B पेक्षा लहान किंवा समान असेल, तर A हे B च्या आधी घडले — B लिहिणाऱ्याने A पाहिले होते.

पण नागपूरमधल्या दीपिकाने कोणतीही चिठ्ठी न वाचता काहीतरी लिहिले. तिचे कार्ड सांगते "नागपूर 1" आणि बाकी सगळीकडे शून्य. ऐश्वर्याचे कार्ड सांगते "पुणे 1, नाशिक 1, नागपूर 0". प्रत्येक कार्डवर असा एक खाना आहे जो दुसऱ्यापेक्षा मोठा आहे. कोणीच दुसऱ्याचे पाहिले नाही. त्या concurrent आहेत — दोन जणींनी एकाच वेळी एकच गोष्ट बदलली, आणि काय ठेवायचे ते कोणीतरी ठरवायलाच हवे.

🗺️ आकृती

flowchart LR
    e1["e1 at Pune<br/>pune 1 · nashik 0 · nagpur 0"]
    e2["e2 at Nashik, after reading e1<br/>pune 1 · nashik 1 · nagpur 0"]
    e3["e3 at Nagpur, saw nobody<br/>pune 0 · nashik 0 · nagpur 1"]
    e1 -->|"note: e1 before e2"| e2
    c["⚡ e2 vs e3: concurrent<br/>a real conflict to resolve"]
    e2 --- c
    e3 --- c

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

❓ काय

Causality — "a चा b वर परिणाम होऊ शकला असता": धडा 02 मधल्या happened-before अर्थाने a → b.
Vector clock — counters ची एक यादी, प्रत्येक node साठी एक. Node प्रत्येक घटनेसाठी स्वतःच्या entry मध्ये 1 मिळवतो. Receive वर, तो आपला vector आणि message चा vector यांचा element-wise maximum घेतो, आणि मग स्वतःच्या entry मध्ये 1 मिळवतो.
दोन vectors A आणि B ची तुलना:
- same — प्रत्येक entry समान
- before — A ची प्रत्येक entry ≤ B (आणि किमान एक लहान): a → b
- after — A ची प्रत्येक entry ≥ B: b → a
- concurrent — प्रत्येक बाजूला एखादी entry मोठी: कोणीच दुसऱ्याचे पाहिले नाही
Lamport clocks पेक्षा vector clocks काय जास्त देतात — Lamport clocks: a → b ⇒ L(a) < L(b), पण उलट नाही. Vector clocks: a → b ⇔ V(a) < V(b). त्यामुळे ते concurrency ओळखतात; Lamport क्रमांक ओळखू शकत नाहीत.
किंमत — प्रत्येक message आणि प्रत्येक साठवलेल्या value वर प्रत्येक node ची एक entry. खूप nodes (किंवा खूप clients) असतील तर vector वाढत जातो; खऱ्या systems version vectors (प्रत्येक client नव्हे, प्रत्येक replica साठी एक entry) आणि dotted version vectors (Riak) असे प्रकार वापरतात.
Conflict — एकाच item वर दोन concurrent writes. System दोन्ही ठेवू शकते ("siblings") आणि application किंवा माणसाला ते merge करू देऊ शकते, CRDT ने आपोआप merge करू शकते (असा data type ज्याचे merges नेहमी जुळतात, जसे counter किंवा set), किंवा एक टाकून देऊ शकते (last-writer-wins, धडा 08).

🤔 का

कारण concurrent writes साठी "शेवटी कोणता write आला?" या प्रश्नाला उत्तरच नाही. जी system time stamp नुसार एक निवडते ती दुसरा गुपचूप गमावते. Vector clocks असलेली system हा फरक पाहू शकते: "ऐश्वर्याच्या बदलाने कतरिनाच्या बदलाची जागा घेतली" (before → नवा ठेवा) आणि "ऐश्वर्या आणि दीपिका दोघींनी न कळता बदलले" (concurrent → दोन्ही ठेवा, merge करा किंवा विचारा). Conflict दिसणे ही data न गमावण्याची पहिली पायरी आहे.

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

dist/sim.py मधले VectorClock(me, nodes) प्रत्येक शाखेसाठी एक counter असलेली dict ठेवते. tick() स्वतःच्या entry मध्ये 1 मिळवते. recv(other) प्रत्येक entry चा maximum घेते, आणि मग tick करते. compare(a, b) प्रत्येक key साठी a[k] <= b[k] आणि a[k] >= b[k] तपासून 'same', 'before', 'after' किंवा 'concurrent' परत देते.

🧪 करून पाहा

python3 dist/demo.py ordering
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import VectorClock, compare
B = ["pune", "nashik", "nagpur", "kolhapur"]
vp, vn, vg = VectorClock("pune", B), VectorClock("nashik", B), VectorClock("nagpur", B)
e1 = vp.tick(); e2 = vn.recv(e1); e3 = vg.recv(e2)     # this time Nagpur reads Nashik's note first
print("e3 =", e3)
print("e1 vs e3:", compare(e1, e3), "· e2 vs e3:", compare(e2, e3), "· e3 vs e1:", compare(e3, e1))
x = vp.tick(); y = vg.tick()                            # both write again without talking
print("x =", x); print("y =", y); print("x vs y:", compare(x, y))
EOF

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

ordering हे print करते:

── vector clocks: e1 at Pune {'pune': 1, 'nashik': 0, 'nagpur': 0, 'kolhapur': 0}
   e2 at Nashik after reading e1 {'pune': 1, 'nashik': 1, 'nagpur': 0, 'kolhapur': 0}
   e3 at Nagpur, unaware of both {'pune': 0, 'nashik': 0, 'nagpur': 1, 'kolhapur': 0}
   e1 vs e2: before
   e2 vs e3: concurrent
   e1 vs e3: concurrent

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

e3 = {'pune': 1, 'nashik': 1, 'nagpur': 1, 'kolhapur': 0}
e1 vs e3: before · e2 vs e3: before · e3 vs e1: after
x = {'pune': 2, 'nashik': 0, 'nagpur': 0, 'kolhapur': 0}
y = {'pune': 1, 'nashik': 1, 'nagpur': 2, 'kolhapur': 0}
x vs y: concurrent

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

नागपूरचा तोच write demo मध्ये "concurrent" आहे आणि तुमच्या snippet मध्ये "after". एकमेव फरक: तुमच्या snippet मध्ये नागपूरने आधी चिठ्ठी वाचली. Causality म्हणजे लिहिणाऱ्याला काय माहीत होते, घड्याळाने त्याने कधी लिहिले असे सांगितले ते नव्हे. आणि y च्या बहुतेक खान्यांत मोठे आकडे असूनही x विरुद्ध y concurrent आहे — पुणे खान्यात x मोठा आहे, त्यामुळे कोणीच दुसऱ्याचे पाहिले नाही.

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

"concurrent" म्हणजे "एकाच सेकंदाला" असे समजणे — त्याचा अर्थ "कोणालाच दुसऱ्याबद्दल माहीत नव्हते"
प्रत्येक conflict last-writer-wins ने सोडवणे, आणि एक write गमावणे
replica ऐवजी प्रत्येक client साठी एक vector entry — vector अमर्याद वाढत जातो
पुढच्या write सोबत vector परत पाठवायला विसरणे, त्यामुळे लिहिणाऱ्याने काय पाहिले होते ते server ला कळत नाही
queue किंवा log त्याच्या सगळ्या भागांमध्ये एक global order ठेवतो असे मानणे (खाली Kafka पाहा)

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

Kafka फक्त एका partition च्या आतच क्रम ठेवतो. एका topic मध्ये अनेक partitions असतात, आणि consumers ते समांतर वाचतात. एकाच key चे messages एकाच partition मध्ये जातात, त्यामुळे ते क्रमाने राहतात; वेगवेगळ्या keys च्या messages मध्ये कोणताही क्रम नसतो. On a real account — एका वर्गाचे timetable बदल वर्गाला key म्हणून पाठवा:

kafka-console-producer.sh --bootstrap-server localhost:9092 --topic timetable \
    --property parse.key=true --property key.separator=:
# then type lines such as:
# class-3A:exam moved to Tuesday
# class-3A:exam room is 12

दोन्ही class-3A ओळी एकाच partition मध्ये, त्याच क्रमाने जातात. class-4B ची ओळ त्यांच्या आधी किंवा नंतर वाचली जाऊ शकते.

Dynamo-style stores — मूळ Amazon Dynamo paper (2007) vector clocks वापरत असे आणि सगळ्या concurrent versions merge करण्यासाठी application ला परत देत असे (shopping cart दोन्ही versions मधली प्रत्येक item ठेवत असे). allow_mult चालू असेल तर Riak concurrent writes siblings म्हणून साठवते, dotted version vectors ने track करून. इतर अनेक systems (Cassandra, DynamoDB global tables) त्याऐवजी time stamp नुसार last-writer-wins वापरतात — सोपे, आणि ते दोन concurrent writes पैकी एक टाकून देते.

CRDTs (conflict-free replicated data types) — आपोआप merge होणारे counters, sets आणि text types; Redis Enterprise active-active databases मध्ये आणि collaborative editors मध्ये (Automerge, Yjs) वापरले जातात.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: दोन ठिकाणी लिहिता येणाऱ्या data च्या प्रत्येक तुकड्यासाठी आधीच ठरवा: कोणती key त्याचे बदल क्रमाने ठेवते, आणि दोन बदल concurrent असतील तर काय होते — दोन्ही ठेवायचे, merge करायचे, की जाणूनबुजून एक टाकायचा.

⏭️ पुढे

आत्तापर्यंत गप्प शाखा हळू असू शकते किंवा बंद पडलेली. तुम्ही ठरवता कसे? Heartbeats आणि timeouts — आणि तो निर्णय कधीच खात्रीचा का नसतो.

git checkout lesson-04-failure-detection

🔀 Lesson 03 — Ordering & causality: before, after, or at the same time

📍 You are here: Lesson 03 of 12 · Previous: lesson-02-clocks · Next: lesson-04-failure-detection

📦 What's in this branch

Lessons 01–02, plus vector clocks: one counter per branch, carried on every note. With them, two events are either before, after, the same, or concurrent — and "concurrent" means a real conflict, not a delay. ordering() in dist/demo.py and VectorClock + compare() in dist/sim.py.

🧒 Explain like I'm 5

Each branch now keeps a small card with four boxes: Pune, Nashik, Nagpur, Kolhapur. 🗂️ Each box counts "how many things from that branch I have seen".

When Katrina in Pune writes something, she adds 1 to the Pune box.
Her note carries a copy of her card.
When Aishwarya in Nashik reads the note, she takes the bigger number in each box, then adds 1 to the Nashik box.

Now compare two cards. If every box on card A is less than or equal to card B, then A happened before B — B's writer had seen A.

But Dipika in Nagpur wrote something without reading any note. Her card says "Nagpur 1" and zero everywhere else. Aishwarya's card says "Pune 1, Nashik 1, Nagpur 0". Each card has a box that is bigger than the other's. Neither saw the other. They are concurrent — two people changed the same thing at the same time, and someone must decide what to keep.

🗺️ Diagram

flowchart LR
    e1["e1 at Pune<br/>pune 1 · nashik 0 · nagpur 0"]
    e2["e2 at Nashik, after reading e1<br/>pune 1 · nashik 1 · nagpur 0"]
    e3["e3 at Nagpur, saw nobody<br/>pune 0 · nashik 0 · nagpur 1"]
    e1 -->|"note: e1 before e2"| e2
    c["⚡ e2 vs e3: concurrent<br/>a real conflict to resolve"]
    e2 --- c
    e3 --- c

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

❓ What

Causality — "a could have influenced b": a → b in the happened-before sense from lesson 02.
Vector clock — a list of counters, one per node. A node adds 1 to its own entry for each event. On receive, it takes the element-wise maximum of its vector and the message's vector, then adds 1 to its own entry.
Comparing two vectors A and B:
- same — every entry equal
- before — every entry of A ≤ B (and at least one smaller): a → b
- after — every entry of A ≥ B: b → a
- concurrent — some entry bigger on each side: neither saw the other
What vector clocks add over Lamport clocks — Lamport clocks: a → b ⇒ L(a) < L(b), but not the reverse. Vector clocks: a → b ⇔ V(a) < V(b). So they detect concurrency; Lamport numbers cannot.
The cost — one entry per node on every message and every stored value. With many nodes (or many clients), the vector grows; real systems use variants such as version vectors (one entry per replica, not per client) and dotted version vectors (Riak).
Conflict — two concurrent writes to the same item. A system can keep both ("siblings") and let the application or a person merge them, merge automatically with a CRDT (a data type designed so that merges always agree, such as a counter or a set), or drop one (last-writer-wins, lesson 08).

🤔 Why

Because "which write came last?" has no answer for concurrent writes. A system that picks one by time stamp silently loses the other. A system with vector clocks can see the difference between "Aishwarya's change replaced Katrina's" (before → keep the newer) and "Aishwarya and Dipika both changed it without knowing" (concurrent → keep both, merge or ask). Seeing the conflict is the first step to not losing data.

🔧 How (in this repo)

VectorClock(me, nodes) in dist/sim.py holds a dict with one counter per branch. tick() adds 1 to its own entry. recv(other) takes the maximum of each entry, then ticks. compare(a, b) returns 'same', 'before', 'after' or 'concurrent' by checking a[k] <= b[k] and a[k] >= b[k] for every key.

🧪 Try it

python3 dist/demo.py ordering
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import VectorClock, compare
B = ["pune", "nashik", "nagpur", "kolhapur"]
vp, vn, vg = VectorClock("pune", B), VectorClock("nashik", B), VectorClock("nagpur", B)
e1 = vp.tick(); e2 = vn.recv(e1); e3 = vg.recv(e2)     # this time Nagpur reads Nashik's note first
print("e3 =", e3)
print("e1 vs e3:", compare(e1, e3), "· e2 vs e3:", compare(e2, e3), "· e3 vs e1:", compare(e3, e1))
x = vp.tick(); y = vg.tick()                            # both write again without talking
print("x =", x); print("y =", y); print("x vs y:", compare(x, y))
EOF

✅ Verify — what you should see

ordering prints:

── vector clocks: e1 at Pune {'pune': 1, 'nashik': 0, 'nagpur': 0, 'kolhapur': 0}
   e2 at Nashik after reading e1 {'pune': 1, 'nashik': 1, 'nagpur': 0, 'kolhapur': 0}
   e3 at Nagpur, unaware of both {'pune': 0, 'nashik': 0, 'nagpur': 1, 'kolhapur': 0}
   e1 vs e2: before
   e2 vs e3: concurrent
   e1 vs e3: concurrent

Your snippet prints:

e3 = {'pune': 1, 'nashik': 1, 'nagpur': 1, 'kolhapur': 0}
e1 vs e3: before · e2 vs e3: before · e3 vs e1: after
x = {'pune': 2, 'nashik': 0, 'nagpur': 0, 'kolhapur': 0}
y = {'pune': 1, 'nashik': 1, 'nagpur': 2, 'kolhapur': 0}
x vs y: concurrent

🏁 What you just proved

The same Nagpur write is "concurrent" in the demo and "after" in your snippet. The only difference: in your snippet Nagpur read the note first. Causality is about what a writer knew, not about when the clock said it wrote. And x vs y is concurrent even though y has bigger numbers in most boxes — x is bigger in the Pune box, so neither saw the other.

⚠️ Common mistakes

treating "concurrent" as "at the same second" — it means "neither knew about the other"
resolving every conflict with last-writer-wins, and losing one of the writes
one vector entry per client instead of per replica — the vector grows without end
forgetting to send the vector back with the next write, so the server cannot tell what the writer had seen
assuming a queue or a log keeps a global order across all its parts (see Kafka below)

🏭 In production

Kafka keeps order only inside one partition. A topic has many partitions, and consumers read them in parallel. Messages with the same key go to the same partition, so they stay in order; messages with different keys have no order between them. On a real account — send the timetable changes for one class with the class as the key:

kafka-console-producer.sh --bootstrap-server localhost:9092 --topic timetable \
    --property parse.key=true --property key.separator=:
# then type lines such as:
# class-3A:exam moved to Tuesday
# class-3A:exam room is 12

Both class-3A lines land in one partition, in that order. A class-4B line may be read before or after them.

Dynamo-style stores — the original Amazon Dynamo paper (2007) used vector clocks and returned all concurrent versions to the application to merge (a shopping cart kept every item from both versions). Riak stores concurrent writes as siblings, tracked with dotted version vectors, when allow_mult is on. Many other systems (Cassandra, DynamoDB global tables) use last-writer-wins by time stamp instead — simple, and it drops one of two concurrent writes.

CRDTs (conflict-free replicated data types) — counters, sets and text types that merge automatically; used in Redis Enterprise active-active databases and in collaborative editors (Automerge, Yjs).

🏭 Why this matters in production: for each piece of data that two places can write, decide in advance: which key keeps its changes in order, and what happens when two changes are concurrent — keep both, merge, or knowingly drop one.

⏭️ Next

So far a silent branch might be slow or dead. How do you decide? Heartbeats and timeouts — and why the decision is never certain.

git checkout lesson-04-failure-detection

← Previousclocks Next →failure detection

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