Distributed system-এর OS-দিক — RPC, clock আর distributed file system

১ · কেন একাধিক কম্পিউটার, আর কেন তা কঠিন

আপনি bKash বা ব্যাংকের অ্যাপে টাকা পাঠালেন। স্ক্রিনে ঘুরছে “অপেক্ষা করুন…”, তারপর লেখা এলো “Request timed out”. টাকা কি গেছে? আপনি জানেন না। অ্যাপও নিশ্চিত জানে না। আবার চাপলে কি দুবার কাটবে? এই একটি প্রশ্নের ভেতরেই পুরো distributed system-এর কঠিনতা লুকিয়ে আছে।

এ পর্যন্ত কোর্সে আমরা একটি কম্পিউটারের OS দেখেছি। সেখানে প্রসেসগুলো একই RAM, একই ঘড়ি আর একই kernel ভাগ করে। একটি distributed system হলো নেটওয়ার্কে যুক্ত অনেকগুলো স্বাধীন কম্পিউটার, যারা শুধু বার্তা পাঠিয়ে একসাথে কাজ করে। কেন এমন করা হয়?

দাম কী? এক কম্পিউটারে যা বিনামূল্যে পাওয়া যেত, এখানে সেগুলো আর নেই:

• Shared memory নেই। পর্ব ১২-এর shared memory বা পর্ব ২৪-এর mutex একটি RAM-এর ওপর দাঁড়ানো। এখানে আছে শুধু message passing — আর বার্তা দেরিতে আসতে পারে, হারাতে পারে, দুবার আসতে পারে।
• সবার জন্য এক ঘড়ি নেই। প্রতিটি যন্ত্রের নিজের ঘড়ি, আর সেগুলো আলাদা গতিতে চলে। “কোনটি আগে ঘটেছে” প্রশ্নের উত্তর দিতে আলাদা কৌশল লাগে (অংশ ৫ ও ৬)।
• ব্যর্থতা আংশিক। এক কম্পিউটার crash করলে সব একসাথে থামে। এখানে একটি যন্ত্র মরে, বাকিরা চলে। আর বাইরে থেকে “মৃত”, “খুব ধীর” আর “নেটওয়ার্ক কাটা” — তিনটি দেখতে হুবহু এক: উত্তর আসছে না। একেই বলে partial failure.

Distributed computing-এর আটটি ভ্রান্তি

১৯৯০-এর দশকে Sun Microsystems-এ L Peter Deutsch ও সহকর্মীরা কয়েকটি ভুল অনুমানের তালিকা করেন, যা নতুন distributed প্রোগ্রামাররা প্রায় সবাই করেন; প্রচলিত বর্ণনা অনুযায়ী অষ্টমটি পরে James Gosling যোগ করেন (তালিকার ইতিহাসের খুঁটিনাটি সূত্রভেদে একটু আলাদা)। একে বলা হয় fallacies of distributed computing:

২ · Network OS, distributed OS আর middleware

অনেক যন্ত্রকে একসাথে চালানোর দায়িত্ব কে নেবে — OS নিজে, নাকি OS-এর ওপরের একটি স্তর? ইতিহাসে তিনটি উত্তর এসেছে:

এগুলোর কোনোটিই ব্যাপক বাজার পায়নি — সাধারণ Unix/Linux আর Windows-এর ওপর middleware-ই জিতেছে (ভাবনার প্রশ্ন ৫-এ কারণ)। কিন্তু ধারণাগুলো বেঁচে আছে: Linux-এর per-process mount namespace (পর্ব ৫১-এর container-এর ভিত্তি) Plan 9-এর namespace থেকে অনুপ্রাণিত, আর 9P আজও Linux kernel-এ (v9fs) আছে; WSL-এ Windows থেকে Linux-এর ফাইল খোলার পথেও 9P ব্যবহার হয় বলে Microsoft জানিয়েছে। আজকের Kubernetes-কে অনেকে “ডেটা সেন্টারের OS” বলেন — কাজের ধরনে এটি middleware, কিন্তু scheduling, resource limit আর service discovery-র মতো OS-এর দায়িত্বই পালন করে।

৩ · RPC — দূরের ফাংশনকে কাছের মতো ডাকা

পর্ব ১২-এ (IPC — socket) দেখেছেন, দুই প্রসেস socket দিয়ে বাইট পাঠাতে পারে, আর একটি TCP socket একই কোড দিয়ে অন্য মেশিনেও পৌঁছায়। কিন্তু প্রতিটি অনুরোধের জন্য নিজে বাইট সাজানো, পাঠানো, উত্তর খোলা — এটি ক্লান্তিকর আর ভুলপ্রবণ। ১৯৮৪ সালে Andrew Birrell আর Bruce Nelson-এর বিখ্যাত গবেষণাপত্র এর একটি পরিচ্ছন্ন রূপ দেয়: remote procedure call. প্রোগ্রামার লেখেন balance = deposit(acct, 500); — যেন সাধারণ ফাংশন। ভেতরে কী হয়, ধাপে ধাপে দেখুন:

xid  = 00 00 00 29      ; request id 41
proc = DEPOSIT (v1)
acct = 00 00 04 b7      ; 1207
amt  = 00 00 01 f4      ; 500

reply xid = 41, status = OK, balance = 1500
; client প্রোগ্রাম দেখে: balance = 1500

Stub হাতে লিখতে হয় না। প্রোগ্রামার একটি interface definition language (IDL)-এ ফাংশনের নাম আর argument-এর ধরন লেখেন, আর একটি টুল দুই দিকের stub তৈরি করে — ONC RPC-তে rpcgen, gRPC-তে Protocol Buffers-এর .proto ফাইল থেকে protoc.

Binding — server কোথায়?

Client-কে জানতে হবে কোন মেশিনের কোন port-এ server শুনছে। এই খোঁজার নাম binding. ONC RPC-তে প্রতিটি মেশিনে একটি rpcbind (পুরোনো নাম portmapper) port 111-এ বসে থাকে; server চালু হয়ে সেখানে নাম লেখায়, client আগে তাকে জিজ্ঞেস করে। Microsoft RPC-তে (DCE RPC থেকে আসা) একই কাজ করে endpoint mapper (port 135). আধুনিক microservice-এ binding সাধারণত DNS বা Kubernetes-এর service নামের মাধ্যমে হয়।

৪ · RPC যখন ব্যর্থ হয় — semantics, idempotency আর retry

স্থানীয় ফাংশন হয় ফেরে, নয় পুরো প্রোগ্রাম crash করে। RPC-তে মাঝামাঝি অনেক অবস্থা আছে। Client শুধু দেখে “নির্দিষ্ট সময়ে (timeout) উত্তর আসেনি” — কিন্তু কারণ পাঁচরকম হতে পারে:

আরেকটি ঘটনা উল্টো দিকের: client নিজে crash করলে server-এ তার পাঠানো কাজ চলতেই থাকে, কেউ ফলের অপেক্ষায় নেই — একে বলে orphan. এই অনিশ্চয়তার মুখে RPC system তিনটি প্রতিশ্রুতির একটি দেয়:

নিচের C প্রোগ্রামে parent হলো client, child হলো ব্যাংকের server, আর মাঝে একটি socketpair নেটওয়ার্কের ভূমিকায়। Server প্রথম উত্তরটি ইচ্ছা করে “হারিয়ে” ফেলে। Client ১০০ ms অপেক্ষা করে (poll), উত্তর না পেলে একই request id দিয়ে আবার পাঠায়। একবার চলে সরল (naive) server, একবার duplicate-চেনা server:

#include <stdio.h>
#include <poll.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/wait.h>
#define SZ(x) ((ssize_t)sizeof(x))
typedef struct { int id, val; } Msg;   /* request: id + deposit amount; reply: id + balance */
static void server(int fd, int dedup) {
    int balance = 1000, dropped = 0; Msg q, last = {-1, 0};
    while (read(fd, &q, sizeof q) == SZ(q)) {
        if (!(dedup && q.id == last.id)) {           /* new request (or naive): execute */
            balance += q.val; last.id = q.id; last.val = balance;
            if (!dropped) { dropped = 1; continue; }  /* first reply is "lost" */
        }                                            /* a duplicate gets the saved reply */
        if (write(fd, &last, sizeof last) != SZ(last)) break;
    }
}
static void client(int fd, const char *mode) {
    Msg q = {1, 500}, r; struct pollfd p = {fd, POLLIN, 0};   /* id 1: deposit 500 */
    for (int attempt = 1; attempt <= 3; attempt++) {
        if (write(fd, &q, sizeof q) != SZ(q)) return;
        if (poll(&p, 1, 100) > 0 && read(fd, &r, sizeof r) == SZ(r)) {
            printf("%s attempt %d: reply id=%d balance=%d\n", mode, attempt, r.id, r.val); return;
        }
        printf("%s attempt %d: no reply in 100 ms, resend id=%d\n", mode, attempt, q.id);
    }
}
int main(void) {
    for (int dedup = 0; dedup <= 1; dedup++) {
        int sv[2]; if (socketpair(AF_UNIX, SOCK_STREAM, 0, sv) == -1) return 1;
        fflush(stdout);                              /* empty the stdio buffer before fork */
        if (fork() == 0) { close(sv[0]); server(sv[1], dedup); _exit(0); }
        close(sv[1]); client(sv[0], dedup ? "dedup:" : "naive:"); close(sv[0]); wait(NULL);
    }
}

naive: attempt 1: no reply in 100 ms, resend id=1
naive: attempt 2: reply id=1 balance=2000
dedup: attempt 1: no reply in 100 ms, resend id=1
dedup: attempt 2: reply id=1 balance=1500

Timeout আর retry-এর নিয়ম

• প্রতিটি কলে সময়সীমা। Timeout ছাড়া একটি মৃত server-এর অপেক্ষায় থ্রেড চিরকাল আটকে থাকে। gRPC প্রতিটি কলে deadline দিতে বলে, আর সেটি পরের সার্ভিসেও বয়ে নেয়।
• সময় মাপুন monotonic ঘড়িতে। Timeout হিসাব CLOCK_REALTIME-এ করলে NTP ঘড়ি পিছিয়ে দিলে timeout লম্বা বা ছোট হয়ে যায়। Linux-এ CLOCK_MONOTONIC (Windows-এ QueryPerformanceCounter) কখনো পেছায় না — অংশ ৫-এ কারণ।
• Retry-তে exponential backoff আর jitter. সবাই একসাথে সাথে সাথে retry করলে সদ্য-জাগা server আবার ডুবে যায়। অপেক্ষা ১০০, ২০০, ৪০০ ms… আর একটু এলোমেলো।
• শুধু idempotent বা key-যুক্ত কাজে retry. বাকিগুলোতে retry-র আগে জিজ্ঞেস করা: “id ৪১-এর কী অবস্থা?”

৫ · Physical clock — drift, Cristian, NTP আর Berkeley

প্রতিটি কম্পিউটারে একটি কোয়ার্টজ স্ফটিক নির্দিষ্ট হারে কাঁপে, আর হার্ডওয়্যার timer সেই কাঁপন গুনে OS-কে সময় দেয় (পর্ব ৪)। কিন্তু দুটি স্ফটিক হুবহু এক হারে কাঁপে না, তাপমাত্রায় হার বদলায়। ফলে ঘড়ি ধীরে ধীরে সরে যায় — একে বলে clock drift. কোনো মুহূর্তে দুটি ঘড়ির দেখানো সময়ের পার্থক্য হলো clock skew. মানদণ্ড হলো UTC, যা পারমাণবিক ঘড়ি থেকে আসে।

Numerical — কত ঘন ঘন মেলাতে হবে

ধরুন নির্মাতা বলেছেন সর্বোচ্চ drift rate ρ = ১০^−৬ (প্রতি সেকেন্ডে সর্বোচ্চ ১ µs ভুল; সাধারণ কোয়ার্টজ এর কাছাকাছি থেকে কয়েক গুণ খারাপ পর্যন্ত হয়)।

• এক দিনে: ৮৬,৪০০ s × ১০^−৬ = ০.০৮৬৪ s ≈ ৮৬.৪ ms.
• দুটি ঘড়ি: সবচেয়ে খারাপ অবস্থায় একটি দ্রুত, অন্যটি ধীর চলে — Δt সময়ে পার্থক্য বাড়ে ২ρΔt পর্যন্ত। পার্থক্য δ-এর মধ্যে রাখতে ২ρΔt ≤ δ, অর্থাৎ Δt ≤ δ/(২ρ).
• δ = ১ ms হলে: ১০^−৩/(২ × ১০^−৬) = ৫০০ s — প্রায় সোয়া আট মিনিট পরপর মেলাতে হবে। শুধু UTC থেকে δ-এর মধ্যে রাখতে চাইলে δ/ρ = ১,০০০ s.

Cristian-এর algorithm — RTT-এর অর্ধেক যোগ

১৯৮৯ সালে Flaviu Cristian সহজ একটি পথ দেন: একটি time server-কে সময় জিজ্ঞেস করা। সমস্যা হলো, উত্তর আসতে আসতে সময় আরও এগিয়ে গেছে। সমাধান — যাওয়া-আসার সময় (round-trip time, RTT) মেপে তার অর্ধেক যোগ করা। ধাপে ধাপে:

1 T0 = client clock; send "time?"2 server reads Ts, sends it back3 T1 = client clock on arrival4 estimate = Ts + (T1 - T0) / 25 adjust; error <= (T1-T0)/2 - min

NTP — চারটি timestamp, দুটি সূত্র

David Mills (University of Delaware)-এর Network Time Protocol ১৯৮৫ সাল থেকে ইন্টারনেটের ঘড়ি মেলাচ্ছে। Server-গুলো স্তরে সাজানো (stratum ০ = পারমাণবিক বা GPS ঘড়ি, stratum ১ = তার সাথে সরাসরি যুক্ত server…)। NTP যাওয়া আর আসার সময় সমান ধরে না, চারটি timestamp নেয়: t₁ client পাঠাল, t₂ server পেল, t₃ server পাঠাল, t₄ client পেল (t₁, t₄ client-এর ঘড়িতে; t₂, t₃ server-এর)।

Numerical: client আসলে server থেকে ৫০ ms পিছিয়ে; যেতে ১০ ms, server-এ ২ ms কাজ, ফিরতে ১৪ ms. চারটি timestamp: t₁ = ১০০০, t₂ = ১০৬০, t₃ = ১০৬২, t₄ = ১০২৬ (ms). তাহলে θ = ((১০৬০ − ১০০০) + (১০৬২ − ১০২৬))/২ = (৬০ + ৩৬)/২ = ৪৮ ms, আর δ = (১০২৬ − ১০০০) − (১০৬২ − ১০৬০) = ২৬ − ২ = ২৪ ms. আসল offset ৫০, অনুমান ৪৮ — ২ ms ভুল এসেছে যাওয়া-আসার অসমতা থেকে: (১৪ − ১০)/২ = ২. অসমতা মাপা অসম্ভব, তাই NTP-র ভুলের সীমা δ/২. ইন্টারনেটে সাধারণত কয়েক থেকে কয়েক দশ মিলিসেকেন্ড, ভালো LAN-এ এক মিলিসেকেন্ডের নিচে নির্ভুলতা পাওয়া যায়; আরও সূক্ষ্ম কাজে হার্ডওয়্যার timestamp-যুক্ত PTP (IEEE 1588) ব্যবহার হয়।

$ timedatectl                 # Linux (systemd): NTP চালু কি না, ঘড়ি মেলানো কি না
$ chronyc tracking            # chrony থাকলে: offset, frequency (ppm) ইত্যাদি
PS> w32tm /query /status      # Windows-এর Windows Time সার্ভিস

OS ভেদে ব্যবস্থা আলাদা: অনেক Linux ডিস্ট্রো chrony বা systemd-timesyncd চালায়, Windows-এ W32Time সার্ভিস, macOS-এ নিজস্ব timed ডেমন।

Berkeley algorithm — কারও ঘড়ি ঠিক না হলে গড়

যেখানে কোনো UTC উৎস নেই, সেখানে উদ্দেশ্য সবার ঘড়ি একে অপরের সাথে মেলানো। Gusella আর Zatti-র (১৯৮০-এর দশকের শেষে, Berkeley Unix-এর জন্য) পদ্ধতিতে একজন master সবাইকে জিজ্ঞেস করে (RTT সংশোধনসহ), গড় বের করে, আর প্রত্যেককে কতটুকু সরাতে হবে তা পাঠায় — সময় নয়, পার্থক্য পাঠানো হয়, যাতে পথের দেরি ফলকে বিকৃত না করে।

উদাহরণ: master-এর সাপেক্ষে A +১২ s, B −৯ s, C +৪৫ s. সীমা ২০ s ধরলে C স্পষ্টতই গোলমেলে, তাই গড় থেকে বাদ: (০ + ১২ − ৯)/৩ = +১ s. নির্দেশ: master +১, A −১১, B +১০, আর C −৪৪ (C-ও সংশোধন পায়, শুধু গড়ে ভোট দেয় না)। যাদের পেছাতে হবে (A, C), তারা slew করে।

৬ · Logical clock — সময় নয়, ক্রম

অনেক কাজে আসল সময় দরকারই নেই — দরকার শুধু ক্রম: কোন আপডেট আগে, কোনটি পরে। ১৯৭৮ সালে Leslie Lamport-এর “Time, Clocks, and the Ordering of Events in a Distributed System” প্রবন্ধ দেখায়, বার্তা দিয়েই একটি সুসংগত ক্রম তৈরি করা যায়। প্রথমে সম্পর্কটি — happened-before (→):

1. একই প্রসেসে a আগে, b পরে ঘটলে a → b.
2. a যদি একটি বার্তা পাঠানো আর b সেই বার্তা পাওয়া হয়, তাহলে a → b.
3. a → b আর b → c হলে a → c (transitive).

a → b-ও নয়, b → a-ও নয় — এমন দুটি ঘটনা concurrent (a ∥ b): কেউ কারও খবর জানত না। খেয়াল করুন, এই “→” পর্ব ২৩-এর memory model-এর happens-before-এর পূর্বসূরি — সেখানেও একই চিন্তা, থ্রেড আর মেমরির জন্য।

Lamport-এর নিয়ম

প্রতিটি প্রসেস একটি পূর্ণসংখ্যা counter C রাখে, শুরু ০:

• নিয়ম ১: প্রতিটি ঘটনার (local বা send) আগে C = C + ১; ঘটনাটির timestamp L = C.
• নিয়ম ২: বার্তা পাঠানোর সময় বার্তার সাথে C পাঠানো।
• নিয়ম ৩: timestamp t-সহ বার্তা পেলে C = max(C, t) + ১.

// Lamport clocks: 3 processes, events listed in one possible real-time order.
// [process, event, kind, message]   kind: L = local, S = send, R = receive
const script = [
  ["P1","a","L"], ["P3","h","L"], ["P1","b","S","m1"], ["P3","i","L"],
  ["P2","e","R","m1"], ["P3","j","L"], ["P2","f","S","m2"], ["P1","c","L"],
  ["P3","k","R","m2"], ["P2","g","L"], ["P3","l","S","m3"], ["P1","d","R","m3"],
];
const C = { P1: 0, P2: 0, P3: 0 };   // one counter per process
const carried = {};                   // message -> timestamp it carries
const L = {};                         // event -> Lamport timestamp
for (const [p, ev, kind, m] of script) {
  let how;
  if (kind === "R") {                 // rule 3: max(own, message) + 1
    how = "recv " + m + ": max(" + C[p] + ", " + carried[m] + ") + 1";
    C[p] = Math.max(C[p], carried[m]) + 1;
  } else {                            // rules 1 and 2: tick before the event
    C[p] += 1;
    how = kind === "S" ? "send " + m + " carrying " + C[p] : "local";
    if (kind === "S") carried[m] = C[p];
  }
  L[ev] = C[p];
  console.log(p + " " + ev + " = " + C[p] + "   (" + how + ")");
}
// total order: by timestamp, ties broken by process number
const total = script.map(([p, ev]) => [L[ev], +p[1], ev])
  .sort((x, y) => x[0] - y[0] || x[1] - y[1])
  .map(([t, n, ev]) => ev + "(" + t + "." + n + ")");
console.log("Total order: " + total.join(" "));
console.log("c = " + L.c + " < f = " + L.f + ", yet c and f are not causally related");

P1 a = 1   (local)
P3 h = 1   (local)
P1 b = 2   (send m1 carrying 2)
P3 i = 2   (local)
P2 e = 3   (recv m1: max(0, 2) + 1)
P3 j = 3   (local)
P2 f = 4   (send m2 carrying 4)
P1 c = 3   (local)
P3 k = 5   (recv m2: max(3, 4) + 1)
P2 g = 5   (local)
P3 l = 6   (send m3 carrying 6)
P1 d = 7   (recv m3: max(3, 6) + 1)
Total order: a(1.1) h(1.3) b(2.1) i(2.3) c(3.1) e(3.2) j(3.3) f(4.2) g(5.2) k(5.3) l(6.3) d(7.1)
c = 3 < f = 4, yet c and f are not causally related

Vector clock — concurrency চেনা

উল্টো দিকটি জানতে — দুটি ঘটনা আসলে কারণ-সম্পর্কিত কি না — ১৯৮৮ সালে Colin Fidge আর Friedemann Mattern আলাদাভাবে vector clock দেন। n প্রসেস হলে প্রতিটি প্রসেস n সংখ্যার একটি vector V রাখে; V[j] মানে “প্রসেস j-এর কতগুলো ঘটনার খবর আমি জানি”:

• প্রতিটি ঘটনার আগে নিজের ঘর বাড়ানো: V[i] = V[i] + ১.
• পাঠানোর সময় পুরো vector পাঠানো।
• পেলে প্রতিটি ঘরে max নেওয়া, তারপর নিজের ঘর + ১.
• তুলনা: V(a) ≤ V(b) মানে প্রতিটি ঘরে ≤. a → b ⇔ V(a) ≤ V(b) এবং V(a) ≠ V(b); কোনো দিকেই ≤ না হলে a ∥ b.

// Vector clocks on the same 12 events; then compare pairs of events.
const script = [
  ["P1","a","L"], ["P3","h","L"], ["P1","b","S","m1"], ["P3","i","L"],
  ["P2","e","R","m1"], ["P3","j","L"], ["P2","f","S","m2"], ["P1","c","L"],
  ["P3","k","R","m2"], ["P2","g","L"], ["P3","l","S","m3"], ["P1","d","R","m3"],
];
const V = { P1: [0,0,0], P2: [0,0,0], P3: [0,0,0] };
const carried = {}, at = {};
for (const [p, ev, kind, m] of script) {
  const i = +p[1] - 1, v = V[p];
  if (kind === "R") carried[m].forEach((x, j) => { v[j] = Math.max(v[j], x); });
  v[i] += 1;                                   // tick own entry
  if (kind === "S") carried[m] = [...v];       // message carries a copy
  at[ev] = [...v];
  console.log(p + " " + ev + " = [" + v + "]");
}
const leq = (x, y) => x.every((n, j) => n <= y[j]);
function relation(a, b) {
  const x = at[a], y = at[b];
  if (leq(x, y) && x.join() !== y.join()) return a + " -> " + b;
  if (leq(y, x) && x.join() !== y.join()) return b + " -> " + a;
  return a + " || " + b + "  (concurrent)";
}
for (const [a, b] of [["b","k"], ["c","f"], ["e","j"], ["g","l"], ["h","d"], ["c","e"]])
  console.log("[" + at[a] + "] vs [" + at[b] + "]: " + relation(a, b));

P1 a = [1,0,0]
P3 h = [0,0,1]
P1 b = [2,0,0]
P3 i = [0,0,2]
P2 e = [2,1,0]
P3 j = [0,0,3]
P2 f = [2,2,0]
P1 c = [3,0,0]
P3 k = [2,2,4]
P2 g = [2,3,0]
P3 l = [2,2,5]
P1 d = [4,2,5]
[2,0,0] vs [2,2,4]: b -> k
[3,0,0] vs [2,2,0]: c || f  (concurrent)
[2,1,0] vs [0,0,3]: e || j  (concurrent)
[2,3,0] vs [2,2,5]: g || l  (concurrent)
[0,0,1] vs [4,2,5]: h -> d
[3,0,0] vs [2,1,0]: c || e  (concurrent)

৭ · Distributed mutual exclusion আর leader election

পর্ব ২৪-এর mutex একটি মেশিনের atomic instruction-এর ওপর দাঁড়ানো। কয়েকটি মেশিন যদি একটি shared ফাইল বা প্রিন্টার এক এক করে ব্যবহার করতে চায়, তাহলে mutual exclusion বার্তা দিয়েই করতে হবে। তিনটি ক্লাসিক পথ:

• Centralised: একজন coordinator — ব্যাংকের টোকেন-কাউন্টারের মতো। চাইলে REQUEST, ফাঁকা থাকলে GRANT, শেষে RELEASE: প্রতি প্রবেশে ৩টি বার্তা। সহজ ও ন্যায্য (FIFO), কিন্তু coordinator একক বিপদ-বিন্দু, আর তার নীরবতা থেকে বোঝা যায় না “ব্যস্ত” না “মৃত”।
• Ricart–Agrawala (১৯৮১): কোনো coordinator নেই। প্রবেশ করতে চাইলে সবাইকে (n − ১ জন) Lamport timestamp-সহ REQUEST পাঠানো, সবার OK পেলে প্রবেশ। REQUEST পেলে: নিজে আগ্রহী না হলে সাথে সাথে OK; নিজে ভেতরে থাকলে উত্তর জমা; নিজেও অপেক্ষায় থাকলে (timestamp, id) তুলনা — অন্যজনেরটি ছোট হলে OK, নিজেরটি ছোট হলে জমা। বের হয়ে জমা উত্তরগুলো পাঠানো। মোট ২(n − ১) বার্তা।
• Token ring: প্রসেসগুলো একটি যৌক্তিক বৃত্তে; একটিমাত্র token ঘোরে, যার হাতে token সে-ই ঢুকতে পারে — রিলে দৌড়ের ব্যাটনের মতো। প্রতি প্রবেশে ১ থেকে অসীম বার্তা (কেউ না চাইলেও token ঘোরে), অপেক্ষা ০ থেকে n − ১ ধাপ। Token হারালে বা কেউ মরলে নতুন token বানাতে হয় — আর হারানো token আর ধীর token আলাদা করা কঠিন।

Leader election — নতুন coordinator কে?

Centralised mutex, Berkeley-র master, ডেটাবেসের primary — সবখানে একজন নেতা লাগে। নেতা মরলে বাকিদের একমত হয়ে নতুন নেতা বাছতে হয় — leader election. Hector Garcia-Molina-র (১৯৮২) bully algorithm-এ ধরা হয় প্রত্যেকের একটি অনন্য id আছে, বার্তা নির্ভরযোগ্য, আর timeout দিয়ে crash চেনা যায়। নিয়ম একটাই: সবচেয়ে বড় id-ধারী জীবিত প্রসেস নেতা।

// Bully election: P1..P5, coordinator P5 has crashed, P2 notices first.
const N = 5, alive = [false, true, true, true, true, false]; // index 1..5
const starter = 2;
const count = { ELECTION: 0, OK: 0, COORDINATOR: 0 };
function send(type, from, to) {
  count[type]++;
  console.log("  P" + from + " -> P" + to + "  " + type +
    (alive[to] ? "" : "   (no answer: P" + to + " is down)"));
}
const queue = [starter], started = new Set();
let round = 0;
while (queue.length) {
  const p = queue.shift();
  if (started.has(p)) continue;
  started.add(p);
  console.log("Round " + (++round) + ": P" + p + " holds an election");
  let gotOk = false;
  for (let q = p + 1; q <= N; q++) {          // ask every higher id
    send("ELECTION", p, q);
    if (!alive[q]) continue;
    send("OK", q, p);                           // "I am bigger, I take over"
    gotOk = true;
    if (!started.has(q)) queue.push(q);         // q runs its own election
  }
  if (gotOk) { console.log("  P" + p + " got OK, steps aside and waits"); continue; }
  console.log("  P" + p + " timed out waiting for OK -> P" + p + " wins");
  for (let q = 1; q < p; q++) if (alive[q]) send("COORDINATOR", p, q);
  break;
}
const total = count.ELECTION + count.OK + count.COORDINATOR;
console.log("Messages: ELECTION " + count.ELECTION + ", OK " + count.OK +
  ", COORDINATOR " + count.COORDINATOR + ", total " + total);

Round 1: P2 holds an election
  P2 -> P3  ELECTION
  P3 -> P2  OK
  P2 -> P4  ELECTION
  P4 -> P2  OK
  P2 -> P5  ELECTION   (no answer: P5 is down)
  P2 got OK, steps aside and waits
Round 2: P3 holds an election
  P3 -> P4  ELECTION
  P4 -> P3  OK
  P3 -> P5  ELECTION   (no answer: P5 is down)
  P3 got OK, steps aside and waits
Round 3: P4 holds an election
  P4 -> P5  ELECTION   (no answer: P5 is down)
  P4 timed out waiting for OK -> P4 wins
  P4 -> P1  COORDINATOR
  P4 -> P2  COORDINATOR
  P4 -> P3  COORDINATOR
Messages: ELECTION 6, OK 3, COORDINATOR 3, total 12

Ring algorithm (Chang ও Roberts-এর ধারায়): প্রসেসগুলো বৃত্তে সাজানো; যে টের পায় সে একটি ELECTION বার্তা পরের জীবিতকে পাঠায়, প্রত্যেকে নিজের id যোগ করে এগিয়ে দেয় (মৃতকে ডিঙিয়ে)। বার্তা শুরুর জনের কাছে ফিরলে তালিকার সবচেয়ে বড় id নেতা, আর আরেক পাক ঘুরে COORDINATOR জানানো হয়। উপরের উদাহরণে (P5 মৃত, P2 শুরু): P2 → P3 → P4 → P1 → P2, তালিকা [২, ৩, ৪, ১] — নেতা P4; তারপর COORDINATOR আরও ৪ ধাপ: মোট ৮টি বার্তা, প্রায় ২n.

৮ · Distributed file system — NFS, AFS আর GFS/HDFS

পর্ব ৪২-এ (Directory, link আর mounting — VFS) দেখেছেন, VFS-এর কারণে NFS-এর মতো দূরের file system-ও একটি সাধারণ ডিরেক্টরিতে mount করা যায়, আর open/read একই থাকে। এখানে প্রশ্ন ভেতরের: অনেক client একই ফাইল cache করলে কে কখন কার লেখা দেখবে, আর server crash করলে কী হবে।

NFS — stateless থেকে stateful

NFS (Sun, ১৯৮৪-৮৫) ONC RPC-র ওপর চলে। প্রতিটি ফাইল একটি অস্বচ্ছ file handle দিয়ে চেনা হয়, আর প্রতিটি অনুরোধ নিজেই সম্পূর্ণ: “এই handle-এর এই offset থেকে এত বাইট পড়া” — কোনো “খোলা ফাইল” server মনে রাখে না।

Caching আর close-to-open consistency: NFS client ফাইলের ডেটা আর attribute (আকার, mtime) কিছুক্ষণ cache করে — Linux-এ attribute cache-এর মেয়াদ সাধারণত কয়েক সেকেন্ড থেকে এক মিনিটের মধ্যে (acregmin/acregmax mount option). প্রতিশ্রুতিটি দুর্বল কিন্তু কাজের: ফাইল close করার সময় client সব লেখা server-এ পাঠায়, আর open করার সময় server-এর কাছে attribute যাচাই করে। তাই A লিখে বন্ধ করার পরে B খুললে A-র লেখা দেখবে — কিন্তু দুজনে একসাথে খোলা রেখে লিখলে কে কখন কী দেখবে, তার নিশ্চয়তা নেই। এই খুঁটিনাটি mount option আর version ভেদে আলাদা, তাই গুরুত্বপূর্ণ কাজে NFS-এর ওপর একসাথে লেখার আগে নথি দেখে পরীক্ষা করা জরুরি।

AFS — পুরো ফাইল cache আর callback

Carnegie Mellon-এর Andrew প্রকল্পের (১৯৮০-এর দশকের মাঝামাঝি) AFS-এর লক্ষ্য ছিল হাজার হাজার ওয়ার্কস্টেশন। কৌশল দুটি। Whole-file caching: খোলার সময় পুরো ফাইল client-এর লোকাল ডিস্কে আনা, পড়া-লেখা সব লোকালি, বন্ধ করলে পুরোটা ফেরত — লাইব্রেরি থেকে পুরো বই বাসায় নেওয়ার মতো। আর callback: server প্রতিশ্রুতি দেয়, “ফাইলটি বদলালে আমি আপনাকে জানাব”; ফলে প্রতিবার খোলার সময় server-কে জিজ্ঞেস করতে হয় না। কেউ নতুন সংস্করণ ফেরত দিলে server বাকিদের callback ভাঙে। এতে server-এর ভার খুব কমে।

GFS আর HDFS — বড় ফাইল, বড় টুকরো, তিন কপি

২০০৩ সালের Google File System প্রবন্ধ ভিন্ন প্রয়োজন থেকে আসে: কয়েক GB-র ফাইল, বেশিরভাগ লেখা শেষে জোড়া (append), আর হাজারো সস্তা যন্ত্র, যার কিছু প্রতিদিনই নষ্ট হয়। নকশা: একটি master শুধু metadata রাখে (কোন ফাইলের কোন টুকরো কোথায়), ডেটা থাকে chunk server-এ, প্রতিটি chunk ৬৪ MB, ডিফল্ট ৩টি কপি আলাদা যন্ত্রে। Client master-কে শুধু ঠিকানা জিজ্ঞেস করে, ডেটা সরাসরি chunk server থেকে আনে। Hadoop-এর HDFS একই ধাঁচে বানানো (NameNode আর DataNode; নতুন version-এ ডিফল্ট block ১২৮ MB, replication ৩)। বড় chunk মানে metadata ছোট, master-এ কম অনুরোধ — কিন্তু ছোট ফাইলের জন্য অপচয়ী।

Consistency semantics — কে কখন কার লেখা দেখে

৯ · Failure detection, consensus আর বাস্তবের OS

প্রায় প্রতিটি algorithm-এ “timeout হলে মৃত ধরে নেওয়া” লুকিয়ে আছে। বাস্তবে এটি করা হয় heartbeat দিয়ে: প্রতিটি যন্ত্র নির্দিষ্ট সময় পরপর “আমি আছি” পাঠায়; কয়েকটি পরপর না এলে failure detector তাকে সন্দেহ করে — বাড়ির দারোয়ান যেমন প্রতি ঘণ্টায় ঘণ্টা বাজান, না বাজলে কেউ খোঁজ নিতে যান। দুই দিকের ভুল আছে: timeout ছোট হলে ধীর-কিন্তু-জীবিত যন্ত্রকে মৃত ধরা (মিথ্যা সন্দেহ), বড় হলে সত্যিকারের মৃত্যু দেরিতে ধরা। একটি asynchronous নেটওয়ার্কে — যেখানে দেরির কোনো ঊর্ধ্বসীমা নেই — নিখুঁত failure detector অসম্ভব।

মিথ্যা সন্দেহের সবচেয়ে বড় বিপদ split-brain: পুরোনো নেতা আসলে বেঁচে ছিল (হয়তো garbage collection-এ কয়েক সেকেন্ড থেমে ছিল), এদিকে নতুন নেতাও নির্বাচিত — দুজনেই লিখছে। প্রতিকার: majority quorum ছাড়া কেউ নেতা নয়, আর প্রতিটি নেতৃত্বের একটি ক্রমবর্ধমান নম্বর (term বা fencing token) — স্টোরেজ পুরোনো নম্বরের লেখা ফিরিয়ে দেয়।

Consensus — এক অনুচ্ছেদে

Bully algorithm ধরে নেয় timeout নির্ভুল; সেটি না হলে দুজন নেতা হতে পারে। সাধারণ সমস্যাটির নাম consensus: কয়েকটি যন্ত্র, যার কিছু crash করতে পারে আর বার্তা দেরিতে আসতে পারে, একটি মানে একমত হবে, আর সিদ্ধান্ত কখনো উল্টাবে না। ১৯৮৫ সালের FLP ফল দেখায়, সম্পূর্ণ asynchronous নেটওয়ার্কে একটিমাত্র crash থাকলেও কোনো নির্ধারিত (deterministic) algorithm সবসময় শেষ হওয়ার নিশ্চয়তা দিতে পারে না; বাস্তব algorithm তাই নিরাপত্তা সবসময় রাখে, আর অগ্রগতি পায় যখন নেটওয়ার্ক কিছুটা শান্ত। Leslie Lamport-এর Paxos ক্লাসিক সমাধান; Diego Ongaro ও John Ousterhout-এর Raft (২০১৪) একই কাজ বোঝার সুবিধাকে লক্ষ্য রেখে করে — একজন নেতা, একটি replicated log, majority-তে পৌঁছালে commit; ২f + ১ যন্ত্রে f-টি crash সয়। Quorum, CAP আর replication-এর ডেটাবেস-দিক বিস্তারিত আছে DBMS · consistency model, quorum আর consensus-এ (CAP: অংশ ৭)।

বাস্তবে — Kubernetes আর etcd

Kubernetes-এর পুরো ক্লাস্টারের অবস্থা — কোন pod কোথায়, কোন config — রাখা হয় etcd-এ, যা Raft দিয়ে সাধারণত ৩ বা ৫টি যন্ত্রে replicate হয় (৩টিতে ১টি, ৫টিতে ২টি ব্যর্থতা সয়)। Controller-রা API server-এর Lease object (যা শেষ পর্যন্ত etcd-তেই থাকে) দিয়ে নেতা বাছাই করে, যাতে একই কাজ দুজন না করে; প্রতিটি node-এর kubelet নিয়মিত heartbeat (node lease) পাঠায়, দেরি হলে node “NotReady” হয়। অর্থাৎ এই পর্বের প্রায় প্রতিটি ধারণা — RPC (API server-এর সাথে gRPC/HTTP), lease, heartbeat, election, consensus — একটি সাধারণ ক্লাস্টারেই প্রতিদিন চলছে, প্রতিটি যন্ত্রের Linux kernel-এর ওপরে।

১০ · AI-এর যুগে distributed systems

AI খুব আত্মবিশ্বাসের সাথে retry লুপ, leader election বা ঘড়ি-মেলানোর কোড লিখে দেয়। সমস্যা হলো, distributed বাগ প্রায় কখনো ল্যাপটপে ধরা পড়ে না — একটি মেশিনে নেটওয়ার্ক হারায় না, ঘড়ি সরে না, কেউ অর্ধেক মরে না। “আমার মেশিনে তো চলছে” এখানে কোনো প্রমাণই নয়।

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

• প্রতিটি নেটওয়ার্ক কলে timeout আছে, আর সময় মাপা হচ্ছে monotonic ঘড়িতে
• যে কাজে retry হয়, সেটি idempotent, অথবা idempotency key দিয়ে server-এ duplicate বাদ যায় — আর key টেকসই জায়গায় রাখা
• “উত্তর হারানো” আর “server কাজের পরে crash” — দুটি ঘটনা ইচ্ছা করে ঘটিয়ে পরীক্ষা করেছি
• দুই মেশিনের wall-clock তুলনা করে ক্রম ঠিক করা হচ্ছে না
• নেতা বা lock-এর জন্য নিজে লেখা algorithm নয়, পরীক্ষিত consensus টুল (etcd, ZooKeeper) বা ডেটাবেসের lock ব্যবহার করেছি
• AI-এর দেওয়া সংখ্যা (resync interval, message count, NTP offset) হাতে বা simulator-এ মিলিয়েছি, আর কমান্ডগুলো আমার OS আর ডিস্ট্রোর জন্য কি না দেখেছি