لذلك دعونا نتخيل. هناك 5 قطط محبوسة في الغرفة ، ومن أجل الذهاب لإيقاظ المالك ، يجب أن يتفقوا جميعًا على هذا ، لأنهم لا يستطيعون فتح الباب إلا بالاعتماد عليه مع خمسة منهم. إذا كانت إحدى القطط هي قطة شرودنغر والقطط الأخرى غير مدركة لقراره ، فإن السؤال الذي يطرح نفسه: "كيف يمكنهم فعل هذا؟"
في هذا المقال ، سأخبرك بعبارات بسيطة عن المكون النظري لعالم الأنظمة الموزعة ومبادئ عملها. وأيضًا ضع في اعتبارك بشكل سطحي الفكرة الرئيسية الكامنة وراء Paxos'a.
عندما يستخدم المطورون البنى التحتية السحابية ، وقواعد البيانات المختلفة ، والعمل في مجموعات من عدد كبير من العقد ، فإنهم واثقون من أن البيانات ستكون متسقة وآمنة ومتاحة دائمًا. لكن أين الضمانات؟
في الواقع ، الضمانات التي لدينا هي ضمانات الموردين. تم وصفها في الوثائق على النحو التالي: "هذه الخدمة موثوقة تمامًا ، ولديها اتفاقية مستوى خدمة معينة ، لا تقلق ، كل شيء سيعمل موزعة كما تتوقع."
نميل إلى الإيمان بالأفضل ، لأن الأعمام الأذكياء من الشركات الكبرى أكدوا لنا أن كل شيء سيكون على ما يرام. نحن لا نسأل أنفسنا: لماذا ، في الواقع ، يمكن أن ينجح هذا على الإطلاق؟ هل هناك أي مبرر رسمي للتشغيل الصحيح لمثل هذه الأنظمة؟
ذهبت مؤخرا إلى وكان مستوحى للغاية من هذا الموضوع. كانت المحاضرات في المدرسة أشبه بفصول في التحليل الرياضي أكثر من أي شيء متعلق بأنظمة الكمبيوتر. ولكن هذه هي بالضبط الطريقة التي تم بها إثبات أهم الخوارزميات التي نستخدمها كل يوم ، دون الشك في ذلك ، في وقت واحد.
تستخدم معظم الأنظمة الموزعة الحديثة خوارزمية إجماع Paxos وتعديلاتها المختلفة. أروع شيء هو أنه يمكن إثبات صحة هذه الخوارزمية ، ومن حيث المبدأ ، إمكانية وجود هذه الخوارزمية ببساطة باستخدام قلم وورقة. في الوقت نفسه ، من الناحية العملية ، يتم استخدام الخوارزمية في أنظمة كبيرة تعمل على عدد كبير من العقد في السحب.
توضيح خفيف لما سيتم مناقشته بعد ذلك: مشكلة جنراليندعونا نلقي نظرة على الإحماء .
لدينا جيشان - أحمر وأبيض. تتمركز القوات البيضاء في المدينة المحاصرة. القوات الحمراء بقيادة الجنرالات A1 و A2 تقع على جانبي المدينة. مهمة حمر الشعر هي مهاجمة المدينة البيضاء والفوز. ومع ذلك ، فإن جيش كل جنرال أحمر على حدة أصغر من جيش البيض.
شروط انتصار حمر الشعر: يجب أن يهاجم كلا الجنرالات في نفس الوقت من أجل الحصول على ميزة عددية على البيض. للقيام بذلك ، يجب أن يتفق الجنرالات A1 و A2 مع بعضهما البعض. إذا هاجم الجميع بشكل منفصل ، فإن حمر الشعر سيخسر.
للتفاوض ، يمكن للجنرالات A1 و A2 إرسال رسل لبعضهم البعض عبر أراضي المدينة البيضاء. قد يصل الرسول بنجاح إلى جنرال متحالف ، أو قد يعترضه العدو. سؤال: هل يوجد مثل هذا التسلسل من الاتصالات بين الجنرالات ذوي الشعر الأحمر (تسلسل إرسال الرسل من A1 إلى A2 والعكس من A2 إلى A1) ، حيث يضمنون الموافقة على الهجوم في الساعة X. هنا ، من خلال الضمانات ، من المفهوم أن كلا الجنرالات سيكون لهما تأكيد لا لبس فيه على أن حليفًا (جنرالًا آخر) سيهاجم بالضبط في الوقت المحدد X.
لنفترض أن A1 أرسل رسولًا إلى A2 برسالة: "فلنهاجم اليوم في منتصف الليل!". لا يمكن للجنرال A1 الهجوم بدون تأكيد من الجنرال A2. إذا وصل الرسول من A1 ، فإن الجنرال A2 يرسل تأكيدًا بالرسالة: "نعم ، دعنا نملأ البيض اليوم." لكن الآن لا يعرف الجنرال A2 ما إذا كان رسوله قد وصل أم لا ، ليس لديه أي ضمانات ما إذا كان الهجوم سيكون متزامنًا. الآن يحتاج الجنرال A2 مرة أخرى إلى التأكيد.
إذا وصفنا اتصالاتهم أكثر ، فقد اتضح ما يلي: بغض النظر عن عدد دورات تبادل الرسائل ، لا توجد طريقة لضمان أن كلا الجنرالات قد تم استلام رسائلهم (بافتراض أنه يمكن اعتراض أي من الرسل).
مشكلة الجنرالين هي توضيح رائع لنظام موزع بسيط للغاية حيث توجد عقدتان مع اتصال غير موثوق به. لذلك ليس لدينا ضمان بنسبة 100٪ بأنها متزامنة. حول مشاكل مماثلة فقط على نطاق أوسع لاحقًا في المقالة.
التعريف بمفهوم النظم الموزعة
النظام الموزع عبارة عن مجموعة من أجهزة الكمبيوتر (يشار إليها فيما يلي باسم العقد) يمكنها تبادل الرسائل. كل عقدة فردية هي كيان مستقل. يمكن للعقدة معالجة المهام من تلقاء نفسها ، ولكن من أجل التواصل مع العقد الأخرى ، فإنها تحتاج إلى إرسال الرسائل واستلامها.
كيف يتم تنفيذ الرسائل على وجه التحديد ، ما هي البروتوكولات المستخدمة - هذا لا يهمنا في هذا السياق. من المهم أن تتمكن عقد النظام الموزع من تبادل البيانات مع بعضها البعض عن طريق إرسال الرسائل.
لا يبدو التعريف بحد ذاته معقدًا للغاية ، ولكن ضع في اعتبارك أن النظام الموزع يحتوي على عدد من السمات التي ستكون مهمة بالنسبة لنا.
سمات الأنظمة الموزعة
- التوافق - إمكانية حدوث أحداث متزامنة أو تنافسية في النظام. علاوة على ذلك ، سوف نعتبر أن الأحداث التي حدثت على عقدتين مختلفتين متزامنة بشكل محتمل حتى يكون لدينا ترتيب واضح لحدوث هذه الأحداث. وعادة لا نفعل ذلك.
- لا توجد ساعة عالمية. ليس لدينا ترتيب واضح للأحداث بسبب عدم وجود ساعة عالمية. في عالم الناس العادي ، تعودنا على حقيقة أن لدينا ساعات ووقت على الإطلاق. كل شيء يتغير عندما يتعلق الأمر بالأنظمة الموزعة. حتى الساعات الذرية فائقة الدقة لها انجراف ، وهناك حالات لا يمكننا فيها تحديد أي من الحدثين حدث أولاً. لذلك ، لا يمكننا الاعتماد على الوقت أيضًا.
- فشل مستقل لعقد النظام. هناك مشكلة أخرى: يمكن أن يحدث خطأ ما لمجرد أن عقدنا ليست أبدية. قد يفشل محرك الأقراص الثابتة ، وقد يتم إعادة تشغيل الجهاز الظاهري في السحابة ، وقد تومض الشبكة وستفقد الرسائل. علاوة على ذلك ، هناك مواقف عندما تعمل العقد ، لكنها في نفس الوقت تعمل ضد النظام. حتى أن الفئة الأخيرة من المشاكل حصلت على اسم منفصل: المشكلة . المثال الأكثر شيوعًا لنظام موزع مع مثل هذه المشكلة هو Blockchain. لكننا اليوم لن ننظر في هذه الفئة الخاصة من المشاكل. سنكون مهتمين بالحالات التي يمكن أن تفشل فيها عقدة واحدة أو أكثر.
- نماذج الاتصال (نماذج الرسائل) بين العقد. لقد اكتشفنا بالفعل أن العقد تتواصل من خلال تبادل الرسائل. يوجد نموذجان معروفان للمراسلة: متزامن وغير متزامن.
نماذج الاتصال بين العقد في الأنظمة الموزعة
نموذج متزامن - نعلم على وجه اليقين أن هناك دلتا زمنية محددة ومحدودة يتم ضمان وصول الرسالة من عقدة إلى أخرى. إذا انتهى هذا الوقت ولم تصل الرسالة ، فيمكننا القول بأمان أن العقدة قد فشلت. في مثل هذا النموذج ، لدينا وقت انتظار متوقع.
نموذج غير متزامن - في النماذج غير المتزامنة ، نفترض أن وقت الانتظار محدود ، ولكن لا توجد دلتا زمنية يمكن بعدها ضمان فشل العقدة. أولئك. يمكن أن يكون وقت انتظار رسالة من العقدة طويلًا بشكل تعسفي. هذا تعريف مهم وسنتحدث عنه أكثر.
مفهوم التوافق في الأنظمة الموزعة
قبل تحديد مفهوم الإجماع رسميًا ، ضع في اعتبارك مثالًا للموقف الذي نحتاج إليه ، وهو - النسخ المتماثل للجهاز.
لدينا بعض السجلات الموزعة. نود أن تكون متسقة وتحتوي على بيانات متطابقة على جميع عقد النظام الموزع. عندما تتعلم إحدى العقد قيمة جديدة ستقوم بكتابتها في السجل ، تتمثل مهمتها في تقديم هذه القيمة لجميع العقد الأخرى بحيث يتم تحديث السجل على جميع العقد ، ويتحول النظام إلى حالة متسقة جديدة. في الوقت نفسه ، من المهم أن تتفق العقد فيما بينها: توافق جميع العقد على أن القيمة الجديدة المقترحة صحيحة ، وتقبل جميع العقد هذه القيمة ، وفي هذه الحالة فقط يمكن للجميع تسجيل قيمة جديدة.
بمعنى آخر: لم تعترض أي من العقد على أن لديها معلومات أكثر حداثة ، وأن القيمة المقترحة كانت غير صحيحة. الاتفاق بين العقد والاتفاق على قيمة مقبولة واحدة صحيحة هو الإجماع في نظام موزع. بعد ذلك ، سنتحدث عن الخوارزميات التي تسمح للنظام الموزع بالوصول إلى إجماع مضمون.
بشكل أكثر رسمية ، يمكننا تحديد خوارزمية الإجماع (أو ببساطة خوارزمية الإجماع) باعتبارها بعض الوظائف التي تأخذ نظامًا موزعًا من الحالة A إلى الحالة B. علاوة على ذلك ، يتم قبول هذه الحالة من قبل جميع العقد ، ويمكن لجميع العقد تأكيدها. كما اتضح ، هذه المهمة ليست تافهة على الإطلاق كما تبدو للوهلة الأولى.
خصائص خوارزمية الإجماع
يجب أن تحتوي خوارزمية الإجماع على ثلاث خصائص حتى يستمر النظام في الوجود ويحقق بعض التقدم في الانتقال من حالة إلى أخرى:
- اتفاقية - يجب أن تأخذ جميع العقد التي تعمل بشكل صحيح نفس القيمة (في المقالات توجد هذه الخاصية أيضًا كخاصية أمان). يجب أن تتوصل جميع العقد التي تعمل الآن (ليست معطلة ولا تفقد الاتصال بالباقي) إلى اتفاق وتقبل بعض القيم المشتركة النهائية.
من المهم أن نفهم هنا أن العقد في النظام الموزع الذي ندرسه تريد الاتفاق. أي أننا نتحدث الآن عن الأنظمة التي يمكن أن يفشل فيها شيء ما ببساطة (على سبيل المثال ، تفشل بعض العقدة) ، ولكن في هذا النظام لا توجد بالتأكيد أي عقد تعمل عن عمد ضد الآخرين (مهمة الجنرالات البيزنطيين). بسبب هذه الخاصية ، يظل النظام ثابتًا.
- النزاهة - إذا كانت جميع العقد التي تعمل بشكل صحيح تقدم نفس القيمة v، لذلك يجب أن تقبل كل عقدة تعمل بشكل صحيح هذه القيمة v.
- الانهاء - ستكتسب جميع العقد العاملة بشكل صحيح في النهاية بعض القيمة (خاصية الحياة) ، مما يسمح للخوارزمية بالتقدم في النظام. يجب على كل عقدة فردية تعمل بشكل صحيح أن تقبل عاجلاً أم آجلاً القيمة النهائية وتؤكدها: "بالنسبة لي ، هذه القيمة صحيحة ، وأنا أتفق مع النظام بأكمله."
مثال على كيفية عمل خوارزمية الإجماع
في حين أن خصائص الخوارزمية قد لا تكون واضحة تمامًا. لذلك ، سوف نوضح بمثال ما هي المراحل التي تمر بها أبسط خوارزمية إجماع في نظام مع نموذج مراسلة متزامنة ، حيث تعمل جميع العقد كما هو متوقع ، ولا تضيع الرسائل ولا شيء ينكسر (هل هذا يحدث بالفعل؟).
- كل شيء يبدأ بمقترح زواج (إقتراح). لنفترض أن عميلاً يتصل بعقدة تسمى "Node 1" ويبدأ معاملة ، ويمرر قيمة جديدة إلى العقدة - O. من الآن فصاعدًا ، سنسمي "العقدة 1" اقترح. نظرًا لأنه يتعين على مقدم الطلب "العقدة 1" الآن إخطار النظام بأكمله بأنه لديه بيانات حديثة ، ويرسل رسائل إلى جميع العقد الأخرى: "انظر! تلقيت القيمة "O" ، وأريد كتابتها! يُرجى تأكيد أنك ستسجل أيضًا "O" في سجلك. "
- المرحلة التالية هي التصويت على القيمة المقترحة (التصويت). لما هذا؟ قد يحدث أن العقد الأخرى تلقت معلومات أكثر حداثة ، ولديها بيانات عن نفس المعاملة.
عندما ترسل العقدة "العقدة 1" Propuse الخاص بها ، تتحقق العقد الأخرى من سجلاتها بحثًا عن بيانات حول هذا الحدث. إذا لم يكن هناك تعارض ، تعلن العقد: "نعم ، ليس لدي بيانات أخرى لهذا الحدث. قيمة "O" هي أحدث المعلومات التي نستحقها ".في أي حالة أخرى ، يمكن للعقد الاستجابة لـ "العقدة 1": "استمع! لدي المزيد من البيانات الحديثة عن هذه المعاملة. ليس "أوه" ، ولكن شيء أفضل. "
في مرحلة التصويت ، تتخذ العقد قرارًا: إما أنها تقبل جميعًا نفس القيمة ، أو يصوت أحدهم ضدها ، مما يدل على أن لديه بيانات أحدث.
- إذا كانت جولة التصويت ناجحة ، وكان الجميع مؤيدين ، ينتقل النظام إلى مرحلة جديدة - قبول القيمة (قبول). تجمع "العقدة 1" جميع الردود من العقد والتقارير الأخرى: "اتفق الجميع على القيمة" O "! الآن أعلن رسميًا أن "O" هو معناها الجديد ، وهو نفس المعنى للجميع! اكتبها في دفتر ملاحظاتك ، ولا تنس. اكتب إلى السجل الخاص بك! "
- ترسل بقية العقد تأكيدًا (مقبولاً) بأنهم كتبوا القيمة "O" لأنفسهم ، ولم يتم استلام أي شيء جديد خلال هذا الوقت (نوع من الالتزام على مرحلتين). بعد هذا الحدث المهم ، نعتبر أن الصفقة الموزعة قد اكتملت.
وهكذا ، تتكون خوارزمية الإجماع في حالة بسيطة من أربع خطوات: اقتراح ، تصويت (تصويت) ، قبول (قبول) ، تأكيد القبول (مقبول).
إذا لم نتمكن في مرحلة ما من التوصل إلى اتفاق ، فسيتم إعادة تشغيل الخوارزمية ، مع مراعاة المعلومات المقدمة من العقد التي رفضت تأكيد القيمة المقترحة.
خوارزمية التوافق في النظام غير المتزامن
قبل ذلك ، كان كل شيء سلسًا ، لأنه كان يتعلق بنموذج المراسلة المتزامن. لكننا نعلم أننا معتادون في العالم الحديث على القيام بكل شيء بشكل غير متزامن. كيف تعمل خوارزمية مماثلة في نظام مع نموذج مراسلة غير متزامن ، حيث نعتقد أن وقت انتظار الاستجابة من عقدة يمكن أن يكون طويلًا بشكل تعسفي (بالمناسبة ، يمكن أيضًا اعتبار فشل العقدة كمثال عند العقدة يمكن أن تستجيب لفترة طويلة بشكل تعسفي).
الآن بعد أن عرفنا كيف تعمل خوارزمية الإجماع من حيث المبدأ ، فإن السؤال المطروح للقراء الفضوليين الذين وصلوا إلى هذه النقطة: كم عدد العقد في نظام N العقد مع نموذج رسالة غير متزامن يمكن أن ينخفض بحيث لا يزال بإمكان النظام الوصول إلى إجماع ؟
الإجابة الصحيحة والأساس المنطقي وراء المفسد.الجواب الصحيح هو: 0. إذا تعطلت عقدة واحدة في نظام غير متزامن ، فلن يتمكن النظام من الوصول إلى توافق في الآراء. تم إثبات هذه العبارة في نظرية FLP المعروفة (1985 ، Fischer ، Lynch ، Paterson ، الرابط إلى الأصل في نهاية المقالة): "استحالة الوصول إلى إجماع موزع إذا فشلت عقدة واحدة على الأقل."
يا رفاق ، إذن لدينا مشكلة ، لقد تعودنا على حقيقة أن كل شيء غير متزامن معنا. وهي كذلك. كيف تستمر في العيش؟
لقد تحدثنا للتو عن النظرية والرياضيات. ماذا تعني عبارة "لا يمكن الوصول إلى إجماع" ، الترجمة من اللغة الرياضية إلى لغتنا - الهندسة؟ هذا يعني أنه "لا يمكن تحقيقه دائمًا" ، أي هناك حالة لا يمكن تحقيق الإجماع فيها. وما هي هذه الحالة؟
هذا هو بالضبط انتهاك لخاصية التيسير الموضحة أعلاه. ليس لدينا اتفاق مشترك ، ولا يمكن للنظام أن يتقدم (لا يمكن أن ينتهي في وقت محدد) في حالة عدم وجود استجابة من جميع العقد. لأنه في النظام غير المتزامن ليس لدينا وقت استجابة يمكن التنبؤ به ولا يمكننا معرفة ما إذا كانت العقدة معطلة أو تستغرق وقتًا طويلاً للاستجابة.
لكن من الناحية العملية ، يمكننا إيجاد حل. دع خوارزمية لدينا قادرة على العمل لفترة طويلة في حالة الفشل (يمكن أن تعمل إلى أجل غير مسمى). ولكن في معظم الحالات ، عندما تعمل معظم العقد بشكل صحيح ، سيكون لدينا تقدم في النظام.
في الممارسة العملية ، نحن نتعامل مع نماذج اتصال متزامنة جزئيًا. يُفهم التزامن الجزئي على النحو التالي: في الحالة العامة ، لدينا نموذج غير متزامن ، ولكن يتم تقديم مفهوم معين عن "وقت التثبيت الشامل" لنقطة زمنية معينة بشكل رسمي.
قد لا تأتي هذه اللحظة من الزمن لوقت طويل بشكل اعتباطي ، لكن يجب أن تأتي في يوم من الأيام. سوف يرن المنبه الافتراضي ، ومن تلك اللحظة فصاعدًا يمكننا التنبؤ بالدلتا الزمنية التي ستصل فيها الرسائل. من هذه النقطة فصاعدًا ، يتحول النظام من غير متزامن إلى متزامن. في الممارسة العملية ، نتعامل مع مثل هذه الأنظمة.
خوارزمية Paxos تحل مشاكل الإجماع
هي مجموعة من الخوارزميات التي تحل مشكلة الإجماع للأنظمة المتزامنة جزئيًا ، بشرط أن تفشل بعض العقد. مؤلف Paxos هو . اقترح دليلًا رسميًا على وجود الخوارزمية وصحتها في عام 1989.
لكن تبين أن الدليل لم يكن تافهاً بأي حال من الأحوال. تم إصدار المنشور الأول فقط في عام 1998 (33 صفحة) يصف الخوارزمية. كما اتضح ، كان من الصعب للغاية فهمه ، وفي عام 2001 تم نشر شرح للمقال ، والذي استغرق 14 صفحة. يتم إعطاء مجلدات المنشورات لإظهار أن مشكلة الإجماع في الواقع ليست بسيطة على الإطلاق ، وخلف هذه الخوارزميات هناك عمل ضخم لأذكى الناس.
من المثير للاهتمام أن ليزلي لامبور نفسه أشار في محاضرته إلى أنه في شرح المقال الثاني هناك عبارة واحدة ، سطر واحد (لم يحدد أي منها) ، والتي يمكن تفسيرها بطرق مختلفة. وبسبب هذا ، فإن عددًا كبيرًا من تطبيقات Paxos الحديثة لا تعمل بشكل صحيح تمامًا.
سيتطلب التحليل التفصيلي لعمل Paxos أكثر من مقال واحد ، لذلك سأحاول نقل الفكرة الرئيسية للخوارزمية باختصار شديد. ستجد في الروابط الموجودة في نهاية مقالتي مواد لمزيد من الغوص في هذا الموضوع.
الأدوار في باكسوس
خوارزمية باكسوس لديها مفهوم الأدوار. ضع في اعتبارك ثلاثة عناصر رئيسية (هناك تعديلات بأدوار إضافية):
- مقدمو العروض (قد تكون هناك أيضًا مصطلحات: قادة أو منسقون). هؤلاء هم الأشخاص الذين يتعلمون عن بعض المعنى الجديد من المستخدم ويتولون دور القائد. مهمتهم هي إطلاق جولة من المقترحات لقيمة جديدة وتنسيق المزيد من الإجراءات للعقد. علاوة على ذلك ، يسمح Paxos بوجود العديد من القادة في مواقف معينة.
- الموافقون (المصوتون). هذه هي العقد التي تصوت لقبول أو رفض قيمة معينة. دورهم مهم للغاية ، لأن القرار يعتمد عليهم: ما الحالة التي سينتقل إليها النظام (أو لا يذهب) بعد المرحلة التالية من خوارزمية الإجماع.
- المتعلمين. العقد التي تقبل وتكتب القيمة المقبولة الجديدة ببساطة عندما تتغير حالة النظام. إنهم لا يتخذون قرارات ، بل يتلقون البيانات فقط ويمكنهم إعطائها للمستخدم النهائي.
يمكن أن تجمع عقدة واحدة بين عدة أدوار في مواقف مختلفة.
مفهوم النصاب
نحن نفترض أن لدينا نظام N العقد. ومعظمهم F العقد قد تفشل. إذا فشلت العقد F ، فيجب أن يكون لدينا على الأقل 2ف+1 العقد المقبولة.
هذا ضروري حتى نتمتع دائمًا ، حتى في أسوأ الحالات ، بالأغلبية "الجيدة" ، والعقد العاملة بشكل صحيح. إنه ف + 1 العقد "الجيدة" التي وافقت ، وسيتم قبول القيمة النهائية. خلاف ذلك ، قد يكون هناك موقف تأخذ فيه المجموعات المحلية المختلفة معاني مختلفة ولن تكون قادرة على الاتفاق فيما بينها. لذلك نحن بحاجة إلى أغلبية مطلقة للفوز بالتصويت.
فكرة عامة عن خوارزمية إجماع باكسوس
تفترض خوارزمية Paxos مرحلتين كبيرتين ، تنقسم كل منهما إلى خطوتين:
- المرحلة 1 أ: التحضير. أثناء مرحلة الإعداد ، يقوم القائد (مقدم الاقتراح) بإبلاغ جميع العقد: "نحن نبدأ مرحلة تصويت جديدة. لدينا جولة جديدة. عدد هذه الجولة ن. سنبدأ التصويت الآن ". حتى الآن ، يقوم فقط بالإبلاغ عن بداية دورة جديدة ، لكنه لا يبلغ عن القيمة الجديدة. تتمثل مهمة هذه المرحلة في بدء جولة جديدة وإبلاغ الجميع برقمها الفريد. الرقم المستدير مهم ، يجب أن يكون أكبر من جميع أرقام التصويت السابقة من جميع القادة السابقين. نظرًا لأنه بفضل الرقم الدائري ، ستفهم العقد الأخرى في النظام مدى حداثة بيانات القائد. من المحتمل أن العقد الأخرى لديها بالفعل نتائج تصويت من جولات متأخرة وستخبر القائد ببساطة أنه متأخر عن الزمن.
- المرحلة 1 ب: الوعد. عندما تتلقى العقد المقبولة عدد مرحلة التصويت الجديدة ، هناك نتيجتان محتملتان:
- العدد n للتصويت الجديد أكبر من عدد الأصوات السابقة التي شارك فيها المُقبل. ثم يرسل المُقبل وعدًا إلى القائد بأنه لن يشارك بعد ذلك في أي أصوات يقل عددها عن n. إذا كان المُقبل قد صوّت بالفعل لشيء ما (أي أنه قد قبل بالفعل بعض القيمة في المرحلة الثانية) ، فإنه يُلحق القيمة المقبولة ورقم التصويت الذي شارك فيه بوعده.
- خلاف ذلك ، إذا كان المتقبل يعرف بالفعل عدد الأصوات المرتفعة ، فيمكنه ببساطة تجاهل خطوة التحضير وعدم الرد على القائد.
- المرحلة 2 أ: قبول. يحتاج القائد إلى انتظار استجابة من النصاب القانوني (معظم العقد في النظام) ، وإذا تم تلقي العدد المطلوب من الردود ، فسيكون لديه خياران لتطوير الأحداث:
- قدم بعض المقبولين القيم التي صوتوا لها بالفعل. في هذه الحالة ، يختار القائد القيمة من التصويت ذي الرقم الأعلى. دعنا نسمي هذه القيمة x ، ونرسل رسالة مثل هذه إلى جميع العقد: "Accept (n، x)" ، حيث تكون القيمة الأولى هي رقم التصويت من خطوة Propose الخاصة بها ، والقيمة الثانية هي ما جمع الجميع من أجله ، أي القيمة التي ، في الواقع ، نصوت لها.
- إذا لم يرسل أي من المتقبلين أي قيم ، لكنهم ببساطة وعدوا بالتصويت في هذه الجولة ، يمكن للقائد دعوتهم للتصويت لقيمتها ، وهي القيمة التي أصبح قائدًا لها على الإطلاق. دعنا نسميها y. يرسل إلى جميع العقد رسالة من النموذج: "Accept (n، y)" بالقياس مع النتيجة السابقة.
- المرحلة 2 ب: مقبولة. علاوة على ذلك ، فإن العقد المقبولة ، عند تلقي الرسالة "قبول (...)" ، من القائد تتفق معها (أرسل تأكيدًا إلى جميع العقد بأنها توافق على القيمة الجديدة) فقط إذا لم تكن قد وعدت ببعض (أخرى) زعيم للمشاركة في التصويت مع عدد الجولة ن '> نوإلا فإنهم يتجاهلون مطالبة التأكيد.
إذا أجابت غالبية العقد على القائد ، وأكدوا جميعًا القيمة الجديدة ، فإن القيمة الجديدة تعتبر مقبولة. الصيحة! إذا لم تتم كتابة الأغلبية أو كانت هناك عقد رفضت قبول القيمة الجديدة ، فسيبدأ كل شيء من جديد.
هذه هي الطريقة التي تعمل بها خوارزمية Paxos. تحتوي كل مرحلة من هذه المراحل على العديد من التفاصيل الدقيقة ، ولم نأخذ في الاعتبار عمليًا أنواعًا مختلفة من الإخفاقات ، ومشكلات القادة المتعددين ، وأكثر من ذلك بكثير ، ولكن الغرض من هذه المقالة هو تعريف القارئ بعالم الحوسبة الموزعة على أعلى مستوى.
وتجدر الإشارة أيضًا إلى أن Paxos ليس الوحيد من نوعه ، فهناك خوارزميات أخرى ، على سبيل المثال ، ولكن هذا موضوع لمقال آخر.
روابط لمواد لمزيد من الدراسة
مستوى المبتدئ:
- ، بريثي كاسيردي ، مقال في مدونة على موقع Medium
- ، Adi Kancherla ، مقالة مدونة على Medium
- مدونة إيتاي إبراهيم
- ، إيتاي أبراهام ، مقال في المدونة
مستوى ليزلي لامبورت:
- فيشر ، لينش وباترسون ، ورقة بحثية ، 1985
- ، ليزلي لامبورت ، ورقة بحث ، 1998
- ، ليزلي لامبورت ، ورقة بحث ، 2001
المصدر: www.habr.com