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

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

🕰️ धडा 02 — Clocks: प्रत्येक शाखेचे घड्याळ थोडेसे चुकीचे असते

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

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

धडा 01, अधिक वेळ. प्रत्येक शाखेचे स्वतःचे wall clock असते, आणि ती हळूहळू वेगळी होत जातात. वेगवेगळ्या machines वरच्या घटनांचा क्रम wall time सुरक्षितपणे का ठरवू शकत नाही, NTP काय दुरुस्त करू शकतो आणि काय नाही, monotonic विरुद्ध wall clocks, आणि Lamport clocks — कोणत्याही खऱ्या घड्याळाशिवाय कारणाला परिणामाच्या आधी ठेवणारा एक counter. dist/demo.py मधले clocks() आणि dist/sim.py मधले LamportClock.

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

प्रत्येक शाखेच्या भिंतीवर एक घड्याळ आहे. 🕰️ सगळी एकाच दिवशी लावली होती. पण घड्याळे परिपूर्ण नसतात. पुण्याचे घड्याळ थोडे पुढे पळते. नाशिकचे थोडे मागे राहते.

एकाच क्षणी, पुण्याचे घड्याळ 10:00:00.120 दाखवते आणि नाशिकचे 09:59:59.980.

पुण्यातली कतरिना "exam at 10" लिहिते आणि तिच्या घड्याळानुसार त्यावर 10:00:00.100 अशी वेळ टाकते. एका क्षणाने नंतर, नाशिकमधली ऐश्वर्या ते बदलून "exam at 11" करते आणि तिच्या घड्याळानुसार त्यावर 10:00:00.050 अशी वेळ टाकते.

आता कोणीतरी चिठ्ठ्या वेळेनुसार लावते. पुण्याच्या चिठ्ठीवरची वेळ मोठी आहे. म्हणून पुण्याची चिठ्ठी जिंकते. पण ऐश्वर्याचा बदल नंतर आला होता! तिचा बदल फेकून दिला जातो, आणि कोणाच्या लक्षातही येत नाही.

म्हणून शाखा वेगळी कल्पना वापरून पाहतात. प्रत्येक शाखा एक counter ठेवते. 🔢 प्रत्येक वेळी तुम्ही लिहिता, 1 मिळवा. प्रत्येक चिठ्ठीवर तुमचा counter असतो. तुम्हाला चिठ्ठी मिळाली की तुमचा counter "माझा आणि चिठ्ठीचा यांपैकी मोठा, अधिक 1" असा करा. आता उत्तराला नेहमी ते ज्या प्रश्नाचे उत्तर आहे त्याच्यापेक्षा मोठा क्रमांक असतो. Wall clock ची गरजच नाही. त्या counter ला Lamport clock म्हणतात.

🗺️ आकृती

flowchart LR
    subgraph wall["🕰️ wall clocks: Pune is 140 ms ahead"]
      p1["Pune writes 'exam at 10'<br/>stamp 10:00:00.100"] --> n1["Nashik writes 'exam at 11' LATER<br/>stamp 10:00:00.050"]
      n1 --> lww["sort by stamp: Pune's note wins<br/>the later change is lost"]
    end
    subgraph lam["🔢 Lamport clocks"]
      a["Pune writes<br/>L = 1"] -->|"note carries 1"| b["Nashik receives<br/>L = max(0, 1) + 1 = 2"]
      b --> c["Nashik writes<br/>L = 3"]
    end

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

❓ काय

Wall clock (दिवसातील वेळ) — "10:00:00" सांगणारे घड्याळ. Computer चा crystal oscillator थोडा जलद किंवा हळू चालतो, त्यामुळे घड्याळ पुढे-मागे होते (drift) (सामान्य आकडा म्हणजे सुमारे 200 parts per million पर्यंत — कोणी दुरुस्त केले नाही तर दिवसाला सुमारे 17 सेकंदांपर्यंत).
Clock skew — एकाच क्षणी दोन घड्याळांमधला फरक. Demo मध्ये: 10:00:00.120 − 09:59:59.980 = 140 ms.
NTP (Network Time Protocol) — machine time servers ना विचारते आणि आपले घड्याळ दुरुस्त करते. याची खूप मदत होते, पण मर्यादा आहेत: internet वरून दहा-दहा milliseconds च्या चुका सामान्य आहेत, आणि network delay दोन्ही दिशांना सारखाच असेल यावर ते अवलंबून असते. एखादी दुरुस्ती wall clock ला मागेही उडी मारायला लावू शकते.
Monotonic clock — फक्त पुढेच जाणारे घड्याळ, एकाच machine वर कालावधी मोजण्यासाठी (Python time.monotonic(), Linux CLOCK_MONOTONIC). त्याच्या आकड्याला दुसऱ्या machine वर काहीच अर्थ नसतो. ते timeouts आणि "याला किती वेळ लागला" साठी वापरा; wall clock फक्त माणसाला वेळ दाखवण्यासाठी वापरा.
Wall time नुसार last-writer-wins (LWW) — सर्वात मोठी वेळ असलेला write ठेवा. Skew दोन writes मधल्या अंतरापेक्षा मोठा असेल तर आधीचा write जिंकतो आणि नंतरचा गुपचूप हरवतो.
Happened-before (→) — Leslie Lamport ची 1978 ची कल्पना: a → b जर एकाच node वर a हे b च्या आधी आले, किंवा a message पाठवत आहे आणि b तो घेत आहे, किंवा अशांची एक साखळी आहे. a → b ही नाही आणि b → a ही नाही, तर त्या घटना concurrent आहेत.
Lamport clock — प्रत्येक node वर एक counter. tick() प्रत्येक घटनेसाठी 1 मिळवते. recv(t) counter ला max(mine, t) + 1 करते. तो हमी देतो तो नियम: a → b असेल तर L(a) < L(b). उलट खरे नाही: L(a) < L(b) म्हणजे a मुळे b झाले असे नाही. बरोबरी सोडवायला node चे नाव जोडा, आणि तुम्हाला प्रत्येक node मान्य करतो असा total order मिळतो.

🤔 का

कारण "सर्वात नवा write ठेवा" हा distributed data मधला सर्वात सामान्य नियम आहे, आणि "सर्वात नवा" म्हणजे सहसा "सर्वात मोठी time stamp". Skew असेल तर सर्वात मोठी stamp म्हणजे सर्वात नवा write नसतो. Data चे नुकसान गुपचूप होते: error नाही, log line नाही, फक्त एक बदल नाहीसा होतो. Lamport clocks असा क्रम देतात जो नेहमी कारण आणि परिणाम पाळतो, आणि त्याची किंमत म्हणजे प्रत्येक message वर एक छोटा आकडा.

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

dist/sim.py मधल्या LamportClock मध्ये t, tick() (+1) आणि recv(other) (max(t, other) + 1) आहेत. dist/demo.py मधले clocks() skew ची गोष्ट आणि एक पुणे → नाशिक देवाणघेवाण print करते. खालच्या snippet मधला wall-clock भाग साधे गणित आहे: प्रत्येक शाखेची time stamp म्हणजे खरी वेळ अधिक त्या शाखेचा offset, आणि धडा 08 मधले resolve(..., "lww") सर्वात मोठी stamp ठेवते.

🧪 करून पाहा

python3 dist/demo.py clocks
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import LamportClock, resolve
p, n, g = LamportClock(), LamportClock(), LamportClock()
a = p.tick(); b = p.tick()            # Pune writes twice
c = g.tick()                          # Nagpur writes once, sees nobody
d = n.recv(b)                         # Nashik reads Pune's second note
e = n.tick()                          # Nashik writes
print(f"Pune a={a} b={b} · Nagpur c={c} · Nashik receives b → {d}, writes e={e}")
print("b caused e, so b < e:", b < e)
print("c and b never met, yet c < b:", c < b, "— a smaller number does NOT mean 'caused'")
# true time in ms after 10:00:00.000; each branch's clock is off by an offset
for pune_off, nashik_off in ((120, -20), (100, 0), (60, 0), (0, 0)):
    pune_stamp   = -20 + pune_off        # Pune writes FIRST, at true time -20 ms
    nashik_stamp =  70 + nashik_off      # Nashik writes 90 ms LATER, at true time +70 ms
    kept = resolve((pune_stamp, "exam at 10"), (nashik_stamp, "exam at 11"), "lww")
    print(f"Pune ahead by {pune_off - nashik_off:>3} ms → stamps pune {pune_stamp:>3}, nashik {nashik_stamp:>3} → last-writer-wins keeps {kept!r}")
EOF

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

clocks हे print करते:

── wall clocks drift: Pune's clock reads 10:00:00.120, Nashik's reads 09:59:59.980 at the same instant
   Pune writes 'exam at 10' at 10:00:00.100 by its clock; Nashik then writes 'exam at 11' at 10:00:00.050 by its clock
   sorting by wall time says Pune's note was LAST — the later change is silently thrown away
── Lamport: Pune writes (L=1) → Nashik receives (L=2) → Nashik writes (L=3) — cause always has a smaller number

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

Pune a=1 b=2 · Nagpur c=1 · Nashik receives b → 3, writes e=4
b caused e, so b < e: True
c and b never met, yet c < b: True — a smaller number does NOT mean 'caused'
Pune ahead by 140 ms → stamps pune 100, nashik  50 → last-writer-wins keeps 'exam at 10'
Pune ahead by 100 ms → stamps pune  80, nashik  70 → last-writer-wins keeps 'exam at 10'
Pune ahead by  60 ms → stamps pune  40, nashik  70 → last-writer-wins keeps 'exam at 11'
Pune ahead by   0 ms → stamps pune -20, nashik  70 → last-writer-wins keeps 'exam at 11'

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

दोन writes मध्ये 90 ms चे अंतर होते. 100 किंवा 140 ms च्या skew ने last-writer-wins ने जुना write ठेवला. 60 ms किंवा त्याहून कमी skew ने त्याने बरोबर write ठेवला. म्हणजे wall-clock क्रम फक्त तेव्हाच सुरक्षित आहे जेव्हा skew writes मधल्या अंतरापेक्षा लहान असतो — आणि तुम्हाला यापैकी कोणताच आकडा क्वचितच माहीत असतो. Lamport क्रमांक नेहमी कारणाला परिणामाच्या आधी ठेवतात (b=2 < e=4), पण c=1 < b=2 दाखवते की लहान क्रमांक अशा घटनेचाही असू शकतो जिचा दुसरीशी काहीच संबंध नव्हता. हे दोन प्रकार वेगळे ओळखणे हा पुढचा धडा आहे.

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

wall clock ने timeout मोजणे — NTP दुरुस्तीमुळे तो negative किंवा प्रचंड होऊ शकतो
वेगवेगळ्या machines वरचे writes त्यांच्या wall-clock time stamps नुसार क्रमाने लावणे
"NTP चालू आहे" म्हणजे घड्याळे millisecond पर्यंत जुळतात असे मानणे
L(a) < L(b) चा अर्थ "a मुळे b झाले" असा घेणे
receive वर max(...) + 1 विसरणे — मग उत्तराला त्याच्या प्रश्नापेक्षा लहान क्रमांक मिळू शकतो

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

On a real server — या machine चे घड्याळ त्याच्या time servers पासून किती दूर आहे ते तपासा. chrony सह (अनेक Linux distributions वरचा default NTP client):

chronyc tracking      # "System time : 0.000012 seconds fast of NTP time", plus the estimated error
chronyc sources -v    # which servers it uses and how far each one is
timedatectl           # "System clock synchronized: yes"

AWS वर, Amazon Time Sync Service प्रत्येक VPC च्या आत 169.254.169.123 वर असते; chrony /etc/chrony.conf मधल्या एका ओळीने ती वापरते:

server 169.254.169.123 prefer iburst minpoll 4 maxpoll 4

कालावधी monotonic clock ने मोजा:

import time
start = time.monotonic()
do_work()
elapsed = time.monotonic() - start      # safe even if NTP moves the wall clock meanwhile

ज्या systems ना machines पलीकडे वेळ लागते त्या error bar असलेले घड्याळ वापरतात, शब्दांत:

Google TrueTime (Spanner च्या आत) — प्रत्येक data center मध्ये GPS receivers आणि atomic clocks. TT.now() एक वेळ नव्हे तर एक interval [earliest, latest] परत देते. मग Spanner commit report करण्याआधी तो interval संपेपर्यंत थांबतो ("commit wait"), त्यामुळे commit वेळा खऱ्या क्रमाशी जुळतात. हा interval सहसा काही milliseconds चा असतो.
Hybrid logical clocks (HLC) — CockroachDB आणि YugabyteDB वापरतात. Time stamp म्हणजे wall time अधिक एक छोटा Lamport-सारखा counter. तो खऱ्या वेळेच्या जवळ राहतो, आणि घड्याळे थोडी चुकली तरी कारणाला परिणामाच्या आधी ठेवतो. हे databases जास्तीत जास्त परवानगी असलेला clock offset ही ठरवतात (CockroachDB चा default 500 ms आहे) आणि ज्या node चे घड्याळ खूप दूर गेले आहे त्याला थांबवतात.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: तुमच्या code मध्ये machines पलीकडे "sort by created_at" आणि time.time() पासून बनवलेले timeouts शोधा. कालावधीसाठी monotonic clock वापरा, आणि क्रमासाठी database sequence, version number किंवा Lamport/HLC time stamp वापरा.

⏭️ पुढे

Lamport क्रमांक "कदाचित आधी" सांगतात. "या दोघांना एकमेकांबद्दल माहीत नव्हते" हे ते सांगू शकत नाहीत. Vector clocks सांगू शकतात.

git checkout lesson-03-ordering

🕰️ Lesson 02 — Clocks: every branch's clock is a little wrong

📍 You are here: Lesson 02 of 12 · Previous: lesson-01-partial-failure · Next: lesson-03-ordering

📦 What's in this branch

Lesson 01, plus time. Every branch has its own wall clock, and they drift apart. Why wall time cannot safely order events on different machines, what NTP can and cannot fix, monotonic vs wall clocks, and Lamport clocks — a counter that orders cause before effect with no real clock at all. clocks() in dist/demo.py and LamportClock in dist/sim.py.

🧒 Explain like I'm 5

Every branch has a clock on the wall. 🕰️ They were all set on the same day. But clocks are not perfect. Pune's clock runs a little fast. Nashik's runs a little slow.

At the same moment, Pune's clock says 10:00:00.120 and Nashik's says 09:59:59.980.

Katrina in Pune writes "exam at 10" and stamps it 10:00:00.100 by her clock. A moment later, Aishwarya in Nashik changes it to "exam at 11" and stamps it 10:00:00.050 by her clock.

Now someone sorts the notes by the time stamp. Pune's note has the bigger time. So Pune's note wins. But Aishwarya's change came later! Her change is thrown away, and nobody notices.

So the branches try a different idea. Each branch keeps a counter. 🔢 Every time you write, add 1. Every note carries your counter. When you get a note, set your counter to "the bigger of mine and the note's, plus 1". Now an answer always has a bigger number than the question it answers. No wall clock needed. That counter is a Lamport clock.

🗺️ Diagram

flowchart LR
    subgraph wall["🕰️ wall clocks: Pune is 140 ms ahead"]
      p1["Pune writes 'exam at 10'<br/>stamp 10:00:00.100"] --> n1["Nashik writes 'exam at 11' LATER<br/>stamp 10:00:00.050"]
      n1 --> lww["sort by stamp: Pune's note wins<br/>the later change is lost"]
    end
    subgraph lam["🔢 Lamport clocks"]
      a["Pune writes<br/>L = 1"] -->|"note carries 1"| b["Nashik receives<br/>L = max(0, 1) + 1 = 2"]
      b --> c["Nashik writes<br/>L = 3"]
    end

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

❓ What

Wall clock (time of day) — the clock that says "10:00:00". A computer's crystal oscillator runs a little fast or slow, so the clock drifts (a common figure is up to about 200 parts per million — up to about 17 seconds a day if nobody corrects it).
Clock skew — the difference between two clocks at the same moment. In the demo: 10:00:00.120 − 09:59:59.980 = 140 ms.
NTP (Network Time Protocol) — a machine asks time servers and corrects its clock. It helps a lot, but it has limits: over the internet, errors of tens of milliseconds are common, and it depends on the network delay being the same both ways. A correction can even make the wall clock jump backwards.
Monotonic clock — a clock that only goes forward, for measuring durations on one machine (Python time.monotonic(), Linux CLOCK_MONOTONIC). Its number means nothing on another machine. Use it for timeouts and "how long did this take"; use the wall clock only to show a time to a person.
Last-writer-wins (LWW) by wall time — keep the write with the biggest time stamp. When skew is bigger than the gap between two writes, the earlier write wins and the later one is silently lost.
Happened-before (→) — Leslie Lamport's 1978 idea: a → b if a came before b on the same node, or a is sending a message and b is receiving it, or there is a chain of those. If neither a → b nor b → a, the events are concurrent.
Lamport clock — a counter per node. tick() adds 1 for each event. recv(t) sets the counter to max(mine, t) + 1. The rule it guarantees: if a → b, then L(a) < L(b). The reverse is not true: L(a) < L(b) does not mean a caused b. Add the node's name to break ties, and you get a total order that every node agrees on.

🤔 Why

Because "keep the newest write" is the most common rule in distributed data, and "newest" usually means "biggest time stamp". With skew, the biggest stamp is not the newest write. The data loss is silent: no error, no log line, just a change that vanished. Lamport clocks give an order that always respects cause and effect, at the cost of one small number on every message.

🔧 How (in this repo)

LamportClock in dist/sim.py has t, tick() (+1) and recv(other) (max(t, other) + 1). clocks() in dist/demo.py prints the skew story and one Pune → Nashik exchange. The wall-clock part of the snippet below is plain arithmetic: each branch's time stamp is the true time plus that branch's offset, and resolve(..., "lww") from lesson 08 keeps the biggest stamp.

🧪 Try it

python3 dist/demo.py clocks
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import LamportClock, resolve
p, n, g = LamportClock(), LamportClock(), LamportClock()
a = p.tick(); b = p.tick()            # Pune writes twice
c = g.tick()                          # Nagpur writes once, sees nobody
d = n.recv(b)                         # Nashik reads Pune's second note
e = n.tick()                          # Nashik writes
print(f"Pune a={a} b={b} · Nagpur c={c} · Nashik receives b → {d}, writes e={e}")
print("b caused e, so b < e:", b < e)
print("c and b never met, yet c < b:", c < b, "— a smaller number does NOT mean 'caused'")
# true time in ms after 10:00:00.000; each branch's clock is off by an offset
for pune_off, nashik_off in ((120, -20), (100, 0), (60, 0), (0, 0)):
    pune_stamp   = -20 + pune_off        # Pune writes FIRST, at true time -20 ms
    nashik_stamp =  70 + nashik_off      # Nashik writes 90 ms LATER, at true time +70 ms
    kept = resolve((pune_stamp, "exam at 10"), (nashik_stamp, "exam at 11"), "lww")
    print(f"Pune ahead by {pune_off - nashik_off:>3} ms → stamps pune {pune_stamp:>3}, nashik {nashik_stamp:>3} → last-writer-wins keeps {kept!r}")
EOF

✅ Verify — what you should see

clocks prints:

── wall clocks drift: Pune's clock reads 10:00:00.120, Nashik's reads 09:59:59.980 at the same instant
   Pune writes 'exam at 10' at 10:00:00.100 by its clock; Nashik then writes 'exam at 11' at 10:00:00.050 by its clock
   sorting by wall time says Pune's note was LAST — the later change is silently thrown away
── Lamport: Pune writes (L=1) → Nashik receives (L=2) → Nashik writes (L=3) — cause always has a smaller number

Your snippet prints:

Pune a=1 b=2 · Nagpur c=1 · Nashik receives b → 3, writes e=4
b caused e, so b < e: True
c and b never met, yet c < b: True — a smaller number does NOT mean 'caused'
Pune ahead by 140 ms → stamps pune 100, nashik  50 → last-writer-wins keeps 'exam at 10'
Pune ahead by 100 ms → stamps pune  80, nashik  70 → last-writer-wins keeps 'exam at 10'
Pune ahead by  60 ms → stamps pune  40, nashik  70 → last-writer-wins keeps 'exam at 11'
Pune ahead by   0 ms → stamps pune -20, nashik  70 → last-writer-wins keeps 'exam at 11'

🏁 What you just proved

The two writes were 90 ms apart. With skew of 100 or 140 ms, last-writer-wins kept the older write. With skew of 60 ms or less, it kept the right one. So wall-clock ordering is only safe when skew is smaller than the gap between writes — and you rarely know either number. Lamport numbers always put cause before effect (b=2 < e=4), but c=1 < b=2 shows that a smaller number can belong to an event that had nothing to do with the other. Telling those apart is the next lesson.

⚠️ Common mistakes

measuring a timeout with the wall clock — an NTP correction can make it negative or huge
ordering writes from different machines by their wall-clock time stamps
trusting that "NTP is running" means clocks agree to the millisecond
reading L(a) < L(b) as "a caused b"
forgetting the max(...) + 1 on receive — then an answer can get a smaller number than its question

🏭 In production

On a real server — check how far this machine's clock is from its time servers. With chrony (the default NTP client on many Linux distributions):

chronyc tracking      # "System time : 0.000012 seconds fast of NTP time", plus the estimated error
chronyc sources -v    # which servers it uses and how far each one is
timedatectl           # "System clock synchronized: yes"

On AWS, the Amazon Time Sync Service is at 169.254.169.123 inside every VPC; chrony uses it with one line in /etc/chrony.conf:

server 169.254.169.123 prefer iburst minpoll 4 maxpoll 4

Measure durations with a monotonic clock:

import time
start = time.monotonic()
do_work()
elapsed = time.monotonic() - start      # safe even if NTP moves the wall clock meanwhile

Systems that need time across machines use a clock with an error bar, in words:

Google TrueTime (inside Spanner) — GPS receivers and atomic clocks in every data center. TT.now() returns an interval [earliest, latest], not one time. Spanner then waits until the interval has passed before it reports a commit ("commit wait"), so commit times match real order. The interval is usually a few milliseconds.
Hybrid logical clocks (HLC) — used by CockroachDB and YugabyteDB. A time stamp is the wall time plus a small Lamport-style counter. It stays close to real time, and it still orders cause before effect when clocks are a little off. These databases also set a maximum allowed clock offset (CockroachDB's default is 500 ms) and stop a node whose clock is too far off.

🏭 Why this matters in production: search your code for "sort by created_at" across machines and for timeouts built from time.time(). Use a monotonic clock for durations, and a database sequence, a version number or a Lamport/HLC time stamp for order.

⏭️ Next

Lamport numbers say "maybe before". They cannot say "these two did not know about each other". Vector clocks can.

git checkout lesson-03-ordering

← Previouspartial failure Next →ordering

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