Consensus — Raft-এর leader election আর log replication, Paxos-এর ধারণা

১ · Consensus সমস্যা — কয়েকটি যন্ত্র, একটিই সিদ্ধান্ত

পর্ব ২২-এ আমরা leader-follower replication দেখেছি। সেখানে একটি প্রশ্ন খোলা ছিল: leader মরলে নতুন leader কে ঠিক করবে? বাইরের একটি monitor ঠিক করলে সে নিজেই single point of failure. আবার network ভাগ হলে দুই দিকে দুজন নিজেকে leader ভাবতে পারে — split-brain (পর্ব ২২)। এই পর্বের বিষয় সেই প্রশ্নের নীতিগত উত্তর: সার্ভারগুলো নিজেরাই, নিয়ম মেনে, একটি সিদ্ধান্তে একমত হবে।

তিনটি শর্ত

ধরা যাক কয়েকটি process, প্রত্যেকে একটি মান প্রস্তাব করতে পারে। Consensus প্রোটোকলের কাছে তিনটি জিনিস চাওয়া হয়:

1. Agreement: সচল কোনো দুটি process ভিন্ন মানে সিদ্ধান্ত নেবে না।
2. Validity: সিদ্ধান্ত হওয়া মানটি কেউ না কেউ প্রস্তাব করেছিল — প্রোটোকল নিজে মান বানায় না।
3. Termination: যে process crash করেনি, সে শেষ পর্যন্ত একটি সিদ্ধান্তে পৌঁছাবে।

প্রথম দুটি safety — “খারাপ কিছু কখনো ঘটবে না”। তৃতীয়টি liveness — “ভালো কিছু শেষে ঘটবেই”। পর্ব ৩৮-এ FLP ফল দেখেছেন: বার্তার দেরির কোনো সীমা না থাকলে, একটি process-ও crash করতে পারলে, কোনো deterministic প্রোটোকল তিনটিই সব সময় দিতে পারে না। তাই Raft আর Paxos-এর মতো প্রোটোকলের কৌশল একই: safety কখনো ছাড়ে না, আর liveness দেয় যখন network মোটামুটি ভালো আচরণ করে — এই ধারণাকে বলা হয় partial synchrony.

ব্যর্থতার মডেল: সার্ভার crash করে পরে ডিস্ক নিয়ে ফিরতে পারে; বার্তা হারাতে, দেরিতে, দুবার বা উল্টো ক্রমে আসতে পারে। কিন্তু কেউ মিথ্যা বলে না — crash fault মডেল। মিথ্যাবাদী বা ভাঙা সার্ভারের Byzantine fault আলাদা, আরও দামি সমস্যা (ভাবনার প্রশ্ন ৪)।

কোথায় কোথায় লাগে

দ্বিতীয় কার্ডটিই এই পর্বের কেন্দ্র — replicated state machine: প্রতিটি সার্ভারে একটি consensus module, একটি log আর একটি state machine (যেমন key-value টেবিল)। পর্ব ৩৩-এর log-ভিত্তিক streaming-এর পেছনেও এই চিন্তা (পর্ব ৩৩)।

২ · Majority quorum — ২f + ১ কেন, আর দুই majority কেন মেলে

সিদ্ধান্ত পাকা করতে কতজনের সম্মতি লাগবে? দুই চরম পথই খারাপ:

• সবার সম্মতি: পর্ব ২৫-এর two-phase commit-এর মতো। একজন বিকল হলেই সব থামে (পর্ব ২৫)।
• যেকোনো একজন: Network দুই ভাগ হলে দুই দিকে দুটি ভিন্ন সিদ্ধান্ত — agreement ভাঙে।

মাঝের পথটি quorum: N সদস্যের মধ্যে অর্ধেকের বেশি, অর্থাৎ Q = ⌊N/২⌋ + ১. তাহলে একসাথে f = N − Q = ⌊(N − ১)/২⌋ জন crash করলেও বাকিরা Q পূরণ করতে পারে। উল্টো দিক থেকে: f-টি ব্যর্থতা সহ্য করতে কমপক্ষে N = ২f + ১ সদস্য লাগে।

প্রমাণ: যেকোনো দুটি majority মেলে

ধরুন A আর B দুটি majority. প্রতিটির আকার অন্তত ⌊N/২⌋ + ১, তাই |A| + |B| ≥ ২⌊N/২⌋ + ২ ≥ (N − ১) + ২ = N + ১. কিন্তু মোট সদস্য মাত্র N জন। কবুতরের খোপের নীতিতে (pigeonhole) অন্তত একজন সদস্যকে দুই দলেই থাকতে হবে। ∎

এই ছোট সত্য থেকেই দুটি বড় ফল:

1. Network ভাগ হলে বড়জোর এক ভাগ এগোয়। দুই ভাগই majority হতে পারে না। ছোট ভাগ লেখা নেয় না — নিরাপদ, কিন্তু সেখানে সেবা বন্ধ। পর্ব ৪০-এর ভাষায় এটি consistency-র পক্ষে বাছাই (পর্ব ৪০)।
2. পুরোনো সিদ্ধান্ত হারায় না। একটি entry majority-তে পৌঁছে পাকা হলো। পরে যে majority নতুন leader বাছবে, তার অন্তত একজন সদস্যের কাছে entry-টি আছে। Raft-এর ভোটের নিয়ম সেই সদস্যকে দিয়েই পাহারা বসায় (অংশ ৭)।

৩ · Raft-এর মানচিত্র — তিন ভূমিকা, term আর দুটি RPC

তিন ভূমিকা

• Follower: নিষ্ক্রিয়; শুধু leader আর candidate-এর বার্তার উত্তর দেয়। শুরুতে সবাই follower.
• Candidate: leader-এর খবর না পেয়ে যে নিজেকে প্রার্থী ঘোষণা করে ভোট চাইছে।
• Leader: সব client অনুরোধ নেয়, log-এ entry যোগ করে follower-দের পাঠায়, আর নিয়মিত heartbeat দিয়ে জানায় “আমি আছি”। Log শুধু leader থেকে follower-এর দিকে যায়, উল্টো দিকে কখনো নয়।

Term — সময়ের বদলে ক্রমিক যুগ

Raft সময়কে ভাগ করে term-এ: ১, ২, ৩ … প্রতিটি term শুরু হয় একটি নির্বাচন দিয়ে। কেউ জিতলে বাকি term সে leader; ভোট ভাগ হয়ে কেউ না জিতলে term-টি leader ছাড়াই শেষ, আর নতুন term-এ আবার নির্বাচন। প্রতিটি সার্ভার নিজের currentTerm রাখে, আর প্রতিটি বার্তায় term লেখা থাকে। দুটি নিয়ম:

1. নিজের চেয়ে বড় term দেখলে সঙ্গে সঙ্গে সেটি গ্রহণ, আর leader বা candidate হলে follower-এ নেমে আসা।
2. ছোট term-এর অনুরোধ প্রত্যাখ্যান — পুরোনো leader ফিরে এসে লেখাতে পারবে না।

অর্থাৎ term একটি logical clock (পর্ব ৩৯), আর একই সাথে fencing token: পর্ব ২২-এর epoch-এর মতো, বড় নম্বর পুরোনো নেতাকে থামায়।

কী ডিস্কে, কী মেমরিতে

পুরো প্রোটোকল চলে দুটি RPC দিয়ে: RequestVote (candidate ভোট চায়) আর AppendEntries (leader entry পাঠায়; ফাঁকা হলে এটিই heartbeat). পরে snapshot-এর জন্য তৃতীয় একটি — InstallSnapshot (অংশ ৮)।

৪ · Leader election — randomized timeout, RequestVote আর up-to-date যাচাই

প্রতিটি follower একটি টাইমার চালায় — election timeout. Leader-এর heartbeat এলে, বা কোনো candidate-কে ভোট দিলে, টাইমার নতুন করে শুরু হয়। কিছুই না এলে সময় ফুরায়, আর follower candidate হয়:

1. currentTerm এক বাড়ায়, নিজেকে ভোট দেয়, দুটোই ডিস্কে লেখে।
2. সবাইকে RequestVote পাঠায়: নিজের term, নিজের id, আর নিজের log-এর শেষ entry-র index ও term — lastLogIndex, lastLogTerm.
3. তিনটির একটি ঘটা পর্যন্ত অপেক্ষা: (ক) majority ভোট পেলে leader, আর সঙ্গে সঙ্গে heartbeat; (খ) সমান বা বড় term-এর একজন leader-এর AppendEntries পেলে follower; (গ) আবার timeout হলে নতুন term-এ নতুন নির্বাচন।

কে ভোট পাবে — দুটি শর্ত

• এক term-এ এক ভোট: যে আগে চাইল, সে পায় (first-come-first-served); votedFor ডিস্কে থাকে বলে restart-এর পরেও দ্বিতীয় ভোট নেই।
• Up-to-date যাচাই: candidate-এর log ভোটদাতার log-এর অন্তত সমান হালনাগাদ হতে হবে। তুলনা: শেষ entry-র term যার বড়, সে এগিয়ে; শেষ term সমান হলে যার log লম্বা, সে এগিয়ে।

প্রথম শর্ত আর majority মিলে দেয় Election Safety: এক term-এ দুজন majority পেতে হলে অন্তত একজনকে দুবার ভোট দিতে হতো — যা নিয়মে নিষেধ। দ্বিতীয় শর্তটি অংশ ৬ আর ৭-এর মূল চাবি।

Timeout কেন random

সবার টাইমার এক হলে সবাই একসাথে candidate হয়ে নিজেকে ভোট দেবে — কেউ majority পাবে না: split vote, চিরকাল চলতে পারে। Raft-এর সমাধান সরল: প্রতিবার timeout একটি সীমার মধ্যে random — গবেষণাপত্রের উদাহরণে ১৫০ থেকে ৩০০ ms. সাধারণত একজনের টাইমার আগে ফুরায়, আর অন্যদের ফুরানোর আগেই সে ভোট জোগাড় করে ফেলে; ভোট ভাগ হলেও পরের term-এ নতুন random সময়।

এবার একটি নির্বাচন ধাপে ধাপে। পাঁচটি সার্ভার; term ১-এর leader S1 হঠাৎ crash করল। বাকি চারজনের random টাইমার: S2 = ২৪৪, S3 = ১৫০, S4 = ২২৯, S5 = ২৯৭ ms. বার্তা পৌঁছাতে ৫ থেকে ২০ ms. (সংখ্যাগুলো নিচের simulator-এর seed ১-এর হুবহু আউটপুট।) “পরে” চাপুন:

এবার নিজে চালান। পাঁচ সার্ভারের ছোট একটি event-ভিত্তিক মডেল: timeout ১৫০–২৯৯ ms, বার্তার দেরি ৫–২০ ms, seed-সহ PRNG (mulberry32), তাই প্রতিবার একই ফল। দ্বিতীয় seed-এ দুজন প্রায় একসাথে candidate হয়:

// Raft leader election: 5 servers, old leader S1 (term 1) crashes at t=0. Seeded, times in ms.
function mulberry32(a) { return () => { a = a + 0x6D2B79F5 | 0; let t = Math.imul(a ^ a >>> 15, 1 | a);
  t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; }; }
function elect(seed) {
  const rnd = mulberry32(seed), N = 5, MAJ = 3, ev = [];
  const timeout = () => 150 + Math.floor(rnd() * 150);     // randomized election timeout: 150..299
  const delay = () => 5 + Math.floor(rnd() * 16);          // one-way message delay: 5..20
  const s = [1, 2, 3, 4, 5].map(i => ({ id: "S" + i, term: 1, voted: "S1", role: "follower", votes: 0, due: 0 }));
  s[0].role = "crashed";
  const arm = (x, t) => { x.due = t + timeout(); ev.push({ t: x.due, k: "timeout", to: x, due: x.due }); };
  const send = (t, from, k) => s.forEach(y => { if (y !== from) ev.push({ t: t + delay(), k, from, to: y, term: from.term }); });
  s.slice(1).forEach(x => arm(x, 0));
  console.log(`--- seed ${seed}: timers ` + s.slice(1).map(x => x.id + "=" + x.due).join(" "));
  let end = Infinity;
  while (ev.length) {
    ev.sort((a, b) => a.t - b.t); const e = ev.shift(), x = e.to;
    if (e.t > end) break;
    if (x.role === "crashed" || (e.k === "timeout" && (e.due !== x.due || x.role === "leader"))) continue;
    if (e.term > x.term) { x.term = e.term; x.voted = null; x.role = "follower"; }
    if (e.k === "timeout") {
      if (x.role === "candidate") console.log(`t=${e.t} ${x.id}: term ${x.term} ended with only ${x.votes} votes (split vote)`);
      x.term++; x.role = "candidate"; x.voted = x.id; x.votes = 1; arm(x, e.t);
      console.log(`t=${e.t} ${x.id}: timeout -> candidate, term ${x.term}, votes for itself, next timeout t=${x.due}`); send(e.t, x, "ask");
    } else if (e.k === "ask") {
      const ok = e.term === x.term && (x.voted === null || x.voted === e.from.id);
      if (ok) { x.voted = e.from.id; arm(x, e.t); console.log(`t=${e.t} ${x.id}: votes for ${e.from.id} in term ${x.term}`); }
      ev.push({ t: e.t + delay(), k: "vote", from: x, to: e.from, term: x.term, ok });
    } else if (e.k === "vote" && x.role === "candidate" && e.ok && e.term === x.term && ++x.votes === MAJ) {
      x.role = "leader"; end = e.t + 25;
      console.log(`t=${e.t} ${x.id}: LEADER of term ${x.term} (${MAJ} of ${N} votes), sends heartbeats`); send(e.t, x, "beat");
    } else if (e.k === "beat" && e.term === x.term) { x.role = "follower"; arm(x, e.t); console.log(`t=${e.t} ${x.id}: heartbeat from ${e.from.id}, follower in term ${x.term}`); }
  }
}
elect(1);   // a clean election
elect(23);  // two candidates at once: a split vote

--- seed 1: timers S2=244 S3=150 S4=229 S5=297
t=150 S3: timeout -> candidate, term 2, votes for itself, next timeout t=445
t=161 S5: votes for S3 in term 2
t=164 S2: votes for S3 in term 2
t=166 S4: votes for S3 in term 2
t=173 S3: LEADER of term 2 (3 of 5 votes), sends heartbeats
t=179 S4: heartbeat from S3, follower in term 2
t=184 S5: heartbeat from S3, follower in term 2
t=185 S2: heartbeat from S3, follower in term 2
--- seed 23: timers S2=163 S3=160 S4=244 S5=195
t=160 S3: timeout -> candidate, term 2, votes for itself, next timeout t=358
t=163 S2: timeout -> candidate, term 2, votes for itself, next timeout t=314
t=169 S4: votes for S2 in term 2
t=178 S5: votes for S3 in term 2
t=314 S2: term 2 ended with only 2 votes (split vote)
t=314 S2: timeout -> candidate, term 3, votes for itself, next timeout t=590
t=321 S5: votes for S2 in term 3
t=322 S3: votes for S2 in term 3
t=331 S4: votes for S2 in term 3
t=342 S2: LEADER of term 3 (3 of 5 votes), sends heartbeats
t=357 S3: heartbeat from S2, follower in term 3
t=358 S5: heartbeat from S2, follower in term 3
t=359 S4: heartbeat from S2, follower in term 3

৫ · Log replication — AppendEntries, consistency check আর commit index

Leader পাওয়া গেল; এখন আসল কাজ। Client একটি আদেশ পাঠালে leader সেটি নিজের log-এ নতুন entry হিসেবে যোগ করে — index, নিজের term আর আদেশ। তারপর সব follower-কে সমান্তরালে AppendEntries পাঠায়:

AppendEntries {
  term:         3,      // leader's current term
  leaderId:     "S1",
  prevLogIndex: 5,      // index of the entry just before the new ones
  prevLogTerm:  3,      // term of that entry
  entries:      [ { index: 6, term: 3, cmd: "SET A3=rumana" } ],   // empty = heartbeat
  leaderCommit: 5       // leader's commitIndex
}
reply { term: 3, success: true }   // false if the follower lacks (prevLogIndex, prevLogTerm)

Consistency check — একটি entry দিয়ে পুরো log মেলানো

Follower নতুন entry নেয় কেবল যদি তার log-এ prevLogIndex জায়গায় ঠিক prevLogTerm-এর entry থাকে; না থাকলে success: false. এই consistency check থেকে induction-এ আসে Log Matching: দুটি log-এ একই index আর term-এর entry থাকলে সেই index পর্যন্ত দুটি log পুরোপুরি এক — কারণ এক term-এ একজন leader এক index-এ একটিই entry বানায়, আর প্রতিটি যোগের আগে ঠিক আগের entry মেলানো হয়।

প্রত্যাখ্যান হলে leader সেই follower-এর nextIndex এক কমিয়ে আবার পাঠায়। পেছাতে পেছাতে যেখানে দুই log মেলে, সেখান থেকে বাকি সব entry যায়; follower-এর বিরোধী entry মুছে leader-এরটি বসে। অনেক বাস্তবায়নে follower বিরোধী term-এর প্রথম index জানিয়ে দেয়, তাই এক ঘর এক ঘর না পিছিয়ে কয়েক ধাপেই মিল মেলে।

Commit index — কখন পাকা

Leader প্রতিটি follower-এর matchIndex জানে। কোনো index N majority-র কাছে থাকলে, আর N-এর entry leader-এর বর্তমান term-এর হলে, leader commitIndex = N করে। তখন N পর্যন্ত সব entry committed: leader সেগুলো state machine-এ চালায় আর client-কে উত্তর দেয়। পরের AppendEntries-এর leaderCommit দেখে follower-রাও নিজেদের state machine-এ চালায়। মোটা অক্ষরের শর্তের কারণ অংশ ৬-এ।

ধাপে ধাপে একটি entry. পাঁচ সার্ভার, leader S1 (term ৩); সবার log-এ index ১–৫ আছে আর commitIndex ৫. ধরা যাক একমুখী পথ ০.৫ ms, একটি fsync ১ ms; S3-এর ডিস্ক ব্যস্ত (fsync ৩ ms) আর S5 দূরের zone-এ (একমুখী ২ ms). একটি বাস-টিকিট সেবা (কাল্পনিক) সিট A3 রুমানার নামে লিখতে চায়:

এবার কঠিন অবস্থা: অনেকক্ষণ বন্ধ থাকা একটি follower, আর একটু পিছিয়ে থাকা আরেকজন। S1 সদ্য term ৩-এর leader হয়েছে; নতুন leader সবার nextIndex ধরে নেয় নিজের শেষ index + ১ — আশাবাদী অনুমান। S3-এর log-এ মাত্র ৩টি entry, আর S5-এর ৪টি:

// Raft log replication with the consistency check. Entry = "term:command"; index = position + 1.
const TERM = 3, MAJ = 3, base = ["1:x=1", "1:y=2", "2:x=5", "2:z=7", "2:y=9"];
const L = { S1: [...base], S2: [...base], S3: base.slice(0, 3), S4: [...base], S5: base.slice(0, 4) };
const up = { S2: true, S3: false, S4: true, S5: true };          // S3 crashed long ago, still down
const next = {}, match = {}; let commit = 3;                      // S1 knows 1..3 are committed
for (const f in up) { next[f] = L.S1.length + 1; match[f] = 0; }  // a new leader starts optimistic
const term = (log, i) => (i === 0 ? 0 : +log[i - 1].split(":")[0]);
function appendEntries(f) {
  const prev = next[f] - 1, log = L[f], pt = term(L.S1, prev);
  if (prev > log.length || term(log, prev) !== pt) {              // consistency check fails
    console.log(`  AE->${f} prevLogIndex=${prev} prevLogTerm=${pt}: REJECT (${f} has ${log.length} entries)`);
    next[f]--; return false;
  }
  const entries = L.S1.slice(prev);
  entries.forEach((e, k) => { const i = prev + k;                 // drop a conflicting suffix, add missing
    if (i < log.length && term(log, i + 1) !== +e.split(":")[0]) log.length = i;
    if (i >= log.length) log.push(e); });
  match[f] = prev + entries.length; next[f] = match[f] + 1;
  console.log(`  AE->${f} prevLogIndex=${prev} prevLogTerm=${pt}: OK, sent ${entries.length}, matchIndex=${match[f]}`);
  return true;
}
function round(title) {
  console.log(title);
  for (const f in up) if (up[f]) while (!appendEntries(f));
  for (let n = L.S1.length; n > commit; n--) {                    // highest n stored on a majority...
    const copies = 1 + Object.values(match).filter(m => m >= n).length;
    if (copies >= MAJ && term(L.S1, n) === TERM) { commit = n; break; }   // ...and from the CURRENT term
  }
  console.log(`  copies of index 5: ${1 + Object.values(match).filter(m => m >= 5).length}, leader commitIndex=${commit}`);
}
round("round 1: S1 just won term 3; S3 is down");
L.S1.push("3:x=8"); round("round 2: client sends x=8 -> index 6, term 3");
up.S3 = true; round("round 3: S3 restarts with 3 entries");
for (const s in L) console.log(`${s}: ${L[s].join(" ")}`);

round 1: S1 just won term 3; S3 is down
  AE->S2 prevLogIndex=5 prevLogTerm=2: OK, sent 0, matchIndex=5
  AE->S4 prevLogIndex=5 prevLogTerm=2: OK, sent 0, matchIndex=5
  AE->S5 prevLogIndex=5 prevLogTerm=2: REJECT (S5 has 4 entries)
  AE->S5 prevLogIndex=4 prevLogTerm=2: OK, sent 1, matchIndex=5
  copies of index 5: 4, leader commitIndex=3
round 2: client sends x=8 -> index 6, term 3
  AE->S2 prevLogIndex=5 prevLogTerm=2: OK, sent 1, matchIndex=6
  AE->S4 prevLogIndex=5 prevLogTerm=2: OK, sent 1, matchIndex=6
  AE->S5 prevLogIndex=5 prevLogTerm=2: OK, sent 1, matchIndex=6
  copies of index 5: 4, leader commitIndex=6
round 3: S3 restarts with 3 entries
  AE->S2 prevLogIndex=6 prevLogTerm=3: OK, sent 0, matchIndex=6
  AE->S3 prevLogIndex=5 prevLogTerm=2: REJECT (S3 has 3 entries)
  AE->S3 prevLogIndex=4 prevLogTerm=2: REJECT (S3 has 3 entries)
  AE->S3 prevLogIndex=3 prevLogTerm=2: OK, sent 3, matchIndex=6
  AE->S4 prevLogIndex=6 prevLogTerm=3: OK, sent 0, matchIndex=6
  AE->S5 prevLogIndex=6 prevLogTerm=3: OK, sent 0, matchIndex=6
  copies of index 5: 5, leader commitIndex=6
S1: 1:x=1 1:y=2 2:x=5 2:z=7 2:y=9 3:x=8
S2: 1:x=1 1:y=2 2:x=5 2:z=7 2:y=9 3:x=8
S3: 1:x=1 1:y=2 2:x=5 2:z=7 2:y=9 3:x=8
S4: 1:x=1 1:y=2 2:x=5 2:z=7 2:y=9 3:x=8
S5: 1:x=1 1:y=2 2:x=5 2:z=7 2:y=9 3:x=8

৬ · Leader বদল, log মেরামত আর “শুধু নিজের term” নিয়ম

গোলমাল বাধে leader মরলে: কারও কাছে কিছু entry নেই, কারও কাছে এমন entry, যা কখনো commit হয়নি। Raft-এর উত্তর কড়া কিন্তু সরল — নতুন leader-এর log-ই সত্য। Follower-দের তার সাথে মেলাতে হবে; বিরোধী entry মুছে leader-এরটি বসবে। Leader নিজে কখনো নিজের entry মোছে না — Leader Append-Only. এটি নিরাপদ, কারণ ভোটের up-to-date নিয়ম নিশ্চিত করে যে নতুন leader-এর কাছে সব committed entry আছেই।

নিচের stepper-এ প্রতিটি log দেখানো হয়েছে index ধরে প্রতিটি entry-র term দিয়ে — যেমন “১ ১ ২ ২” মানে index ১ আর ২-এ term ১-এর entry, ৩ আর ৪-এ term ২-এর:

কেন পুরোনো term-এর entry কপি গুনে commit করা যায় না

অংশ ৫-এর simulator-এ index ৫ চার কপিতে থেকেও commit হয়নি। কেন এত সাবধানতা? Raft গবেষণাপত্রের একটি বিখ্যাত উদাহরণ (সেখানে Figure 8), পাঁচ সার্ভারে, শুধু index ২ নিয়ে:

তাই নিয়ম: leader কপি গুনে commit করে শুধু নিজের term-এর entry; আগের entry-গুলো তার সাথে পরোক্ষভাবে commit হয়। নতুন leader term-এর শুরুতে no-op যোগ করে এজন্যই — নতুন অনুরোধের অপেক্ষা ছাড়াই আগের entry পাকা হয়, আর leader জানে commitIndex কত।

৭ · Safety — পাঁচটি নিশ্চয়তা আর একটি ছোট প্রমাণ

Raft গবেষণাপত্র পাঁচটি property প্রমাণ করে। এগুলো মিলেই “কোনো দুটি সার্ভার কখনো একই index-এ ভিন্ন আদেশ চালাবে না”:

Leader Completeness — প্রমাণের ধারণা

ধরুন term T-এর leader একটি entry e commit করেছে। তাহলে e আছে একটি majority M₁-এর কাছে। এখন T-এর পরের প্রথম কোনো term U-র leader L, যার log-এ e নেই — এমন ধরে নিই, আর দেখি অসংগতি আসে কি না।

1. L জিতেছে একটি majority M₂-এর ভোটে। M₁ আর M₂ মেলে (অংশ ২) — একজন ভোটদাতা v, যার কাছে e আছে, আর যে L-কে ভোট দিয়েছে।
2. v ভোট দিয়েছে, তাই L-এর log v-এর log-এর অন্তত সমান হালনাগাদ। দুই সম্ভাবনা:
3. L-এর শেষ term v-এর শেষ term-এর সমান: তাহলে L-এর log লম্বা বা সমান; Log Matching অনুযায়ী v-এর পুরো log L-এর ভেতরে আছে — e-সহ। অসংগতি।
4. L-এর শেষ term বড়: সেই শেষ entry বানিয়েছিল আগের কোনো leader, যার term T-এর চেয়ে বড় (কারণ v-এর শেষ term অন্তত T) আর U-র চেয়ে ছোট। ধরে নেওয়া অনুযায়ী সেই leader-এর log-এ e ছিল (U-ই প্রথম e-হীন leader). Log Matching অনুযায়ী L-এর log-এ সেই entry পর্যন্ত সব আছে — e-সহ। আবার অসংগতি। ∎

কোথায় “শুধু নিজের term” নিয়মটি লাগল? “Commit” মানে ধরে নেওয়া হয়েছে, e যে term-এ commit হলো, সেই term-এর leader-ই কপি গুনেছে। অংশ ৬-এর ধাপ “ঘ”-তে এই শর্ত ভেঙেছিল — term ৪-এর leader term ২-এর entry গুনেছিল।

৮ · Client, read, snapshot আর membership বদল

Client — leader খোঁজা আর একবারের বেশি নয়

Client যেকোনো সার্ভারে পাঠাতে পারে; follower হলে সে leader-এর ঠিকানা জানিয়ে ফিরিয়ে দেয় (redirect). সূক্ষ্ম সমস্যা অন্যখানে: leader entry commit করে চালাল, কিন্তু উত্তর দেওয়ার আগেই crash করল। Client নতুন leader-কে আবার পাঠালে আদেশ দুবার চলবে — যেমন wallet থেকে ৫০০ টাকা কাটা। Raft গবেষণাপত্রের সমাধান: client-এর id আর প্রতিটি অনুরোধের ক্রমিক নম্বর; state machine প্রতিটি client-এর শেষ নম্বর আর উত্তর মনে রাখে, পুরোনো নম্বর এলে আগের উত্তর দেয়, আবার চালায় না। এটি পর্ব ০৮-এর idempotency key-এর একই চিন্তা (পর্ব ০৮, পর্ব ৩৪)।

Linearizable read — leader-এর কাছ থেকে পড়লেও কেন যথেষ্ট নয়

লেখা log দিয়ে যায়; পড়া কি সরাসরি leader-এর state machine থেকে দেওয়া যায়? বিপদ: partition-এ S1 ছোট ভাগে, বড় ভাগে নতুন leader নতুন লেখা commit করছে, আর S1 জানে না সে আর leader নয় — পুরোনো মান পড়াবে। Linearizability (পর্ব ৪০) রাখতে তিনটি পথ:

1. পড়াটিও log-এ: সরল, কিন্তু প্রতিটি পড়ায় একটি লেখার দাম।
2. ReadIndex: leader বর্তমান commitIndex মনে রাখে (term-এ নিজের একটি entry আগে commit হতে হবে — no-op-এর আরেক কাজ), একটি heartbeat-এ majority-র সাড়া নিয়ে নিশ্চিত হয় সে এখনো leader, আর state machine ততদূর চালানো হলে পড়ায় — ডিস্ক নয়, একটি round trip. Follower-ও leader-এর কাছে read index জেনে পড়াতে পারে।
3. Leader lease: heartbeat-এ majority সাড়া দিলে leader ধরে নেয়, election timeout-এর চেয়ে কম একটি সময় পর্যন্ত আর কেউ leader হবে না, আর সেই সময়ে round trip ছাড়াই পড়ায়। দ্রুততম, কিন্তু নিরাপত্তা নির্ভর করে ঘড়ির গতির পার্থক্য সীমিত থাকার ওপর — দীর্ঘ GC pause বা ঘড়ির ভুলে পুরোনো মান পড়ানো সম্ভব (পর্ব ৩৯, পর্ব ৪৩)।

লেখার সময়ের documentation অনুযায়ী etcd ডিফল্টে linearizable read দেয়, আর চাইলে “serializable” read দেয় — স্থানীয় কপি থেকে, দ্রুত, কিন্তু পুরোনো মান হতে পারে। অর্থাৎ পড়ার নিশ্চয়তাও একটি বাছাই।

Snapshot আর log compaction

Log চিরকাল বাড়লে ডিস্ক ভরবে, আর restart-এ পুরো log চালাতে ঘণ্টা লাগবে। তাই প্রতিটি সার্ভার মাঝে মাঝে নিজেই state machine-এর একটি snapshot নেয় — কোন index (lastIncludedIndex) আর কোন term (lastIncludedTerm) পর্যন্ত — তারপর সেই পর্যন্ত log মুছে ফেলে। শেষ index আর term রাখা হয়, যাতে পরের AppendEntries-এর consistency check তখনো চলে। কোনো follower এত পিছিয়ে থাকে যে তার দরকারি entry leader আর রাখেনি, তখন leader পাঠায় পুরো snapshot — InstallSnapshot.

Membership বদল — সংক্ষেপে

৩টি সার্ভার থেকে ৫টিতে যেতে হলে সবাই একসাথে নতুন তালিকা জানবে না। মাঝের সময়ে পুরোনো তালিকার একটি majority আর নতুন তালিকার আরেকটি majority না মিলতে পারে — একই term-এ দুজন leader. Raft-এর দুটি সমাধান:

• Joint consensus (মূল গবেষণাপত্র): মাঝখানে একটি অন্তর্বর্তী configuration, যেখানে প্রতিটি সিদ্ধান্তে পুরোনো আর নতুন — দুই তালিকারই আলাদা majority লাগে। সেটি commit হলে নতুন তালিকায় যাওয়া।
• একবারে একটি সার্ভার (Ongaro-র PhD গবেষণাপত্র): শুধু একটি করে যোগ বা বাদ। তখন পুরোনো আর নতুন তালিকার যেকোনো majority সব সময় মেলে, তাই অন্তর্বর্তী ধাপ লাগে না। পরে এর একটি সূক্ষ্ম ত্রুটি আর তার সমাধান (নতুন leader আগে নিজের term-এর একটি entry commit করবে) প্রকাশিত হয় বলে জানা যায়; বাস্তবায়নের আগে সর্বশেষ বিবরণ মিলিয়ে নিন।

খালি নতুন সার্ভার majority-তে ঢুকলে commit আটকাতে পারে, তাই অনেক সিস্টেমে তাকে আগে ভোটহীন সদস্য (etcd-এ learner) করে log ধরানো হয়।

৯ · Paxos-এর ধারণা, আর Raft–Paxos–ZAB–VR পাশাপাশি

Paxos Leslie Lamport-এর, Raft-এর প্রায় পঁচিশ বছর আগের (ইতিহাস ভাবনার প্রশ্ন ১-এ)। একটি মানে একমত হওয়ার রূপটি single-decree Paxos. তিনটি ভূমিকা, একই যন্ত্র একাধিকটি নিতে পারে:

• Proposer: একটি মান প্রস্তাব করে।
• Acceptor: ভোটার; এদের majority যা গ্রহণ করে, সেটিই সিদ্ধান্ত।
• Learner: সিদ্ধান্ত জেনে নেয় আর কাজে লাগায়।

কেন নিরাপদ: কোনো মান majority-তে গৃহীত হলে পরের যেকোনো proposer-এর promise-দাতাদের অন্তত একজন সেই খবর আনবে (অংশ ২), আর ধাপ ২ক-এর নিয়মে সেই মানই প্রস্তাব করতে হবে। Raft-এর up-to-date ভোট আর Paxos-এর “সবচেয়ে বড় নম্বরের মান নাও” — একই intersection-এর দুটি রূপ। কেন আটকাতে পারে: দুজন proposer পালা করে বড় নম্বরে Prepare পাঠালে একে অপরের ধাপ ২ বাতিল করতে থাকে — livelock. সমাধান একজন প্রধান proposer, অর্থাৎ leader, আর random বিরতি — Raft-এর random timeout-এর মতোই।

Multi-Paxos: একটি log মানে অনেকগুলো slot, প্রতিটিতে একটি Paxos. একজন স্থির leader সব ভবিষ্যৎ slot-এর জন্য ধাপ ১ একবারে সেরে নেয়, তারপর প্রতিটি আদেশে শুধু ধাপ ২ — majority-র সাথে একটি round trip, Raft-এর AppendEntries-এর মতো। এর একক আনুষ্ঠানিক বর্ণনা নেই, তাই বাস্তবায়নভেদে খুঁটিনাটি আলাদা — Raft-এর জন্মের একটি কারণ।

১০ · দাম, cluster-এর আকার আর AI-এর যুগে যাচাই

একটি commit-এর দাম

Leader নিজের কপি নিজেই রাখে, তাই তার দরকার আরও Q − ১টি follower-এর সাফল্য। Commit-এর latency প্রায় = leader থেকে (Q − ১)-তম দ্রুততম follower-এর RTT + সেই follower-এর fsync (leader-এর fsync সমান্তরালে)। Leader-এর নিজের “RTT” ০ ধরে সবার RTT সাজালে, বিজোড় N-এ এটি ঠিক মাঝের মান — median. সবচেয়ে ধীরজন নয়, মাঝের জন। নিচের simulator প্রথমে N = ১ থেকে ৭-এর টেবিল দেখায়, তারপর ধরা যাক দুই ধরনের বসানোয় seed-সহ RTT নিয়ে commit-এর সময়:

// Majority quorums: size, failures tolerated, and what one commit costs in network time.
function mulberry32(a) { return () => { a = a + 0x6D2B79F5 | 0; let t = Math.imul(a ^ a >>> 15, 1 | a);
  t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; }; }
const maj = (n) => Math.floor(n / 2) + 1;
console.log(" N  majority  failures-tolerated  acks-the-leader-waits-for");
for (let n = 1; n <= 7; n++)
  console.log(String(n).padStart(2) + String(maj(n)).padStart(9) + String(n - maj(n)).padStart(15) +
    String(maj(n) - 1).padStart(20) + (n % 2 === 0 ? "   (even: no gain over " + (n - 1) + ")" : ""));
const rnd = mulberry32(42);
const places = [["one region, 3 zones", 0.4, 2.0], ["spread over 3 regions", 40, 180]];  // assumed RTT ranges (ms)
for (const [name, lo, hi] of places) {
  const rtt = Array.from({ length: 6 }, () => +(lo + rnd() * (hi - lo)).toFixed(1));
  console.log(`--- ${name}: leader->follower RTTs (ms) = ${rtt.join(", ")}`);
  for (const n of [3, 5, 7]) {
    const all = [0, ...rtt.slice(0, n - 1)].sort((a, b) => a - b);   // leader's own copy costs 0
    const commit = all[maj(n) - 1];                                  // majority-th fastest = median
    console.log(`N=${n}: sorted [${all.join(", ")}] -> commit waits ${commit} ms (fastest ${maj(n)} of ${n})`);
  }
}

 N  majority  failures-tolerated  acks-the-leader-waits-for
 1        1              0                   0
 2        2              0                   1   (even: no gain over 1)
 3        2              1                   1
 4        3              1                   2   (even: no gain over 3)
 5        3              2                   2
 6        4              2                   3   (even: no gain over 5)
 7        4              3                   3
--- one region, 3 zones: leader->follower RTTs (ms) = 1.4, 1.1, 1.8, 1.5, 0.7, 1.2
N=3: sorted [0, 1.1, 1.4] -> commit waits 1.1 ms (fastest 2 of 3)
N=5: sorted [0, 1.1, 1.4, 1.5, 1.8] -> commit waits 1.4 ms (fastest 3 of 5)
N=7: sorted [0, 0.7, 1.1, 1.2, 1.4, 1.5, 1.8] -> commit waits 1.2 ms (fastest 4 of 7)
--- spread over 3 regions: leader->follower RTTs (ms) = 78.3, 127.5, 161.2, 106.1, 75, 163.5
N=3: sorted [0, 78.3, 127.5] -> commit waits 78.3 ms (fastest 2 of 3)
N=5: sorted [0, 78.3, 106.1, 127.5, 161.2] -> commit waits 106.1 ms (fastest 3 of 5)
N=7: sorted [0, 75, 78.3, 106.1, 127.5, 161.2, 163.5] -> commit waits 106.1 ms (fastest 4 of 7)

কেন ৩ বা ৫, আর কোথায় বসাবেন

• ৩: একটি ব্যর্থতা সহ্য করে; একটি রক্ষণাবেক্ষণে থাকলে আরেকটি বিকল হলেই লেখা বন্ধ।
• ৫: দুটি সহ্য করে — একটি রক্ষণাবেক্ষণে আর একটি হঠাৎ বিকল হলেও চলে।
• ৭ বা বেশি: leader-এর বার্তা বাড়ে, majority বড় হয়; লাভ সামান্য। বেশি কপি লাগলে ভোটহীন read replica.
• বসানো: আলাদা failure domain-এ, যেমন তিনটি availability zone-এ; দুটি data centre-এ ভাগ করার ফাঁদ অনুশীলন ৩-এ।
• Leader-হীন সময়: নতুন leader না আসা পর্যন্ত লেখা বন্ধ — মোটামুটি একটি election timeout আর একটি নির্বাচন, যা availability-র হিসাবে ঢোকে (পর্ব ০৫)।

Throughput: সব লেখা একজন leader দিয়ে যায়, তাই একটি group-এর গতি একটি যন্ত্রের সীমায় বাঁধা। বড় ডেটাবেস তাই ডেটা টুকরোয় ভাগ করে (পর্ব ২৩) প্রতিটির জন্য আলাদা Raft group চালায় — Multi-Raft, প্রকাশিত নকশা অনুযায়ী CockroachDB আর TiKV-তে। আর অ্যাপের lock, lease বা configuration-এর জন্য নিজে Raft না লিখে etcd বা ZooKeeper-এর মতো coordination service ব্যবহার করুন; সেই নকশা পর্ব ৪৩-এ (পর্ব ৪৩)।

AI-এর যুগে consensus-এর নকশা যাচাই

“High availability-র জন্য কী করব?” — AI প্রায়ই বলে, “Raft, etcd, Kafka আর Redis যোগ করুন।” নামগুলো ঠিক, কিন্তু সংখ্যা আর ব্যর্থতার হিসাব প্রায়ই ভুল:

AI-এর নকশা মানার আগে — চেকলিস্ট

• Quorum, সহনশীলতা আর প্রতিটি failure domain হারানোর হিসাব নিজে আবার করেছি
• Commit latency সব RTT সাজিয়ে Q-তম দ্রুততম ধরে হিসাব করেছি, fsync-সহ
• পড়ার নিশ্চয়তা লেখা আছে — log, ReadIndex, lease না স্থানীয় কপি — আর lease-এর ঘড়ির শর্ত মেনেছি
• Leader crash, partition আর ধীর follower simulator বা পরীক্ষামূলক cluster-এ চালিয়ে দেখেছি
• পণ্যের ডিফল্ট আর সীমা অফিশিয়াল documentation-এ মিলিয়েছি; দরকার না হলে নিজে consensus লিখছি না