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

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

👑 धडा 09 — Consensus & Raft: एक leader, एक log

📍 तुम्ही इथे आहात: 12 पैकी धडा 09 · मागे: lesson-08-cap-pacelc · पुढे: lesson-10-locks-leases

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

धडे 01–08, आणि भाग 3 सुरू होतो: एकमत. Consensus अनेक nodes ना एका value वर एकमत करायला लावते — इथे, एक leader आणि बदलांचा एक log — काही nodes बंद असल्या किंवा तुटलेल्या असल्या तरीही. Raft हे terms, randomized election timeouts, RequestVote, majorities, AppendEntries आणि commit index वापरून करते. dist/demo.py मधील raft() आणि dist/sim.py मधील Raft.

⚠️ Lab मधील Raft हे एक सोपे केलेले model आहे: बहुमताचा नियम दाखवण्यासाठी ते मते आणि प्रती मोजते. त्यात timers नाहीत, प्रत्येक node चे वेगळे logs नाहीत, आणि मत देताना log ची तपासणी नाही. खऱ्या Raft मध्ये हे तिन्ही असतात; त्यांचे वर्णन खाली दिले आहे.

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

आता पाच शाखा आहेत: पुणे, नाशिक, नागपूर, कोल्हापूर आणि सातारा. त्यांना प्रत्येक बदलाचा क्रम ठरवणारे एक मुख्य office हवे आहे. 👑

नियम: एखादी शाखा मुख्य office तेव्हाच बनते जेव्हा बहुमत — 5 पैकी 3 — तिला मत देतात. प्रत्येक निवडणूक फेरीत प्रत्येक शाखा एकदाच मत देते. प्रत्येक फेरीला एक क्रमांक असतो, तो म्हणजे term.

नाशिक term 1 मध्ये मते मागते. पाचही जण होकार देतात. नाशिक मुख्य office बनते. 🎉

आता नाशिक "exam मंगळवारी" असे लिहिते आणि ते इतरांना पाठवते. 5 पैकी 3 जणांनी (नाशिक आणि आणखी दोन) ते लिहून घेतले की ते committed होते — अंतिम, कधीच मागे न घेतले जाणारे.

मग वादळ रस्ता तोडते: एका बाजूला {नाशिक, पुणे}, दुसऱ्या बाजूला {नागपूर, कोल्हापूर, सातारा}.

नाशिकची बाजू मते मागते: फक्त 2. बहुमत नाही. तिथे मुख्य office नाही.
नागपूरची बाजू मागते: 3 मते. नागपूर term 3 साठी मुख्य office बनते.

5 पैकी 3 चे कोणतेही दोन गट किमान एक शाखा वाटून घेतातच. म्हणून एकाच term मध्ये कधीच दोन मुख्य offices असू शकत नाहीत. लहान बाजूला थांबावे लागते. ⏳

🗺️ आकृती

flowchart LR
    subgraph minority["2 of 5 — cannot elect or commit"]
      na["🏫 Nashik<br/>term 2: got 2/5"]
      pu["🏫 Pune"]
    end
    subgraph majority["3 of 5 — can elect"]
      ng["👑 Nagpur<br/>term 3: elected 3/5"]
      ko["🏫 Kolhapur"]
      sa["🏫 Satara"]
    end
    na -.-x|"✂️ road cut"| ng
    ng -->|"AppendEntries"| ko
    ng -->|"AppendEntries"| sa

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

❓ काय

Consensus — nodes च्या गटाला एका value वर एकमत करायला लावणे (आणि ती कधीच न बदलणे), काही nodes crash झाल्या किंवा messages हरवले तरीही. Log असेल तर ते प्रत्येक slot मधील value वर एकमत करतात: बदलांचा एक क्रम. प्रत्येक node तो log आपल्या स्वतःच्या प्रतीवर लागू करते — हीच replicated state machine.
Raft (Diego Ongaro आणि John Ousterhout, 2014) — समजायला सोपा असावा म्हणून design केलेला consensus algorithm. प्रत्येक node एकतर follower, candidate किंवा leader असते.
Term — फक्त वाढत जाणारा क्रमांक; प्रत्येक term मध्ये जास्तीत जास्त एकच leader असतो. प्रत्येक message मध्ये पाठवणाऱ्याचा term असतो; मोठा term पाहणारी node follower बनते आणि तो term स्वीकारते.
Randomized election timeout — ज्या follower ला आपल्या election timeout इतक्या काळात (एक random value, उदा. Raft paper मध्ये 150–300 ms) leader कडून काहीच ऐकू येत नाही, ती candidate बनते. Random timeouts मुळे दोन candidates एकाच वेळी सुरू होऊन मते विभागण्याची शक्यता कमी होते.
RequestVote — candidate term मध्ये 1 मिळवते, स्वतःला मत देते, आणि इतरांना मागते. प्रत्येक node प्रत्येक term मध्ये जास्तीत जास्त एक मत देते, आणि तेही फक्त ज्या candidate चा log तिच्या स्वतःच्या log इतका तरी अद्ययावत आहे तिलाच (आधी शेवटच्या entry चा term तुलना करा, मग log ची लांबी).
Majority — candidate सर्व nodes च्या अर्ध्याहून जास्त मतांनी जिंकते — ती पोहोचू शकते त्या nodes च्या अर्ध्याहून नव्हे. 5 nodes ना 3 हवे; 3 nodes ना 2; 4 nodes ना 3. 2f + 1 nodes चा cluster f failures मध्ये टिकतो (3 → 1, 5 → 2). सम संख्या कोणतीही जास्त सुरक्षितता देत नाही: 4 nodes सुद्धा फक्त 1 मध्येच टिकतात.
AppendEntries — leader नव्या log entries followers ना पाठवतो (आणि रिकाम्या entries heartbeats म्हणून, धडा 04). Follower तेव्हाच स्वीकारते जेव्हा नव्या entries च्या अगदी आधीच्या entry वर तिचा log leader च्या log शी जुळतो; नाहीतर leader मागे सरकतो आणि रिकामी जागा भरतो.
Commit index — leader ने entry बहुमतावर साठवली की ती committed होते. Committed entries कधीच हरवत नाहीत आणि state machine वर लागू केल्या जातात. (एक बारकावा: leader अशा प्रकारे replicas फक्त त्याच्या स्वतःच्या term मधील entries साठीच मोजतो.)
Leader completeness — नंतरच्या term मधील कोणत्याही leader कडे प्रत्येक committed entry आधीच असते. का: committed entry बहुमतावर असते; जिंकणाऱ्याला बहुमताची मते लागतात; ही दोन बहुमते एक node वाटून घेतात; ती node फक्त अशाच candidate ला मत देते जिचा log तिच्या स्वतःच्या log इतका तरी अद्ययावत आहे.
FLP (Fischer, Lynch आणि Paterson, 1985) — पूर्णपणे asynchronous network मध्ये एकही crash असेल तर कोणताही deterministic algorithm consensus पूर्ण होईल याची हमी देऊ शकत नाही. Raft नेहमी सुरक्षित राहतो आणि timing पुरेसे चांगले असेल तेव्हा (timeouts त्यांचे काम करतात) पूर्ण होतो.

🤔 का

कारण "leader कोण?" आणि "बदलांचा क्रम काय?" हेच प्रश्न failover (धडा 05), locks (धडा 10) आणि प्रत्येक CP system (धडा 08) यांच्यामागे आहेत. फक्त heartbeat ने त्यांची उत्तरे दिली तर split brain होतो. बहुमत आणि terms ने उत्तरे दिली, तर अल्पसंख्य बाजू काहीही करू शकत नाही — त्याची किंमत म्हणजे ती थांबते.

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

dist/sim.py मधील Raft(nodes) term, leader आणि log ठेवते. elect(candidate, alive) term मध्ये 1 मिळवते आणि alive nodes ना मते म्हणून मोजते; ती len(votes) > len(nodes) // 2 असेल तर जिंकते — सर्व nodes चे बहुमत. append(entry, reached) entry log मध्ये जोडते आणि reached followers आणि leader मिळून बहुमत होत असेल तर 'committed' परत करते. सोपे केलेले भाग: प्रत्येक alive node होकार देते (log ची तपासणी नाही, प्रत्येक term मध्ये एक मत याची नोंद नाही), आणि प्रत्येक node चा वेगळा log नसून एकच सामायिक log आहे.

🧪 करून पाहा

python3 dist/demo.py raft
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import Raft
for nodes, alive in ((3, 2), (4, 2), (4, 3), (5, 2), (5, 3), (6, 3), (7, 4)):
    r = Raft([f"b{i}" for i in range(nodes)])
    print(f"{nodes} nodes, {alive} reachable → " + r.elect("b0", alive={f"b{i}" for i in range(alive)}))
r = Raft(["pune", "nashik", "nagpur", "kolhapur"])
print("4 nodes split 2 | 2:", r.elect("pune", {"pune", "nashik"}), "·", r.elect("nagpur", {"nagpur", "kolhapur"}))
EOF

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

raft हे print करते:

── 5 branches run Raft; a leader needs a majority of ALL 5 (3 votes)
   term 1: nashik elected with 5/5 votes
   append 'exam on Tuesday', copied to pune + nagpur → committed — 3 of 5 with the leader
   append 'trip on Friday', copied to pune only   → not committed (no majority) — only 2 of 5
── the road splits: {nashik, pune} | {nagpur, kolhapur, satara}
   term 2: nashik got 2/5 — no majority, no leader
   term 3: nagpur elected with 3/5 votes
   the minority side cannot elect or commit — so there are never two leaders in the same term

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

3 nodes, 2 reachable → term 1: b0 elected with 2/3 votes
4 nodes, 2 reachable → term 1: b0 got 2/4 — no majority, no leader
4 nodes, 3 reachable → term 1: b0 elected with 3/4 votes
5 nodes, 2 reachable → term 1: b0 got 2/5 — no majority, no leader
5 nodes, 3 reachable → term 1: b0 elected with 3/5 votes
6 nodes, 3 reachable → term 1: b0 got 3/6 — no majority, no leader
7 nodes, 4 reachable → term 1: b0 elected with 4/7 votes
4 nodes split 2 | 2: term 1: pune got 2/4 — no majority, no leader · term 2: nagpur got 2/4 — no majority, no leader

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

अर्धे म्हणजे बहुमत नव्हे: 4 पैकी 2 आणि 6 पैकी 3 कोणालाच निवडत नाहीत. म्हणून 2 | 2 असा फुटलेल्या 4-node cluster मध्ये कोणत्याही बाजूला leader नसतो — 3 nodes पेक्षाही वाईट, जे 2 सह तरीही निवड करतात. म्हणूनच clusters विषम संख्येचे असतात. आणि "trip on Friday", जे फक्त 5 पैकी 2 कडे होते, ते committed झाले नाही: नव्या leader कडे ते नसू शकते, म्हणून कोणीही ते अंतिम मानू नये.

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

"सुरक्षिततेसाठी" सम संख्येचा cluster — 4 nodes फक्त 1 failure सहन करतात, 3 इतकेच
एकच consensus cluster हळू links वर पसरवणे, त्यामुळे प्रत्येक write सर्वात हळू बहुमतासाठी थांबतो
"leader ने लिहिले" म्हणजे "committed" असे मानणे
कोणत्याही member कडून वाचून सर्वात नवी value अपेक्षित धरणे — linearizable read मागा
production साठी स्वतःचा consensus algorithm लिहिणे

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

etcd (Kubernetes मागचे store) Raft चालवते. On a real account, प्रत्येक member, leader आणि सध्याचा term पाहा:

etcdctl --endpoints=http://pune:2379,http://nashik:2379,http://nagpur:2379 endpoint status -w table
# columns include: ENDPOINT · IS LEADER · RAFT TERM · RAFT INDEX · RAFT APPLIED INDEX
etcdctl --endpoints=http://pune:2379 member list -w table
etcdctl --endpoints=http://pune:2379 put exam-day Tuesday      # OK only once a majority has it
etcdctl --endpoints=http://pune:2379 move-leader 8211f1d0f64f3269   # hand leadership to another member (by ID)

ZooKeeper असाच एक protocol वापरतो, ZAB (ZooKeeper Atomic Broadcast): निवडलेला leader, epochs (terms सारखे), आणि quorum (बहुमत) ने मान्य केल्यावर write committed होतो. zkCli.sh आणि echo srvr | nc nashik 2181 प्रत्येक server चा mode दाखवतात (leader किंवा follower).

Kafka ने ZooKeeper ऐवजी KRaft आणले — controller nodes चा Raft-आधारित quorum, जो cluster च्या metadata वर एकमत करतो. Consul, CockroachDB आणि TiKV सुद्धा Raft वापरतात.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: consensus clusters 3 किंवा 5 members सह वेगवेगळ्या failure zones मध्ये चालवा, leader बदलांवर आणि Raft index मध्ये मागे पडलेल्या members वर alert लावा, आणि त्यांत फक्त छोटा coordination data ठेवा (leaders, config, locks) — मोठ्या प्रमाणातील application data नव्हे.

⏭️ पुढे

Consensus मुळे एक node lock धरू शकते. पण lock धरणारी node थांबू शकते आणि तिला ते कळतही नाही. पुढे: leases आणि fencing tokens.

git checkout lesson-10-locks-leases

👑 Lesson 09 — Consensus & Raft: one leader, one log

📍 You are here: Lesson 09 of 12 · Previous: lesson-08-cap-pacelc · Next: lesson-10-locks-leases

📦 What's in this branch

Lessons 01–08, plus Part 3 begins: agreement. Consensus gets several nodes to agree on one value — here, one leader and one log of changes — even when some are down or cut off. Raft does it with terms, randomized election timeouts, RequestVote, majorities, AppendEntries and a commit index. raft() in dist/demo.py and Raft in dist/sim.py.

⚠️ The lab's Raft is a simplified model: it counts votes and copies to show the majority rule. It has no timers, no per-node logs, and no log check on votes. Real Raft has all three; they are described below.

🧒 Explain like I'm 5

Now there are five branches: Pune, Nashik, Nagpur, Kolhapur and Satara. They want one head office that decides the order of every change. 👑

The rule: a branch becomes head office only if a majority — 3 of the 5 — vote for it. Each branch votes once per election round. Each round has a number, the term.

Nashik asks for votes in term 1. All five agree. Nashik is head office. 🎉

Now Nashik writes "exam on Tuesday" and sends it to the others. When 3 of 5 (Nashik plus two more) have written it down, it is committed — final, never undone.

Then the storm cuts the road: {Nashik, Pune} on one side, {Nagpur, Kolhapur, Satara} on the other.

Nashik's side asks for votes: only 2. Not a majority. No head office there.
Nagpur's side asks: 3 votes. Nagpur becomes head office for term 3.

Two groups of 3 out of 5 must share at least one branch. So there can never be two head offices in the same term. The small side must wait. ⏳

🗺️ Diagram

flowchart LR
    subgraph minority["2 of 5 — cannot elect or commit"]
      na["🏫 Nashik<br/>term 2: got 2/5"]
      pu["🏫 Pune"]
    end
    subgraph majority["3 of 5 — can elect"]
      ng["👑 Nagpur<br/>term 3: elected 3/5"]
      ko["🏫 Kolhapur"]
      sa["🏫 Satara"]
    end
    na -.-x|"✂️ road cut"| ng
    ng -->|"AppendEntries"| ko
    ng -->|"AppendEntries"| sa

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

❓ What

Consensus — getting a group of nodes to agree on a value (and never change it), even if some nodes crash or messages are lost. With a log, they agree on the value in each slot: one order of changes. Each node applies the log to its own copy — a replicated state machine.
Raft (Diego Ongaro and John Ousterhout, 2014) — a consensus algorithm designed to be easy to understand. Each node is a follower, a candidate or the leader.
Term — a number that only goes up; each term has at most one leader. Every message carries the sender's term; a node that sees a bigger term steps down to follower and adopts it.
Randomized election timeout — a follower that hears nothing from a leader for its election timeout (a random value, for example 150–300 ms in the Raft paper) becomes a candidate. Random timeouts make it unlikely that two candidates start at once and split the votes.
RequestVote — the candidate adds 1 to the term, votes for itself, and asks the others. Each node grants at most one vote per term, and only to a candidate whose log is at least as up to date as its own (compare the last entry's term, then the log length).
Majority — a candidate wins with votes from more than half of all nodes — not half of the nodes it can reach. 5 nodes need 3; 3 nodes need 2; 4 nodes need 3. A cluster of 2f + 1 nodes survives f failures (3 → 1, 5 → 2). An even size adds no safety: 4 nodes also survive only 1.
AppendEntries — the leader sends new log entries to followers (and empty ones as heartbeats, lesson 04). A follower accepts only if its log matches the leader's at the entry just before the new ones; otherwise the leader steps back and fills the gap.
Commit index — an entry is committed once the leader has stored it on a majority. Committed entries are never lost and are applied to the state machine. (One detail: a leader only counts replicas this way for entries from its own term.)
Leader completeness — any leader of a later term already has every committed entry. Why: a committed entry is on a majority; a winner needs votes from a majority; the two majorities share a node; that node only votes for a candidate whose log is at least as up to date as its own.
FLP (Fischer, Lynch and Paterson, 1985) — no deterministic algorithm can guarantee consensus will finish in a fully asynchronous network with even one crash. Raft stays safe always and finishes when timing is good enough (the timeouts do their job).

🤔 Why

Because "who is the leader?" and "what is the order of changes?" are the questions behind failover (lesson 05), locks (lesson 10) and every CP system (lesson 08). Answer them with only a heartbeat, and you get split brain. Answer them with majorities and terms, and the minority side cannot act — the price is that it waits.

🔧 How (in this repo)

Raft(nodes) in dist/sim.py keeps term, leader and log. elect(candidate, alive) adds 1 to the term and counts the alive nodes as votes; it wins with len(votes) > len(nodes) // 2 — a majority of all nodes. append(entry, reached) adds the entry to the log and returns 'committed' when the followers reached plus the leader make a majority. Simplifications: every alive node votes yes (no log check, no one-vote-per-term record), and there is one shared log, not one per node.

🧪 Try it

python3 dist/demo.py raft
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import Raft
for nodes, alive in ((3, 2), (4, 2), (4, 3), (5, 2), (5, 3), (6, 3), (7, 4)):
    r = Raft([f"b{i}" for i in range(nodes)])
    print(f"{nodes} nodes, {alive} reachable → " + r.elect("b0", alive={f"b{i}" for i in range(alive)}))
r = Raft(["pune", "nashik", "nagpur", "kolhapur"])
print("4 nodes split 2 | 2:", r.elect("pune", {"pune", "nashik"}), "·", r.elect("nagpur", {"nagpur", "kolhapur"}))
EOF

✅ Verify — what you should see

raft prints:

── 5 branches run Raft; a leader needs a majority of ALL 5 (3 votes)
   term 1: nashik elected with 5/5 votes
   append 'exam on Tuesday', copied to pune + nagpur → committed — 3 of 5 with the leader
   append 'trip on Friday', copied to pune only   → not committed (no majority) — only 2 of 5
── the road splits: {nashik, pune} | {nagpur, kolhapur, satara}
   term 2: nashik got 2/5 — no majority, no leader
   term 3: nagpur elected with 3/5 votes
   the minority side cannot elect or commit — so there are never two leaders in the same term

Your snippet prints:

3 nodes, 2 reachable → term 1: b0 elected with 2/3 votes
4 nodes, 2 reachable → term 1: b0 got 2/4 — no majority, no leader
4 nodes, 3 reachable → term 1: b0 elected with 3/4 votes
5 nodes, 2 reachable → term 1: b0 got 2/5 — no majority, no leader
5 nodes, 3 reachable → term 1: b0 elected with 3/5 votes
6 nodes, 3 reachable → term 1: b0 got 3/6 — no majority, no leader
7 nodes, 4 reachable → term 1: b0 elected with 4/7 votes
4 nodes split 2 | 2: term 1: pune got 2/4 — no majority, no leader · term 2: nagpur got 2/4 — no majority, no leader

🏁 What you just proved

Half is not a majority: 2 of 4 and 3 of 6 elect nobody. So a 4-node cluster split 2 | 2 has no leader on either side — worse than 3 nodes, which still elect with 2. That is why clusters use an odd size. And "trip on Friday", held by only 2 of 5, was not committed: a new leader may not have it, so no one may treat it as final.

⚠️ Common mistakes

an even cluster size "for safety" — 4 nodes tolerate 1 failure, the same as 3
stretching one consensus cluster across slow links, so every write waits on the slowest majority
treating "the leader wrote it" as "committed"
reading from any member and expecting the newest value — ask for a linearizable read
writing your own consensus algorithm for production

🏭 In production

etcd (the store behind Kubernetes) runs Raft. On a real account, see each member, the leader and the current term:

etcdctl --endpoints=http://pune:2379,http://nashik:2379,http://nagpur:2379 endpoint status -w table
# columns include: ENDPOINT · IS LEADER · RAFT TERM · RAFT INDEX · RAFT APPLIED INDEX
etcdctl --endpoints=http://pune:2379 member list -w table
etcdctl --endpoints=http://pune:2379 put exam-day Tuesday      # OK only once a majority has it
etcdctl --endpoints=http://pune:2379 move-leader 8211f1d0f64f3269   # hand leadership to another member (by ID)

ZooKeeper uses a similar protocol, ZAB (ZooKeeper Atomic Broadcast): an elected leader, epochs (like terms), and a write is committed once a quorum (majority) acknowledges it. zkCli.sh and echo srvr | nc nashik 2181 show each server's mode (leader or follower).

Kafka replaced ZooKeeper with KRaft — a Raft-based quorum of controller nodes that agree on the cluster's metadata. Consul, CockroachDB and TiKV use Raft too.

🏭 Why this matters in production: run consensus clusters with 3 or 5 members in separate failure zones, alert on leader changes and on members behind in the Raft index, and keep only small coordination data in them (leaders, config, locks) — not bulk application data.

⏭️ Next

With consensus, one node can hold a lock. But a lock holder can pause and not know it. Next: leases and fencing tokens.

git checkout lesson-10-locks-leases

← Previouscap pacelc Next →locks leases

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