Time, Lamport ও Vector Clocks

সমস্যাটা কী?

ধরো তুমি একটা messaging app বানাচ্ছো যেখানে তিনটা সার্ভার আছে — ঢাকা, চট্টগ্রাম আর সিলেটে। একজন ইউজার মেসেজ পাঠালো, আরেকজন রিপ্লাই দিলো। এখন তুমি চাও মেসেজগুলো সঠিক ক্রমে দেখাতে — প্রশ্নের পরে উত্তর, উত্তরের আগে প্রশ্ন নয়।

স্বাভাবিকভাবেই মনে হবে, প্রতিটা মেসেজে একটা timestamp বসিয়ে দিই, তারপর সাজিয়ে দিলেই হলো। কিন্তু এখানেই বিপদ। ঢাকার সার্ভারের ঘড়ি আর সিলেটের সার্ভারের ঘড়ি ঠিক একই সময় দেখায় না। একটা হয়তো ৩০ মিলিসেকেন্ড এগিয়ে, আরেকটা পিছিয়ে। ফলে উত্তরের timestamp প্রশ্নের চেয়ে ছোট হয়ে যেতে পারে — মানে উত্তর প্রশ্নের "আগে" এসেছে দেখাবে, যা অসম্ভব।

distributed system-এ এই সমস্যা সর্বত্র। কোন update আগে হলো, কোন write জিতবে, কোন ঘটনা কার ফলে ঘটলো — এসব ঠিকভাবে বুঝতে হলে আমাদের একটা নির্ভরযোগ্য "ক্রম" দরকার, যা শুধু physical ঘড়ির উপর নির্ভর করে না।

মূল ধারণা

Happens-before (→): একটা ঘটনা A আরেকটা ঘটনা B-এর "happens-before" তখনই, যখন A হয়তো B-কে কারণগতভাবে (causally) প্রভাবিত করতে পেরেছে। অর্থাৎ একই প্রসেসে A আগে ঘটেছে, অথবা A একটা মেসেজ পাঠিয়েছে যা B রিসিভ করেছে।

মূল বুদ্ধিটা Leslie Lamport দিয়েছিলেন ১৯৭৮ সালে: আমরা physical time ভুলে যাই, বদলে শুধু logical ordering নিয়ে ভাবি। দুটি ঘটনার মধ্যে যদি কোনো causal সংযোগ না থাকে — একজন ঢাকায় ছবি আপলোড করলো, আরেকজন একই মুহূর্তে সিলেটে স্ট্যাটাস দিলো, এদের একে অপরের সাথে কোনো সম্পর্ক নেই — তখন এদের ক্রম নিয়ে মাথা ঘামানোর দরকারই নেই। এদের বলা হয় concurrent।

মূল প্রশ্ন তিনটা:

• কোন ঘটনাগুলোর মধ্যে happens-before সম্পর্ক আছে?
• কোনগুলো concurrent?
• এই সম্পর্ক আমরা কীভাবে cheap-ভাবে track করব?

কীভাবে কাজ করে

Lamport timestamp

প্রতিটা প্রসেস একটা integer counter C রাখে। নিয়ম তিনটা:

1. কোনো local event ঘটলে: C = C + 1
2. মেসেজ পাঠানোর সময়: আগে C = C + 1, তারপর মেসেজের সাথে C attach করে পাঠাও।
3. মেসেজ রিসিভ করার সময়: C = max(C, received_C) + 1

P1:  a(1) ---- b(2) ---- send m(3) ----------
                                  \
P2:        x(1) ----------------- recv m(4) -- y(5)

এখানে নিয়ম: যদি A → B হয়, তাহলে অবশ্যই C(A) < C(B)। কিন্তু উল্টোটা সত্য নয় — C(A) < C(B) মানেই A → B নয়। উপরে x(1) আর b(2) দুটোই concurrent, তবু একটার timestamp ছোট।

Vector clock

এই দুর্বলতা ঠিক করতে এলো vector clock। N নোডের system-এ প্রতিটা নোড একটা vector V[1..N] রাখে, যেখানে V[i] মানে "i নম্বর নোডের কতগুলো event আমি দেখেছি"।

অপারেশন	নিয়ম
Local event (নোড i)	V[i] = V[i] + 1
Send (নোড i)	আগে V[i] = V[i] + 1, তারপর পুরো V পাঠাও
Receive (নোড i)	প্রতি j-এর জন্য V[j] = max(V[j], received_V[j]), তারপর V[i] = V[i] + 1

তুলনার নিয়ম:

• V_A happens-before V_B — যদি A এর সব component B এর কম বা সমান হয়, এবং অন্তত একটা কঠোরভাবে ছোট হয়।
• দুটি concurrent — যদি কেউ কাউকে dominate না করে।

দুটির তুলনা

বৈশিষ্ট্য	Lamport	Vector
আকার	একটা integer	N-length array
Happens-before ধরে	হ্যাঁ	হ্যাঁ
Concurrency শনাক্ত	না	হ্যাঁ
খরচ	সস্তা	নোড বাড়লে ভারী

প্রকারভেদ

কৌশল

বাস্তবে কোনটা কখন ব্যবহার করবে:

• Lamport timestamp — যখন তোমার শুধু একটা total order দরকার (যেমন distributed lock, mutual exclusion), আর concurrency আলাদা করার দরকার নেই। সস্তা এবং সহজ।
• Vector clock — যখন conflict detection দরকার। যেমন একই key দুই জায়গায় edit হলে তুমি জানতে চাও সেগুলো সত্যিই conflict (concurrent), নাকি একটা আরেকটার পরের version।
• Version vector — vector clock-এর একটা practical রূপ, replica-based storage-এ ব্যবহৃত (Riak, Dynamo)।
• Hybrid Logical Clock (HLC) — physical time আর logical counter মিলিয়ে; CockroachDB-তে ব্যবহৃত, যাতে timestamp মানুষের কাছেও অর্থবহ থাকে।

কখন ব্যবহার করবে / করবে না

ব্যবহার করবে যখন একাধিক নোডে ঘটা events-এর causal relationship গুরুত্বপূর্ণ — replication, conflict resolution, distributed debugging।

ব্যবহার করবে না যখন সিস্টেম single-node, অথবা একটা strongly consistent database (যেমন একক leader-এর Postgres) ইতিমধ্যে সব ordering সামলাচ্ছে।

বাস্তব উদাহরণ

• Amazon Dynamo / Riak: version vector দিয়ে concurrent write শনাক্ত করে। দুটো version concurrent হলে siblings হিসেবে রাখে, পরে client merge করে।
• Cassandra: সরল last-write-wins ব্যবহার করে timestamp দিয়ে, যা কিছু edge case-এ ডেটা হারায় — এটাই logical clock না থাকার মূল্য।
• Git: commit graph আসলে এক ধরনের causal ordering; parent pointer happens-before relation প্রকাশ করে।
• Google Spanner: TrueTime নামের বিশেষ hardware (atomic clock + GPS) দিয়ে clock uncertainty সীমিত রাখে, ফলে physical time-কেই অনেকটা নির্ভরযোগ্য করে তোলে — কিন্তু এটা ব্যয়বহুল ব্যতিক্রম।