Consensus (Raft, Paxos) - কয়েকটা server যেভাবে একমত হয়

০০ যে প্রশ্নগুলোর উত্তর খুঁজবো

আগের সেশনগুলোতে একটা প্রশ্ন আমরা বারবার পাশ কাটিয়ে গেছি। সেশন ০৩ এ primary down হলে replica কে promote করার কথা বলেছিলাম, কিন্তু কে নিশ্চিত হয়ে বলবে যে primary সত্যিই down? সেশন ১৫ এ quorum দেখেছি, কিন্তু node গুলো আসলে কীভাবে একমত হয়, সেটা দেখিনি।

এই সেশনে সেই প্রশ্নের উত্তর খুঁজবো। একটা রাতের একটা ঘটনা ধরে ধরে আমরা Raft শিখবো, তারপর তার বড় ভাই Paxos এর সাথে পরিচয় হবে। শেষে আপনি বুঝবেন, Kubernetes বা Kafka এর মতো system এর একদম ভেতরে কোন নিয়মটা চুপচাপ সব ঠিক রাখে।

০১ তিনটা server কে একটা সত্যে একমত করানো এত কঠিন কেন?

রাত তিনটা বারো। ফারহানা একটা food delivery কোম্পানির backend engineer, আর আজ রাতে on-call এ শুধু সে-ই জেগে আছে। হঠাৎ phone এ alert বেজে উঠলো: cfg-1 unreachable। ফারহানার বুক ধক করে উঠলো, কারণ cfg-1 ছিলো config cluster এর leader। Dashboard খুলে সে দেখলো, প্রায় ৩০০ ms এর মধ্যেই cfg-3 নতুন leader হয়ে গেছে, আর একটা order ও আটকায়নি। স্বস্তি নিয়ে চা বানাতে উঠলো সে। কিন্তু মাথায় একটা প্রশ্ন ঘুরতেই থাকলো: কেউ তো ভোট গুনতে বসেনি, তিনটা machine নিজেরা নিজেরা একমত হলো কীভাবে?

Config cluster টা কী রাখে

এই cluster এ তিনটা server: cfg-1, cfg-2 আর cfg-3। এরা কোম্পানির ছোট কিন্তু খুব জরুরি কিছু তথ্য রাখে। যেমন এখন কোন database primary (db_primary), কোন payment gateway চালু, কোন offer চালু (promo_on)। ঢাকার order সামলানো প্রায় ২০০টা app server প্রতি কয়েক সেকেন্ডে এখান থেকে এসব settings পড়ে।

Server একটা রাখলে সেটা হতো SPOF, মানে single point of failure (সেশন ০১)। ওটা down হলে ২০০টা app server এর কেউই জানতো না কোন database এ লিখতে হবে। তাই কপি তিনটা। কিন্তু তিনটা কপি রাখলেই নতুন একটা দায়িত্ব আসে: তিনজনকে সবসময় একই কথা বলতে হবে।

ধরুন cfg-1 বলছে db_primary হলো db-a, আর cfg-2 বলছে db-b। তখন অর্ধেক app server এক database এ লিখবে, বাকি অর্ধেক আরেকটায়। দুই database এর data আলাদা হয়ে যাবে। এটাই সেশন ০৩ এর split brain, শুধু অন্য চেহারায়।

কয়েকটা server মিলে একটা মান নিয়ে একমত হওয়ার এই কাজটার নাম consensus। আরেকটু ঠিক করে বললে, consensus মানে কয়েকটা server একটা মান (বা একটার পর একটা মানের list) নিয়ে এমনভাবে একমত হয়, যাতে কিছু server crash করলে বা network গোলমাল করলেও একবার নেওয়া সিদ্ধান্ত আর কখনো বদলায় না।

একমত হওয়া কেন কঠিন

চায়ের দোকানে বসে তিন বন্ধু পিকনিকের জায়গা ঠিক করলে কাজটা সহজ। সবাই সামনাসামনি, কথা সাথে সাথে পৌঁছায়। এবার ভাবুন, তিন বন্ধু তিন শহরে, আর কথা হচ্ছে শুধু SMS এ। কোনো SMS দেরিতে আসে, কোনোটা আসেই না, আর কারো phone হঠাৎ বন্ধ হয়ে যায়। Server দের অবস্থা ঠিক এমন। তিনটা সমস্যা একসাথে চলে:

1. Crash: একটা server কাজের মাঝখানে থেমে যেতে পারে। হয়তো একজনকে খবরটা দিয়েছে, আরেকজনকে দেওয়ার আগেই বন্ধ হয়ে গেছে।
2. Delay: Network এ message দেরিতে আসে, উল্টো ক্রমে আসে, বা হারিয়ে যায়। একই data center এর ভেতরে যে message সাধারণত ১ ms এ পৌঁছায়, কখনো কখনো সেটাতেই ২ সেকেন্ড লেগে যায়।
3. Shared clock নেই: প্রতিটা machine এর ঘড়ি একটু একটু আলাদা চলে। তাই কার write আগে হয়েছে, সেটা timestamp দেখে নিশ্চিত বলা যায় না।

সবচেয়ে কঠিন কথাটা হলো, বাইরে থেকে একটা crash করা server আর একটা ধীর server দেখতে হুবহু এক।

০২ সবার না, শুধু majority quorum এর সম্মতি কেন যথেষ্ট?

সেশন ১৫ এ quorum দেখেছেন: একটা কাজ সফল ধরার জন্য কমপক্ষে কয়টা node এর সম্মতি লাগে, সেই সংখ্যা। Consensus এ এই সংখ্যাটা সবসময় majority, মানে মোট node এর অর্ধেকের চেয়ে বেশি। একে বলে majority quorum। ৩টা node এ majority হলো ২, আর ৫টা node এ ৩।

প্রশ্ন আসে, সবার সম্মতি নিলেই তো সবচেয়ে নিরাপদ। নিরাপদ ঠিকই, কিন্তু অচল। তিনটার একটা down থাকলে “সবার সম্মতি” আর কখনো পাওয়া যাবে না, আর cluster একটা write ও নিতে পারবে না। Majority লাগলে একটা server down থাকলেও বাকি দুইটা দিয়ে কাজ চলে।

উল্টো দিকে, একজনের সম্মতি কেন যথেষ্ট নয়? কারণ তখন দুইটা server দুইটা আলাদা সিদ্ধান্ত নিয়ে ফেলতে পারে, আর কেউ কারো খবর জানবে না। Majority এর আসল গুণ অন্য জায়গায়:

যেকোনো দুইটা majority তে অন্তত একটা node common থাকে।

ক্লাসের ৪০ জনের মধ্যে ২১ জন বললো, “পিকনিক কক্সবাজারে।” এখন আরেকটা আলাদা ২১ জনের দল কখনো “সিলেটে” বলে সিদ্ধান্ত পাস করাতে পারবে না। কারণ দুই দল মিলে ৪২ জন লাগে, অথচ ক্লাসে আছে ৪০ জন। অন্তত দুইজন দুই দলেই আছে, আর তারা আগের সিদ্ধান্তের কথা জানে।

ফারহানার cluster এ এর মানে কী? db_primary বদলানোর লেখাটা ছিলো log এর #41 নম্বর entry (log কী, সেটা ০৫ নম্বর সেকশনে দেখবো)। #41 একবার majority তে পৌঁছালে, পরের যেকোনো majority তে অন্তত একজন থাকবে যার কাছে #41 আছে। Cluster এর স্মৃতি এভাবেই টিকে থাকে। পরের সেকশনগুলোতে এই একটা সত্য বারবার কাজে লাগবে।

০৩ Raft এ leader, follower, candidate আর term কী?

Consensus এর সবচেয়ে জনপ্রিয় algorithm এখন Raft। ২০১৪ সালে Stanford এর Diego Ongaro আর John Ousterhout এটা প্রকাশ করেন। তাঁদের মূল লক্ষ্য ছিলো এমন একটা algorithm বানানো, যেটা সাধারণ engineer রা পড়ে বুঝতে পারে। Raft এর মূল idea সহজ। একসময়ে cluster এ একজনই leader থাকে। সব write leader এর কাছে যায়, আর leader সেটা বাকিদের কাছে copy করে।

Raft এ প্রতিটা server তিনটা role এর যেকোনো একটায় থাকে:

• Follower: চুপচাপ থাকে। Leader এর কথা শোনে, entry জমা রাখে, আর election এ vote দেয়। শুরুতে সবাই follower।
• Candidate: একজন follower অনেকক্ষণ leader এর কোনো খবর না পেলে নিজেই candidate হয়, আর সবার কাছে vote চায়।
• Leader: Client এর সব write নেয়, follower দের কাছে copy করে, আর প্রতি ৫০ ms এ heartbeat পাঠিয়ে জানায় “আমি আছি।” Heartbeat হলো নিয়মিত ছোট একটা “বেঁচে আছি” বার্তা, যেটা সেশন ০২ এ load balancer এর সাথে দেখেছেন।

Term: Raft এর নিজের ঘড়ি

০১ নম্বর সেকশনে দেখেছি, machine গুলোর মধ্যে shared clock নেই। Raft এই সমস্যা এড়ায় একটা সাধারণ সংখ্যা দিয়ে, যার নাম term। Term হলো election এর ক্রমিক নম্বর। প্রতিটা নতুন election এ term এক করে বাড়ে, আর এক term এ বড়জোর একজন leader থাকে। ফারহানার রাতে cfg-1 ছিলো term 7 এর leader। Election এর পর cfg-3 হলো term 8 এর leader।

Term এর নিয়ম তিনটা, আর তিনটাই সহজ:

1. প্রতিটা message এর সাথে পাঠানো server নিজের term লিখে দেয়।
2. কেউ নিজের চেয়ে বড় term দেখলে সাথে সাথে নিজের term আপডেট করে, আর follower হয়ে যায়। সে leader হলেও।
3. নিজের চেয়ে ছোট term এর message এলে সেটা বাতিল করে দেয়, কারণ ওটা পুরোনো সময়ের খবর।

০৪ Leader down হলে randomized timeout দিয়ে leader election কীভাবে হয়?

Leader প্রতি ৫০ ms এ heartbeat পাঠায়। প্রতিটা follower এর একটা election timeout থাকে: এই সময়ের মধ্যে heartbeat না এলে সে ধরে নেয় leader নেই। এই timeout টা fixed নয়। প্রতিবার ১৫০ থেকে ৩০০ ms এর মধ্যে random একটা মান বেছে নেওয়া হয়। একে বলে randomized timeout। কেন random, সেটা একটু পরেই দেখবো। আগে ফারহানার রাতটা ধাপে ধাপে দেখি। নতুন leader বেছে নেওয়ার এই পুরো কাজটার নাম leader election।

1. ০ ms: cfg-1 এর network card fail করলো। শেষ heartbeat এর পর আর কিছু আসছে না।
2. অপেক্ষা: cfg-2 এর random timer ২৯৮ ms, আর cfg-3 এর ২৮৬ ms। দুজনেই চুপচাপ অপেক্ষা করছে।
3. ২৮৬ ms: cfg-3 এর timer আগে শেষ হলো। সে term 7 থেকে term 8 এ গেলো, candidate হলো, নিজেকে একটা vote দিলো। তারপর cfg-1 আর cfg-2 কে RequestVote message পাঠালো, মানে “আমাকে vote দিন” অনুরোধ।
4. ২৮৭ ms: cfg-2 এখনো term 8 এ কাউকে vote দেয়নি। সে cfg-3 কে vote দিলো, আর নিজের timer আবার শুরু থেকে চালু করলো।
5. ২৮৮ ms: cfg-3 এর হাতে এখন ৩টার মধ্যে ২টা vote, মানে majority। সে term 8 এর leader।
6. প্রায় ২৯০ ms: নতুন leader সাথে সাথে heartbeat পাঠালো। cfg-2 এর timer reset হলো, তাই সে আর candidate হলো না।

ফারহানার dashboard এ যে ৩০০ ms দেখাচ্ছিলো, তার প্রায় পুরোটাই ছিলো অপেক্ষা: leader সত্যিই নেই কিনা, সেটা নিশ্চিত হওয়ার সময়। আসল ভোটাভুটিতে লেগেছে মাত্র ২ ms।

একটা server এক term এ মাত্র একবার vote দেয়, আর vote টা disk এ লিখে রাখে। তাই restart করেও একই term এ দ্বিতীয়বার vote দিতে পারে না। এক term এ দুইজন majority পাবে না, এই নিশ্চয়তা এখান থেকেই আসে।

Timeout random কেন

ধরুন দুজনের timer ই ঠিক ২০০ ms। তখন cfg-2 আর cfg-3 একসাথে candidate হবে। দুজনেই নিজেকে vote দেবে, আর একে অপরকে vote দেবে না, কারণ এই term এর vote তো দেওয়া হয়ে গেছে। দুজনের হাতে ১টা করে vote, majority কারো নেই। একে বলে split vote। Timer আবার একসাথে শেষ হলে একই ঘটনা চলতেই থাকবে।

Random timer এই অচলাবস্থা ভাঙে। একই data center এ একটা message যেতে আর ফিরতে ১ ms এর মতো লাগে। দুইটা random timer এর ব্যবধান সাধারণত এর চেয়ে অনেক বেশি; ফারহানার রাতে সেটা ছিলো ১২ ms। তাই একজন প্রায় সবসময় আগে জাগে, আর অন্যজন জাগার আগেই vote চেয়ে জিতে যায়। তবু কখনো split vote হলে term আরো এক বাড়ে, সবাই নতুন random timer নেয়, আর এক দুই round এর মধ্যেই কেউ জিতে যায়।

heartbeat interval   = 50 ms
election timeout     = random(150, 300) ms    # প্রতিবার নতুন করে বাছা হয়
round trip           = ~1 ms                  # একই data center এর ভেতরে

ফারহানার রাত:
  cfg-2 timer = 298 ms
  cfg-3 timer = 286 ms    # আগে শেষ, ব্যবধান 12 ms
  ব্যবধান / round trip = 12 / 1 = 12 গুণ

etcd এর default: heartbeat 100 ms, election timeout 1000 ms

০৫ একটা write কীভাবে সবার কাছে পৌঁছায়?

Leader বেছে নেওয়া গেলো। কিন্তু leader এর আসল কাজ হলো data নিরাপদে কয়েক জায়গায় রাখা। Raft প্রতিটা পরিবর্তনকে একটা log এ entry হিসেবে লেখে। Log হলো হিসাবের খাতার মতো: পুরোনো লাইন বদলায় না, নতুন লাইন শুধু শেষে যোগ হয়।

প্রতিটা entry তে তিনটা জিনিস থাকে: index (ক্রমিক নম্বর), term (কোন leader এর আমলে লেখা), আর command (যেমন SET db_primary = db-b)। সব server একই log একই ক্রমে apply করলে সবার data ও হুবহু এক হয়। এই log সবার কাছে হুবহু একরকম রাখার কাজটাকে বলে log replication।

উদাহরণ: #41 কীভাবে commit হলো

Network fail করার ছয় সেকেন্ড আগে, রাত ৩:১১:৫৮ এ, database টিমের একটা script SET db_primary = db-b পাঠিয়েছিলো। পুরোনো primary db-a এর disk ভরে আসছিলো, তাই এই বদল। তখনো cfg-1 leader। এই একটা write এর যাত্রা দেখুন:

1. Script টা leader cfg-1 এর কাছে command পাঠালো।
2. cfg-1 সেটা নিজের log এ #41 হিসেবে disk এ লিখলো। কিন্তু এখনো apply করেনি, কারণ entry টা এখনো শুধু তার কাছেই আছে।
3. cfg-1 একসাথে cfg-2 আর cfg-3 কে AppendEntries message এ #41 পাঠালো। এই message টাই leader এর “এই entry গুলো log এর শেষে যোগ করুন” অনুরোধ, আর খালি AppendEntries টাই heartbeat হিসেবে কাজ করে।
4. cfg-2 নিজের disk এ লিখে ১ ms এর মধ্যে OK দিলো। cfg-3 তখন একটা GC pause এ আটকে ছিলো (Java এর garbage collector কিছু সময়ের জন্য পুরো program থামিয়ে মেমরি পরিষ্কার করে), তাই একটু পিছিয়ে পড়লো।
5. এখন #41 আছে ৩টার মধ্যে ২টায়, মানে majority তে। cfg-1 #41 কে committed ধরলো, নিজের key-value store এ apply করলো, আর script কে success জানালো।
6. পরের heartbeat এ leader জানিয়ে দিলো commit index = 41। Follower রাও তখন #41 apply করলো। cfg-3 কয়েক ms পরে ধরে ফেললো, কারণ পিছিয়ে থাকা follower কে leader বারবার পাঠাতেই থাকে।

Commit মানে: একটা entry majority তে পৌঁছে গেছে। এরপর সেটা আর কখনো হারাবে না, বদলাবেও না। Commit index হলো সবচেয়ে বড় committed entry র নম্বর। এই নম্বর পর্যন্ত সব entry নিশ্চিন্তে apply করা যায়।

উপরের ছবিটা রাত ৩:১২:০৪ এর, ঠিক যে মুহূর্তে network fail করলো। #41 তিনজনের কাছেই আছে, কারণ cfg-3 ততক্ষণে ধরে ফেলেছে। কিন্তু #42 শুধু cfg-1 এর কাছে। সেটার গল্প পরের সেকশনে।

একটা write এর খরচ

প্রতিটা write কে majority তে পৌঁছাতে হয়। প্রতিটা server কে disk এ পাকাপাকি লিখে (fsync করে) তবেই OK বলতে হয়। একই data center এ round trip ১ ms এর মতো, আর SSD তে fsync এ আরো কয়েক ms। তাই Raft এর একটা write সাধারণত কয়েক ms নেয়। Memory তে লেখা একটা Redis write এর তুলনায় এটা অনেক ধীর। এই বাড়তি সময়টুকুই নিরাপত্তার খরচ।

০৬ Leader বদলালেও committed entry কেন হারায় না?

#42 এর কী হলো

রাত ৩:১২:০৩.৯৯০, network fail করার মাত্র ১০ ms আগে। Marketing টিমের একটা tool পাঠালো SET promo_on = true। cfg-1 সেটা নিজের log এ #42 হিসেবে লিখলো, তারপর AppendEntries পাঠাতে গেলো। কিন্তু তার আগেই network card বন্ধ হয়ে গেলো। #42 আছে ৩ জনের মধ্যে মাত্র ১ জনের কাছে, তাই সেটা committed নয়। Tool টা success পায়নি; কয়েক সেকেন্ড পর timeout পেলো।

নতুন leader cfg-3 এর log #41 এ শেষ। তার কাছে term 7 এর কোনো #42 নেই। Term 8 এ cfg-3 যে নতুন entry গুলো নেবে (যেমন SET surge_limit = 1.2), সেগুলো #42 নম্বর থেকেই বসবে।

রাত ৩:২০ এ data center এর লোকজন cfg-1 এর network card বদলে দিলেন। cfg-1 ফিরে এসে term 8 এর heartbeat পেলো। বড় term দেখে সে চুপচাপ follower হয়ে গেলো। তারপর leader তার log মিলিয়ে দেখলো।

মেলানোর নিয়মটা সহজ। Leader প্রতিটা AppendEntries এর সাথে ঠিক আগের entry র index আর term পাঠায়। Follower এর log এ ঐ জায়গায় একই term এর entry না থাকলে সে “না” বলে দেয়। Leader তখন এক ধাপ পিছিয়ে আবার চেষ্টা করে। এভাবে যেখান থেকে দুজনের log আলাদা হয়েছে, সেখানে পৌঁছে leader নিজের entry গুলো বসিয়ে দেয়। cfg-1 এর ক্ষেত্রে #41 পর্যন্ত মিললো, #42 মিললো না। তাই cfg-1 নিজের পুরোনো #42 মুছে leader এর #42 copy করে নিলো।

এটা কি data হারানো? না। #42 কখনো commit হয়নি, আর tool টা কখনো success পায়নি। Tool টা timeout পেয়ে আবার চেষ্টা করলে নতুন leader এর কাছে লেখা হবে। Raft এর প্রতিশ্রুতি হলো committed entry কখনো হারাবে না। Uncommitted entry হারাতে পারে, আর client সেটা জানে, কারণ সে success পায়নি।

পুরোনো log নিয়ে কেউ leader হতে পারে না কেন

একটা ভয় তবু থেকে যায়। এমন কেউ যদি leader হয়ে যায়, যার কাছে #41 নেই? তাহলে তো সে নিজের log সবার উপর বসিয়ে দেবে, আর committed #41 মুছে যাবে। Raft এটা আটকায় vote দেওয়ার একটা নিয়ম দিয়ে:

এখানে ০২ নম্বর সেকশনের সেই সত্যটা কাজে লাগে। #41 committed মানে সেটা majority র কাছে আছে। Leader হতে হলে candidate কে majority র vote পেতে হবে। দুইটা majority তে অন্তত একজন common, আর সেই common জন #41 ছাড়া কোনো candidate কে vote দেবে না। তাই যে জিতবে, তার কাছে #41 থাকবেই।

ফারহানার রাতে ব্যাপারটা কেমন হতো, একবার ভাবুন। ধরুন cfg-3 তখনো GC pause থেকে ধরে উঠতে পারেনি, তার শেষ entry #40। তাহলে cfg-2 তাকে vote দিতো না। মাত্র ১২ ms পরে cfg-2 এর নিজের timer শেষ হতো। সে term 9 এ candidate হতো, আর cfg-3 তাকে vote দিতো, কারণ cfg-2 এর log বেশি নতুন। Election এ কয়েক ms বেশি লাগতো, কিন্তু #41 হারাতো না।

০৭ Network partition এ split brain কীভাবে আটকায়?

সেশন ০৩ এ split brain দেখেছেন: একসাথে দুইটা primary, দুটোই write নিচ্ছে, আর দুই জায়গার data আলাদা হয়ে যাচ্ছে। Raft এটা কীভাবে আটকায়, সেটা ৫ node এর একটা cluster এ সবচেয়ে পরিষ্কার দেখা যায়।

ধরুন পরের বছর ফারহানার টিম cluster টা ৫ node এ বাড়ালো: cfg-1 থেকে cfg-5। একদিন একটা network switch খারাপ হয়ে network দুই ভাগ হয়ে গেলো। এক পাশে cfg-1 (তখনকার leader) আর cfg-2, অন্য পাশে cfg-3, cfg-4 আর cfg-5। Network এর এভাবে দুই ভাগ হয়ে যাওয়াকে বলে network partition, যেটা সেশন ১৫ এ দেখেছেন।

• ছোট পাশ (২টা node): cfg-1 জানে না যে সে আলাদা হয়ে গেছে। তাই নিজেকে এখনো term 7 এর leader ভাবে, আর write নিতে থাকে। কিন্তু OK আসে শুধু cfg-2 থেকে, মানে ৫ এর মধ্যে ২। এটা majority নয়, তাই কোনো write commit হয় না। Client রা success পায় না, timeout পায়।
• বড় পাশ (৩টা node): Heartbeat না পেয়ে cfg-3 term 8 এ election চালায়। সে ৩টা vote পায়, যা ৫ এর majority, তাই leader হয়। এই পাশে write commit হয়, কারণ ৩টা OK পাওয়া যায়।

অর্থাৎ কিছুক্ষণের জন্য দুইজন নিজেকে leader ভাবছে ঠিকই, কিন্তু commit করতে পারছে শুধু একজন। ফলে data দুই ভাগ হয় না। Network ঠিক হলে cfg-1 term 8 দেখে follower হয়ে যায়, আর তার uncommitted entry গুলো আগের সেকশনের মতো মুছে যায়।

একটা সূক্ষ্ম ফাঁক তবু থাকে: read। পুরোনো leader cfg-1 এর কাছে কেউ db_primary পড়তে চাইলে সে নিজের পুরোনো মান দিয়ে দিতে পারে। তাই etcd এর মতো system read এর উত্তর দেওয়ার আগে leader একবার heartbeat পাঠিয়ে নিশ্চিত হয় যে majority এখনো তাকে leader মানে। এতে read একটু ধীর হয়, কিন্তু বাসি উত্তর আসে না।

০৮ Cluster এ ৩ বা ৫টা node কেন, ২ বা ৪টা নয়?

উত্তরটা majority quorum এর হিসাব থেকেই আসে। N টা node এর cluster এ majority কত, আর cluster একসাথে কয়টা node হারিয়েও চলতে পারে, সেটা নিচের দুইটা সূত্রে:

majority(N) = floor(N / 2) + 1
tolerate(N) = N - majority(N)          # কয়টা node একসাথে fail করলেও চলে

N = 5:  majority = floor(2.5) + 1 = 3
        tolerate = 5 - 3 = 2
N = 4:  majority = 2 + 1 = 3
        tolerate = 4 - 3 = 1           # N = 3 এর সমান, কিন্তু machine একটা বেশি

টেবিল থেকে তিনটা কথা বেরিয়ে আসে:

1. ২টা node একটার চেয়েও খারাপ: দুইটাই majority তে লাগে, তাই একটা down হলেই cluster থেমে যায়। অথচ machine লাগছে দ্বিগুণ।
2. জোড় সংখ্যায় লাভ নেই: ৪টা node ও ৩টার মতো মাত্র ১টা failure সহ্য করে, কিন্তু একটা machine বেশি চালাতে হয়। তার উপর network ঠিক ২ আর ২ এ ভাগ হলে কোনো পাশেই majority থাকে না, আর পুরো cluster write নেওয়া বন্ধ করে দেয়।
3. বেশি node মানে ধীর write: ৭টা node এ প্রতিটা write কে ৪টা OK এর জন্য অপেক্ষা করতে হয়, আর leader কে ৬ জনের কাছে copy পাঠাতে হয়।

তাই বাস্তবে প্রায় সবাই ৩ বা ৫ বেছে নেয়। ৩টা node একটা failure সহ্য করে, আর বেশিরভাগ ক্ষেত্রে এটুকুই যথেষ্ট। ৫টা node দুইটা failure সহ্য করে। ফলে একটা server এ maintenance চলার সময় আরেকটা হঠাৎ fail করলেও cluster চলতে থাকে।

০৯ Paxos কী, আর etcd, ZooKeeper, Consul, Kafka KRaft এ consensus কোথায় চলে?

Paxos: Raft এর বড় ভাই

Raft আসার অনেক আগে, ১৯৮৯ সালে, Leslie Lamport Paxos লিখেছিলেন। Paper টা প্রকাশ হয় ১৯৯৮ সালে। সেটা লেখা ছিলো Paxos নামের এক কাল্পনিক গ্রিক দ্বীপের সংসদের গল্প হিসেবে, যেখানে সাংসদরা যখন খুশি সংসদে আসেন আর চলে যান। Algorithm টা নির্ভুল, কিন্তু বোঝা এত কঠিন যে ২০০১ সালে Lamport কে “Paxos Made Simple” নামে আরেকটা paper লিখতে হয়েছিলো। Raft এর জন্মই হয়েছিলো এই কঠিনতা কমানোর জন্য।

Basic Paxos একটা মাত্র মান নিয়ে একমত হয়, দুই ধাপে। এখানে role দুইটা: proposer মান প্রস্তাব করে, আর acceptor রা ভোট দেয়।

1. Prepare আর promise: Proposer একটা unique proposal number বেছে নেয় (এখানে 5), যেটা আগের সব number এর চেয়ে বড়। সে acceptor দের বলে prepare(5)। প্রতিটা acceptor কথা দেয়: এখন থেকে ৫ এর ছোট কোনো proposal সে আর মানবে না। আগে কোনো মান accept করে থাকলে সেটাও জানিয়ে দেয়।
2. Accept আর accepted: Majority কথা দিলে proposer আসল মানটা পাঠায়: accept(5, db-b)। একটা কড়া নিয়ম আছে। কোনো acceptor আগে কোনো মান accept করে থাকলে, proposer কে নিজের মান বাদ দিয়ে সেই মানটাই পাঠাতে হয়। Acceptor রা এর মধ্যে বড় কোনো number কে কথা না দিয়ে থাকলে মানটা accept করে। Majority accept করলেই মানটা chosen, আর সেটা কখনো বদলাবে না।

চেনা চেনা লাগছে? Proposal number অনেকটা Raft এর term এর মতো, আর এখানেও সব সিদ্ধান্ত majority দিয়ে। একটার পর একটা মান নিয়ে, মানে পুরো একটা log নিয়ে একমত হতে Paxos কে বারবার চালাতে হয়। এই রূপটাকে বলে Multi-Paxos। সেখানে একজন স্থায়ী leader প্রথম ধাপটা বারবার না করে শুধু দ্বিতীয় ধাপ চালায়। তখন সেটা দেখতে অনেকটা Raft এর মতোই হয়ে যায়।

Consensus কোথায় চলে

আপনি নিজে হয়তো কখনো Raft লিখবেন না। কিন্তু প্রায় প্রতিটা বড় system এর ভেতরে কোথাও না কোথাও এটা চলছে:

• etcd: Raft দিয়ে বানানো একটা key-value store। Kubernetes তার পুরো cluster এর অবস্থা etcd তে রাখে: কোন container কোন machine এ চলছে, কোন configuration চালু।
• Consul: HashiCorp এর service discovery আর configuration এর tool। এর ৩ বা ৫টা server node নিজেদের মধ্যে Raft চালায়। Service discovery নিয়ে বিস্তারিত সেশন ১৪ এ।
• ZooKeeper: Apache এর পুরোনো আর বহুল ব্যবহৃত coordination service। এটা ZAB (ZooKeeper Atomic Broadcast) নামের নিজস্ব protocol চালায়, যেটা Paxos এর খুব কাছাকাছি। Hadoop, HBase আর পুরোনো Kafka এর উপর নির্ভর করতো। সেশন ০৯ এর distributed lock প্রায়ই ZooKeeper বা etcd দিয়ে বানানো হয়।
• Kafka KRaft: আগে Kafka তার metadata রাখতে আলাদা একটা ZooKeeper cluster চালাতো। Metadata মানে কোন topic কোথায়, কোন broker কোন partition এর leader। এখন KRaft mode এ Kafka এর নিজের কয়েকটা controller node Raft দিয়ে এগুলো রাখে। Kafka 4.0 (২০২৫) থেকে ZooKeeper পুরোপুরি বাদ।

সবগুলোর pattern একই। একটা ছোট consensus cluster পুরো system এর “সত্য” টুকু রাখে: কে leader, কোন configuration চালু, কোন lock কার হাতে। বড় data, যেমন কোটি কোটি order, থাকে অন্য database এ।

১০ মগজে প্রেশার দিন

আগে নিজে ভাবুন। তারপর উত্তর খুলে দেখুন: বেশিরভাগ মানুষ কীভাবে ভাবে, সেই চিন্তায় কী বাদ পড়ে, আর আসল কথাটা কোথায়।

১১ যে টার্মগুলো শিখলাম

১২ শর্ট সামারি

১৩ মনে রাখুন

• Consensus দ্রুততার না, নির্ভুলতার প্রতিশ্রুতি দেয়। খারাপ network এ সিদ্ধান্ত দেরিতে আসতে পারে, কিন্তু দুইটা আলাদা সিদ্ধান্ত কখনো হয় না।
• সব সিদ্ধান্ত majority দিয়ে। দুইটা majority সবসময় একটা node এ মেলে, আর সেই node আগের সিদ্ধান্ত মনে রাখে।
• বড় term সবসময় জেতে। নিজের চেয়ে বড় term দেখলে leader ও চুপচাপ follower হয়ে যায়।
• Random timeout split vote ভাঙে। একজন প্রায় সবসময় আগে জাগে, আর অন্যজন জাগার আগেই জিতে যায়।
• Majority তে পৌঁছালে তবেই commit। Client success পায় এর পরেই; uncommitted entry মুছে যেতে পারে, committed entry কখনো না।
• Node সংখ্যা ৩ বা ৫ রাখুন। জোড় সংখ্যা বাড়তি failure সহ্য করে না, শুধু খরচ বাড়ায়।
• Consensus cluster এ ছোট আর জরুরি data রাখুন। কে leader, কোন database primary, কোন lock কার; বড় data অন্য database এ।