Membership আর failure detection — heartbeat, gossip আর SWIM

১ · Membership সমস্যা — cluster-এ কে আছে, কে বেঁচে আছে

একটি কাল্পনিক ride-sharing অ্যাপের কথা ভাবুন। চালকদের location রাখা হয় ৩০০টি সার্ভারের একটি distributed cache-এ, আর কোন চালকের তথ্য কোন সার্ভারে থাকবে তা ঠিক হয় পর্ব ১৬-এর consistent hashing ring দিয়ে। Ring বানাতে প্রত্যেক সার্ভারের হাতে একটি তালিকা লাগে: এই মুহূর্তে কারা আছে. একটি সার্ভার হঠাৎ বিদ্যুৎ হারালে তার ভাগের key অন্যদের নিতে হবে — কিন্তু তার আগে কাউকে টের পেতে হবে যে সে আর নেই।

এখানে আসলে দুটি প্রশ্ন। প্রথমটি সদস্যপদ: কে ইচ্ছা করে যোগ দিল (join), কে ইচ্ছা করে বেরিয়ে গেল (leave). এগুলো ঘোষণা দিয়ে হয়, তাই তুলনামূলক সহজ। দ্বিতীয়টি বেঁচে থাকা: কে কোনো ঘোষণা ছাড়াই crash করল, আটকে গেল, বা network থেকে বিচ্ছিন্ন হলো। এটাই কঠিন অংশ, কারণ মৃত সার্ভার নিজের মৃত্যুর খবর দেয় না।

পর্ব ৩৮-এ দেখেছেন, একটি অনুরোধের উত্তর না এলে আপনি জানেন না অনুরোধটি হারিয়েছে, উত্তর হারিয়েছে, সার্ভার ধীর, না সার্ভার মৃত — এটাই partial failure. তাই কোনো যন্ত্র নিশ্চিতভাবে বলতে পারে না “ও মারা গেছে”; বলতে পারে শুধু “অনেকক্ষণ ওর কোনো সাড়া পাইনি।” Membership সেবার কাজ এই অনিশ্চয়তার ভেতরে যথেষ্ট ভালো একটি তালিকা সবার হাতে রাখা।

ভালো membership সেবার কাছে আমরা চাই: দ্রুত ধরা (পর্ব ৫-এর MTTR-এর প্রথম অংশই টের পাওয়ার সময়), কম ভুল (প্রতিটি ভুল ঘোষণা অকারণ failover আর ডেটা সরানো ডেকে আনে), কম খরচ, বড় হলেও চলা, আর কিছুক্ষণের মধ্যে মোটামুটি মেলানো তালিকা — প্রতি মুহূর্তে হুবহু এক হওয়ার নিশ্চয়তা সাধারণত থাকে না (অংশ ৯)।

২ · Failure detector — completeness, accuracy আর সময়ের টানাপোড়েন

১৯৯৬ সালে Tushar Chandra আর Sam Toueg একটি প্রভাবশালী paper-এ failure detector-কে দুটি গুণ দিয়ে মাপার ভাষা দেন। Completeness: যে সদস্য সত্যিই crash করেছে, তাকে শেষ পর্যন্ত (জীবিত) সবাই সন্দেহ করবে। Accuracy: জীবিত সদস্যকে কেউ সন্দেহ করবে না। দুটিই একসাথে পুরোপুরি পাওয়া মানে একটি “নিখুঁত” detector.

সমস্যা হলো, বাস্তবের network-এ বার্তা কতক্ষণে পৌঁছাবে তার কোনো ঊর্ধ্বসীমা নেই (asynchronous model). সেখানে নিখুঁত detector বানানো যায় না: যত বড় timeout-ই নিন, একটি জীবিত কিন্তু ধীর সদস্য তার চেয়েও দেরি করতে পারে। Fischer, Lynch আর Paterson-এর ১৯৮৫ সালের বিখ্যাত ফলাফল (FLP) এরই আরেক রূপ — এমন মডেলে একটি process-ও crash করতে পারলে সবসময় শেষ হওয়ার নিশ্চয়তাসহ consensus অসম্ভব। Chandra–Toueg দেখান, detector যদি শুধু “এক সময় পরে” নির্ভুল হয় (eventually accurate), তাতেই majority সচল থাকলে consensus সম্ভব — পর্ব ৪২-এর Raft ঠিক এই ধরনের অনুমানের ওপর দাঁড়িয়ে।

প্রকৌশলের ভাষায় তাই প্রশ্নটি দাঁড়ায় তিনটি সংখ্যায় (Wei Chen, Sam Toueg আর Marcos Aguilera-র ২০০২ সালের একটি paper এই মাপকাঠিগুলো বিশদ করে):

এই টানাপোড়েন এড়ানোর কোনো উপায় নেই; আছে শুধু আরও বুদ্ধিমান মাপজোখ। পরের অংশগুলোতে তিনটি কৌশল দেখবেন: network-এর আচরণ শিখে নেওয়া (phi accrual), এক চোখের বদলে কয়েক চোখে দেখা (SWIM-এর পরোক্ষ ping), আর সঙ্গে সঙ্গে মৃত না বলে আগে “সন্দেহ” বলা (suspicion).

৩ · Heartbeat — push বনাম pull, নির্দিষ্ট timeout আর all-to-all-এর O(n²) খরচ

সবচেয়ে সহজ detector হলো heartbeat: প্রতি Δ সময় পরপর একটি ছোট “আমি আছি” বার্তা। দুই রকমে করা যায়:

নির্দিষ্ট timeout-এর হিসাব. ধরা যাক Δ = ১ s, আর timeout T = ৩ s (পরপর তিনটি heartbeat না এলে)। Crash ঘটে শেষ heartbeat পৌঁছানোর পর কোনো এলোমেলো মুহূর্তে — ০ থেকে Δ-এর মধ্যে, যখন পরেরটি যাওয়ার কথা। তাই ধরার সময় T − Δ থেকে T-এর মধ্যে, গড়ে প্রায় T − Δ/2 = ২.৫ s. অন্যদিকে, একটি জীবিত সদস্যের heartbeat-এর মাঝের ফাঁক (inter-arrival time) কখনো T ছাড়ালেই false positive. ফাঁক বড় হয় network-এর jitter, packet loss, অতিরিক্ত ব্যস্ত CPU বা GC pause-এর কারণে।

সবাই সবাইকে — all-to-all-এর দাম

একটি কেন্দ্রীয় পর্যবেক্ষক সবার heartbeat নিলে সে নিজেই একটি single point of failure, আর তার network খারাপ হলে সে সবাইকে মৃত ভাববে। তাই peer-to-peer সমাধানে স্বাভাবিক চিন্তা: প্রত্যেকে প্রত্যেককে heartbeat পাঠাক। n জন সদস্য হলে প্রতি Δ-তে বার্তা n(n − 1), আর প্রত্যেককে প্রতি Δ-তে n − 1টি বার্তা গ্রহণ ও প্রক্রিয়া করতে হয়।

ভুলও বাড়ে: n(n − 1)টি জোড়া আলাদা করে বিচার করে, তাই n বড় হলে কোনো না কোনো জোড়ার ফাঁক timeout ছাড়াবেই। কয়েক ডজন সদস্যে all-to-all ঠিক আছে; শত শত বা হাজারে নতুন চিন্তা লাগে।

৪ · Phi accrual — “মৃত না জীবিত” নয়, সন্দেহের মাত্রা

নির্দিষ্ট timeout একটি একক সংখ্যা, কিন্তু network-এর আচরণ বদলায়: রাতে শান্ত, দুপুরে ভিড়ে jitter বেশি; এক data center-এ ফাঁক স্থির, দূরের region-এ ছড়ানো। ২০০৪ সালে Naohiro Hayashibara ও সহকর্মীরা (Défago, Yared, Katayama) প্রস্তাব করেন φ (phi) accrual failure detector: detector “মৃত/জীবিত” বলবে না, বরং একটি অবিরাম সংখ্যা দেবে — সন্দেহ কতটা।

পদ্ধতিটি এরকম। সাম্প্রতিক কয়েকশো heartbeat-এর ফাঁক একটি sliding window-এ রাখা হয়, তা থেকে গড় μ আর standard deviation σ. শেষ heartbeat-এর পর t সময় চুপ থাকলে প্রশ্ন: জীবিত থাকলে এত দেরি হওয়ার সম্ভাবনা কত? সেই সম্ভাবনা P_later(t) হলে

সুবিধা দুটি। প্রথমত, network ঝাঁকুনি দিলে σ বাড়ে, ফলে একই নীরবতায় φ কম আসে — detector নিজে থেকে ধৈর্য বাড়ায়। দ্বিতীয়ত, একই detector থেকে ভিন্ন কাজ ভিন্ন সীমায় সিদ্ধান্ত নিতে পারে: φ = 2-তে নতুন অনুরোধ পাঠানো বন্ধ (সস্তা, ফেরানো যায়), φ = 8-এ failover শুরু (দামি)। লেখার সময়ের ডকুমেন্টেশন অনুযায়ী Cassandra আর Akka cluster দুটিই phi accrual ব্যবহার করে, ডিফল্ট সীমা ৮-এর কাছাকাছি; সংস্করণভেদে বিবরণ আলাদা।

নিচের simulator এক ঘণ্টার (৩,৬০০টি) heartbeat-এর ফাঁক বানায়: গড়ে ১,০০০ ms, ±৪৫০ ms-এর মধ্যে ছড়ানো (মাঝখানে ঘন, দুই পাশে পাতলা — bell curve-এর মতো), আর ১% ক্ষেত্রে ০–৪,০০০ ms-এর বাড়তি বিরতি (GC pause বা ভিড়ের মতো)। তারপর কয়েকটি নির্দিষ্ট timeout-এ ভুলের সংখ্যা আর ধরার সময় গোনে, আর তিন রকম মডেলে φ হিসাব করে।

// Heartbeat every 1000 ms; arrival gaps jitter, and 1% of gaps hit a long pause.
let seed = 7; function rand() {      // mulberry32: seeded PRNG
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
function gap() {                     // ms between two heartbeats of a HEALTHY node
  const g = 1000 + 150 * (rand() + rand() + rand() - 1.5) * 2;   // ~bell curve around 1000
  return rand() < 0.01 ? g + 4000 * rand() : g;                  // 1%: GC pause / congestion
}
const hour = Array.from({ length: 3600 }, gap);    // one hour of heartbeats
console.log("timeout  false alarms/hour  detect time after crash (avg, max)");
for (const T of [1200, 1500, 2000, 3000, 5000]) {
  const fp = hour.filter(g => g > T).length;
  // crash happens at a uniform moment after the last heartbeat arrived
  let sum = 0; for (let i = 0; i < 1000; i++) sum += T - 1000 * rand();
  console.log(String(T).padStart(7) + "  " + String(fp).padStart(17) + "  " +
    (sum / 1000).toFixed(0).padStart(6) + " ms, " + T + " ms");
}
// phi accrual: phi = -log10(P(next gap > t)), normal fit on the last 1000 gaps
const win = hour.slice(-1000);
const mu = win.reduce((a, b) => a + b) / win.length;
const sd = Math.sqrt(win.reduce((a, b) => a + (b - mu) ** 2, 0) / win.length);
const tail = t => { const y = (t - mu) / sd;   // logistic approximation of the normal tail
  return 1 / (1 + Math.exp(y * (1.5976 + 0.070566 * y * y))); };
console.log("window mean " + mu.toFixed(0) + " ms, std " + sd.toFixed(0) + " ms");
console.log("silent for   phi(normal)  phi(exponential)  phi(measured)");
for (const t of [1000, 1500, 2000, 2500, 3000])
  console.log(String(t).padStart(7) + " ms  " + (-Math.log10(tail(t))).toFixed(2).padStart(11) +
    "  " + (t / mu * Math.LOG10E).toFixed(2).padStart(16) +
    "  " + (-Math.log10(win.filter(g => g > t).length / win.length)).toFixed(2).padStart(13));

timeout  false alarms/hour  detect time after crash (avg, max)
   1200                346     720 ms, 1200 ms
   1500                 32    1012 ms, 1500 ms
   2000                 28    1505 ms, 2000 ms
   3000                 15    2499 ms, 3000 ms
   5000                  0    4495 ms, 5000 ms
window mean 1009 ms, std 242 ms
silent for   phi(normal)  phi(exponential)  phi(measured)
   1000 ms         0.29              0.43           0.32
   1500 ms         1.68              0.65           2.10
   2000 ms         4.97              0.86           2.15
   2500 ms        11.50              1.08           2.22
   3000 ms        22.89              1.29           2.40

৫ · কেন্দ্রীয় membership — coordination service-এর হাতে তালিকা

সবচেয়ে প্রচলিত সমাধানটি আসলে সবচেয়ে সরল: তালিকাটি রাখুন একটি coordination service-এ — ZooKeeper বা etcd-এর মতো ছোট, অত্যন্ত নির্ভরযোগ্য একটি cluster, যা নিজে consensus দিয়ে তথ্য মেলায় (পর্ব ৪৩)। প্রতিটি সদস্য যোগ দেওয়ার সময় সেখানে একটি ephemeral node (ZooKeeper) বা lease-যুক্ত key (etcd) বানায়, আর নিজের session বা lease নিয়মিত heartbeat দিয়ে নবায়ন করে। Heartbeat থামলে session-এর মেয়াদ শেষে entry নিজে থেকেই মুছে যায়, আর যারা “watch” করছে তারা সঙ্গে সঙ্গে খবর পায়।

বাস্তবে এর উদাহরণ অনেক। প্রকাশিত ডকুমেন্টেশন অনুযায়ী Kubernetes-এ প্রতিটি node-এর kubelet নিয়মিত একটি Lease object নবায়ন করে, আর control plane নির্দিষ্ট সময় নবায়ন না দেখলে node-এর Ready অবস্থা Unknown করে দেয় (kubectl-এ NotReady দেখায়); সেই অবস্থা শেষ পর্যন্ত etcd-তে থাকে। Kafka-র পুরোনো সংস্করণে broker-দের তালিকা ZooKeeper-এ ephemeral node হিসেবে থাকত; সাম্প্রতিক সংস্করণ নিজস্ব Raft-ভিত্তিক controller (KRaft)-এ সরে গেছে। পর্ব ৪৭-এ service discovery-তে এই ধরনের registry আবার আসবে।

৬ · Gossip — খবর যেভাবে গ্রামে ছড়ায়

গ্রামে একটি বিয়ের খবর কীভাবে ছড়ায়? কেউ মাইকে ঘোষণা দেয় না। চায়ের দোকানে একজন দুজনকে বলেন; তাঁরা বিকেলে হাটে আরও কয়েকজনকে; পরদিন সকালের মধ্যে প্রায় সবাই জানেন। কেউ পুরো গ্রামের দায়িত্ব নেননি, কেউ একা অনেককে বলেননি — তবু খবর দ্রুত সবার কাছে, আর দু-একজন বাড়িতে না থাকলেও খবর থামে না। Computer science-এ এর নাম gossip বা epidemic protocol — রোগ যেমন ছড়ায়।

প্রতি রাউন্ডে (ধরা যাক প্রতি সেকেন্ডে) প্রত্যেক সদস্য এলোমেলোভাবে fanout f জন সঙ্গী বাছে। তিনটি রূপ:

• Push: যে জানে, সে সঙ্গীকে বলে। শুরুতে দ্রুত, শেষে ধীর — শেষের দিকে প্রায় সবাই আগেই জানে, তাই বেশিরভাগ বার্তা অপচয়।
• Pull: প্রত্যেকে সঙ্গীকে জিজ্ঞেস করে “নতুন কী?” শুরুতে ধীর (জানে প্রায় কেউই না), শেষে খুব দ্রুত — যে না জানে সে নিজেই খোঁজে।
• Push-pull: দুজন দেখা হলে দুজনেই নিজের খবর দেয়-নেয়। দুই পর্যায়েই ভালো, তাই বাস্তবে বেশি প্রচলিত।

নিচের stepper-এ ৮ জন সদস্য (A থেকে H), push gossip, fanout ২. ● মানে খবর জানে, ○ মানে জানে না। প্রতিটি রাউন্ডে যারা জানে, তারা দুজন করে এলোমেলো সঙ্গীকে বলে।

কেন O(log n) রাউন্ড — প্রমাণের ধারণা

Push, fanout ১ ধরে দুই পর্যায়ে ভাবুন। বৃদ্ধির পর্যায়: যতক্ষণ জানে এমন সদস্য অর্ধেকের কম, প্রতিটি বার্তা বেশিরভাগ সময় অজানা কাউকে পায়, তাই জানার সংখ্যা প্রতি রাউন্ডে প্রায় দ্বিগুণ: ১, ২, ৪, ৮ … — n/2-তে পৌঁছাতে প্রায় log₂ n রাউন্ড। শেষ পর্যায়: ধরুন এখন অজানা অংশ s. একটি নির্দিষ্ট অজানা সদস্যকে প্রতিটি বার্তা ১/n সম্ভাবনায় বেছে নেয়; প্রায় n জন পাঠাচ্ছে, তাই সে কারও বার্তা না পাওয়ার সম্ভাবনা (1 − 1/n)ⁿ ≈ 1/e. অর্থাৎ প্রতি রাউন্ডে অজানা অংশ e গুণ কমে: s → s/e. n/2 অজানা থেকে ১-এর নিচে নামতে লাগে প্রায় ln n রাউন্ড। মোট ≈ log₂ n + ln n — Pittel-এর ফলাফল।

Fanout f হলে বৃদ্ধির পর্যায়ে গুণক (১ + f), আর শেষ পর্যায়ে না-পাওয়ার সম্ভাবনা ≈ e^−f, তাই ≈ log_(1+f) n + (ln n)/f. Push-pull-এ শেষ পর্যায় আরও নাটকীয়: অজানা সদস্য নিজে কাউকে জিজ্ঞেস করে, আর সেই সঙ্গীও অজানা হওয়ার সম্ভাবনা s, ফলে s → s² — প্রতি রাউন্ডে অজানা অংশ বর্গ হয়ে কমে। Karp ও সহকর্মীদের ২০০০ সালের একটি গবেষণা দেখায়, push-pull-এ O(log n) রাউন্ডে মোট মাত্র O(n log log n) বার্তায় খবর সবার কাছে পৌঁছানো যায়।

এবার simulator-এ মিলিয়ে দেখুন — ১০০, ১,০০০ আর ১০,০০০ সদস্য, fanout ১ ও ৩, প্রতিটি পাঁচবার চালিয়ে গড়:

// Push gossip: each round every informed node tells `f` random others.
// theory (push, fanout f): log_(f+1)(n) + ln(n)/f rounds; f = 1 gives log2(n) + ln(n)
let seed = 44; function rand() {   // mulberry32: seeded PRNG, same output every run
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
function spread(n, f) {              // returns [rounds until all know, total messages]
  const know = new Uint8Array(n); know[0] = 1;
  let informed = 1, rounds = 0, msgs = 0;
  while (informed < n) {
    rounds++;
    const senders = [];
    for (let i = 0; i < n; i++) if (know[i]) senders.push(i);
    for (const s of senders) for (let j = 0; j < f; j++) {
      let t = Math.floor(rand() * (n - 1)); if (t >= s) t++;   // anyone except self
      msgs++; if (!know[t]) { know[t] = 1; informed++; }
    }
  }
  return [rounds, msgs];
}
console.log("     n  f  rounds(avg of 5)  log2(n)  theory  msgs/node");
for (const n of [100, 1000, 10000]) for (const f of [1, 3]) {
  let r = 0, m = 0;
  for (let trial = 0; trial < 5; trial++) { const [a, b] = spread(n, f); r += a; m += b; }
  const l2 = Math.log2(n), th = Math.log(n) / Math.log(f + 1) + Math.log(n) / f;
  console.log(String(n).padStart(6) + "  " + f + "  " + (r / 5).toFixed(1).padStart(15) +
    "  " + l2.toFixed(1).padStart(7) + "  " + th.toFixed(1).padStart(6) +
    "  " + (m / 5 / n).toFixed(1).padStart(9));
}

     n  f  rounds(avg of 5)  log2(n)  theory  msgs/node
   100  1             12.2      6.6    11.2        5.5
   100  3              5.4      6.6     4.9        5.8
  1000  1             17.4     10.0    16.9        7.4
  1000  3              8.4     10.0     7.3        9.6
 10000  1             22.2     13.3    22.5        8.8
 10000  3             10.8     13.3     9.7       11.9

Rumor mongering বনাম anti-entropy

সাধারণ নকশায় দুটিই থাকে: দ্রুত খবরে rumor mongering, নিরাপত্তা-জাল হিসেবে ধীর anti-entropy. ফল eventual consistency (পর্ব ৪০): বদল থামলে সবার তালিকা মিলে যায়।

৭ · Gossip-ভিত্তিক membership — heartbeat counter-এর তালিকা মেলানো

Gossip দিয়ে failure detection কীভাবে? ১৯৯৮ সালে Robbert van Renesse, Yaron Minsky আর Mark Hayden একটি সহজ নকশা প্রকাশ করেন। প্রত্যেক সদস্য একটি তালিকা রাখে: প্রতিটি সদস্যের একটি heartbeat counter, আর নিজের ঘড়িতে শেষ কখন সেটি বেড়েছিল। নিয়ম চারটি:

1. প্রতি gossip interval-এ নিজের counter এক বাড়ানো, তারপর পুরো তালিকা এলোমেলো একজনকে পাঠানো।
2. কারও তালিকা এলে প্রতিটি সদস্যের জন্য বড় counter-টি রাখা; বাড়লে নিজের ঘড়ির সময় লিখে রাখা।
3. কারও counter T_fail সময় ধরে না বাড়লে তাকে failed চিহ্নিত করা।
4. আরও কিছুক্ষণ, T_cleanup পর্যন্ত, failed entry রেখে দেওয়া, তারপর মুছে ফেলা।

খেয়াল করুন, কেউ কাউকে সরাসরি ping করে না। একজনের counter বাড়ার খবর gossip-এ ছড়ায়; থেমে যাওয়া counter-ই মৃত্যুর চিহ্ন। আর “বড়টি রাখা” নিয়মটি ক্রম-নিরপেক্ষ ও পুনরাবৃত্তি-নিরাপদ — একই তালিকা দুবার এলে বা উল্টো ক্রমে এলেও ফল এক। পর্ব ৪৬-এ দেখবেন, এই ধর্মগুলোই CRDT-র ভিত্তি। নিচে A-এর চোখে তালিকা দেখুন; T_fail = ১০ s, T_cleanup = ২০ s, আর প্রত্যেকে প্রতি সেকেন্ডে নিজের counter এক বাড়ায়।

এই নকশার দুটি দুর্বলতা আছে। প্রথমত, ধরার সময় n-এর সাথে বাড়ে: counter বাড়ার খবর সবার কাছে পৌঁছাতেই O(log n) রাউন্ড লাগে, তাই T_fail-কেও সেই অনুপাতে বড় রাখতে হয়। দ্বিতীয়ত, বার্তার আকার O(n): প্রতিটি gossip-এ পুরো তালিকা যায়, তাই cluster-জুড়ে প্রতি রাউন্ডে বাইট O(n²)। বাস্তবে তাই শুধু বদল বা digest পাঠানো হয়।

প্রকাশিত নকশা অনুযায়ী Amazon-এর Dynamo (২০০৭) gossip দিয়ে membership আর ring-এর মালিকানার খবর ছড়াত, আর বিচ্ছিন্ন দলগুলো যাতে চিরকাল আলাদা না থাকে সেজন্য কয়েকটি পরিচিত seed node রাখত। Cassandra-র ডকুমেন্টেশন অনুযায়ী তার gossip প্রতি সেকেন্ডে সর্বোচ্চ তিনজনের সাথে অবস্থা বিনিময় করে, entry-তে generation আর version রাখে, আর মৃত্যু বিচার করে phi accrual দিয়ে। Redis Cluster-ও নিজের cluster bus-এ gossip-ধাঁচে ping-pong বিনিময় করে (পর্ব ৩০); সংস্করণভেদে বিবরণ বদলায়।

৮ · SWIM — ping, ping-req, সন্দেহ আর incarnation

২০০২ সালে Cornell-এর Abhinandan Das, Indranil Gupta আর Ashish Motivala প্রকাশ করেন SWIM (Scalable Weakly-consistent Infection-style process group Membership). এর মূল চিন্তা: failure detection আর dissemination আলাদা করা, আর দুটিকেই প্রতি সদস্যের জন্য n-নিরপেক্ষ খরচে চালানো।

Failure detection. প্রতিটি protocol period-এ (ধরা যাক ১ s) সদস্য M_i একজন সদস্য M_j বাছে আর তাকে ping পাঠায়। একটি ছোট timeout-এর (round-trip সময়ের ভিত্তিতে, period-এর চেয়ে অনেক কম) মধ্যে ack না এলে M_i এলোমেলো k জন সদস্যকে ping-req(Mj) পাঠায়, অর্থাৎ অনুরোধ করে যেন তারা M_j-কে ping করে ফল জানায়। তারা M_j-কে ping করে, আর ack পেলে M_i-কে ফেরত পাঠায়। Period শেষেও কোনো ack না এলে M_i সিদ্ধান্ত নেয়। এটিই indirect probe.

লক্ষ্য বাছাই. মূল paper দেখায়, প্রতি period-এ এলোমেলো লক্ষ্য বাছলে একটি crash প্রথমবার কারও চোখে পড়ার প্রত্যাশিত সময় প্রায় e/(e − 1) ≈ ১.৫৮ period — n যত বড়ই হোক। তবে এলোমেলো বাছাইয়ে কেউ অনেকক্ষণ বাদ পড়তে পারে; তাই paper-এর উন্নত রূপে তালিকা এলোমেলো সাজিয়ে round-robin-এ ping করা হয়, ফলে সবচেয়ে খারাপ ক্ষেত্রেও 2n − 1 period-এর মধ্যে ধরা পড়ে।

Suspicion আর incarnation — সঙ্গে সঙ্গে মৃত নয়

মূল SWIM-এর একটি বাড়তি অংশ ভুল সন্দেহকে আরও কমায়। ping-req-ও ব্যর্থ হলে M_i সরাসরি “মৃত” না বলে M_j-কে suspect চিহ্নিত করে, আর সেই খবর ছড়ায়। Suspect সদস্য তখনো তালিকায় থাকে। নির্দিষ্ট suspicion timeout-এর মধ্যে খণ্ডন না এলে তবেই “confirm” — মৃত। খণ্ডন করতে পারে শুধু M_j নিজে: নিজের সম্পর্কে সন্দেহ শুনলে সে নিজের incarnation number বাড়িয়ে ঘোষণা দেয় “আমি বেঁচে আছি, #৫”. নিয়মগুলো (একই সদস্য M_j-এর বার্তার মধ্যে):

• alive #x আগের suspect #y বা alive #y-কে বাতিল করে, যদি x > y.
• suspect #x আগের suspect #y-কে বাতিল করে, যদি x > y; আর alive #y-কে, যদি x ≥ y — সমান নম্বরে সন্দেহ জেতে।
• confirm (মৃত) সব কিছুকে বাতিল করে; incarnation নম্বর বাড়াতে পারে শুধু সদস্যটি নিজে।

Dissemination — ping-এর পিঠে চড়ে. SWIM join, leave, suspect, alive, confirm-এর খবর আলাদা বার্তায় পাঠায় না; প্রতিটি ping, ping-req আর ack-এর ভেতরে সাম্প্রতিক কয়েকটি বদল জুড়ে দেয় — একে বলে piggybacking. প্রতিটি বদল প্রায় λ log n বার পিঠে চড়ে, তারপর বাদ পড়ে; যেহেতু প্রতি period-এ প্রত্যেকে কাউকে ping করছেই, খবর gossip-এর মতো O(log n) period-এ ছড়ায়, বাড়তি বার্তা ছাড়াই।

এবার সংখ্যায় দেখি ping-req কতটা কাজের। ধরে নিচ্ছি M_j জীবিত, প্রতিটি বার্তা স্বাধীনভাবে p সম্ভাবনায় হারায়। সরাসরি পথে দুটি বার্তা (ping, ack), আর প্রতিটি পরোক্ষ পথে চারটি (ping-req, ping, ack, ack). তাই একটি ভুল সন্দেহের সম্ভাবনা

// SWIM probe of an ALIVE member M_j: every message is lost with probability p.
let seed = 2002; function rand() {   // mulberry32: seeded PRNG
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
const ok = p => rand() >= p;         // one message arrives?
function probe(p, k) {               // true = M_i wrongly suspects M_j
  if (ok(p) && ok(p)) return false;  // ping -> M_j, ack -> M_i
  for (let i = 0; i < k; i++)        // ping-req via helper i: 4 messages in a row
    if (ok(p) && ok(p) && ok(p) && ok(p)) return false;
  return true;
}
const N = 200000;
console.log("loss   k  simulated  formula   (false suspicions per probe)");
for (const p of [0.05, 0.20]) for (const k of [0, 3]) {
  let bad = 0; for (let i = 0; i < N; i++) if (probe(p, k)) bad++;
  const f = (1 - (1 - p) ** 2) * (1 - (1 - p) ** 4) ** k;
  console.log((p * 100 + "%").padEnd(5) + "  " + k + "  " + (100 * bad / N).toFixed(3).padStart(8) +
    "%  " + (100 * f).toFixed(3).padStart(6) + "%");
}

loss   k  simulated  formula   (false suspicions per probe)
5%     0     9.736%   9.750%
5%     3     0.060%   0.062%
20%    0    36.008%  36.000%
20%    3     7.428%   7.409%

খরচের তুলনা — all-to-all, gossip আর SWIM

শেষে তিন নকশার খরচ পাশাপাশি। ধরা যাক প্রতি সেকেন্ডে একটি রাউন্ড; প্রতিটি বার্তার header ৬০ byte আর প্রতিটি সদস্যের entry ৪০ byte; gossip প্রতি রাউন্ডে পুরো তালিকা একজনকে পাঠায়; SWIM-এর প্রতিটি বার্তায় সর্বোচ্চ ৬টি বদল piggyback হয়, আর loss-এর বাড়তি ping-req এখানে ধরা হয়নি।

// Messages and bytes per second for failure detection, one round per second.
// Assumed sizes: header 60 B, one member entry 40 B,
// gossip sends the full list to f = 1 peer, SWIM piggybacks up to 6 updates.
const H = 60, E = 40;
const fmt = x => x >= 1e6 ? (x / 1e6).toFixed(1) + " M" : x >= 1e3 ? (x / 1e3).toFixed(1) + " K" : x.toFixed(0) + "  ";
console.log("    n  scheme                 msgs/s  per node   bytes/s");
for (const n of [10, 100, 1000]) {
  const rows = [
    ["all-to-all heartbeat", n * (n - 1), H + E],
    ["gossip (full list)", n * 1, H + E * n],
    ["SWIM ping+ack", n * 2, H + E * 6],
  ];
  for (const [name, msgs, size] of rows)
    console.log(String(n).padStart(5) + "  " + name.padEnd(21) + fmt(msgs).padStart(8) +
      String((msgs / n).toFixed(0)).padStart(9) + "  " + fmt(msgs * size).padStart(8));
}

    n  scheme                 msgs/s  per node   bytes/s
   10  all-to-all heartbeat     90          9     9.0 K
   10  gossip (full list)       10          1     4.6 K
   10  SWIM ping+ack            20          2     6.0 K
  100  all-to-all heartbeat    9.9 K       99   990.0 K
  100  gossip (full list)      100          1   406.0 K
  100  SWIM ping+ack           200          2    60.0 K
 1000  all-to-all heartbeat  999.0 K      999    99.9 M
 1000  gossip (full list)      1.0 K        1    40.1 M
 1000  SWIM ping+ack           2.0 K        2   600.0 K

Lifeguard — নিজের অসুস্থতাও টের পাওয়া

HashiCorp-এর open-source Go library memberlist SWIM-এর একটি বহুল ব্যবহৃত রূপ; প্রকাশিত ডকুমেন্টেশন অনুযায়ী Consul, Serf আর Nomad এর ওপর দাঁড়ানো। বাস্তবে তাঁরা দেখেন, অনেক false positive-এর উৎস পর্যবেক্ষক নিজে: M_i-এর CPU ব্যস্ত, তাই সে ack সময়মতো পড়তে না পেরে অন্যদের সন্দেহ করে। ২০১৭–১৮ সালের দিকে প্রকাশিত তাঁদের Lifeguard নামের উন্নয়নে তিনটি ধারণা:

• নিজের স্বাস্থ্য মাপা: নিজের probe বারবার ব্যর্থ হলে বা নিজের সম্পর্কে সন্দেহ শুনলে সদস্যটি নিজের timeout বাড়ায়।
• বদলানো suspicion timeout: শুরু লম্বা timeout দিয়ে; অন্য স্বাধীন সদস্যরাও একই সন্দেহ জানালে তা ছোট হয় — একজনের সন্দেহে ধীরে, অনেকের সন্দেহে দ্রুত।
• সন্দেহভাজনকে সরাসরি জানানো: suspect সদস্যের ping-এই সন্দেহের খবর জুড়ে দেওয়া, যাতে সে দ্রুত খণ্ডন করে।

memberlist মাঝে মাঝে TCP-তে দুই সদস্যের পূর্ণ অবস্থাও মিলিয়ে নেয় — piggyback-এর সাথে anti-entropy-র নিরাপত্তা-জাল। বিবরণ সংস্করণভেদে আলাদা।

৯ · Split brain, membership ≠ consensus আর বাস্তবের knob

ধরুন ৫টি সদস্যের cluster: A, B, C এক switch-এর নিচে, D, E আরেকটির নিচে, আর মাঝের link কেটে গেল — network partition. SWIM বা gossip দুই পাশেই ঠিকঠাক কাজ করবে: {A, B, C} বলবে D, E মৃত; {D, E} বলবে A, B, C মৃত। দুই পাশের তালিকাই নিজের চোখে সঠিক. এখন প্রত্যেক পাশ যদি নিজের তালিকা দেখে একজন leader বানায়, বা মৃতদের shard নিজের নামে লিখে নেয় — একই shard-এর দুজন মালিক, দুই দিকে আলাদা লেখা। এটাই split brain.

বাস্তবের নকশাও এই ভাগ মানে। প্রকাশিত ডকুমেন্টেশন অনুযায়ী Consul-এ সব agent gossip-এ (memberlist) membership আর স্বাস্থ্যের খবর ছড়ায়, কিন্তু service catalog-এর মতো সিদ্ধান্ত রাখে কয়েকটি server-এর Raft cluster. Redis Cluster-এ একজন node কাউকে সাড়া না পেলে শুধু নিজের কাছে “সম্ভবত বিকল” (PFAIL) চিহ্ন দেয়; master-দের majority একমত হলে তবেই FAIL, তারপর failover. Elasticsearch-এর পুরোনো সংস্করণে master-এর ন্যূনতম সংখ্যা হাতে ঠিক করতে হতো, আর ভুল মানে split brain; ডকুমেন্টেশন অনুযায়ী সংস্করণ ৭ থেকে cluster নিজেই quorum সামলায়।

বাস্তবের knob — কোনটি বাড়ালে কী হয়

১০ · AI-এর যুগে — membership নকশা যাচাই

Failure detection-এর নকশা চাইলে AI প্রায়ই চটপটে উত্তর দেয়: “প্রতি ১০০ ms-এ heartbeat, একটি মিস হলেই node বাদ, আর Redis-এ সবার তালিকা।” এক নজরে তিনটি সমস্যা: একটি মিসেই বাদ মানে flapping; সবাই সবাইকে মানে n বাড়লে বিস্ফোরণ; আর Redis-এর নিজের বিকলতা কে দেখবে? খসড়া AI দেয়, failure mode আর সংখ্যা যাচাই আপনার।

AI-এর membership নকশা হাতে পেলে — যাচাইয়ের চেকলিস্ট

• বার্তার সংখ্যা আর বাইট নিজে হিসাব করেছি — n(n − 1), 2n, বা বার্তার আকার × সংখ্যা
• ধরার সময় আর false positive দুটিই সংখ্যায় দেখেছি, ছোট একটি simulation বা মাপা heartbeat-ফাঁক দিয়ে
• GC pause, এক পথের loss, পর্যবেক্ষকের নিজের ব্যস্ততা আর partition — চারটি failure mode-এ নকশাটি কী করে, লিখে দেখেছি
• “বিকল” ঘোষণার পর কী ঘটে (ডেটা সরানো, failover) আর তা কতটা দামি — সেই অনুযায়ী detector-এর সাবধানতা বেছেছি
• Leader বা মালিক ঠিক করার জায়গায় consensus বা fencing আছে; শুধু membership-এর তালিকার ওপর নির্ভর করিনি
• AI-এর বলা পণ্যের ডিফল্ট মান অফিসিয়াল ডকুমেন্টেশনে মিলিয়েছি