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

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

💓 धडा 04 — Failure detection: बंद पडली की फक्त हळू?

📍 तुम्ही इथे आहात: 12 पैकी धडा 04 · मागे: lesson-03-ordering · पुढे: lesson-05-replication

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

धडे 01–03, अधिक failure detection: प्रत्येक शाखा ठरलेल्या वेळापत्रकानुसार एक छोटी "मी चालू आहे" चिठ्ठी (एक heartbeat) पाठवते, आणि वेळेत heartbeat आला नाही तर बाकीच्या तिच्यावर संशय घेतात. एकमेव knob — timeout — लवकर कळणे आणि खोटे alarms यांच्यात तडजोड करतो. dist/demo.py मधले detection() आणि dist/sim.py मधले HeartbeatDetector.

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

कोल्हापूर पुण्याला साधारण दर 100 ms ला एक postcard 💌 पाठवण्याचे वचन देते: "अजून उघडे आहे!"

पुण्यातली दीपिका postcards येताना पाहते. सहसा ते दर 95 ते 120 ms ला येतात. पण कधी कधी एखादे उशिरा येते — एकदा 340 ms, कारण कोल्हापूरचा clerk office साफ करायला थांबला होता (एक मोठा pause). नंतर एकदा 180 ms उशीर, कारण रस्त्यावर गर्दी होती.

दीपिकाला एक नियम निवडावा लागतो: "X ms पर्यंत postcard आले नाही तर मी कोल्हापूर बंद आहे असे म्हणेन".

X = 150 ms: खरोखर बंद झाले तर तिला ते लवकर कळते. पण कोल्हापूर उघडे असताना ती दोनदा "बंद!" असे ओरडतेही. 🚨🚨
X = 800 ms: ती कधीच चुकून ओरडत नाही. पण कोल्हापूर खरोखर बंद झाले की ते लक्षात यायला तिला 800 ms वाट पाहावी लागते. 🐢

जलद आणि कधीच न चुकणारा असा कोणताच X नाही. दीपिका फक्त कोणती चूक तिला चालेल ते निवडू शकते.

🗺️ आकृती

flowchart LR
    k["🏫 Kolhapur<br/>heartbeat every ~100 ms"] -->|"gaps 100 110 95 340 105 120 180 95<br/>then it really dies"| d["💓 detector in Pune"]
    d --> t1["timeout 150 ms<br/>2 false alarms<br/>death noticed after 150 ms"]
    d --> t2["timeout 400 ms<br/>0 false alarms<br/>noticed after 400 ms"]
    d --> t3["timeout 800 ms<br/>0 false alarms<br/>noticed after 800 ms"]

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

❓ काय

Heartbeat — "मी चालू आहे" सांगण्यासाठी node ठरलेल्या वेळापत्रकानुसार पाठवतो तो छोटा message. अनेकदा नेहमीचा traffic (किंवा leader चे messages, धडा 09) हाच heartbeat म्हणूनही काम करतो.
Timeout-based failure detector — timeout पेक्षा जास्त वेळ heartbeat आला नाही तर node वर संशय घ्या.
खोटा alarm (false positive) — चालू असलेल्या node वर संशय घेतला जातो. कारणे: मोठा garbage-collection pause, व्यस्त CPU, हळू किंवा चिठ्ठ्या हरवणारे network. Node ठीक आहे; त्याचा heartbeat उशिरा आला आहे.
Detection time — खरा crash झाल्यानंतर detector ला किती वेळाने कळते. Timeout असेल तर तो साधारण timeout इतका असतो (अधिक नेहमीचे heartbeat अंतर).
Failure detectors स्वभावतःच अविश्वसनीय असतात — ज्या network मध्ये delay ला कोणतीही वरची मर्यादा नाही (धडा 01), तिथे crash झालेला node आणि खूप हळू node सारखेच दिसतात. म्हणून detector फक्त संशय घेऊ शकतो, कधीच खात्रीने जाणू शकत नाही. प्रत्येक detector एक तडजोड आहे: लवकर कळणे म्हणजे जास्त खोटे alarms.
Phi accrual failure detector (Hayashibara आणि इतर, 2004) — हो/नाही ऐवजी, तो heartbeat अंतरांचा नेहमीचा पसारा शिकतो आणि एक संशय पातळी φ (phi) देतो: साधारण, φ = 8 म्हणजे "इतके मोठे अंतर योगायोगाने साधारण 10⁸ मध्ये 1 वेळा येईल". Cassandra तो वापरते (phi_convict_threshold, default 8); Akka ही वापरते. तो हळू network शी आपोआप जुळवून घेतो, पण तरीही ती तडजोडच आहे.
कृती सुरक्षित करा — संशय चुकीचा असू शकतो, म्हणून संशयावरून घेतलेली कृती (fail over, restart, कुलूप ताब्यात घेणे) node प्रत्यक्षात चालू असतानाही सुरक्षित असायला हवी. धडे 05, 09 आणि 10 नेमके याबद्दलच आहेत.

🤔 का

कारण प्रत्येक आपोआप होणारी recovery "तो node बंद पडला" इथून सुरू होते. Leader खूप लवकर बदलला, तर GC pause मुळे failover होतो — किंवा दोन leaders (धडा 05). खूप उशिरा बदलला, तर users खऱ्या outage मध्ये वाट पाहत राहतात. फुकटचे उत्तर नाही, म्हणून तुम्ही तुमच्या network साठी timeout जुळवता आणि संशयावरून घेतलेली प्रत्येक कृती चुकून घडली तरी सुरक्षित ठेवता.

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

dist/sim.py मधल्या HeartbeatDetector(timeout_ms) मध्ये दोन methods आहेत. verdicts(gaps_ms) प्रत्येक अंतराला 'alive' किंवा 'suspected' (gap > timeout) असे चिन्हांकित करते. run(gaps_ms) (चालू असताना आलेले खोटे alarms, खरा मृत्यू लक्षात यायला लागलेले ms) परत देते — ते timeout पेक्षा मोठी अंतरे मोजते, आणि लक्षात यायची वेळ म्हणजे फक्त timeout च. dist/demo.py मधले detection() 150, 400 आणि 800 ms वापरून पाहते.

🧪 करून पाहा

python3 dist/demo.py detection
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import HeartbeatDetector
gaps = [100, 110, 95, 340, 105, 120, 180, 95]
for t in (100, 200, 350):
    fa, notice = HeartbeatDetector(t).run(gaps)
    print(f"timeout {t} ms → false alarms {fa} · death noticed after {notice} ms")
print("verdicts at 150 ms:", HeartbeatDetector(150).verdicts(gaps))
busy = [100, 450, 900, 120]            # a very bad day: a long GC pause and a slow road
print("bad day at 400 ms:", HeartbeatDetector(400).verdicts(busy))
EOF

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

detection हे print करते:

   timeout 150 ms → false alarms while alive: 2 · the real death is noticed after 150 ms
   timeout 400 ms → false alarms while alive: 0 · the real death is noticed after 400 ms
   timeout 800 ms → false alarms while alive: 0 · the real death is noticed after 800 ms

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

timeout 100 ms → false alarms 5 · death noticed after 100 ms
timeout 200 ms → false alarms 1 · death noticed after 200 ms
timeout 350 ms → false alarms 0 · death noticed after 350 ms
verdicts at 150 ms: ['alive', 'alive', 'alive', 'suspected', 'alive', 'alive', 'suspected', 'alive']
bad day at 400 ms: ['alive', 'suspected', 'suspected', 'alive']

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

या अंतरांसह, snippet मधला 350 ms हा एकमेव timeout होता ज्यात एकही खोटा alarm नव्हता — तो सर्वात मोठ्या नेहमीच्या अंतराच्या (340 ms) अगदी वर आहे. पण वाईट दिवशी (450 ms आणि 900 ms चे अंतर), 400 ms सुद्धा चालू असलेल्या शाखेवर दोनदा संशय घेतो. "बरोबर" timeout तुमच्या नियंत्रणात नसलेल्या network वर अवलंबून असतो. म्हणूनच detector फक्त संशय घेऊ शकतो.

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

नेहमीच्या garbage-collection pause पेक्षा लहान timeout
संशयावरून असुरक्षित कृती करणे — उदाहरणार्थ, दोन nodes दोघेही leader म्हणून लिहितात
database सुद्धा तपासणारा liveness check: database हळू आहे, म्हणून service ची प्रत्येक प्रत एकाच वेळी restart होते
एक heartbeat चुकला = बंद पडला; बहुतेक systems अनेक चुकण्याची वाट पाहतात
खोट्या alarms वर alert नाही, त्यामुळे सतत चालू-बंद होणारा (flapping) node लक्षात येत नाही

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

Kubernetes probes — प्रत्येक node वरचा kubelet प्रत्येक container तपासतो. अयशस्वी liveness probe container restart करतो. अयशस्वी readiness probe फक्त pod ला Service च्या endpoints मधून काढतो (traffic नाही), restart न करता:

containers:
  - name: timetable
    image: school/timetable:1.4
    livenessProbe:                    # "is the process stuck?" — keep it cheap and local
      httpGet: { path: /livez, port: 8080 }
      periodSeconds: 10
      timeoutSeconds: 2
      failureThreshold: 3             # 3 misses in a row → restart
    readinessProbe:                   # "can it serve now?" — may check its own dependencies
      httpGet: { path: /readyz, port: 8080 }
      periodSeconds: 5
      failureThreshold: 2

Kubernetes node heartbeats — प्रत्येक kubelet kube-node-lease namespace मधला एक Lease object renew करतो (default नुसार दर 10 सेकंदांनी). Node monitor grace period इतका वेळ renewals थांबले तर node NotReady म्हणून चिन्हांकित होतो; त्यावरचे pods त्यांच्या toleration नंतर (default नुसार 300 सेकंद) evict होतात. On a real account:

kubectl get lease -n kube-node-lease
kubectl get nodes

etcd heartbeats — Raft leader (धडा 09) दर --heartbeat-interval ला (default 100 ms) heartbeat पाठवतो; --election-timeout (default 1000 ms) इतका वेळ काहीच न ऐकलेला follower election सुरू करतो. etcd docs सुचवतात की heartbeat interval members मधल्या round-trip time इतका असावा, आणि election timeout त्याच्या किमान 10 पट:

etcd --heartbeat-interval=100 --election-timeout=1000 ...

Cassandra — phi accrual detector, cassandra.yaml मध्ये:

phi_convict_threshold: 8      # raise it (for example to 12) on slow or shared networks

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: तुम्ही चालवता त्या प्रत्येक detector साठी (probes, node leases, database failover, consensus), त्याचा timeout, तुम्ही पाहिलेला सर्वात मोठा नेहमीचा pause, आणि खोटा alarm कोणती कृती सुरू करतो ते लिहून ठेवा. मग ती कृती सुरक्षित करा.

⏭️ पुढे

भाग 1 पूर्ण: हरवलेल्या चिठ्ठ्या, चुकीची घड्याळे, अज्ञात क्रम, अनिश्चित मृत्यू. भाग 2 अनेक शाखांमध्ये नोंदवहीच्या प्रती ठेवतो — एक leader आणि त्याचे followers यांपासून सुरुवात करून.

git checkout lesson-05-replication

💓 Lesson 04 — Failure detection: dead or just slow?

📍 You are here: Lesson 04 of 12 · Previous: lesson-03-ordering · Next: lesson-05-replication

📦 What's in this branch

Lessons 01–03, plus failure detection: each branch sends a small "I am alive" note (a heartbeat) on a schedule, and the others suspect it when no heartbeat arrives in time. The one knob — the timeout — trades fast notice against false alarms. detection() in dist/demo.py and HeartbeatDetector in dist/sim.py.

🧒 Explain like I'm 5

Kolhapur promises to send Pune a postcard 💌 about every 100 ms: "still open!"

Dipika in Pune watches the postcards arrive. Usually they come every 95 to 120 ms. But sometimes one is late — 340 ms once, because Kolhapur's clerk stopped to clean the office (a long pause). Later one is 180 ms late, because the road was busy.

Dipika must pick a rule: "if no postcard for X ms, I say Kolhapur is closed".

X = 150 ms: she notices a real closing quickly. But she also shouts "closed!" twice while Kolhapur was open. 🚨🚨
X = 800 ms: she never shouts by mistake. But when Kolhapur really closes, she waits 800 ms to notice. 🐢

There is no X that is both fast and never wrong. Dipika can only choose which mistake she prefers.

🗺️ Diagram

flowchart LR
    k["🏫 Kolhapur<br/>heartbeat every ~100 ms"] -->|"gaps 100 110 95 340 105 120 180 95<br/>then it really dies"| d["💓 detector in Pune"]
    d --> t1["timeout 150 ms<br/>2 false alarms<br/>death noticed after 150 ms"]
    d --> t2["timeout 400 ms<br/>0 false alarms<br/>noticed after 400 ms"]
    d --> t3["timeout 800 ms<br/>0 false alarms<br/>noticed after 800 ms"]

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

❓ What

Heartbeat — a small message a node sends on a schedule to say "I am alive". Often the normal traffic (or the leader's messages, lesson 09) doubles as a heartbeat.
Timeout-based failure detector — suspect a node when no heartbeat arrives for longer than the timeout.
False alarm (false positive) — a live node is suspected. Causes: a long garbage-collection pause, a busy CPU, a slow or lossy network. The node is fine; its heartbeat is late.
Detection time — how long after a real crash the detector notices. With a timeout, it is about the timeout (plus the normal heartbeat gap).
Failure detectors are unreliable by nature — in a network with no upper bound on delay (lesson 01), a crashed node and a very slow node look the same. So a detector can only suspect, never know. Every detector is a trade: faster notice means more false alarms.
Phi accrual failure detector (Hayashibara and others, 2004) — instead of yes/no, it learns the normal spread of heartbeat gaps and outputs a suspicion level φ (phi): roughly, φ = 8 means "a gap this long would happen by chance about 1 time in 10⁸". Cassandra uses it (phi_convict_threshold, default 8); Akka uses it too. It adapts to a slow network on its own, but it is still a trade.
Make the action safe — because suspicion can be wrong, the action taken on suspicion (fail over, restart, take over a lock) must be safe even when the node is actually alive. Lessons 05, 09 and 10 are about exactly this.

🤔 Why

Because every automatic recovery starts with "that node is dead". Replace a leader too fast, and a GC pause causes a failover — or two leaders (lesson 05). Replace it too slowly, and users wait through a real outage. There is no free answer, so you tune the timeout for your network and make every action taken on suspicion safe to do by mistake.

🔧 How (in this repo)

HeartbeatDetector(timeout_ms) in dist/sim.py has two methods. verdicts(gaps_ms) marks each gap 'alive' or 'suspected' (gap > timeout). run(gaps_ms) returns (false alarms while alive, ms to notice the real death) — it counts gaps above the timeout, and the notice time is simply the timeout itself. detection() in dist/demo.py tries 150, 400 and 800 ms.

🧪 Try it

python3 dist/demo.py detection
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import HeartbeatDetector
gaps = [100, 110, 95, 340, 105, 120, 180, 95]
for t in (100, 200, 350):
    fa, notice = HeartbeatDetector(t).run(gaps)
    print(f"timeout {t} ms → false alarms {fa} · death noticed after {notice} ms")
print("verdicts at 150 ms:", HeartbeatDetector(150).verdicts(gaps))
busy = [100, 450, 900, 120]            # a very bad day: a long GC pause and a slow road
print("bad day at 400 ms:", HeartbeatDetector(400).verdicts(busy))
EOF

✅ Verify — what you should see

detection prints:

   timeout 150 ms → false alarms while alive: 2 · the real death is noticed after 150 ms
   timeout 400 ms → false alarms while alive: 0 · the real death is noticed after 400 ms
   timeout 800 ms → false alarms while alive: 0 · the real death is noticed after 800 ms

Your snippet prints:

timeout 100 ms → false alarms 5 · death noticed after 100 ms
timeout 200 ms → false alarms 1 · death noticed after 200 ms
timeout 350 ms → false alarms 0 · death noticed after 350 ms
verdicts at 150 ms: ['alive', 'alive', 'alive', 'suspected', 'alive', 'alive', 'suspected', 'alive']
bad day at 400 ms: ['alive', 'suspected', 'suspected', 'alive']

🏁 What you just proved

With these gaps, 350 ms was the only timeout in the snippet with no false alarm — it is just above the biggest normal gap (340 ms). But on a worse day (a 450 ms and a 900 ms gap), even 400 ms suspects a live branch twice. The "right" timeout depends on a network you do not control. That is why a detector can only suspect.

⚠️ Common mistakes

a timeout shorter than a normal garbage-collection pause
taking an unsafe action on suspicion — for example, two nodes both writing as leader
a liveness check that also checks the database: the database is slow, so every copy of the service is restarted at once
one missed heartbeat = dead; most systems wait for several
no alert on false alarms, so a flapping node goes unnoticed

🏭 In production

Kubernetes probes — the kubelet on each node checks each container. A failed liveness probe restarts the container. A failed readiness probe only removes the pod from the Service's endpoints (no traffic), without a restart:

containers:
  - name: timetable
    image: school/timetable:1.4
    livenessProbe:                    # "is the process stuck?" — keep it cheap and local
      httpGet: { path: /livez, port: 8080 }
      periodSeconds: 10
      timeoutSeconds: 2
      failureThreshold: 3             # 3 misses in a row → restart
    readinessProbe:                   # "can it serve now?" — may check its own dependencies
      httpGet: { path: /readyz, port: 8080 }
      periodSeconds: 5
      failureThreshold: 2

Kubernetes node heartbeats — each kubelet renews a Lease object in the kube-node-lease namespace (every 10 seconds by default). If the renewals stop for the node monitor grace period, the node is marked NotReady; pods on it are evicted after their toleration (300 seconds by default). On a real account:

kubectl get lease -n kube-node-lease
kubectl get nodes

etcd heartbeats — the Raft leader (lesson 09) sends a heartbeat every --heartbeat-interval (default 100 ms); a follower that hears nothing for --election-timeout (default 1000 ms) starts an election. The etcd docs suggest the heartbeat interval be about the round-trip time between members, and the election timeout at least 10 times that:

etcd --heartbeat-interval=100 --election-timeout=1000 ...

Cassandra — the phi accrual detector, in cassandra.yaml:

phi_convict_threshold: 8      # raise it (for example to 12) on slow or shared networks

🏭 Why this matters in production: for each detector you run (probes, node leases, database failover, consensus), write down its timeout, the biggest normal pause you have seen, and what action a false alarm triggers. Then make that action safe.

⏭️ Next

Part 1 is done: lost notes, wrong clocks, unknown order, uncertain death. Part 2 keeps copies of the register in several branches — starting with a leader and its followers.

git checkout lesson-05-replication

← Previousordering Next →replication

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