تو، آئیے تصور کریں۔ کمرے میں 5 بلیاں بند ہیں، اور مالک کو جگانے کے لیے، ان سب کو آپس میں اس پر متفق ہونا ضروری ہے، کیونکہ وہ صرف پانچ بلیوں کے ساتھ ٹیک لگا کر ہی دروازہ کھول سکتی ہیں۔ اگر بلیوں میں سے ایک شروڈنگر کی بلی ہے، اور دوسری بلیوں کو اس کے فیصلے کے بارے میں معلوم نہیں ہے، تو سوال پیدا ہوتا ہے: "وہ یہ کیسے کر سکتی ہیں؟"
اس مضمون میں، میں آپ کو تقسیم شدہ نظاموں کی دنیا کے نظریاتی جزو اور ان کے آپریشن کے اصولوں کے بارے میں آسان الفاظ میں بتاؤں گا۔ میں Paxos کے بنیادی خیال پر بھی سطحی طور پر غور کروں گا۔
جب ڈویلپرز کلاؤڈ انفراسٹرکچر، مختلف ڈیٹا بیسز، اور نوڈس کی ایک بڑی تعداد کے کلسٹرز میں کام کرتے ہیں، تو انہیں یقین ہوتا ہے کہ ڈیٹا مکمل، محفوظ اور ہمیشہ دستیاب ہوگا۔ لیکن ضمانتیں کہاں ہیں؟
بنیادی طور پر، ہمارے پاس جو ضمانتیں ہیں وہ سپلائر کی ضمانتیں ہیں۔ دستاویزات میں ان کی وضاحت اس طرح کی گئی ہے: "یہ سروس کافی قابل اعتماد ہے، اس میں ایک SLA دیا گیا ہے، فکر نہ کریں، ہر چیز آپ کی توقع کے مطابق تقسیم کے ساتھ کام کرے گی۔"
ہم بہترین پر یقین رکھتے ہیں، کیونکہ بڑی کمپنیوں کے ہوشیار لوگوں نے ہمیں یقین دلایا کہ سب کچھ ٹھیک ہو جائے گا۔ ہم یہ سوال نہیں پوچھتے: کیوں، حقیقت میں، یہ بالکل کام کر سکتا ہے؟ کیا ایسے نظاموں کے درست آپریشن کا کوئی باقاعدہ جواز ہے؟
میں حال ہی میں گیا تھا۔ اور اس موضوع سے بہت متاثر ہوا۔ اسکول میں لیکچرز کمپیوٹر سسٹم سے متعلق کسی چیز سے زیادہ کیلکولس کلاسز کی طرح تھے۔ لیکن یہ بالکل اسی طرح ہے کہ سب سے اہم الگورتھم جو ہم ہر روز استعمال کرتے ہیں، یہاں تک کہ یہ جانے بغیر، ایک وقت میں ثابت ہوئے تھے۔
زیادہ تر جدید تقسیم شدہ نظام Paxos اتفاق رائے الگورتھم اور اس کی مختلف ترمیمات کا استعمال کرتے ہیں۔ سب سے اچھی بات یہ ہے کہ درستگی اور اصولی طور پر اس الگورتھم کے وجود کے امکان کو محض قلم اور کاغذ سے ثابت کیا جا سکتا ہے۔ عملی طور پر، الگورتھم بڑے سسٹمز میں استعمال ہوتا ہے جو بادلوں میں بہت زیادہ نوڈس پر چلتے ہیں۔
آگے کیا بات کی جائے گی اس کی ایک ہلکی سی مثال: دو جرنیلوں کا کامآئیے وارم اپ کے لیے ایک نظر ڈالتے ہیں۔ .
ہمارے پاس دو لشکر ہیں - سرخ اور سفید۔ سفید فام دستے محصور شہر میں مقیم ہیں۔ جنرل A1 اور A2 کی قیادت میں سرخ دستے شہر کے دو اطراف میں موجود ہیں۔ ریڈ ہیڈز کا کام سفید شہر پر حملہ کرنا اور جیتنا ہے۔ تاہم انفرادی طور پر ہر سرخ جرنیل کی فوج سفید فوج سے چھوٹی ہوتی ہے۔
سرخوں کے لیے فتح کے حالات: گوروں پر عددی برتری حاصل کرنے کے لیے دونوں جرنیلوں کو ایک ہی وقت میں حملہ کرنا چاہیے۔ ایسا کرنے کے لیے، جنرلز A1 اور A2 کو ایک دوسرے کے ساتھ معاہدہ کرنے کی ضرورت ہے۔ اگر سب الگ الگ حملہ کرتے ہیں تو سرخ بالوں والے کھو جائیں گے۔
ایک معاہدے تک پہنچنے کے لیے، جنرل A1 اور A2 سفید شہر کے علاقے کے ذریعے ایک دوسرے کو پیغام رساں بھیج سکتے ہیں۔ قاصد کامیابی سے کسی اتحادی جنرل تک پہنچ سکتا ہے یا دشمن کی طرف سے روکا جا سکتا ہے۔ سوال: کیا سرخ بالوں والے جرنیلوں (A1 سے A2 اور اس کے برعکس A2 سے A1 تک میسنجر بھیجنے کا سلسلہ) کے درمیان بات چیت کا ایسا سلسلہ ہے جس میں انہیں X گھنٹے پر حملے پر اتفاق کرنے کی ضمانت دی گئی ہے۔ یہاں، ضمانتوں کا مطلب یہ ہے کہ دونوں جرنیلوں کو اس بات کی غیر واضح تصدیق ہوگی کہ ایک اتحادی (دوسرا جنرل) مقررہ وقت پر ضرور حملہ کرے گا۔
فرض کریں کہ A1 ایک میسنجر کو A2 کو اس پیغام کے ساتھ بھیجتا ہے: "آئیے آج آدھی رات کو حملہ کریں!" جنرل A1 جنرل A2 کی تصدیق کے بغیر حملہ نہیں کر سکتا۔ اگر A1 کا میسنجر آ گیا ہے، تو جنرل A2 پیغام کے ساتھ تصدیق بھیجتا ہے: "ہاں، آج گوروں کو مارتے ہیں۔" لیکن اب جنرل اے ٹو کو نہیں معلوم کہ ان کا میسنجر آیا ہے یا نہیں، ان کے پاس اس بات کی کوئی گارنٹی نہیں کہ حملہ بیک وقت ہوگا۔ اب جنرل A2 کو دوبارہ تصدیق کی ضرورت ہے۔
ان کی کمیونیکیشنز کو بیان کرنے سے مندرجہ ذیل باتوں کا پتہ چلتا ہے: اس بات سے کوئی فرق نہیں پڑتا ہے کہ کتنے ہی میسج سائیکل ہوں، اس بات کی ضمانت دینے کا کوئی طریقہ نہیں ہے کہ دونوں جرنیلوں کو مطلع کیا گیا ہے کہ ان کے پیغامات موصول ہو چکے ہیں (یہ فرض کرتے ہوئے کہ دونوں میں سے کسی بھی میسنجر کو روکا جا سکتا ہے)۔
دو جرنیلوں کا مسئلہ ایک بہت ہی آسان تقسیم شدہ نظام کی ایک عمدہ مثال ہے جہاں ناقابل اعتماد مواصلات کے ساتھ دو نوڈس ہیں۔ اس کا مطلب ہے کہ ہمارے پاس 100% گارنٹی نہیں ہے کہ وہ مطابقت پذیر ہیں۔ اسی طرح کے مسائل پر مضمون میں بعد میں صرف بڑے پیمانے پر بات کی گئی ہے۔
ہم تقسیم شدہ نظام کا تصور متعارف کراتے ہیں۔
تقسیم شدہ نظام کمپیوٹرز کا ایک گروپ ہے (اس کے بعد ہم انہیں نوڈز کہیں گے) جو پیغامات کا تبادلہ کر سکتے ہیں۔ ہر انفرادی نوڈ کسی نہ کسی قسم کا خود مختار ادارہ ہے۔ ایک نوڈ اپنے طور پر کاموں پر کارروائی کرسکتا ہے، لیکن دوسرے نوڈس کے ساتھ بات چیت کرنے کے لیے، اسے پیغامات بھیجنے اور وصول کرنے کی ضرورت ہے۔
پیغامات کو کس طرح لاگو کیا جاتا ہے، کون سے پروٹوکول استعمال کیے جاتے ہیں - یہ اس تناظر میں ہمارے لیے دلچسپی کا باعث نہیں ہے۔ یہ ضروری ہے کہ تقسیم شدہ نظام کے نوڈس پیغامات بھیج کر ایک دوسرے کے ساتھ ڈیٹا کا تبادلہ کر سکیں۔
تعریف بذات خود بہت پیچیدہ نہیں لگتی، لیکن ہمیں اس بات کو ذہن میں رکھنا چاہیے کہ تقسیم شدہ نظام میں کئی صفات ہیں جو ہمارے لیے اہم ہوں گی۔
تقسیم شدہ نظام کی خصوصیات
- ہم آہنگی - نظام میں بیک وقت یا ہم آہنگی کے واقعات کا امکان۔ مزید برآں، ہم دو مختلف نوڈس پر پیش آنے والے واقعات کو ممکنہ طور پر ہم آہنگی پر غور کریں گے جب تک کہ ہمارے پاس ان واقعات کے وقوع پذیر ہونے کا کوئی واضح ترتیب نہ ہو۔ لیکن، ایک اصول کے طور پر، ہمارے پاس یہ نہیں ہے۔
- کوئی عالمی گھڑی نہیں۔. عالمی گھڑی کی کمی کی وجہ سے ہمارے پاس واقعات کی واضح ترتیب نہیں ہے۔ لوگوں کی عام دنیا میں، ہم اس حقیقت کے عادی ہیں کہ ہمارے پاس گھڑی اور وقت بالکل ہے۔ جب تقسیم شدہ نظام کی بات آتی ہے تو سب کچھ بدل جاتا ہے۔ یہاں تک کہ انتہائی درست ایٹمی گھڑیاں بھی چلی گئی ہیں، اور ایسے حالات ہوسکتے ہیں جہاں ہم یہ نہیں بتا سکتے کہ دو واقعات میں سے کون سا پہلا واقعہ پیش آیا۔ اس لیے ہم وقت پر بھی بھروسہ نہیں کر سکتے۔
- سسٹم نوڈس کی آزادانہ ناکامی۔. ایک اور مسئلہ ہے: کچھ غلط ہو سکتا ہے کیونکہ ہمارے نوڈس ہمیشہ کے لیے نہیں رہتے۔ ہارڈ ڈرائیو ناکام ہو سکتی ہے، کلاؤڈ میں ورچوئل مشین دوبارہ شروع ہو سکتی ہے، نیٹ ورک جھپک سکتا ہے اور پیغامات ضائع ہو سکتے ہیں۔ اس کے علاوہ، ایسی صورت حال ہوسکتی ہے جہاں نوڈس کام کرتے ہیں، لیکن ایک ہی وقت میں نظام کے خلاف کام کرتے ہیں. مسائل کی آخری کلاس کو ایک الگ نام بھی ملا: مسئلہ . اس مسئلے کے ساتھ تقسیم شدہ نظام کی سب سے مشہور مثال Blockchain ہے۔ لیکن آج ہم اس خاص طبقے کے مسائل پر غور نہیں کریں گے۔ ہم ان حالات میں دلچسپی لیں گے جن میں صرف ایک یا زیادہ نوڈس ناکام ہو سکتے ہیں۔
- نوڈس کے درمیان مواصلاتی ماڈل (پیغام رسانی کے ماڈل). ہم پہلے ہی قائم کر چکے ہیں کہ نوڈس پیغامات کے تبادلے سے بات چیت کرتے ہیں۔ پیغام رسانی کے دو معروف ماڈل ہیں: ہم وقت ساز اور غیر مطابقت پذیر۔
تقسیم شدہ نظاموں میں نوڈس کے درمیان مواصلات کے ماڈل
ہم وقت ساز ماڈل - ہم یقینی طور پر جانتے ہیں کہ وقت کا ایک محدود معلوم ڈیلٹا ہے جس کے دوران ایک پیغام کے ایک نوڈ سے دوسرے تک پہنچنے کی ضمانت ہے۔ اگر یہ وقت گزر چکا ہے اور پیغام نہیں پہنچا ہے، تو ہم محفوظ طریقے سے کہہ سکتے ہیں کہ نوڈ ناکام ہو گیا ہے۔ اس ماڈل میں ہمارے پاس متوقع انتظار کے اوقات ہیں۔
غیر مطابقت پذیر ماڈل - غیر مطابقت پذیر ماڈلز میں ہم سمجھتے ہیں کہ انتظار کا وقت محدود ہے، لیکن وقت کا کوئی ایسا ڈیلٹا نہیں ہے جس کے بعد ہم اس بات کی ضمانت دے سکیں کہ نوڈ ناکام ہو گیا ہے۔ وہ. نوڈ سے پیغام کے انتظار کا وقت من مانی طور پر طویل ہو سکتا ہے۔ یہ ایک اہم تعریف ہے، اور ہم اس پر مزید بات کریں گے۔
تقسیم شدہ نظاموں میں اتفاق رائے کا تصور
اتفاق کے تصور کی باقاعدہ وضاحت کرنے سے پہلے، آئیے ایک ایسی صورت حال کی مثال پر غور کریں جہاں ہمیں اس کی ضرورت ہے، یعنی - ریاستی مشین کی نقل.
ہمارے پاس کچھ تقسیم شدہ لاگ ہیں۔ ہم چاہیں گے کہ یہ مستقل ہو اور تقسیم شدہ نظام کے تمام نوڈس پر یکساں ڈیٹا پر مشتمل ہو۔ جب نوڈس میں سے کوئی ایک نئی ویلیو سیکھتا ہے کہ وہ لاگ پر لکھنے جا رہا ہے، تو اس کا کام بن جاتا ہے کہ وہ اس ویلیو کو دوسرے تمام نوڈس کو پیش کرے تاکہ لاگ تمام نوڈس پر اپ ڈیٹ ہوجائے اور سسٹم ایک نئی مستقل حالت میں چلا جائے۔ اس معاملے میں، یہ ضروری ہے کہ نوڈس آپس میں متفق ہوں: تمام نوڈس متفق ہیں کہ مجوزہ نئی قدر درست ہے، تمام نوڈس اس قدر کو قبول کرتے ہیں، اور صرف اس صورت میں ہر کوئی لاگ میں نئی قدر لکھ سکتا ہے۔
دوسرے الفاظ میں: نوڈس میں سے کسی نے بھی اعتراض نہیں کیا کہ اس میں زیادہ متعلقہ معلومات ہیں، اور مجوزہ قیمت غلط تھی۔ نوڈس کے درمیان معاہدہ اور ایک واحد درست قبول شدہ قیمت پر معاہدہ تقسیم شدہ نظام میں اتفاق رائے ہے۔ اگلا، ہم الگورتھم کے بارے میں بات کریں گے جو تقسیم شدہ نظام کو اتفاق رائے تک پہنچنے کی ضمانت دیتے ہیں۔
مزید رسمی طور پر، ہم ایک متفقہ الگورتھم (یا محض ایک متفقہ الگورتھم) کو ایک مخصوص فنکشن کے طور پر بیان کر سکتے ہیں جو ایک تقسیم شدہ نظام کو ریاست A سے ریاست B میں منتقل کرتا ہے۔ مزید یہ کہ یہ حالت تمام نوڈس کے ذریعے قبول کی جاتی ہے، اور تمام نوڈس اس کی تصدیق کر سکتے ہیں۔ جیسا کہ پتہ چلتا ہے، یہ کام اتنا معمولی نہیں ہے جتنا کہ پہلی نظر میں لگتا ہے۔
متفقہ الگورتھم کی خصوصیات
متفقہ الگورتھم میں تین خصوصیات کا ہونا ضروری ہے تاکہ نظام کو جاری رکھا جا سکے اور ریاست سے دوسری ریاست میں منتقل ہونے میں کچھ پیش رفت ہو:
- معاہدہ - تمام صحیح طریقے سے کام کرنے والے نوڈس کو ایک ہی قدر لینا چاہیے (مضامین میں اس پراپرٹی کو سیفٹی پراپرٹی بھی کہا جاتا ہے)۔ تمام نوڈس جو فی الحال کام کر رہے ہیں (دوسروں سے رابطہ ناکام یا ختم نہیں ہوا ہے) کو ایک معاہدے پر آنا چاہئے اور کچھ حتمی مشترکہ قدر کو قبول کرنا چاہئے۔
یہاں یہ سمجھنا ضروری ہے کہ تقسیم شدہ نظام میں جن نوڈس پر ہم غور کر رہے ہیں وہ متفق ہونا چاہتے ہیں۔ یعنی اب ہم ان سسٹمز کے بارے میں بات کر رہے ہیں جن میں کوئی چیز آسانی سے فیل ہو سکتی ہے (مثال کے طور پر کچھ نوڈ فیل ہو جاتے ہیں)، لیکن اس سسٹم میں یقینی طور پر کوئی نوڈز نہیں ہیں جو جان بوجھ کر دوسروں کے خلاف کام کریں (بازنطینی جرنیلوں کا کام)۔ اس خاصیت کی وجہ سے، نظام مسلسل رہتا ہے.
- سالمیت - اگر تمام صحیح طریقے سے کام کرنے والے نوڈس ایک ہی قیمت پیش کرتے ہیں۔ vجس کا مطلب ہے کہ ہر صحیح طریقے سے کام کرنے والے نوڈ کو اس قدر کو قبول کرنا چاہیے۔ v.
- تکمیل کا - تمام صحیح طریقے سے کام کرنے والے نوڈس آخر کار ایک خاص قدر (جاندار جائیداد) کو لے لیں گے، جو الگورتھم کو سسٹم میں ترقی کرنے کی اجازت دیتا ہے۔ ہر فرد کو درست طریقے سے کام کرنے والے نوڈ کو جلد یا بدیر حتمی قیمت کو قبول کرنا چاہیے اور اس کی تصدیق کرنی چاہیے: "میرے لیے، یہ قدر درست ہے، میں پورے نظام سے متفق ہوں۔"
متفقہ الگورتھم کیسے کام کرتا ہے اس کی ایک مثال
جبکہ الگورتھم کی خصوصیات مکمل طور پر واضح نہیں ہوسکتی ہیں۔ لہذا، ہم ایک مثال کے ساتھ واضح کریں گے کہ ایک ہم آہنگ میسجنگ ماڈل والے سسٹم میں سب سے آسان متفقہ الگورتھم کن مراحل سے گزرتا ہے، جس میں تمام نوڈس حسب توقع کام کرتے ہیں، پیغامات ضائع نہیں ہوتے اور کچھ نہیں ٹوٹتا (کیا واقعی ایسا ہوتا ہے؟)۔
- یہ سب شادی کی تجویز (پرپوز) سے شروع ہوتا ہے۔ فرض کرتے ہیں کہ ایک کلائنٹ نے "نوڈ 1" نامی نوڈ سے منسلک کیا اور ایک لین دین شروع کیا، نوڈ - O کو ایک نئی قیمت منتقل کر دی۔ اب سے، ہم "نوڈ 1" کو کال کریں گے۔ پیشکش. ایک تجویز کنندہ کے طور پر، "نوڈ 1" کو اب پورے سسٹم کو مطلع کرنا چاہیے کہ اس کے پاس تازہ ڈیٹا ہے، اور یہ دوسرے تمام نوڈس کو پیغامات بھیجتا ہے: "دیکھو! "O" کا مطلب میرے پاس آیا اور میں اسے لکھنا چاہتا ہوں! براہ کرم تصدیق کریں کہ آپ اپنے لاگ میں "O" بھی ریکارڈ کریں گے۔
- اگلا مرحلہ مجوزہ قدر (ووٹنگ) کے لیے ووٹنگ ہے۔ یہ کس لیے ہے؟ یہ ہو سکتا ہے کہ دوسرے نوڈس کو زیادہ حالیہ معلومات ملی ہوں، اور ان کے پاس اسی لین دین کا ڈیٹا ہو۔
جب نوڈ "نوڈ 1" اپنی تجویز بھیجتا ہے، تو دوسرے نوڈس اس ایونٹ کے ڈیٹا کے لیے اپنے لاگز کو چیک کرتے ہیں۔ اگر کوئی تضاد نہیں ہے تو، نوڈس اعلان کرتے ہیں: "ہاں، میرے پاس اس ایونٹ کے لیے کوئی اور ڈیٹا نہیں ہے۔ "O" قدر تازہ ترین معلومات ہے جس کے ہم مستحق ہیں۔کسی بھی دوسری صورت میں، نوڈس "نوڈ 1" کا جواب دے سکتے ہیں: "سنو! میرے پاس اس لین دین کے بارے میں تازہ ترین ڈیٹا ہے۔ 'O' نہیں، لیکن کچھ بہتر ہے۔"
ووٹنگ کے مرحلے پر، نوڈس ایک فیصلے پر آتے ہیں: یا تو وہ سب ایک ہی قدر کو قبول کرتے ہیں، یا ان میں سے ایک اس کے خلاف ووٹ دیتا ہے، جس سے یہ ظاہر ہوتا ہے کہ اس کے پاس حالیہ ڈیٹا ہے۔
- اگر ووٹنگ راؤنڈ کامیاب رہا اور سب اس کے حق میں تھے، تو نظام ایک نئے مرحلے کی طرف بڑھتا ہے - قدر کو قبول کرنا۔ "نوڈ 1" دوسرے نوڈس سے تمام جوابات جمع کرتا ہے اور رپورٹ کرتا ہے: "سب نے "O" کی قدر پر اتفاق کیا! اب میں باضابطہ طور پر اعلان کرتا ہوں کہ "O" ہمارا نیا معنی ہے، سب کے لیے ایک جیسا! اسے اپنی چھوٹی کتاب میں لکھیں، مت بھولیں۔ اسے اپنے لاگ میں لکھو!
- باقی نوڈس تصدیق (قبول شدہ) بھیجتے ہیں کہ انہوں نے "O" کی قدر لکھ دی ہے؛ اس وقت کے دوران کوئی نئی چیز نہیں آئی (ایک قسم کی دو فیز کمٹ)۔ اس اہم واقعہ کے بعد، ہم سمجھتے ہیں کہ تقسیم شدہ لین دین مکمل ہو گیا ہے۔
اس طرح، ایک سادہ کیس میں متفقہ الگورتھم چار مراحل پر مشتمل ہے: تجویز، ووٹ (ووٹ دینا)، قبول (قبول)، قبولیت کی تصدیق (قبول)۔
اگر کسی مرحلے پر ہم معاہدے تک پہنچنے سے قاصر تھے، تو الگورتھم دوبارہ شروع ہوتا ہے، نوڈس کے ذریعے فراہم کردہ معلومات کو مدنظر رکھتے ہوئے جنہوں نے مجوزہ قیمت کی تصدیق کرنے سے انکار کر دیا تھا۔
ایک غیر مطابقت پذیر نظام میں متفقہ الگورتھم
اس سے پہلے، سب کچھ ہموار تھا، کیونکہ ہم ہم وقت ساز پیغام رسانی کے ماڈل کے بارے میں بات کر رہے تھے۔ لیکن ہم جانتے ہیں کہ جدید دنیا میں ہم سب کچھ متضاد طور پر کرنے کے عادی ہیں۔ اسی طرح کا الگورتھم ایک غیر مطابقت پذیر میسجنگ ماڈل والے سسٹم میں کیسے کام کرتا ہے، جہاں ہم سمجھتے ہیں کہ نوڈ سے جواب کا انتظار کرنے کا وقت من مانی طور پر طویل ہو سکتا ہے (ویسے، نوڈ کی ناکامی کو بھی ایک مثال کے طور پر سمجھا جا سکتا ہے جب ایک نوڈ من مانی طور پر طویل عرصے تک جواب دے سکتا ہے)۔
اب جب کہ ہم جانتے ہیں کہ اتفاق رائے کا الگورتھم اصولی طور پر کیسے کام کرتا ہے، ان متجسس قارئین کے لیے ایک سوال جنہوں نے اسے یہاں تک پہنچایا ہے: ایک غیر مطابقت پذیر میسج ماڈل والے N نوڈس کے سسٹم میں کتنے نوڈس ناکام ہو سکتے ہیں تاکہ نظام اب بھی اتفاق رائے تک پہنچ سکے؟
بگاڑنے والے کے پیچھے درست جواب اور جواز ہوتا ہے۔صحیح جواب یہ ہے: 0. اگر غیر مطابقت پذیر نظام میں ایک نوڈ بھی ناکام ہوجاتا ہے، تو نظام اتفاق رائے تک نہیں پہنچ سکے گا۔ یہ بیان FLP تھیوریم میں ثابت ہوا ہے، جو بعض حلقوں میں مشہور ہے (1985، فشر، لنچ، پیٹرسن، مضمون کے آخر میں اصل سے لنک): "کم از کم ایک نوڈ ناکام ہونے کی صورت میں تقسیم شدہ اتفاق رائے حاصل کرنے کا ناممکن "
دوستو، پھر ہمیں ایک مسئلہ درپیش ہے، ہم ہر چیز کے متضاد ہونے کے عادی ہیں۔ اور یہ یہاں ہے. زندگی کیسے جاری رکھی جائے؟
ہم صرف تھیوری کے بارے میں بات کر رہے تھے، ریاضی کے بارے میں۔ "اتفاق رائے حاصل نہیں کیا جا سکتا" کا کیا مطلب ہے، ریاضی کی زبان سے ہماری - انجینئرنگ میں ترجمہ کرنا؟ اس کا مطلب ہے کہ "ہمیشہ حاصل نہیں کیا جا سکتا"، یعنی ایک ایسا معاملہ ہے جس میں اتفاق رائے ممکن نہیں ہے۔ یہ کیسا کیس ہے؟
یہ بالکل اوپر بیان کردہ لائیونس پراپرٹی کی خلاف ورزی ہے۔ ہمارے پاس کوئی مشترکہ معاہدہ نہیں ہے، اور نظام میں پیش رفت نہیں ہو سکتی (ایک مقررہ وقت میں مکمل نہیں ہو سکتی) اس صورت میں جہاں ہمارے پاس تمام نوڈس سے کوئی جواب نہیں ہے۔ کیونکہ ایک غیر مطابقت پذیر نظام میں ہمارے پاس کوئی قابل قیاس رسپانس ٹائم نہیں ہوتا ہے اور ہم یہ نہیں جان سکتے کہ کوئی نوڈ کریش ہو گیا ہے یا جواب دینے میں کافی وقت لگ رہا ہے۔
لیکن عملی طور پر ہم اس کا حل تلاش کر سکتے ہیں۔ ناکامی کی صورت میں ہمارے الگورتھم کو طویل عرصے تک کام کرنے کے قابل ہونے دیں (ممکنہ طور پر یہ غیر معینہ مدت تک کام کر سکتا ہے)۔ لیکن زیادہ تر حالات میں، جب زیادہ تر نوڈس صحیح طریقے سے کام کر رہے ہوں گے، تو ہمارے نظام میں ترقی ہوگی۔
عملی طور پر، ہم جزوی طور پر مطابقت پذیر مواصلاتی ماڈلز سے نمٹتے ہیں۔ جزوی ہم آہنگی کو اس طرح سمجھا جاتا ہے: عام صورت میں، ہمارے پاس ایک غیر مطابقت پذیر ماڈل ہے، لیکن وقت کے ایک خاص نقطہ کے "عالمی استحکام کے وقت" کا ایک خاص تصور باضابطہ طور پر متعارف کرایا جاتا ہے۔
وقت کا یہ لمحہ کسی طوالت کے لیے نہیں آسکتا، لیکن ایک دن ضرور آنا چاہیے۔ ورچوئل الارم کلاک بج جائے گا، اور اس لمحے سے ہم اس وقت کا اندازہ لگا سکتے ہیں جس کے لیے پیغامات آئیں گے۔ اس لمحے سے، نظام متضاد سے ہم آہنگی میں بدل جاتا ہے۔ عملی طور پر، ہم بالکل ایسے نظاموں سے نمٹتے ہیں۔
Paxos الگورتھم متفقہ مسائل کو حل کرتا ہے۔
الگورتھم کا ایک خاندان ہے جو جزوی طور پر مطابقت پذیر نظاموں کے لیے اتفاق رائے کے مسئلے کو حل کرتا ہے، اس امکان کے ساتھ کہ کچھ نوڈس ناکام ہو سکتے ہیں۔ Paxos کے مصنف ہیں . اس نے 1989 میں الگورتھم کے وجود اور درستگی کا باقاعدہ ثبوت تجویز کیا۔
لیکن ثبوت معمولی سے دور نکلا۔ پہلی اشاعت صرف 1998 میں جاری کی گئی تھی (33 صفحات) جس میں الگورتھم کو بیان کیا گیا تھا۔ جیسا کہ یہ نکلا، اسے سمجھنا انتہائی مشکل تھا، اور 2001 میں مضمون کی ایک وضاحت شائع ہوئی، جس میں 14 صفحات تھے۔ اشاعتوں کا حجم یہ ظاہر کرنے کے لیے دیا گیا ہے کہ درحقیقت اتفاق رائے کا مسئلہ بالکل آسان نہیں ہے، اور اس طرح کے الگورتھم کے پیچھے ذہین لوگوں کا بہت بڑا کام ہوتا ہے۔
یہ دلچسپ بات ہے کہ خود لیسلی لیمپورٹ نے اپنے لیکچر میں نوٹ کیا کہ دوسرے وضاحتی مضمون میں ایک بیان ہے، ایک سطر (اس نے یہ واضح نہیں کیا کہ کون سا ہے)، جس کی مختلف طریقوں سے تشریح کی جا سکتی ہے۔ اور اس کی وجہ سے، جدید Paxos کے نفاذ کی ایک بڑی تعداد مکمل طور پر صحیح طریقے سے کام نہیں کرتی ہے۔
Paxos کے کام کے تفصیلی تجزیے میں ایک سے زیادہ مضامین لگیں گے، اس لیے میں بہت مختصر طور پر الگورتھم کے مرکزی خیال کو بیان کرنے کی کوشش کروں گا۔ میرے مضمون کے آخر میں لنکس میں آپ کو اس موضوع میں مزید غوطہ لگانے کے لیے مواد مل جائے گا۔
Paxos میں کردار
Paxos الگورتھم میں کرداروں کا تصور ہے۔ آئیے تین اہم چیزوں پر غور کریں (اضافی کرداروں کے ساتھ ترمیمات ہیں):
- تجویز کنندگان (شرائط بھی استعمال کی جا سکتی ہیں: رہنما یا رابطہ کار). یہ وہ لوگ ہیں جو صارف سے کچھ نئی قدر کے بارے میں سیکھتے ہیں اور لیڈر کا کردار ادا کرتے ہیں۔ ان کا کام ایک نئی قدر کے لیے تجاویز کا ایک دور شروع کرنا اور نوڈس کی مزید کارروائیوں کو مربوط کرنا ہے۔ مزید یہ کہ، Paxos بعض حالات میں کئی رہنماؤں کی موجودگی کی اجازت دیتا ہے۔
- قبول کرنے والے (ووٹرز). یہ نوڈس ہیں جو کسی خاص قدر کو قبول یا مسترد کرنے کے لیے ووٹ دیتے ہیں۔ ان کا کردار بہت اہم ہے، کیونکہ فیصلہ ان پر منحصر ہے: متفقہ الگورتھم کے اگلے مرحلے کے بعد نظام کس حالت میں جائے گا (یا نہیں کرے گا)۔
- سیکھنے والے. نوڈس جو نظام کی حالت تبدیل ہونے پر نئی قبول شدہ قدر کو آسانی سے قبول کرتے اور لکھتے ہیں۔ وہ فیصلے نہیں کرتے، وہ صرف ڈیٹا وصول کرتے ہیں اور اسے آخری صارف کو دے سکتے ہیں۔
ایک نوڈ مختلف حالات میں کئی کرداروں کو اکٹھا کر سکتا ہے۔
کورم کا تصور
ہم فرض کرتے ہیں کہ ہمارے پاس ایک نظام ہے۔ N نوڈس اور ان میں سے زیادہ سے زیادہ F نوڈس ناکام ہو سکتے ہیں. اگر ایف نوڈس ناکام ہوجاتے ہیں، تو ہمارے پاس کم از کم ہونا ضروری ہے۔ 2F+1 قبول کنندگان.
یہ ضروری ہے تاکہ ہمارے پاس ہمیشہ اکثریت ہو، یہاں تک کہ بدترین صورتحال میں بھی، "اچھے" نوڈس جو صحیح طریقے سے کام کرتے ہیں۔ یہ ہے کہ F+1 "اچھے" نوڈس جنہوں نے اتفاق کیا، اور حتمی قیمت قبول کی جائے گی۔ دوسری صورت میں، ایسی صورت حال ہو سکتی ہے کہ ہمارے مختلف مقامی گروہ مختلف معنی لیتے ہیں اور آپس میں متفق نہیں ہو سکتے۔ اس لیے ہمیں ووٹ حاصل کرنے کے لیے قطعی اکثریت کی ضرورت ہے۔
Paxos اتفاق رائے الگورتھم کیسے کام کرتا ہے اس کا عمومی خیال
Paxos الگورتھم میں دو بڑے مراحل شامل ہیں، جو بدلے میں دو مراحل میں تقسیم ہوتے ہیں:
- مرحلہ 1a: تیار کریں۔. تیاری کے مرحلے کے دوران، رہنما (تجویز کنندہ) تمام نوڈس کو مطلع کرتا ہے: "ہم ووٹنگ کا ایک نیا مرحلہ شروع کر رہے ہیں۔ ہمارے پاس ایک نیا دور ہے۔ اس راؤنڈ کا نمبر n ہے۔ اب ہم ووٹنگ شروع کریں گے۔" ابھی کے لیے، یہ صرف ایک نئے سائیکل کے آغاز کی اطلاع دیتا ہے، لیکن کسی نئی قدر کی اطلاع نہیں دیتا ہے۔ اس مرحلے کا کام ایک نیا دور شروع کرنا اور ہر ایک کو اس کے منفرد نمبر سے آگاہ کرنا ہے۔ راؤنڈ نمبر اہم ہے، اس کی قدر تمام سابقہ لیڈروں کے ووٹنگ نمبروں سے زیادہ ہونی چاہیے۔ کیونکہ یہ راؤنڈ نمبر کی بدولت ہے کہ سسٹم میں موجود دیگر نوڈس سمجھ جائیں گے کہ لیڈر کا ڈیٹا کتنا حالیہ ہے۔ اس بات کا امکان ہے کہ دوسرے نوڈس کے پاس پہلے ہی بہت بعد کے راؤنڈز کے ووٹنگ کے نتائج ہیں اور وہ لیڈر کو صرف یہ بتا دیں گے کہ وہ وقت سے پیچھے ہے۔
- مرحلہ 1b: وعدہ. جب قبول کنندہ نوڈس کو ووٹنگ کے نئے مرحلے کا نمبر موصول ہوتا ہے، تو دو نتائج ممکن ہیں:
- نئے ووٹ کا نمبر n کسی بھی پچھلے ووٹ کی تعداد سے زیادہ ہے جس میں قبول کنندہ نے حصہ لیا تھا۔ پھر قبول کرنے والا لیڈر کو ایک وعدہ بھیجتا ہے کہ وہ n سے کم نمبر والے مزید ووٹوں میں حصہ نہیں لے گا۔ اگر قبول کرنے والا پہلے ہی کسی چیز کے لیے ووٹ دے چکا ہے (یعنی دوسرے مرحلے میں اس نے پہلے ہی کچھ قدر قبول کر لی ہے)، تو وہ قبول شدہ قدر اور ووٹ کی تعداد کو منسلک کرتا ہے جس میں اس نے اپنے وعدے کے مطابق حصہ لیا۔
- دوسری صورت میں، اگر قبول کنندہ پہلے سے ہی زیادہ نمبر والے ووٹ کے بارے میں جانتا ہے، تو وہ تیاری کے مرحلے کو نظر انداز کر سکتا ہے اور لیڈر کو جواب نہیں دے سکتا۔
- مرحلہ 2a: قبول کریں۔. رہنما کو کورم (نظام میں نوڈس کی اکثریت) سے جواب کا انتظار کرنے کی ضرورت ہے اور، اگر مطلوبہ تعداد میں جوابات موصول ہو جائیں، تو اس کے پاس واقعات کی ترقی کے لیے دو اختیارات ہیں:
- قبول کرنے والوں میں سے کچھ نے ایسی اقدار بھیجیں جن کے لیے وہ پہلے ہی ووٹ دے چکے تھے۔ اس صورت میں، لیڈر زیادہ سے زیادہ تعداد کے ساتھ ووٹ سے قدر کا انتخاب کرتا ہے۔ آئیے اس ویلیو کو x کہتے ہیں، اور یہ تمام نوڈس کو ایک پیغام بھیجتا ہے جیسے: "Accept (n, x)"، جہاں پہلی ویلیو اس کے اپنے Propose قدم سے ووٹنگ نمبر ہے، اور دوسری ویلیو وہ ہے جس کے لیے ہر کوئی جمع ہوا، یعنی وہ قدر جس کے لیے ہم اصل میں ووٹ دیتے ہیں۔
- اگر قبول کرنے والوں میں سے کسی نے بھی کوئی قدر نہیں بھیجی، لیکن انہوں نے صرف اس دور میں ووٹ دینے کا وعدہ کیا ہے، تو لیڈر انہیں ان کی قدر کے لیے ووٹ دینے کی دعوت دے سکتا ہے، جس قدر کے لیے وہ پہلی جگہ لیڈر بنے۔ آئیے اسے y کہتے ہیں۔ یہ تمام نوڈس کو ایک پیغام بھیجتا ہے جیسے: "قبول کریں (n, y)"، پچھلے نتائج کی طرح۔
- فیز 2b: قبول کر لیا گیا۔. مزید، قبول کنندہ نوڈس، لیڈر کی جانب سے "قبول (...)" پیغام موصول ہونے پر، اس سے اتفاق کرتے ہیں (تمام نوڈس کو تصدیق بھیجیں کہ وہ نئی قدر سے متفق ہیں) صرف اس صورت میں جب انہوں نے کچھ وعدہ نہیں کیا ہے (دوسرے) رہنما راؤنڈ نمبر کے ساتھ ووٹنگ میں حصہ لے گا۔ n' > nبصورت دیگر وہ تصدیق کی درخواست کو نظر انداز کر دیتے ہیں۔
اگر نوڈس کی اکثریت نے لیڈر کو جواب دیا، اور ان سب نے نئی قدر کی تصدیق کی، تو نئی قدر کو قبول سمجھا جاتا ہے۔ ہورے! اگر اکثریت تک نہیں پہنچی ہے یا ایسے نوڈس ہیں جنہوں نے نئی قدر کو قبول کرنے سے انکار کر دیا ہے، تو سب کچھ شروع ہو جاتا ہے۔
Paxos الگورتھم اس طرح کام کرتا ہے۔ ان میں سے ہر ایک مرحلے میں بہت سی باریکیاں ہیں، ہم نے عملی طور پر مختلف قسم کی ناکامیوں، متعدد رہنماؤں کے مسائل اور بہت کچھ پر غور نہیں کیا، لیکن اس مضمون کا مقصد صرف قاری کو اعلیٰ سطح پر تقسیم شدہ کمپیوٹنگ کی دنیا سے متعارف کرانا ہے۔
یہ بات بھی قابل غور ہے کہ Paxos اپنی نوعیت کا واحد نہیں ہے، اس کے علاوہ اور بھی الگورتھم ہیں، مثال کے طور پر، لیکن یہ ایک اور مضمون کا موضوع ہے۔
مزید مطالعہ کے لیے مواد کے لنکس
ابتدائی سطح:
- پریتھی کاسریڈی، میڈیم پر بلاگ مضمون
- , Adi Kancherla , میڈیم پر بلاگ مضمون
- ، اتائی ابراہیم، بلاگ
- ، اتائی ابراہیم، بلاگ مضمون
لیسلی لیمپورٹ کی سطح:
- ، فشر، لنچ اور پیٹرسن، تحقیقی مقالہ، 1985
- لیسلی لیمپورٹ، تحقیقی مقالہ، 1998
- لیسلی لیمپورٹ، تحقیقی مقالہ، 2001
ماخذ: www.habr.com