সময় আর ক্রম — NTP, Lamport clock আর vector clock

১ · কোনটি আগে ঘটেছে — প্রশ্নটি কেন এত কঠিন

একটি কাল্পনিক mobile banking সেবার কথা ভাবুন। রাত ১০টায় একজন গ্রাহক দুটি কাজ করলেন: প্রথমে অ্যাকাউন্টে ৫,০০০ টাকা জমা, তার কয়েক মিলিসেকেন্ড পরে ৪,০০০ টাকা পাঠানো। জমার অনুরোধ গেল সার্ভার A-তে, পাঠানোর অনুরোধ সার্ভার B-তে। প্রতিটি সার্ভার নিজের ঘড়ি দেখে একটি timestamp বসাল। পরে হিসাব মেলানোর সময় দেখা গেল, B-এর timestamp A-এর চেয়ে আগের — যেন টাকা আসার আগেই পাঠানো হয়েছে। কারণ? B-এর ঘড়ি A-এর চেয়ে কয়েক মিলিসেকেন্ড পিছিয়ে ছিল।

এক যন্ত্রের ভেতরে “আগে-পরে” সহজ: একটি CPU একটির পর একটি নির্দেশ চালায়। কিন্তু পর্ব ৩৮ — Distributed system-এর কঠিন সত্য-এ দেখেছেন, আলাদা যন্ত্রের ঘড়ি আলাদা হারে চলে, আর একটি process যেকোনো মুহূর্তে কিছুক্ষণ থেমে যেতে পারে। তাই distributed system-এ “কোনটি আগে” প্রশ্নের দুটি আলাদা উত্তর আছে:

এই পর্বের পথ: আগে physical ঘড়ি কতটা ভুল আর NTP কীভাবে সারায় (অংশ ২–৪), তারপর কেন timestamp দিয়ে ক্রম ঠিক করা বিপজ্জনক (অংশ ৫), তারপর logical clock (অংশ ৬–৭), শেষে দুই জগতের মিশ্রণ আর সময়ক্রমের ID (অংশ ৮–৯)।

২ · Physical ঘড়ি — quartz, drift আর skew

প্রায় প্রতিটি কম্পিউটারের ভেতরে সময় রাখে একটি ছোট quartz crystal, যা নির্দিষ্ট হারে কাঁপে; কম্পন গুনে সময় হিসাব হয়। কিন্তু কম্পনের হার কারখানা, তাপমাত্রা আর বয়সভেদে একটু আলাদা। এই হারের ভুলকে বলে clock drift, মাপা হয় ppm (parts per million — দশ লাখে কত ভাগ) এককে। সাধারণ সার্ভারের ঘড়ি মোটামুটি কয়েক থেকে কয়েক দশ ppm সরে — সঠিক সংখ্যা হার্ডওয়্যার আর তাপমাত্রাভেদে আলাদা।

দুটি শব্দ আলাদা রাখুন। Drift হলো হারের ভুল — একটি ঘড়ি প্রতি সেকেন্ডে কতটা সরে। Clock skew হলো কোনো এক মুহূর্তে দুটি ঘড়ির পার্থক্য। একটি ঘড়ি +২০ ppm আর আরেকটি −২০ ppm হলে দুজনের পার্থক্য বাড়ে ৪০ ppm হারে — দিনে প্রায় ৩.৫ সেকেন্ড। তাই ঘড়ি একবার মিলিয়ে দিলেই চলে না; বারবার মেলাতে হয়।

ঘড়ির আরেক শত্রু process-এর থেমে যাওয়া — garbage collection, virtual machine-এর স্থানান্তর বা ল্যাপটপের sleep. এগুলোতে ঘড়ি ভুল হয় না, কিন্তু প্রোগ্রাম মনে করে “এইমাত্র সময় দেখলাম”, অথচ মাঝে কয়েক সেকেন্ড চলে গেছে। পর্ব ৩৮-এ এর উদাহরণ দেখেছেন; সময়ের ওপর ভরসা করা lease কেন তাই fencing token চায়, তা পর্ব ৪৩ — Coordination-এ।

৩ · NTP — চারটি timestamp থেকে offset আর delay

NTP (Network Time Protocol) ইন্টারনেটের সবচেয়ে পুরোনো চালু protocol-গুলোর একটি; David Mills ১৯৮০-এর দশকে এর কাজ শুরু করেন, আর বর্তমান সংস্করণ NTPv4 (RFC 5905, ২০১০)। এটি UDP port 123-এ চলে। মূল সমস্যাটি এমন: client জানতে চায় সার্ভারের ঘড়ি তার চেয়ে কতটা এগিয়ে বা পিছিয়ে — অথচ বার্তা আসা-যাওয়াতেই সময় লাগে, আর সেই সময় client জানে না।

সমাধান: একটি অনুরোধ-উত্তরে চারটি timestamp লেখা হয়।

• t1 — client অনুরোধ পাঠাল (client-এর ঘড়িতে)
• t2 — সার্ভার অনুরোধ পেল (সার্ভারের ঘড়িতে)
• t3 — সার্ভার উত্তর পাঠাল (সার্ভারের ঘড়িতে)
• t4 — client উত্তর পেল (client-এর ঘড়িতে)

সূত্রটি কোথা থেকে এল — ছোট একটি প্রমাণ

ধরা যাক সার্ভারের ঘড়ি client-এর চেয়ে θ এগিয়ে, যেতে লাগে d₁, ফিরতে d₂. তাহলে t2 = t1 + d₁ + θ, আর t4 = t3 + d₂ − θ. প্রথমটি থেকে t2 − t1 = d₁ + θ, দ্বিতীয়টি থেকে t3 − t4 = θ − d₂.

অর্থাৎ হিসাবের offset θ̂ আসল θ-র সমান হয় কেবল যাওয়া আর আসা সমান হলে। d₁ আর d₂ দুটিই ঋণাত্মক নয় আর যোগফল δ, তাই |d₁ − d₂| ≤ δ — ফলে ভুল কখনো δ/২-এর বেশি নয়। এখান থেকেই NTP-র কৌশল: কয়েকটি নমুনা নিয়ে সবচেয়ে কম delay-এর নমুনাকে বেশি বিশ্বাস করা, কারণ তার ভুলের সীমা সবচেয়ে ছোট। নিচের প্রোগ্রাম ছয়টি নমুনা বানায় — যাওয়া-আসায় এলোমেলো queueing delay, seed নির্দিষ্ট।

// NTP: estimate clock offset and round-trip delay from four timestamps t1..t4
function rng(seed) {                                   // mulberry32: seeded, repeatable
  return () => { 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 rand = rng(39);
const jitter = mean => -mean * Math.log(1 - rand());   // random queueing delay, average = mean
const TRUE_OFFSET = 37.0;      // server clock is 37.0 ms ahead of the client clock (unknown to client)
console.log("#  t1(c)    t2(s)    t3(s)    t4(c)    offset  delay  error");
let best = null;
for (let k = 1; k <= 6; k++) {
  const t1 = 1000 * k;                                 // client clock when request leaves
  const go = 8 + jitter(6), back = 8 + jitter(6);      // one-way delays differ (asymmetry)
  const t2 = t1 + go + TRUE_OFFSET;                    // server clock on arrival
  const t3 = t2 + 0.3 + jitter(0.5);                   // server processing time
  const t4 = t3 + back - TRUE_OFFSET;                  // client clock when reply arrives
  const offset = ((t2 - t1) + (t3 - t4)) / 2;
  const delay = (t4 - t1) - (t3 - t2);
  const s = { k, offset, delay, err: offset - TRUE_OFFSET };
  console.log([k, t1, t2, t3, t4].map((v, i) => i ? v.toFixed(2).padStart(8) : String(v)).join(" ") +
    offset.toFixed(2).padStart(8) + delay.toFixed(2).padStart(7) + s.err.toFixed(2).padStart(7));
  if (!best || delay < best.delay) best = s;
}
console.log("pick min-delay sample #" + best.k + ": offset " + best.offset.toFixed(2) +
  " ms, error " + best.err.toFixed(2) + " ms, bound +/-" + (best.delay / 2).toFixed(2) + " ms");

#  t1(c)    t2(s)    t3(s)    t4(c)    offset  delay  error
1  1000.00  1045.47  1046.16  1025.55   33.04  24.86  -3.96
2  2000.00  2045.23  2045.99  2028.36   31.43  27.60  -5.57
3  3000.00  3045.02  3046.81  3019.80   36.01  18.01  -0.99
4  4000.00  4054.08  4055.14  4040.43   34.39  39.37  -2.61
5  5000.00  5056.24  5056.71  5032.28   40.34  31.81   3.34
6  6000.00  6047.64  6048.41  6023.64   36.21  22.87  -0.79
pick min-delay sample #3: offset 36.01 ms, error -0.99 ms, bound +/-9.00 ms

Stratum, slew আর step

NTP সার্ভারগুলো স্তরে সাজানো — এই স্তরের নাম stratum. Stratum 0 হলো আসল সময়ের উৎস (GPS receiver, পারমাণবিক ঘড়ি); তার সাথে সরাসরি যুক্ত সার্ভার stratum 1; তাদের কাছ থেকে সময় নেওয়া সার্ভার stratum 2, এভাবে চলে। RFC 5905 অনুযায়ী ১৫ পর্যন্ত বৈধ, আর ১৬ মানে “সিঙ্ক হয়নি”। Stratum সংখ্যা নির্ভুলতার মাপ নয় — শুধু উৎস থেকে কত ধাপ দূরে, তার মাপ।

Offset জানার পর ঘড়ি সংশোধনের দুই উপায়। Slew — ঘড়িকে কিছুক্ষণ একটু দ্রুত বা ধীরে চালিয়ে আস্তে আস্তে মেলানো; সময় পেছায় না। Step — এক লাফে নতুন সময় বসানো; offset বড় হলে (ntpd-এর ডিফল্টে প্রায় ১২৮ ms-এর বেশি; chrony-তে setting-নির্ভর) এটি ঘটে, আর তখন ঘড়ি পেছাতেও পারে। কতটা নির্ভুল হয়? মোটামুটি হিসাবে: একই ডেটা সেন্টারের ভেতরে ১ ms-এর নিচে, ইন্টারনেটের দূরের সার্ভার থেকে কয়েক থেকে কয়েক দশ ms; পথ অসম বা জমজমাট হলে আরও খারাপ। আরও কড়া প্রয়োজনে PTP (IEEE 1588) hardware timestamp দিয়ে LAN-এ microsecond-এর নিচে পৌঁছাতে পারে।

৪ · Wall clock বনাম monotonic clock, আর leap second

অপারেটিং সিস্টেম আসলে দুই রকম ঘড়ি দেয়। Wall clock (দেয়ালঘড়ির সময়) বলে এখন ক্যালেন্ডারের কোন তারিখ আর কয়টা বাজে — সাধারণত Unix epoch থেকে কত সেকেন্ড, UTC-তে। NTP একে সংশোধন করে, তাই এটি লাফ দিতে, এমনকি পেছাতে পারে। Monotonic clock শুধু বলে কোনো এক নির্দিষ্ট মুহূর্ত (প্রায়ই যন্ত্র চালুর সময়) থেকে কত সময় গেছে; এটি কখনো পেছায় না। এর মানের কোনো ক্যালেন্ডার-অর্থ নেই, আর দুটি যন্ত্রের monotonic মান তুলনাও অর্থহীন।

ভুল ঘড়ি বাছলে কী হয়, নিচে ধাপে ধাপে দেখুন। একটি সার্ভার একটি অনুরোধের সময় মাপছে, আর মাঝপথে NTP ঘড়িকে এক লাফে (step) ৩০০ ms পিছিয়ে দিল।

Leap second আর smearing

পৃথিবীর ঘূর্ণন একদম সমান নয়, তাই পারমাণবিক ঘড়ির সময় আর সূর্যের সময় মেলাতে ১৯৭২ সাল থেকে UTC-তে মাঝে মাঝে একটি বাড়তি সেকেন্ড যোগ হয়েছে — leap second; সেদিন ঘড়িতে ২৩:৫৯:৫৯-এর পরে আসে ২৩:৫৯:৬০. এখন পর্যন্ত ২৭ বার যোগ হয়েছে, শেষবার ২০১৬ সালের ৩১ ডিসেম্বর। Unix time-এ ৬০ নম্বর সেকেন্ড রাখার জায়গা নেই, তাই অনেক সিস্টেমে একই সেকেন্ড দুবার আসে — অর্থাৎ wall clock এক সেকেন্ড পেছায়। ২০২২ সালে ওজন ও পরিমাপের আন্তর্জাতিক সম্মেলন (CGPM) সিদ্ধান্ত নেয় যে ২০৩৫ সালের মধ্যে leap second বন্ধ করা হবে; বিস্তারিত নিয়ম এখনো চূড়ান্ত হচ্ছে।

অনেক বড় প্রতিষ্ঠান তাই লাফের বদলে leap smear করে: বাড়তি সেকেন্ডটিকে কয়েক ঘণ্টা থেকে এক দিন জুড়ে ছড়িয়ে দেয় — ঘড়ি সেই সময় একটু ধীরে চলে। Google-এর প্রকাশিত নথি অনুযায়ী তাদের public NTP সেবা ২৪ ঘণ্টা ধরে সমান হারে smear করে (দুপুর থেকে দুপুর); প্রতি সেকেন্ডে পার্থক্য তখন ১ ÷ ৮৬,৪০০ ≈ ১১.৬ ppm — সাধারণ quartz drift-এর মাপে। সাবধান: smear করা আর না-করা সার্ভার মিশিয়ে ব্যবহার করলে সেই দিনে দুই দলের মধ্যে আধা সেকেন্ড পর্যন্ত পার্থক্য হতে পারে।

৫ · কেন timestamp দিয়ে আলাদা যন্ত্রের ঘটনা সাজানো যায় না

ধরা যাক NTP সব সার্ভারকে আসল সময়ের ±ε-এর মধ্যে রাখে। তাহলে দুটি সার্ভারের পার্থক্য সর্বোচ্চ ২ε. এখন দুটি ঘটনা আলাদা সার্ভারে ২ε-এর চেয়ে কম ব্যবধানে ঘটলে timestamp উল্টো ক্রম দেখাতেই পারে। আর ε নিজেও নিশ্চিত নয় — কোনো সার্ভারের NTP চুপচাপ বন্ধ হয়ে গেলে, ভুল config-এ, বা virtual machine থেমে থাকার পরে ঘড়ি অনেক দূরে সরে যেতে পারে, আর তা কেউ টেরও পায় না।

সবচেয়ে বিপজ্জনক জায়গা last-write-wins (LWW): একই key-তে দুটি লেখা এলে বড় timestamp-এর লেখাটি থাকে, অন্যটি নিঃশব্দে মুছে যায়। একটি উদাহরণ:

কোনো error নেই, কোনো log-এ সতর্কবার্তা নেই — গ্রাহকের সংশোধন শুধু হারিয়ে গেল। Replication-এ এই ঝুঁকি পর্ব ২২-এ দেখেছেন; সমাধানের পথ — সংস্করণ রেখে মেলানো আর CRDT — পর্ব ৪৬ — Conflict resolution আর CRDT-এ।

৬ · Happened-before আর Lamport clock

১৯৭৮ সালে Leslie Lamport “Time, Clocks, and the Ordering of Events in a Distributed System” নামের paper-এ (Communications of the ACM) প্রশ্নটি নতুন করে সাজান: ঘড়ি কী বলে তা নয়, কোন ঘটনা কোন ঘটনাকে প্রভাবিত করতে পারত, সেটিই আসল ক্রম। তিনি সংজ্ঞা দেন happened-before সম্পর্কের, চিহ্ন a → b:

1. একই process-এ a আগে আর b পরে ঘটলে a → b.
2. a একটি বার্তা পাঠানো আর b সেই বার্তা পাওয়া হলে a → b.
3. a → b আর b → c হলে a → c (একটির পর আরেকটি জুড়ে চলে)।

a → b বা b → a — কোনোটিই না হলে a আর b concurrent, চিহ্ন a ∥ b. এখানে “concurrent” মানে একই মুহূর্তে নয়; মানে একটি আরেকটির খবর জানত না, তাই একটি অন্যটির কারণ হতে পারে না। এই সম্পর্ক সব জোড়াকে সাজায় না — তাই একে বলে partial order বা আংশিক ক্রম।

Lamport clock এই সম্পর্ককে একটি সংখ্যায় ধরার সহজ উপায়। প্রতিটি process একটি counter রাখে, আর দুটি নিয়ম মানে:

নিচের space-time diagram-এ তিনটি process (ওপর থেকে নিচে সময়) আর তিনটি বার্তা। প্রতিটি ঘটনার পাশে তার Lamport মান আর vector clock (অংশ ৭) লেখা।

নিচের প্রোগ্রাম ঠিক এই trace-এ দুই নিয়ম চালায়, তারপর (L, process নম্বর) দিয়ে সব ঘটনা এক সারিতে সাজায় — এটিই total order.

// Lamport clocks on a 3-process trace; then a total order using (L, process id)
// Each event: [name, process, kind, message]. Listed in one possible real-time order.
const trace = [
  ["a", 1, "local"], ["g", 3, "local"],
  ["b", 1, "send", "m1"], ["d", 2, "recv", "m1"],
  ["e", 2, "send", "m2"], ["f", 2, "local"],
  ["h", 3, "recv", "m2"], ["i", 3, "send", "m3"],
  ["c", 1, "recv", "m3"],
];
const L = { 1: 0, 2: 0, 3: 0 };          // one counter per process, starts at 0
const inFlight = {};                     // message -> timestamp carried with it
const stamp = {};
for (const [name, p, kind, msg] of trace) {
  if (kind === "recv") L[p] = Math.max(L[p], inFlight[msg]) + 1;  // rule 2: max, then +1
  else L[p] = L[p] + 1;                                          // rule 1: tick before each event
  if (kind === "send") inFlight[msg] = L[p];                     // the message carries L
  stamp[name] = [L[p], p];
  console.log(`${name}  P${p}  ${kind.padEnd(5)} ${(msg || "").padEnd(3)} L=${L[p]}`);
}
const order = Object.keys(stamp).sort((x, y) =>
  stamp[x][0] - stamp[y][0] || stamp[x][1] - stamp[y][1]);      // tie -> smaller process id
console.log("total order: " + order.map(n => `${n}(${stamp[n][0]}.${stamp[n][1]})`).join(" < "));
console.log("L(g)=" + stamp.g[0] + " < L(b)=" + stamp.b[0] + "   L(f)=" + stamp.f[0] +
  " < L(c)=" + stamp.c[0] + "   (does that mean g->b or f->c? check with vector clocks)");

a  P1  local     L=1
g  P3  local     L=1
b  P1  send  m1  L=2
d  P2  recv  m1  L=3
e  P2  send  m2  L=4
f  P2  local     L=5
h  P3  recv  m2  L=5
i  P3  send  m3  L=6
c  P1  recv  m3  L=7
total order: a(1.1) < g(1.3) < b(2.1) < d(3.2) < e(4.2) < f(5.2) < h(5.3) < i(6.3) < c(7.1)
L(g)=1 < L(b)=2   L(f)=5 < L(c)=7   (does that mean g->b or f->c? check with vector clocks)

নিশ্চয়তা এক দিকে — ছোট প্রমাণ

Clock condition: a → b হলে L(a) < L(b). কারণ, happened-before-এর প্রতিটি ধাপ — একই process-এ পরের ঘটনা, অথবা বার্তা পাঠানো থেকে পাওয়া — নিয়ম ১ বা ২ অনুযায়ী L অন্তত ১ বাড়ায়; একাধিক ধাপ জুড়লে বৃদ্ধিও জোড়া লাগে। কিন্তু উল্টোটি সত্য নয়: L(g) = ১ < L(b) = ২, অথচ g ∥ b. দুই আলাদা process-এর counter স্বাধীনভাবে বাড়ে, তাই ছোট সংখ্যা শুধু বলে “b, g-এর আগে ঘটেনি” — এর বেশি কিছু নয়। Total order তাই কারণ-কার্যের সাথে সামঞ্জস্যপূর্ণ একটি ক্রম, কিন্তু concurrent জোড়ার ক্রম সেখানে ইচ্ছামতো বাছা — বাস্তব সময়ের সাথে তার মিল নাও থাকতে পারে।

৭ · Vector clock — আগে, পরে, না একসাথে

Lamport-এর সীমা কাটাতে প্রতিটি process শুধু নিজের counter নয়, সবার counter-এর একটি তালিকা রাখে — vector clock. ১৯৮৮ সালের দিকে Colin Fidge আর Friedemann Mattern আলাদাভাবে ধারণাটি প্রকাশ করেন। N-টি process থাকলে vector-এ N-টি ঘর; P_i-এর V[j] মানে “P_j-এর কতগুলো ঘটনার খবর আমি জানি”.

দুটি vector তুলনার নিয়ম: সব ঘরে V(a) ≤ V(b) আর অন্তত একটিতে ছোট হলে a → b; উল্টো হলে b → a; কোনোটিই না হলে a ∥ b. এর শক্তি এক বাক্যে — V(a) < V(b) হলে এবং কেবল তখনই a → b, দুই দিকেই সত্য। কারণ V(b)[j] ঠিক সেই সংখ্যা, P_j-এর যতগুলো ঘটনা বার্তার কোনো শিকল ধরে b পর্যন্ত পৌঁছেছে; a সেই তালিকায় থাকলে তবেই V(a)-র প্রতিটি ঘর V(b)-র ঘরের সমান বা ছোট হয়। নিচের প্রোগ্রাম একই trace-এ কয়েকটি জোড়া যাচাই করে।

// Vector clocks on the same 3-process trace; classify pairs of events
const trace = [
  ["a", 0, "local"], ["g", 2, "local"],
  ["b", 0, "send", "m1"], ["d", 1, "recv", "m1"],
  ["e", 1, "send", "m2"], ["f", 1, "local"],
  ["h", 2, "recv", "m2"], ["i", 2, "send", "m3"],
  ["c", 0, "recv", "m3"],
];
const V = [[0, 0, 0], [0, 0, 0], [0, 0, 0]];  // V[p] = what process p knows of each process
const inFlight = {}, vc = {};
for (const [name, p, kind, msg] of trace) {
  if (kind === "recv") V[p] = V[p].map((x, j) => Math.max(x, inFlight[msg][j])); // merge
  V[p][p] += 1;                                  // tick own entry on every event
  if (kind === "send") inFlight[msg] = [...V[p]];   // message carries a copy
  vc[name] = [...V[p]];
}
console.log(Object.entries(vc).map(([n, v]) => `${n}=[${v}]`).join(" "));
function compare(x, y) {
  const le = x.every((v, j) => v <= y[j]), ge = x.every((v, j) => v >= y[j]);
  if (le && ge) return "same";
  if (le) return "before (->)";
  if (ge) return "after (<-)";
  return "concurrent (||)";
}
for (const [x, y] of [["a", "f"], ["b", "c"], ["e", "h"], ["c", "d"],
                      ["g", "b"], ["f", "h"], ["f", "c"]]) {
  console.log(`${x}=[${vc[x]}] vs ${y}=[${vc[y]}]  ${x} ${compare(vc[x], vc[y])} ${y}`);
}

a=[1,0,0] g=[0,0,1] b=[2,0,0] d=[2,1,0] e=[2,2,0] f=[2,3,0] h=[2,2,2] i=[2,2,3] c=[3,2,3]
a=[1,0,0] vs f=[2,3,0]  a before (->) f
b=[2,0,0] vs c=[3,2,3]  b before (->) c
e=[2,2,0] vs h=[2,2,2]  e before (->) h
c=[3,2,3] vs d=[2,1,0]  c after (<-) d
g=[0,0,1] vs b=[2,0,0]  g concurrent (||) b
f=[2,3,0] vs h=[2,2,2]  f concurrent (||) h
f=[2,3,0] vs c=[3,2,3]  f concurrent (||) c

দাম: vector-এর আকার

প্রতিটি বার্তা আর প্রতিটি সংরক্ষিত সংস্করণে N-টি সংখ্যা যায়। ১০টি সার্ভারে সমস্যা নেই; কিন্তু যদি প্রতিটি mobile client বা প্রতিটি অস্থায়ী container নিজের ঘর পায়, vector অসীমভাবে বাড়ে। বাস্তব সিস্টেম তাই ঘর সীমিত রাখে — শুধু সার্ভার বা replica-দের ঘর দেয়, অথবা পুরোনো ঘর ছাঁটে। Amazon-এর Dynamo paper (২০০৭) অনুযায়ী তারা নির্দিষ্ট সংখ্যার (উদাহরণে ১০টি) ঘর ছাড়ালে সবচেয়ে পুরোনোটি বাদ দিত — দাম হলো মাঝে মাঝে concurrency ভুল চেনা।

Version vector বনাম vector clock

নাম দুটি প্রায়ই অদলবদল করে ব্যবহৃত হয়, কিন্তু উদ্দেশ্য আলাদা। Vector clock প্রতিটি ঘটনার কারণ-কার্য ধরে — প্রতিটি process, প্রতিটি ঘটনায় ঘর বাড়ায়। Version vector লাগানো থাকে একটি ডেটার সংস্করণে: ঘর থাকে প্রতিটি replica-র, আর ঘর বাড়ে শুধু সেই replica ওই ডেটায় নতুন লেখা নিলে; replica-রা মেলার সময় vector মেলায়। তুলনার নিয়ম একই — একটি সংস্করণ আরেকটিকে ঢেকে দিলে পুরোনোটি বাদ, concurrent হলে দুটিই রাখা হয়, যাদের বলে siblings. কে কোন নাম কোন অর্থে ব্যবহার করে, তা সিস্টেমভেদে আলাদা — Dynamo paper নিজেই “vector clock” বলে যা আসলে প্রতিটি object-এর version vector-এর কাছাকাছি। পুরো conflict-এর নকশা পর্ব ৪৬-এ, আর quorum-এ পড়ার সময় সংস্করণ মেলানো পর্ব ৪১-এ।

৮ · দুই জগতের মিলন — Hybrid logical clock আর TrueTime

Logical clock কারণ-কার্য রাখে, কিন্তু “গতকাল বিকেল ৩টার ডেটা দেখান” বলা যায় না। Physical clock সময় বলে, কিন্তু ক্রমে ভরসা নেই। দুটির সুবিধা একসাথে পাওয়ার দুটি প্রচলিত পথ আছে।

Hybrid logical clock (HLC)

Sandeep Kulkarni, Murat Demirbas ও সহকর্মীদের ২০১৪ সালের paper (“Logical Physical Clocks…”) hybrid logical clock প্রস্তাব করে। প্রতিটি timestamp দুই অংশের: l — এ পর্যন্ত দেখা সবচেয়ে বড় physical সময়, আর c — একই l-এ ক্রম রাখার ছোট counter. নিয়মগুলো মোটামুটি এমন:

• নিজের ঘটনা বা পাঠানো: l = max(l, নিজের ঘড়ি)। l না বদলালে c + ১, বদলালে c = ০.
• বার্তা পাওয়া: l = max(l, বার্তার l, নিজের ঘড়ি); যে উৎস থেকে বড় l এল, তার c থেকে + ১ (সমান হলে দুই c-র বড়টি + ১), আর নিজের ঘড়িই সবচেয়ে বড় হলে c = ০.

ফল: Lamport-এর মতোই a → b হলে HLC(a) < HLC(b), কিন্তু l আসল সময় থেকে বেশি দূরে যায় না — যতটুকু ঘড়ির পার্থক্য, প্রায় ততটুকু। তাই 64 bit-এর একটি সংখ্যায় বসানো যায়, আর “একটি সময়ের snapshot” চাওয়া যায়। Documentation অনুযায়ী CockroachDB HLC ব্যবহার করে; তবে সেখানেও সব node-এর ঘড়ির পার্থক্যের একটি সর্বোচ্চ সীমা ধরে নেওয়া হয়, আর কোনো node সেই সীমা ছাড়ালে নিজেকে বন্ধ করে — খুঁটিনাটি সংস্করণভেদে আলাদা। HLC vector clock-এর মতো concurrency চেনে না; শুধু কারণ-কার্যের সাথে সামঞ্জস্যপূর্ণ ক্রম দেয়।

TrueTime আর commit-wait

Google-এর Spanner paper (Corbett ও সহকর্মীরা, OSDI ২০১২) উল্টো পথে যায়: ঘড়ির ভুল লুকানোর বদলে তা মেপে API-তেই প্রকাশ করে। TrueTime-এর TT.now() একটি সংখ্যা নয়, একটি ব্যবধান দেয় — [earliest, latest]; প্রতিশ্রুতি হলো আসল সময় এর ভেতরে আছে। Paper অনুযায়ী ডেটা সেন্টারগুলোতে GPS আর পারমাণবিক ঘড়ির time master থাকে; অনিশ্চয়তা ε তখন প্রায় ১ থেকে ৭ ms-এর মধ্যে ওঠানামা করত, গড়ে প্রায় ৪ ms. এরপর commit-wait: transaction-এর timestamp s = TT.now().latest বসিয়ে, আর ততক্ষণ অপেক্ষা যতক্ষণ না TT.now().earliest > s হয়।

৯ · সময়ক্রমের ID — Snowflake, ULID আর UUIDv7

অনেক সিস্টেমে ক্রমের সবচেয়ে চোখে পড়া রূপ হলো ID: নতুন tweet, order বা message-এর ID যদি মোটামুটি সময়ক্রমে বাড়ে, তাহলে “নতুনগুলো আগে” query সস্তা আর B-tree index-এ লেখা এক প্রান্তে জমে। কেন্দ্রীয় counter ছাড়া ID বানানোর পুরো তুলনা — UUID v4, ticket server, ব্লক — পর্ব ২৩ — Partitioning আর sharding-এ আছে। এখানে দেখব ID-র ভেতরে সময় কীভাবে বসে আর তার ক্রমের নিশ্চয়তা কতটুকু।

প্রকাশিত engineering blog আর open-source কোড অনুযায়ী Twitter ২০১০ সালে Snowflake চালু করে; তার README-তে গঠন: 41 bit millisecond-এ সময় (নিজের বাছা একটি epoch থেকে), 10 bit যন্ত্রের নম্বর, 12 bit ক্রমিক সংখ্যা — ওপরের 1 bit খালি রাখা হয়, যাতে signed 64-bit সংখ্যা ধনাত্মক থাকে। নিচের প্রোগ্রাম একটি ID বানিয়ে bit-গুলো ভাগ করে দেখায়, ফেরত পড়ে, আর এক millisecond-এ এক যন্ত্র কয়টি ID দিতে পারে তা গুনে যাচাই করে।

// Snowflake-style 64-bit ID: 1 unused | 41-bit ms since epoch | 10-bit machine | 12-bit sequence
const EPOCH = 1288834974657n;          // the custom epoch in Twitter's published code (Nov 2010)
const encode = (ms, machine, seq) =>
  ((BigInt(ms) - EPOCH) << 22n) | (BigInt(machine) << 12n) | BigInt(seq);
const decode = id => ({ ms: (id >> 22n) + EPOCH, machine: (id >> 12n) & 0x3FFn, seq: id & 0xFFFn });
const ms = Date.UTC(2026, 9, 28, 4, 0, 0, 123);   // fixed clock reading for the demo
const id = encode(ms, 39, 5);
const bits = id.toString(2).padStart(64, "0");
console.log("id      = " + id + "  (" + id.toString().length + " decimal digits)");
console.log("sign    = " + bits.slice(0, 1));
console.log("time    = " + bits.slice(1, 42) + "  (41 bits)");
console.log("machine = " + bits.slice(42, 52) + "  (10 bits)");
console.log("seq     = " + bits.slice(52) + "  (12 bits)");
const d = decode(id);
console.log("decoded: " + new Date(Number(d.ms)).toISOString() + " machine=" + d.machine + " seq=" + d.seq);
let last = -1, seq = 0, made = 0, refused = 0;   // a generator on one machine
function next(now) {
  if (now < last) { refused++; return null; }    // clock went backwards: refuse (or wait)
  if (now === last) { seq = (seq + 1) & 0xFFF; if (seq === 0) return null; } // sequence full
  else seq = 0;
  last = now; made++; return encode(now, 39, seq);
}
while (next(ms) !== null) {}                      // keep asking within the SAME millisecond
console.log("IDs made in one ms on one machine: " + made + " = 2^12 = " + 2 ** 12);
next(ms - 3);                                    // NTP stepped the clock back by 3 ms
console.log("refused after clock moved back 3 ms: " + refused);
console.log("41-bit time lasts " + (2 ** 41 / (365.25 * 864e5)).toFixed(1) + " years; max per machine " +
  (4096 * 1000).toLocaleString("en-US") + "/s");

id      = 2115292471612305413  (19 decimal digits)
sign    = 0
time    = 00111010101101100000111010010111010111010  (41 bits)
machine = 0000100111  (10 bits)
seq     = 000000000101  (12 bits)
decoded: 2026-10-28T04:00:00.123Z machine=39 seq=5
IDs made in one ms on one machine: 4096 = 2^12 = 4096
refused after clock moved back 3 ms: 1
41-bit time lasts 69.7 years; max per machine 4,096,000/s

ক্রমের নিশ্চয়তা কতটুকু? একই যন্ত্রের ID কঠোরভাবে বাড়ে (ঘড়ি পেছালে অপেক্ষা করলে)। আলাদা যন্ত্রের ID-র ক্রম শুধু তাদের ঘড়ির মতো ভালো — ১০ ms skew থাকলে ১০ ms-এর মধ্যে তৈরি ID উল্টো ক্রমে আসতে পারে; এই “প্রায় সাজানো” অবস্থার নাম k-sorted. তাই ID-র ক্রম দিয়ে “কে আগে টিকিট চাপল” ধরনের ন্যায্যতার সিদ্ধান্ত নেওয়া চলে না; তার জন্য একটি জায়গায় ক্রম দরকার — database transaction বা একটি log partition.

128 bit-এর দুটি জনপ্রিয় বিকল্প: ULID — community spec অনুযায়ী 48 bit millisecond সময় + 80 bit এলোমেলো অংশ, Crockford base32-এ ২৬ অক্ষরে লেখা, যাতে লেখা অবস্থাতেই সময়ক্রমে সাজে; আর UUIDv7 — RFC 9562 (২০২৪)-এ মানসম্মত, প্রথম 48 bit-এ Unix millisecond. দুটিতেই যন্ত্রের নম্বর বিলি করতে হয় না, কারণ এলোমেলো অংশ যথেষ্ট বড়; দাম হলো দ্বিগুণ আকার। তিনটিতেই ID থেকে সৃষ্টির সময় পড়া যায় — গোপনীয়তার প্রশ্ন থাকলে মনে রাখুন।

১০ · AI-এর যুগে — সময় আর ক্রমের নকশায় AI-কে যাচাই

“Distributed system-এ event ordering কীভাবে করব?” জিজ্ঞেস করলে AI প্রায়ই দ্রুত উত্তর দেয়: “সব সার্ভারে NTP চালান আর timestamp দিয়ে sort করুন” — সাথে হয়তো “Kafka আর Redis যোগ করুন”। শুনতে সহজ, কিন্তু এই বিষয়ে AI-এর ভুলগুলো বেশ নিয়মিত:

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

• যেখানে timestamp দিয়ে ক্রম ঠিক হচ্ছে, সেখানে skew-এর সীমা লিখে দেখেছি কোন ঘটনা উল্টো আসতে পারে
• প্রতিটি সময়কাল, timeout আর lease monotonic ঘড়িতে মাপা হচ্ছে কি না কোডে খুঁজে দেখেছি
• LWW থাকলে কোন লেখা নিঃশব্দে হারাতে পারে, তার failure-mode পর্যালোচনা করেছি
• Lamport, vector আর HLC-এর দাবি অংশ ৬–৮-এর নিয়মে ছোট একটি trace-এ হাতে বা সিমুলেটরে যাচাই করেছি
• প্রতিটি নির্ভুলতার সংখ্যা মূল উৎসে মিলিয়েছি, আর নিজের সার্ভারে NTP offset মেপে দেখেছি