شروڊنگر جي ٻلي بغير باڪس: ورهايل نظام ۾ اتفاق جو مسئلو

سو، اچو ته تصور ڪريون. ڪمري ۾ 5 ٻليون بند پيل آھن ۽ مالڪ کي جاڳائڻ لاءِ، انھن سڀني کي پاڻ ۾ ان ڳالھ تي متفق ٿيڻو پوندو، ڇاڪاڻ ته اھي رڳو دروازو کولي سگھن ٿيون، انھن مان پنجن کي ان تي ٽيڪ ڏئي. جيڪڏهن ٻلين مان هڪ شروڊنگر جي ٻلي آهي، ۽ ٻيون ٻليون هن جي فيصلي جي باري ۾ نه ڄاڻن ٿيون، سوال پيدا ٿئي ٿو: "اهي اهو ڪيئن ڪري سگهن ٿيون؟"

هن آرٽيڪل ۾، آئون توهان کي ورهايل نظام جي دنيا جي نظرياتي جزو ۽ انهن جي آپريشن جي اصولن بابت سادي اصطلاحن ۾ ٻڌايان ٿو. مان پڻ سطحي طور تي جانچ ڪندس بنيادي خيال بنيادي خيال Paxos.

جڏهن ڊولپر ڪلائوڊ انفراسٽرڪچر، مختلف ڊيٽابيسس، ۽ وڏي تعداد ۾ نوڊس جي ڪلسٽرن ۾ ڪم ڪن ٿا، انهن کي يقين آهي ته ڊيٽا مڪمل، محفوظ ۽ هميشه دستياب هوندي. پر ضمانتون ڪٿي آهن؟

لازمي طور تي، اسان وٽ ضمانتون آهن سپلائر ضمانتون. انهن کي دستاويزن ۾ هن ريت بيان ڪيو ويو آهي: "هي خدمت ڪافي قابل اعتماد آهي، ان کي هڪ SLA ڏنو ويو آهي، پريشان نه ڪريو، هر شي ورهائي ڪم ڪندي جيئن توهان جي توقع آهي."

اسان بهترين تي يقين رکون ٿا، ڇو ته وڏين ڪمپنين جي سمارمن ماڻهن اسان کي يقين ڏياريو ته سڀ ڪجهه ٺيڪ ٿي ويندو. اسان اهو سوال نه پڇندا آهيون: ڇو، حقيقت ۾، اهو سڀ ڪجهه ڪم ڪري سگهي ٿو؟ ڇا اهڙي نظام جي صحيح آپريشن لاء ڪو رسمي جواز آهي؟

مان تازو ويو آهيان ورهايل ڪمپيوٽنگ جو اسڪول ۽ هن موضوع کان تمام گهڻو متاثر ٿيو. اسڪول ۾ ليڪچر ڪمپيوٽر سسٽم سان لاڳاپيل ڪجهه کان وڌيڪ حساب ڪتاب وانگر هئا. پر اهو بلڪل ائين آهي ته سڀ کان وڌيڪ اهم الگورتھم جيڪي اسان هر روز استعمال ڪندا آهيون، ان کي ڄاڻڻ کان سواء، هڪ وقت ۾ ثابت ٿيا.

اڪثر جديد تقسيم سسٽم Paxos اتفاق الورورٿم ۽ ان جي مختلف تبديلين کي استعمال ڪن ٿا. سڀ کان سٺي ڳالهه اها آهي ته صحيح ۽ اصولي طور تي، هن الگورتھم جي وجود جو تمام گهڻو امڪان صرف قلم ۽ ڪاغذ سان ثابت ڪري سگهجي ٿو. عملي طور تي، الورورٿم وڏي سسٽم ۾ استعمال ڪيو ويندو آهي جيڪو بادلن ۾ وڏي تعداد ۾ نوڊس تي هلندو آهي.

ان جو هڪ روشن مثال جيڪو اڳتي هلي بحث ڪيو ويندو: ٻن جنرلن جو ڪماچو ته هڪ گرم اپ لاء هڪ نظر وٺو ٻن جنرلن جو ڪم.

اسان وٽ ٻه لشڪر آهن - ڳاڙهو ۽ اڇو. سفيد فوجون محاصر ٿيل شهر ۾ موجود آهن. جنرل A1 ۽ A2 جي اڳواڻي ۾ لال فوجون شهر جي ٻن پاسن تي واقع آهن. ريڊ هيڊس جو ڪم سفيد شهر تي حملو ڪرڻ ۽ فتح ڪرڻ آهي. بهرحال، هر لال جنرل جي فوج انفرادي طور تي سفيد فوج کان ننڍو آهي.

ڳاڙهي وارن لاءِ فتح جون حالتون: ٻنهي جنرلن کي هڪ ئي وقت حملو ڪرڻ گهرجي ته جيئن اڇين تي عددي فائدو حاصل ڪري سگهجي. هن کي ڪرڻ لاء، جنرلن A1 ۽ A2 هڪ ٻئي سان هڪ معاهدو ڪرڻ جي ضرورت آهي. جيڪڏهن هرڪو الڳ الڳ حملو ڪري، ڳاڙهو ڳاڙهو ٿيندو.

هڪ معاهدي تائين پهچڻ لاء، جنرلن A1 ۽ A2 سفيد شهر جي علائقي ذريعي هڪ ٻئي ڏانهن قاصد موڪلي سگهن ٿا. قاصد ڪاميابيءَ سان ڪنهن اتحادي جنرل تائين پهچي سگهي ٿو يا دشمن طرفان روڪي سگهجي ٿو. سوال: ڇا ڳاڙهي وار وارن جنرلن جي وچ ۾ رابطي جو اهڙو سلسلو آهي (A1 کان A2 ڏانهن قاصد موڪلڻ جو سلسلو ۽ ان جي برعڪس A2 کان A1 تائين)، جنهن ۾ انهن کي ضمانت ڏني وئي آهي ته هو ڪلاڪ X تي حملي تي راضي ٿي وڃن. هتي، ضمانت جو مطلب آهي ته ٻنهي جنرلن کي غير واضح تصديق هوندي ته هڪ اتحادي (ٻيو جنرل) ضرور مقرر وقت تي حملو ڪندو.

فرض ڪريو A1 هڪ ميسينجر کي A2 ڏانهن پيغام سان موڪلي ٿو: ”اچو اڄ اڌ رات جو حملو ڪريون! جنرل A1 جنرل A2 جي تصديق کان سواءِ حملو نٿو ڪري سگهي. جيڪڏهن A1 کان قاصد اچي چڪو آهي، ته پوء جنرل A2 پيغام سان تصديق ڪري ٿو: "ها، اچو ته اڄ اڇا مارون." پر هاڻي جنرل A2 کي خبر ناهي ته سندس ميسينجر آيو آهي يا نه، هن وٽ ڪا به گارنٽي ناهي ته حملو هڪ ئي وقت ٿيندو. هاڻي جنرل A2 ٻيهر تصديق جي ضرورت آهي.

جيڪڏهن اسان انهن جي ڪميونيڪيشن کي وڌيڪ بيان ڪريون ٿا، اهو واضح ٿي وڃي ٿو ته ڪيترو به پيغامن جي مٽاسٽا واري چڪر موجود آهن، ان ڳالهه جي ضمانت ڏيڻ جو ڪو به طريقو ناهي ته ٻنهي جنرلن کي انهن جا پيغام مليا آهن (فرض ڪيو ته ڪنهن به ميسينجر کي مداخلت ڪري سگهجي ٿو).

ٻن جنرلن جو مسئلو هڪ تمام سادي ورهايل نظام جو هڪ بهترين مثال آهي جتي ٻه نوڊس آهن جن ۾ ناقابل اعتبار ڪميونيڪيشن آهي. هن جو مطلب آهي ته اسان وٽ 100٪ گارنٽي ناهي ته اهي هم وقت ساز آهن. ساڳئي مسئلن تي بحث ڪيو ويندو صرف هڪ وڏي پيماني تي مضمون ۾ بعد ۾.

اسان ورهايل نظام جو تصور متعارف ڪرايو

ورهايل سسٽم ڪمپيوٽرن جو هڪ گروپ آهي (هتي اسان انهن کي نوڊس سڏينداسين) جيڪي پيغامن کي مٽائي سگھن ٿا. هر انفرادي نوڊ ڪجهه قسم جي خودمختيار ادارو آهي. ھڪڙو نوڊ پنھنجي ڪم تي عمل ڪري سگھي ٿو، پر ٻين نوڊس سان ڳالھ ٻولھ ڪرڻ لاء، ان کي پيغام موڪلڻ ۽ وصول ڪرڻ جي ضرورت آھي.

ڪيئن صحيح طور تي پيغامن تي عمل ڪيو وڃي ٿو، ڪهڙا پروٽوڪول استعمال ڪيا ويا آهن - هي اسان جي هن حوالي سان دلچسپي نه آهي. اهو ضروري آهي ته ورهايل سسٽم جا نوڊس هڪ ٻئي سان ڊيٽا کي مٽائي سگھن ٿيون پيغام موڪلڻ سان.

تعريف پاڻ کي تمام پيچيده نظر نٿو اچي، پر اسان کي اهو سمجهڻ گهرجي ته هڪ ورهايل نظام ۾ ڪيتريون ئي خاصيتون آهن جيڪي اسان لاء اهم هونديون.

ورهايل نظام جون خاصيتون

1. سموري - سسٽم ۾ هڪ ئي وقت يا سمورو واقعن جو امڪان. ان کان علاوه، اسان انهن واقعن تي غور ڪنداسين جيڪي ٻن مختلف نوڊس تي واقع ٿين ٿيون ممڪن طور تي گڏو گڏ هجن جيستائين اسان وٽ انهن واقعن جي واقعن جو واضح حڪم نه آهي. پر، ضابطي جي طور تي، اسان وٽ اهو ناهي.
2. ڪابه گلوبل ڪلاڪ. عالمي ڪلاڪ جي کوٽ جي ڪري اسان وٽ واقعن جو واضح حڪم نه آهي. ماڻهن جي عام دنيا ۾، اسان ان حقيقت جا عادي آهيون ته اسان وٽ ڪلاڪ ۽ وقت بلڪل آهي. سڀ ڪجھ تبديل ٿي ويندو آھي جڏھن اھو اچي ٿو ورهايل سسٽم. ايستائين جو الٽرا-پريزيس ايٽمي گھڙين ۾ به ڦيرو اچي ويو آهي، ۽ ٿي سگهي ٿو ته اهڙيون حالتون هجن جتي اسان اهو نه ٻڌائي سگهون ته ٻن واقعن مان ڪهڙو پهريون واقعو ٿيو. تنهن ڪري، اسان به وقت تي ڀروسو نٿا ڪري سگهون.
3. سسٽم نوڊس جي آزاد ناڪامي. اتي هڪ ٻيو مسئلو آهي: ڪجهه غلط ٿي سگهي ٿو صرف ڇاڪاڻ ته اسان جا نوڊس هميشه لاءِ نه رهندا آهن. هارڊ ڊرائيو ناڪام ٿي سگھي ٿو، ورچوئل مشين ڪلائوڊ ۾ ريبوٽ ٿي سگھي ٿي، نيٽ ورڪ ٽمٽار ٿي سگھي ٿو ۽ پيغام گم ٿي ويندا. ان کان علاوه، اتي حالتون ٿي سگھي ٿو جتي نوڊس ڪم ڪن ٿا، پر ساڳئي وقت سسٽم جي خلاف ڪم ڪن ٿا. مسئلن جي آخري طبقي کي به هڪ الڳ نالو ملي ٿو: مسئلو بازنطيني جنرلن. هن مسئلي سان ورهايل نظام جو سڀ کان مشهور مثال آهي Blockchain. پر اڄ اسان هن خاص طبقي جي مسئلن تي غور نه ڪنداسين. اسان حالتن ۾ دلچسپي وٺنداسين جن ۾ صرف هڪ يا وڌيڪ نوڊس ناڪام ٿي سگهن ٿيون.
4. رابطي جا ماڊل (ميسيجنگ ماڊل) نوڊس جي وچ ۾. اسان اڳ ۾ ئي قائم ڪيو آهي ته نوڊس پيغامن جي بدلي سان رابطو ڪن ٿا. اتي ٻه مشهور ميسيجنگ ماڊل آهن: هم وقت ساز ۽ هم وقت ساز.

ورهايل سسٽم ۾ نوڊس جي وچ ۾ رابطي جا ماڊل

هم وقت ساز ماڊل - اسان پڪ سان ڄاڻون ٿا ته وقت جو هڪ محدود ڄاڻايل ڊيلٽا آهي جنهن دوران هڪ پيغام هڪ نوڊ کان ٻئي تائين پهچڻ جي ضمانت آهي. جيڪڏهن اهو وقت گذري چڪو آهي ۽ پيغام نه آيو آهي، اسان محفوظ طور تي چئي سگهون ٿا ته نوڊ ناڪام ٿي چڪو آهي. هن ماڊل ۾ اسان وٽ متوقع انتظار جا وقت آهن.

هم وقت سازي ماڊل - هم وقت سازي ماڊلز ۾ اسان سمجهون ٿا ته انتظار جو وقت محدود آهي، پر وقت جو ڪو به اهڙو ڊيلٽا ناهي جنهن کان پوءِ اسان ضمانت ڏئي سگهون ته نوڊ ناڪام ٿي ويو آهي. اهي. نوڊ مان پيغام جي انتظار جو وقت پاڻمرادو ڊگهو ٿي سگهي ٿو. هي هڪ اهم تعريف آهي، ۽ اسان ان بابت وڌيڪ ڳالهائينداسين.

ورهايل نظام ۾ اتفاق راءِ جو تصور

اتفاق جي تصور کي باضابطه طور تي بيان ڪرڻ کان اڳ، اچو ته هڪ اهڙي صورتحال جي مثال تي غور ڪريو جتي اسان کي ان جي ضرورت آهي، يعني - رياستي مشين جي نقل.

اسان وٽ ڪجهه ورهايل لاگ آهن. اسان چاهيون ٿا ته اهو هڪجهڙائي هجي ۽ ورهايل سسٽم جي سڀني نوڊس تي هڪجهڙائي واري ڊيٽا تي مشتمل هجي. جڏهن نوڊس مان ڪو هڪ نئين قيمت سکي ٿو ته اهو لاگ ڏانهن لکڻ وارو آهي، ان جو ڪم اهو هوندو آهي ته اها قيمت ٻين سڀني نوڊس کي پيش ڪري ته جيئن لاگ سڀني نوڊس تي اپڊيٽ ٿي وڃي ۽ سسٽم هڪ نئين مستقل حالت ڏانهن هليو وڃي. هن معاملي ۾، اهو ضروري آهي ته نوڊس پاڻ ۾ متفق آهن: سڀئي نوڊس متفق آهن ته تجويز ڪيل نئين قيمت صحيح آهي، سڀئي نوڊس هن قيمت کي قبول ڪن ٿا، ۽ صرف هن صورت ۾ هرڪو لاگ ۾ نئين قيمت لکي سگهي ٿو.

ٻين لفظن ۾: ڪو به نوڊس اعتراض نه ڪيو ته ان ۾ وڌيڪ لاڳاپيل معلومات هئي، ۽ تجويز ڪيل قيمت غلط هئي. نوڊس جي وچ ۾ معاهدو ۽ هڪ واحد صحيح قبول ٿيل قيمت تي معاهدو ورهايل نظام ۾ اتفاق آهي. اڳيون، اسان الگورتھم بابت ڳالهائينداسين جيڪي ورهايل نظام کي اتفاق راءِ تائين پهچڻ جي ضمانت ڏيڻ جي اجازت ڏين ٿا.

وڌيڪ رسمي طور تي، اسان هڪ اتفاق الورورٿم (يا صرف هڪ اتفاق الورورٿم) کي هڪ خاص فنڪشن جي طور تي بيان ڪري سگهون ٿا جيڪو هڪ ورهايل نظام کي رياست A کان رياست B ڏانهن منتقل ڪري ٿو. ان کان علاوه، هي رياست سڀني نوڊس طرفان قبول ڪيو ويندو آهي، ۽ سڀئي نوڊس ان جي تصديق ڪري سگھن ٿا. جيئن ته اهو ظاهر ٿئي ٿو، اهو ڪم تمام ننڍڙو نه آهي جيئن اهو پهرين نظر ۾ لڳي ٿو.

اتفاق الورورٿم جا خاصيتون

متفقه الگورٿم کي لازمي طور تي ٽي خاصيتون هجڻ گهرجن سسٽم کي جاري رکڻ لاءِ ۽ رياست کان رياست ڏانهن منتقل ٿيڻ ۾ ڪجهه پيش رفت آهي:

1. معاهدو - سڀ صحيح آپريٽنگ نوڊس کي ساڳيو قدر وٺڻ گهرجي (مضمون ۾ هن ملڪيت کي حفاظتي ملڪيت پڻ سڏيو ويندو آهي). سڀئي نوڊس جيڪي في الحال ڪم ڪري رهيا آهن (ٻين سان رابطو ناڪام يا گم ٿيل نه آهن) لازمي طور تي هڪ معاهدو ٿيڻ گهرجي ۽ ڪجهه حتمي عام قدر قبول ڪن.

   هتي اهو سمجهڻ ضروري آهي ته ورهايل سسٽم ۾ نوڊس جنهن تي اسان غور ڪري رهيا آهيون اتفاق ڪرڻ چاهيندا آهن. اھو آھي، اسان ھاڻي انھن سسٽم بابت ڳالھائي رھيا آھيون جن ۾ ڪجھھ ناڪام ٿي سگھي ٿو (مثال طور، ڪجھ نوڊ ناڪام ٿئي ٿو)، پر ھن نظام ۾ يقيني طور تي ڪو به نوڊس نه آھي جيڪي عمدي طور تي ٻين جي خلاف ڪم ڪن ٿا (بزنطيني جنرلن جو ڪم). هن ملڪيت جي ڪري، سسٽم مسلسل رهي ٿو.

2. وحدت - جيڪڏهن سڀئي صحيح ڪم ڪندڙ نوڊس ساڳئي قدر پيش ڪن ٿا v، جنهن جو مطلب آهي هر صحيح آپريٽنگ نوڊ کي هن قدر قبول ڪرڻ گهرجي v.
3. ختم ٿيڻ - سڀئي صحيح آپريٽنگ نوڊس آخرڪار هڪ خاص قدر (زندگي جي ملڪيت) تي کڻندا، جيڪو الگورتھم کي سسٽم ۾ ترقي ڪرڻ جي اجازت ڏئي ٿو. هر فرد صحيح طور تي آپريٽنگ نوڊ کي جلد يا بعد ۾ حتمي قيمت قبول ڪرڻ گهرجي ۽ ان جي تصديق ڪرڻ گهرجي: "منهنجي لاء، هي قيمت صحيح آهي، مان پوري سسٽم سان متفق آهيان."

هڪ مثال ڪيئن اتفاق الورورٿم ڪم ڪندو آهي

جڏهن ته الورورٿم جا خاصيتون مڪمل طور تي واضح نه هوندا. تنهن ڪري، اسان هڪ مثال سان بيان ڪنداسين ته آسان ترين اتفاق الورورٿم ڪهڙي مرحلن مان گذري ٿو هڪ سسٽم ۾ هڪ هم وقت ساز ميسيجنگ ماڊل سان، جنهن ۾ سڀ نوڊس ڪم ڪري رهيا آهن جيئن توقع ڪئي وڃي، پيغام گم نه ٿيندا آهن ۽ ڪجهه به نه ڀڃندو آهي (ڇا اهو واقعي ٿئي ٿو؟).

1. اهو سڀ هڪ شادي جي تجويز (Propose) سان شروع ٿئي ٿو. اچو ته فرض ڪريون ته هڪ ڪلائنٽ هڪ نوڊ سان ڳنڍيل آهي جنهن کي "نوڊ 1" سڏيو ويندو آهي ۽ هڪ ٽرانزيڪشن شروع ڪيو آهي، نوڊ ڏانهن هڪ نئين قيمت گذري ٿو - O. هاڻي کان، اسان "نوڊ 1" کي سڏينداسين. تجويز ڪرڻ. پروپوزر جي طور تي، "نوڊ 1" کي ھاڻي پوري سسٽم کي مطلع ڪرڻ گھرجي ته ان وٽ تازو ڊيٽا آھي، ۽ اھو ٻين سڀني نوڊس ڏانھن پيغام موڪلي ٿو: ”ڏس! معنيٰ ”او“ مون وٽ آئي ۽ مان ان کي لکڻ چاهيان ٿو! مھرباني ڪري پڪ ڪريو ته توھان پڻ "O" کي پنھنجي لاگ ۾ رڪارڊ ڪندا.

   

2. ايندڙ اسٽيج تجويز ڪيل قيمت (ووٽنگ) لاء ووٽنگ آهي. ڇا لاءِ آهي؟ اهو ٿي سگهي ٿو ته ٻين نوڊس کي وڌيڪ تازي معلومات ملي آهي، ۽ انهن وٽ ساڳئي ٽرانزيڪشن تي ڊيٽا آهي.

   
   
   جڏهن نوڊ "نوڊ 1" پنهنجو تجويز موڪلي ٿو، ٻيا نوڊس هن واقعي تي ڊيٽا لاءِ پنهنجا لاگ چيڪ ڪندا آهن. جيڪڏهن ڪو به تضاد نه آهي، نوڊس اعلان ڪري ٿو: "ها، مون وٽ هن واقعي لاء ٻيو ڪوبه ڊيٽا ناهي. "O" قدر جديد معلومات آهي جيڪا اسان مستحق آهيون.

   ڪنهن ٻئي صورت ۾، نوڊس "نوڊ 1" کي جواب ڏئي سگھن ٿا: "ٻڌو! مون وٽ هن ٽرانزيڪشن تي وڌيڪ تازو ڊيٽا آهي. نه 'او'، پر ڪجهه بهتر."

   ووٽنگ اسٽيج تي، نوڊس هڪ فيصلي تي اچي ٿو: يا ته اهي سڀئي ساڳيا قدر قبول ڪن ٿا، يا انهن مان هڪ ووٽ جي خلاف، ظاهر ڪري ٿو ته هن وٽ وڌيڪ تازو ڊيٽا آهي.

3. جيڪڏهن ووٽنگ گول ڪامياب ٿي ويو ۽ هرڪو حق ۾ هو، پوء سسٽم هڪ نئين اسٽيج ڏانهن هلندو آهي - قدر قبول ڪرڻ. "نوڊ 1" ٻين نوڊس ۽ رپورٽن مان سڀني جوابن کي گڏ ڪري ٿو: "هر ڪو قدر تي اتفاق ڪيو "O"! هاڻي مان سرڪاري طور تي اعلان ڪريان ٿو ته ”او“ اسان جي نئين معنيٰ آهي، سڀني لاءِ ساڳيو! ان کي پنهنجي ننڍڙي ڪتاب ۾ لکو، نه وساريو. ان کي پنهنجي لاگ ۾ لکو!”

   

4. باقي نوڊس تصديق (قبول ٿيل) موڪليندا آهن ته انهن قدر لکيو آهي "O"؛ هن وقت ۾ ڪجھ به نئون نه آيو آهي (هڪ قسم جو ٻه مرحلو ڪم). هن اهم واقعي کان پوء، اسان سمجهيو ته ورهايل ٽرانزيڪشن مڪمل ٿي چڪي آهي.
   

اهڙيء طرح، هڪ سادي صورت ۾ اتفاق الورورٿم چار مرحلن تي مشتمل آهي: پروپوزل، ووٽ (ووٽ)، قبول (قبول)، تصديق قبول (قبول).

جيڪڏهن ڪجهه قدم تي اسان معاهدي تائين پهچڻ ۾ ناڪام ٿي ويا آهيون، ته پوء الورورٿم ٻيهر شروع ٿئي ٿو، نوڊس پاران مهيا ڪيل معلومات کي حساب ۾ رکندي جيڪا تجويز ڪيل قيمت جي تصديق ڪرڻ کان انڪار ڪيو.

اتفاق الورورٿم هڪ هم وقت ساز نظام ۾

ان کان اڳ، سڀڪنھن شيء کي هموار هو، ڇاڪاڻ ته اسان هڪ هم وقت ساز پيغام جي ماڊل جي باري ۾ ڳالهائي رهيا هئا. پر اسان ڄاڻون ٿا ته جديد دنيا ۾ اسان هر شي کي غير مطابقت سان ڪرڻ لاء استعمال ڪيو ويو آهي. هڪ اهڙو الورورٿم ڪيئن ڪم ڪندو آهي هڪ سسٽم ۾ هڪ غير مطابقت واري پيغام واري ماڊل سان، جتي اسان يقين رکون ٿا ته نوڊ کان جواب جي انتظار جو وقت پاڻمرادو ڊگهو ٿي سگهي ٿو (انهي سان، نوڊ جي ناڪامي کي پڻ هڪ مثال طور سمجهي سگهجي ٿو جڏهن هڪ نوڊ هڪ غير معمولي ڊگهي وقت لاء جواب ڏئي سگهي ٿو).

هاڻي ته اسان ڄاڻون ٿا ته اتفاق الورورٿم اصولن ۾ ڪيئن ڪم ڪندو آهي، انهن سوالن پڙهندڙن لاءِ هڪ سوال جن ان کي هن وقت تائين پهچايو آهي: اين نوڊس جي سسٽم ۾ ڪيترا نوڊس هڪ غير مطابقت واري پيغام واري ماڊل سان ناڪام ٿي سگهن ٿا ته جيئن سسٽم اڃا تائين اتفاق راءِ تائين پهچي سگهي؟

درست جواب ۽ جواز خراب ڪندڙ جي پويان آهن.صحيح جواب آهي: 0. جيڪڏهن هڪ هم وقت ساز نظام ۾ هڪ نوڊ ناڪام ٿئي ٿو، سسٽم اتفاق راءِ تائين پهچي نه سگهندو. اهو بيان FLP نظريي ۾ ثابت ٿيو آهي، خاص حلقن ۾ مشهور آهي (1985، فشر، لنچ، پيٽرسن، آرٽيڪل جي آخر ۾ اصل سان ڳنڍيل): "جيڪڏهن گهٽ ۾ گهٽ هڪ نوڊ ناڪام ٿئي ٿي ته ورهايل اتفاق حاصل ڪرڻ جو ناممڪن آهي. ”

دوستو، پوءِ اسان وٽ هڪ مسئلو آهي، اسان هر شيءِ کي هم وقت سازي ڪرڻ جا عادي آهيون. ۽ هتي اهو آهي. ڪيئن جيئڻ جاري رکڻ لاء؟

اسان صرف نظريي بابت ڳالهائي رهيا هئاسين، رياضي بابت. ”اتفاق حاصل نه ٿو ڪري سگهجي“ جو مطلب ڇا آهي، رياضياتي ٻولي مان ترجمو ڪرڻ اسان جي - انجنيئرنگ؟ هن جو مطلب آهي ته "هميشه حاصل نه ٿو ڪري سگهجي"، يعني. اتي هڪ ڪيس آهي جنهن ۾ اتفاق راء حاصل نه آهي. هي ڪهڙي قسم جو ڪيس آهي؟

اهو بلڪل مٿي بيان ڪيل زندگي جي ملڪيت جي خلاف ورزي آهي. اسان وٽ هڪ عام معاهدو نه آهي، ۽ سسٽم ترقي نه ٿو ڪري سگهي (مڪمل وقت ۾ مڪمل نه ٿي سگهي) ان صورت ۾ جتي اسان وٽ سڀني نوڊس کان جواب نه آهي. ڇاڪاڻ ته هڪ غير مطابقت واري نظام ۾ اسان وٽ ڪو به اڳڪٿي ڪرڻ وارو جوابي وقت نه آهي ۽ اسان اهو نه ٿا ڄاڻون ته ڪو نوڊ تباهه ٿي ويو آهي يا صرف جواب ڏيڻ ۾ گهڻو وقت وٺي رهيو آهي.

پر عملي طور تي اسان هڪ حل ڳولي سگهون ٿا. اچو ته اسان جي الگورتھم کي ناڪام ٿيڻ جي صورت ۾ ڊگهي وقت تائين ڪم ڪرڻ جي قابل ٿي وڃي (ممڪن طور تي اهو اڻڄاتل ڪم ڪري سگهي ٿو). پر اڪثر حالتن ۾، جڏهن اڪثر نوڊس صحيح ڪم ڪري رهيا آهن، اسان وٽ سسٽم ۾ ترقي ٿيندي.

عملي طور تي، اسان جزوي طور تي هم وقت سازي مواصلاتي ماڊل سان ڊيل ڪندا آهيون. جزوي هم وقت سازي هن ريت سمجهي ويندي آهي: عام صورت ۾، اسان وٽ هڪ غير مطابقت وارو نمونو آهي، پر وقت جي هڪ خاص نقطي جي "عالمي استحڪام واري وقت" جو هڪ خاص تصور رسمي طور تي متعارف ڪرايو ويو آهي.

وقت ۾ هي لمحو ڪنهن به وقت نه اچي سگهي، پر اهو هڪ ڏينهن ضرور ايندو. ورچوئل الارم گھڙي وڄندي، ۽ ان وقت کان اسان اڳڪٿي ڪري سگھون ٿا ته ٽائيم ڊيلٽا جنهن لاءِ پيغام پهچندا. هن لمحي کان، سسٽم هم وقت سازي کان هم وقت تائين بدلجي ٿو. عملي طور تي، اسان خاص طور تي اهڙي سسٽم سان ڊيل ڪندا آهيون.

Paxos الورورٿم اتفاق سان مسئلا حل ڪري ٿو

پينڪس الگورتھم جو ھڪڙو خاندان آھي جيڪو جزوي طور تي هم وقت سازي سسٽم لاءِ اتفاق راءِ جو مسئلو حل ڪري ٿو، ان امڪان جي تابع آھي ته ڪجھ نوڊس ناڪام ٿي سگھن. Paxos جو مصنف آهي ليسلي ليمپٽر. هن 1989 ۾ الورورٿم جي وجود ۽ صحيحيت جو هڪ رسمي ثبوت پيش ڪيو.

پر اهو ثابت ٿيو ته ان جو ثبوت غير معمولي کان پري آهي. پهرين اشاعت صرف 1998 ۾ جاري ڪئي وئي (33 صفحا) الگورتھم کي بيان ڪندي. جيئن ته اهو نڪتو، اهو سمجهڻ تمام ڏکيو هو، ۽ 2001 ۾ مضمون جي وضاحت شايع ڪئي وئي، جيڪا 14 صفحن تي مشتمل هئي. اشاعت جي مقدار کي اهو ظاهر ڪرڻ لاء ڏنو ويو آهي ته حقيقت ۾ اتفاق جو مسئلو بلڪل سادو ناهي، ۽ اهڙي الگورتھم جي پويان ذهين ماڻهن جو هڪ وڏو ڪم آهي.

اها دلچسپ ڳالهه آهي ته ليسلي لامپورٽ پاڻ پنهنجي ليڪچر ۾ نوٽ ڪيو ته ٻئي تفسير واري مضمون ۾ هڪ بيان آهي، هڪ لڪير (هن اها وضاحت نه ڪئي ته ڪهڙي هڪ) آهي، جنهن کي مختلف طريقن سان تشريح ڪري سگهجي ٿو. ۽ انهي جي ڪري، جديد Paxos جي عملن جو هڪ وڏو تعداد مڪمل طور تي صحيح ڪم نٿو ڪري.

Paxos جي ڪم جو تفصيلي تجزيو هڪ کان وڌيڪ مضمون وٺندو، تنهن ڪري مان ڪوشش ڪندس ته مختصر طور تي الورورٿم جو بنيادي خيال بيان ڪريان. منهنجي مضمون جي آخر ۾ لنڪس ۾ توهان هن موضوع ۾ وڌيڪ ڊائيونگ لاء مواد ڳوليندا.

Paxos ۾ ڪردار

Paxos الگورتھم ۾ ڪردار جو تصور آھي. اچو ته ٽن مکيه تي غور ڪريون (اتي اضافي ڪردارن سان تبديليون آهن):

1. تجويز ڪندڙ (اصطلاح پڻ استعمال ڪري سگھجن ٿا: اڳواڻ يا ڪوآرڊينيٽر). اھي ماڻھو آھن جيڪي صارف کان ڪجھ نئين قدر بابت سکندا آھن ۽ اڳواڻ جي ڪردار تي وٺي ويندا آھن. انهن جو ڪم هڪ نئين قيمت لاءِ تجويزن جو هڪ دور شروع ڪرڻ ۽ نوڊس جي وڌيڪ ڪارناما کي همٿائڻ آهي. ان کان علاوه، Paxos ڪجهه حالتن ۾ ڪيترن ئي اڳواڻن جي موجودگي جي اجازت ڏئي ٿو.
2. قبول ڪندڙ (ووٽر). اهي نوڊس آهن جيڪي هڪ خاص قدر کي قبول يا رد ڪرڻ لاءِ ووٽ ڏين ٿا. انهن جو ڪردار تمام اهم آهي، ڇاڪاڻ ته فيصلو انهن تي منحصر آهي: اتفاق جي الگورتھم جي ايندڙ مرحلي کان پوءِ سسٽم ڪهڙي حالت ۾ ويندو (يا نه ڪندو).
3. پڙهندڙن. نوڊس جيڪي صرف قبول ڪن ٿا ۽ نئين قبول ٿيل قدر لکن ٿا جڏهن سسٽم جي حالت تبديل ٿي وئي آهي. اهي فيصلا نه ڪندا آهن، اهي صرف ڊيٽا وصول ڪندا آهن ۽ اهو آخري صارف کي ڏئي سگھن ٿا.

ھڪڙو نوڊ مختلف حالتن ۾ ڪيترن ئي ڪردارن کي گڏ ڪري سگھي ٿو.

ڪورم جو تصور

اسان فرض ڪريون ٿا ته اسان وٽ ھڪڙو نظام آھي N نوڊس ۽ انھن مان وڌ ۾ وڌ F نوڊس ناڪام ٿي سگهن ٿا. جيڪڏهن F نوڊس ناڪام ٿي وڃن، پوء اسان کي گهٽ ۾ گهٽ هجڻ گهرجي 2F+1 قبول ڪندڙ نوڊس.

اهو ضروري آهي ته اسان وٽ هميشه اڪثريت آهي، جيتوڻيڪ بدترين صورتحال ۾، "سٺو" نوڊس جيڪي صحيح ڪم ڪن ٿا. اهو آهي F+1 "سٺو" نوڊس جيڪي اتفاق ڪيو، ۽ آخري قدر قبول ڪيو ويندو. ٻي صورت ۾، اهڙي صورتحال پيدا ٿي سگهي ٿي جتي اسان جا مختلف مقامي گروهه مختلف معنائون وٺن ۽ پاڻ ۾ متفق نه ٿي سگهن. تنهن ڪري، اسان کي ووٽ حاصل ڪرڻ لاء مطلق اڪثريت جي ضرورت آهي.

عام خيال ته ڪيئن Paxos اتفاق الخوارزمي ڪم ڪندو آهي

Paxos الگورتھم ۾ ٻه وڏا مرحلا شامل آھن، جن جي نتيجي ۾ ٻن مرحلن ۾ ورهايل آھن:

1. مرحلو 1a: تيار ڪريو. تياري جي مرحلي دوران، ليڊر (پروپوزر) سڀني نوڊس کي آگاهه ڪري ٿو: ”اسان هڪ نئون ووٽنگ مرحلو شروع ڪري رهيا آهيون. اسان وٽ هڪ نئون دور آهي. هن دور جو تعداد ن آهي. هاڻي اسان ووٽنگ شروع ڪنداسين." هينئر تائين، اهو صرف هڪ نئين چڪر جي شروعات جي رپورٽ ڪري ٿو، پر نئين قيمت جي رپورٽ نٿو ڪري. هن اسٽيج جو ڪم هڪ نئون دور شروع ڪرڻ ۽ هر ڪنهن کي ان جي منفرد نمبر جي خبر ڏيڻ آهي. گول نمبر اھم آھي، اھو ھڪڙو قدر ھجڻ گھرجي سڀني پوئين ووٽنگ نمبرن کان تمام اڳئين اڳواڻن کان. ڇاڪاڻ ته اهو گول نمبر جي مهرباني آهي ته سسٽم ۾ ٻيا نوڊس سمجهندا ته ليڊر جي ڊيٽا ڪيتري تازي آهي. اهو امڪان آهي ته ٻين نوڊس اڳ ۾ ئي ووٽنگ جا نتيجا تمام گهڻو بعد ۾ آهن ۽ صرف ليڊر کي ٻڌائيندو ته هو وقت جي پويان آهي.
2. مرحلو 1b: وعدو. جڏهن قبول ڪندڙ نوڊس نئين ووٽنگ اسٽيج جو نمبر حاصل ڪيو، ٻه نتيجا ممڪن آهن:
   • نئين ووٽ جو نمبر n ڪنهن به اڳوڻي ووٽ جي تعداد کان وڌيڪ آهي جنهن ۾ قبول ڪندڙ حصو ورتو. پوءِ قبول ڪندڙ ليڊر کي واعدو موڪلي ٿو ته اهو ن کان گهٽ تعداد سان وڌيڪ ووٽن ۾ حصو نه وٺندو. جيڪڏهن قبول ڪندڙ پهريان ئي ڪنهن شيءِ لاءِ ووٽ ڏئي چڪو آهي (يعني اهو پهريان ئي ٻئي مرحلي ۾ ڪجهه قدر قبول ڪري چڪو آهي)، پوءِ اهو قبول ٿيل قدر ۽ ووٽ جو تعداد ڳنڍي ٿو جنهن ۾ هن پنهنجي واعدي تي حصو ورتو.
   • ٻي صورت ۾، جيڪڏهن قبول ڪندڙ اڳ ۾ ئي ڄاڻن ٿا ته اعلي نمبرن واري ووٽ بابت، اهو صرف تياري جي قدم کي نظر انداز ڪري سگهي ٿو ۽ اڳواڻ کي جواب نه ڏيندو.
3. مرحلو 2a: قبول ڪريو. ليڊر کي ڪورم جي جواب جو انتظار ڪرڻ جي ضرورت آهي (سسٽم ۾ نوڊس جي اڪثريت) ۽، جيڪڏهن جوابن جو گهربل تعداد ملي ٿو، ته پوء هن وٽ واقعن جي ترقي لاء ٻه اختيار آهن:
   • قبول ڪندڙن مان ڪجھ قدر موڪليا ويا جيڪي اڳ ۾ ئي ووٽ ڏئي چڪا آھن. انهي صورت ۾، اڳواڻ وڌ ۾ وڌ تعداد سان ووٽ مان قيمت چونڊيندو آهي. اچو ته هن قدر کي x سڏيون، ۽ اهو سڀني نوڊس ڏانهن هڪ پيغام موڪلي ٿو جهڙوڪ: "قبول ڪريو (n، x)"، جتي پهرين قيمت پنهنجي پروپوزل قدم کان ووٽنگ نمبر آهي، ۽ ٻيو قدر اهو آهي جيڪو هرڪو گڏ ڪيو ويو آهي، يعني قيمت جنهن لاء اسان اصل ۾ ووٽ.
   • جيڪڏهن قبول ڪندڙن مان ڪنهن به قدر نه موڪليو، پر انهن صرف هن دور ۾ ووٽ ڏيڻ جو واعدو ڪيو، ليڊر انهن کي ووٽ ڏيڻ جي دعوت ڏئي سگهي ٿو انهن جي قيمت، جنهن جي قيمت لاء هو پهرين جڳهه ۾ اڳواڻ بڻجي ويو. اچو ته ان کي y سڏين. اهو سڀني نوڊس ڏانهن پيغام موڪلي ٿو جهڙوڪ: "قبول ڪريو (n، y)"، اڳئين نتيجن وانگر.
4. مرحلو 2b: قبول ٿيل. وڌيڪ، قبول ڪندڙ نوڊس، ليڊر کان "قبول (...)" پيغام حاصل ڪرڻ تي، ان سان متفق آهن (سڀني نوڊس ڏانهن تصديق موڪليو ته اهي نئين قيمت سان متفق آهن) صرف جيڪڏهن انهن ڪجهه واعدو نه ڪيو آهي (ٻيا) ليڊر راؤنڊ نمبر سان ووٽنگ ۾ حصو وٺڻ لاء n' > نٻي صورت ۾ اهي تصديق جي درخواست کي نظر انداز ڪندا.

   جيڪڏهن نوڊس جي اڪثريت ليڊر ڏانهن جواب ڏنو، ۽ انهن سڀني کي نئين قيمت جي تصديق ڪئي، پوء نئين قيمت کي قبول ڪيو ويندو. هوري! جيڪڏهن اڪثريت پهچي نه وئي آهي يا نوڊس آهن جيڪي نئين قيمت کي قبول ڪرڻ کان انڪار ڪري رهيا آهن، پوء هر شي شروع ٿئي ٿي.

اهو ڪيئن آهي Paxos الگورتھم ڪم ڪري ٿو. انهن مرحلن مان هر هڪ ۾ ڪيترائي ذخيرا آهن، اسان عملي طور تي مختلف قسم جي ناڪامين، ڪيترن ئي اڳواڻن جي مسئلن ۽ گهڻو ڪجهه تي غور نه ڪيو آهي، پر هن مضمون جو مقصد صرف پڙهندڙن کي اعلي سطح تي تقسيم ڪيل ڪمپيوٽنگ جي دنيا سان متعارف ڪرائڻ آهي.

اهو پڻ قابل ذڪر آهي ته Paxos صرف پنهنجي قسم جو واحد ناهي، اتي ٻيا الگورتھم آهن، مثال طور، ٻوڙا, پر هي هڪ ٻئي مضمون لاء هڪ موضوع آهي.

وڌيڪ مطالعي لاء مواد جي لنڪ

شروعاتي سطح:

• ورهايل اتفاق ڪيئن ڪم ڪندو آهي؟, Preethi Kasireddy, بلاگ آرٽيڪل تي ميڊيم
• Paxos سادو ڪيو. حقيقي لاء, Adi Kancherla, blog article on Medium
• غير مرڪزي خيالات, Ittai Abraham , blog
• Synchrony، Asynchrony ۽ جزوي هم وقت سازي, Ittai Abraham , بلاگ آرٽيڪل

Leslie Lamport سطح:

• ھڪڙي ناقص عمل سان ورهايل اتفاق راءِ جو امڪان (FLP ناممڪن)، فشر، لنچ ۽ پيٽرسن، ريسرچ پيپر، 1985
• پارٽ ٽائيم پارليامينٽليسلي لمپورٽ، تحقيقي مقالو، 1998
• Paxos سادو ڪيوليسلي لمپورٽ، تحقيقي مقالو، 2001

جو ذريعو: www.habr.com