Consensus Algorithms (Paxos, Raft)

সমস্যাটা কী?

ধরো তুমি একটা banking system বানাচ্ছ যেখানে একটাই সার্ভার নয়, বরং ৫টা সার্ভার (node) একসাথে চলছে। কারণ একটা সার্ভার নষ্ট হলেও যেন সিস্টেম বন্ধ না হয়। এখন একজন গ্রাহক ১০,০০০ টাকা তুলল। প্রশ্ন হলো—এই "ব্যালেন্স কমল" তথ্যটা কোন সার্ভারে সত্য? সব সার্ভার যদি একই সময়ে আলাদা আলাদা request পায়, তারা কীভাবে একমত হবে যে আসলে কী ঘটেছে এবং কোন ক্রমে ঘটেছে?

এটাই distributed system-এর সবচেয়ে কঠিন সমস্যা: একাধিক স্বাধীন node-কে একটা single, consistent সিদ্ধান্তে একমত করানো—যেখানে network মাঝে মাঝে slow হয়, message হারায়, আর সার্ভার যেকোনো সময় crash করতে পারে। এই একমত হওয়ার পদ্ধতিকেই বলে Consensus।

মূল ধারণা

Consensus algorithm হলো এমন একটি protocol, যার মাধ্যমে distributed system-এর একাধিক node—কিছু node fail করলেও বা network সমস্যা থাকলেও—একটি সিদ্ধান্ত (যেমন কোন value বা কোন operation-এর order) নিয়ে নির্ভরযোগ্যভাবে একমত হতে পারে।

মূল চ্যালেঞ্জ হলো নেটওয়ার্ক বিশ্বাসযোগ্য নয়। তুমি জানো না message পৌঁছেছে কিনা, naki node-টা crash করেছে, naki শুধু slow হয়ে গেছে। তাই consensus algorithm কয়েকটা নিশ্চয়তা দেয়:

• Agreement: সব সঠিক node একই value-তে একমত হবে।
• Validity: যে value-তে একমত হবে, সেটা কোনো না কোনো node-ই প্রস্তাব করেছিল।
• Fault tolerance: অর্ধেকের কম node fail করলেও সিস্টেম কাজ করবে।

মনে রাখার সহজ সূত্র: যদি total node সংখ্যা 2f + 1 হয়, তাহলে cluster সর্বোচ্চ f সংখ্যক node-এর crash সহ্য করতে পারে। অর্থাৎ ৫টা node-এ ২টা পর্যন্ত হারানো চলবে।

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

আধুনিক consensus (Raft-এর উদাহরণে) মূলত তিনটি ধাপে কাজ করে।

১. Leader Election

সব node সমান অধিকার নিয়ে কথা বললে বিশৃঙ্খলা হয়। তাই প্রথমে একটা Leader বেছে নেওয়া হয়। বাকিরা হয় Follower। Leader-ই সব client request গ্রহণ করে এবং সিদ্ধান্ত নেয়।

Raft-এ প্রতিটি leader-এর একটা term (মেয়াদ) থাকে—একটা ক্রমবর্ধমান সংখ্যা। Follower নির্দিষ্ট সময়ের মধ্যে leader-এর কাছ থেকে heartbeat না পেলে নিজেকে Candidate ঘোষণা করে, term বাড়ায়, এবং অন্যদের কাছে vote চায়। যে candidate majority vote পায়, সে নতুন leader হয়।

২. Log Replication

Leader প্রতিটি operation-কে নিজের log-এ একটা entry হিসেবে লেখে, তারপর সেটা সব follower-এর কাছে পাঠায়। এই ধাপকেই বলে Log Replication।

ধাপ	কে করে	কী ঘটে
১. Receive	Leader	Client থেকে command (যেমন x=5) আসে
২. Append	Leader	নিজের log-এ uncommitted entry যোগ করে
৩. Replicate	Leader → Followers	সব follower-কে entry পাঠায়
৪. Acknowledge	Followers	log-এ লিখে leader-কে "OK" বলে
৫. Commit	Leader	Majority "OK" দিলে entry commit করে, client-কে success জানায়

৩. Quorum / Majority

কোনো entry তখনই "committed" বলে ধরা হয় যখন majority (quorum) node সেটা লিখে ফেলেছে।

Total Nodes	Quorum (majority)	কতগুলো fail সহ্য করবে
3	2	1
5	3	2
7	4	3

কেন majority? কারণ যেকোনো দুটো majority group-এর মধ্যে অন্তত একটা common node থাকবেই। ফলে কখনো দুটো আলাদা সিদ্ধান্ত একসাথে "জিততে" পারে না। এজন্যই cluster-এ সাধারণত বিজোড় সংখ্যক (3, 5, 7) node রাখা হয়।

প্রকারভেদ: Paxos বনাম Raft

দুটোই consensus সমস্যা সমাধান করে, কিন্তু পথ আলাদা।

Paxos

Leslie Lamport-এর তৈরি (১৯৯৮)। এটাই প্রথম প্রমাণিত-সঠিক consensus algorithm এবং তাত্ত্বিকভাবে অত্যন্ত শক্তিশালী। কিন্তু এর সমস্যা—এটা বোঝা ও সঠিকভাবে implement করা ভয়ঙ্কর কঠিন। এতে Proposer, Acceptor, Learner—এমন আলাদা ভূমিকা আছে এবং multi-Paxos করতে গেলে বাস্তব detail এত জটিল যে অনেক engineer-ই ভুল করে। Lamport নিজেই পরে "Paxos Made Simple" নামে আরেকটা পেপার লিখেছিলেন!

Raft

Stanford-এ তৈরি (২০১৪), মূল লক্ষ্যই ছিল understandability। Raft একই গ্যারান্টি দেয় কিন্তু সমস্যাকে তিনটি পরিষ্কার ভাগে ভাঙে—leader election, log replication, safety। Raft-এ সবসময় একজন শক্তিশালী leader থাকে, যে log-এর প্রবাহ নিয়ন্ত্রণ করে; ফলে যুক্তি অনুসরণ করা সহজ।

বৈশিষ্ট্য	Paxos	Raft
তৈরি	1998, Lamport	2014, Stanford
মূল লক্ষ্য	তাত্ত্বিক correctness	বোঝা সহজ করা
Leader	ঐচ্ছিক (multi-Paxos-এ লাগে)	সবসময় একজন শক্তিশালী leader
শেখা/বানানো	কঠিন	তুলনামূলক সহজ
জনপ্রিয়তা	পুরোনো বড় সিস্টেমে	নতুন সিস্টেমে বহুল ব্যবহৃত

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

ব্যবহার করবে যখন একাধিক node-কে strongly consistent থাকতে হবে—যেমন distributed lock, leader election, configuration store, metadata management, কিংবা যেখানে "একটাই সত্য" থাকা জরুরি।

করবে না যখন তোমার শুধু high availability দরকার আর সামান্য inconsistency সমস্যা নয় (যেমন social media-র like count)। সেখানে eventual consistency যথেষ্ট, এবং consensus-এর overhead অপচয়।

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

• etcd (Raft ব্যবহার করে): Kubernetes-এর সব cluster state—কোন pod কোথায় চলছে, কী configuration—এই key-value store-এ রাখা হয়। Kubernetes control plane সাধারণত ৩ বা ৫টা etcd node চালায়, যাতে একটা/দুটো node গেলেও cluster অচল না হয়।
• ZooKeeper (ZAB নামে নিজস্ব Paxos-সদৃশ protocol): Apache Kafka, HBase, এবং বহু বড় সিস্টেম coordination, leader election ও configuration-এর জন্য ZooKeeper ব্যবহার করত/করে।
• Consul ও CockroachDBও Raft ব্যবহার করে নিজেদের distributed consistency নিশ্চিত করতে।

এই সব সিস্টেমেই মূল ধারণা এক—কিছু node হারালেও যেন "সত্য" একটাই থাকে এবং split-brain না ঘটে।