باكسوس (علوم الحاسوب)

الموسوعة الحرة

في علم الحاسوب ، يُعدّ بروتوكول Paxos مجموعة من البروتوكولات لحلّ مشكلة التوافق في شبكة من المعالجات غير الموثوقة أو المعرّضة للخطأ. التوافق هو عملية الاتفاق على نتيجة واحدة بين مجموعة من المشاركين. وتزداد صعوبة هذه المشكلة عندما يتعرّض المشاركون أو اتصالاتهم لأعطال. [ 1 ]

تُعدّ بروتوكولات الإجماع أساسًا لنهج تكرار آلة الحالة في الحوسبة الموزعة ، كما اقترح ليزلي لامبورت [ 2 ] ودرسه فريد شنايدر [ 3 ] . يُعدّ تكرار آلة الحالة تقنيةً لتحويل الخوارزمية إلى تطبيق موزع مقاوم للأعطال. قد تُهمل التقنيات المخصصة حالات فشل مهمة دون حلّ. يضمن النهج المبدئي الذي اقترحه لامبورت وآخرون معالجة جميع الحالات بأمان.

قُدِّم بروتوكول باكسوس لأول مرة عام 1989، وسُمِّيَ تيمناً بنظام توافق تشريعي خيالي استُخدم في جزيرة باكسوس اليونانية، حيث كتب لامبورت أن البرلمان كان عليه أن يعمل "على الرغم من أن المشرعين كانوا يتجولون باستمرار داخل وخارج قاعة البرلمان". [ 4 ] ونُشِر لاحقاً كمقال في مجلة عام 1998. [ 5 ]

تتضمن عائلة بروتوكولات باكسوس مجموعة من المفاضلات بين عدد المعالجات، وعدد مرات تأخير الرسائل قبل التوصل إلى القيمة المتفق عليها، ومستوى نشاط المشاركين، وعدد الرسائل المرسلة، وأنواع الأعطال. ورغم أنه لا يوجد بروتوكول توافق حتمي مقاوم للأعطال يضمن التقدم في شبكة غير متزامنة (وهي نتيجة أثبتتها ورقة بحثية لفيشر ولينش وباترسون [ 6 ] ) ، فإن باكسوس يضمن السلامة (الاتساق)، ومن الصعب استحداث الظروف التي قد تمنعه ​​من التقدم.

يُستخدم بروتوكول Paxos عادةً في الحالات التي تتطلب استمرارية عالية (مثل نسخ ملف أو قاعدة بيانات )، حيث قد يكون حجم البيانات الدائمة كبيرًا. ويسعى البروتوكول إلى مواصلة العمل حتى خلال فترات توقف عدد محدود من النسخ عن الاستجابة. كما يتضمن آلية لحذف نسخة معطلة نهائيًا أو إضافة نسخة جديدة.

تاريخ

في عام 1988، أثبت لينش ودورك وستوكمير إمكانية حل مشكلة التوافق في مجموعة واسعة من الأنظمة "المتزامنة جزئيًا". [ 7 ] يتشابه بروتوكول باكسوس مع بروتوكول يُستخدم للاتفاق في "النسخ المتماثل المُختوم"، والذي نشره أوكي وليسكوف لأول مرة عام 1988، في سياق المعاملات الموزعة. [ 8 ] قدم باكسوس صيغةً أنيقةً، وتضمن أحد أقدم براهين السلامة لبروتوكول توافق موزع مقاوم للأخطاء.

ترتبط آلات الحالة القابلة لإعادة التكوين بأعمال سابقة حول بروتوكولات البث المتعدد الجماعي الموثوقة التي تدعم عضوية المجموعة الديناميكية، مثل عمل بيرمان في عامي 1985 و1987 على بروتوكول gbcast المتزامن تقريبًا [ 9 ] . يُعدّ gbcast غير شائع في دعم المتانة ومعالجة حالات فشل التقسيم. لا تمتلك معظم بروتوكولات البث المتعدد الموثوقة هذه الخصائص المطلوبة لتطبيقات نموذج تكرار آلة الحالة. وقد نوقشت هذه النقطة في ورقة بحثية من تأليف لامبورت ، ومالخي ، وزو [ 10 ] .

تُعدّ بروتوكولات Paxos جزءًا من فئة نظرية لحلول مشكلة مُصاغة رسميًا على أنها اتفاق موحد مع حالات فشل الأعطال. وقد أثبت كيدار وشراير حدودًا دنيا لهذه المشكلة . [11] وتُقدّم مكتبة Derecho البرمجية المكتوبة بلغة C++، والمخصصة لتكرار آلات الحالة على نطاق واسع في الحوسبة السحابية، بروتوكول Paxos مُدمجًا مع عضوية متزامنة افتراضية ذاتية الإدارة. يتوافق هذا البروتوكول مع حدود كيدار وشراير المثلى ، ويتوافق بكفاءة مع أجهزة مراكز البيانات الحديثة التي تدعم الوصول المباشر للذاكرة عن بُعد (RDMA) . ويستخدم بروتوكول TCP في حال عدم توفر RDMA.

الافتراضات

لتبسيط عرض بروتوكول باكسوس، تم توضيح الافتراضات والتعريفات التالية. توجد تقنيات لتوسيع نطاق التطبيق في المراجع العلمية، ولن يتم تناولها في هذه المقالة.

المعالجات

  • تعمل المعالجات بسرعة عشوائية.
  • قد تتعرض المعالجات للأعطال.
  • قد تعود المعالجات ذات التخزين المستقر إلى الانضمام إلى البروتوكول بعد الأعطال (وفقًا لنموذج فشل الاستعادة بعد التعطل).
  • لا تتواطأ المعالجات، ولا تكذب، ولا تحاول بأي شكل من الأشكال تقويض البروتوكول. (أي أن الأعطال البيزنطية لا تحدث. انظر إلى بروتوكول باكسوس البيزنطي للحصول على حل يسمح بتحمل الأعطال الناجمة عن سلوك عشوائي/خبيث من جانب العمليات).

شبكة

  • يمكن للمعالجات إرسال رسائل إلى أي معالج آخر.
  • يتم إرسال الرسائل بشكل غير متزامن وقد يستغرق تسليمها وقتاً طويلاً بشكل تعسفي.
  • قد تُفقد الرسائل أو يُعاد ترتيبها أو تُكرر.
  • يتم تسليم الرسائل دون تلف. (أي لا تحدث أخطاء بيزنطية. انظر إلى بروتوكول باكسوس البيزنطي للحصول على حل يسمح بتلف الرسائل الناتج عن سلوك عشوائي/خبيث لقنوات المراسلة.)

عدد المعالجات

بشكل عام، يمكن لخوارزمية الإجماع أن تحرز تقدماً باستخدامن=2F+1{\displaystyle n=2F+1}المعالجات، على الرغم من الفشل المتزامن لأي منهاF{\displaystyle F}المعالجات: [ 13 ] بعبارة أخرى، يجب أن يكون عدد العمليات غير المعيبة أكبر بكثير من عدد العمليات المعيبة. مع ذلك، باستخدام إعادة التكوين، يمكن تطبيق بروتوكول يتحمل أي عدد من حالات الفشل الكلي طالما لم يتجاوز عدد حالات الفشل المتزامنة F. بالنسبة لبروتوكولات Paxos، يمكن التعامل مع عمليات إعادة التكوين هذه كتكوينات منفصلة . [ 14 ]

خصائص السلامة والحيوية

لضمان السلامة (وتسمى أيضًا "الاتساق")، تحدد Paxos ثلاث خصائص وتضمن الحفاظ على أول خاصيتين دائمًا، بغض النظر عن نمط الأعطال:

الصلاحية (أو عدم التفاهة )
لا يمكن اختيار وتعلم سوى القيم المقترحة. [ 15 ]
الاتفاق (أو الاتساق ، أو السلامة )
لا يمكن لمتعلمين مختلفين أن يتعلموا قيمًا مختلفة (أو لا يمكن أن يكون هناك أكثر من قيمة واحدة محددة). [ 15 ] [ 16 ]
إنهاء (أو حيوية)
إذا تم اقتراح القيمة C، فسيتعلم المتعلم L في النهاية قيمة ما (إذا بقيت معالجات كافية غير معيبة). [ 16 ]

تجدر الإشارة إلى أن بروتوكول Paxos لا يضمن إنهاء العملية، وبالتالي لا يتمتع بخاصية استمرارية الاتصال. يدعم ذلك نتيجة استحالة فيشر لينش باترسون (FLP) [ 6 ] التي تنص على أن بروتوكول الاتساق لا يمكن أن يمتلك سوى خاصيتين من بين السلامة واستمرارية الاتصال وتحمل الأعطال . وبما أن هدف Paxos هو ضمان تحمل الأعطال ، وهو يضمن السلامة، فإنه لا يمكنه ضمان استمرارية الاتصال أيضًا.

النشر النموذجي

في معظم تطبيقات Paxos، تؤدي كل عملية مشاركة ثلاثة أدوار: المُقترح، والمُستقبِل، والمُتعلِّم. [ 17 ] وهذا يُقلل من تعقيد الرسالة بشكل كبير، دون المساس بصحتها.

في بروتوكول باكسوس، يرسل العملاء الأوامر إلى قائد. أثناء التشغيل العادي، يستقبل القائد أمر العميل، ويُخصص له رقم أمر جديد.أنا{\displaystyle i}ثم يبدأأنا{\displaystyle i}[ 16 ]​​

من خلال دمج الأدوار، يتحول البروتوكول إلى نمط نشر فعال يعتمد على العميل والخادم الرئيسي والنسخة المتماثلة، وهو نمط شائع في مجتمع قواعد البيانات. [ 18 ] وتكمن فائدة بروتوكولات Paxos (بما في ذلك التطبيقات التي تتضمن أدوارًا مدمجة) في ضمان خصائص الأمان الخاصة بها .

يتم تغطية تدفق الرسائل في التنفيذ النموذجي في قسم Multi-Paxos .

باكسوس الأساسي

يُعدّ هذا البروتوكول أبسط بروتوكولات عائلة Paxos. تُحدّد كلّ "نسخة" (أو "تنفيذ") من بروتوكول Paxos الأساسي قيمة مُخرَجة واحدة. يعمل البروتوكول على عدّة جولات. تتكوّن الجولة الناجحة من مرحلتين: المرحلة الأولى (المُقسّمة إلى جزأين أ و ب ) والمرحلة الثانية (المُقسّمة أيضًا إلى جزأين أ و ب ). انظر أدناه وصف المراحل. تجدر الإشارة إلى أننا نفترض نموذجًا غير متزامن، لذا قد يكون مُعالج ما في مرحلة بينما يكون مُعالج آخر في مرحلة أخرى.

المرحلة الأولى

المرحلة 1أ: التحضير

يقوم المُقترح بإنشاء رسالة، نسميها " رسالة تحضير" . تُعرَّف هذه الرسالة برقم فريد، n ، يجب أن يكون أكبر من أي رقم استُخدم سابقًا في رسالة تحضير من قِبل هذا المُقترح. تجدر الإشارة إلى أن n ليس القيمة المُقترحة؛ بل هو مُعرِّف فريد لهذه الرسالة الأولية من قِبل المُقترح. في الواقع، لا يلزم أن تحتوي رسالة التحضير على القيمة المُقترحة (والتي يُرمز لها غالبًا بـ v ).
يختار المُقترح على الأقل نصابًا من المُستقبِلين ، ويرسل إليهم رسالة التحضير التي تحتوي على n منهم. لا ينبغي للمُقترح بدء بروتوكول باكسوس إذا لم يتمكن من التواصل مع عدد كافٍ من المُستقبِلين لتشكيل النصاب.

المرحلة 1ب: الوعد

ينتظر المُستقبِلون رسالة تحضير من أيٍّ من المُقترحين. عندما يتلقى المُستقبِل رسالة تحضير، يجب عليه فحص رقم التعريف، n ، لتلك الرسالة. هناك حالتان:
  1. إذا كان رقم الاقتراح (n) أكبر من أي رقم اقتراح سابق تلقاه المُستقبِل (من أي مُقترح)، فيجب على المُستقبِل إرسال رسالة (تُسمى وعدًا ) إلى المُقترح، تُشير إلى أنه سيتجاهل جميع الاقتراحات المستقبلية التي يقل رقمها عن أو يساوي n . يجب أن يتضمن الوعد أعلى رقم بين الاقتراحات التي قبلها المُستقبِل سابقًا، بالإضافة إلى القيمة المقبولة المقابلة. رسالة التحضير الأولى تُحقق هذا الشرط تلقائيًا.
  2. إذا كان رقم الاقتراح (n) أقل من أو يساوي أي رقم اقتراح سابق تلقاه المُستقبِل، فلا داعي لأن يردّ المُستقبِل ويمكنه تجاهل الاقتراح. مع ذلك، ولأغراض التحسين، فإن إرسال ردّ رفض، أو ردّ إقرار سلبي ( NAK )، سيُعلم المُقترح بأنه يستطيع التوقف عن محاولته التوصل إلى توافق في الآراء باستخدام الاقتراح رقم (n) .

المرحلة الثانية

المرحلة 2أ: القبول

إذا تلقى مُقترح وعودًا من نصاب من المُستقبِلين، فعليه تحديد قيمة v لاقتراحه. إذا كان أي من المُستقبِلين قد قبل أي اقتراح سابقًا، فسيكونون قد أرسلوا قيمهم إلى المُقترح، الذي يجب عليه الآن تحديد قيمة اقتراحه، v ، لتكون القيمة المرتبطة بأعلى رقم اقتراح أبلغ عنه المُستقبِلون، ولنسمها z . إذا لم يقبل أي من المُستقبِلين أي اقتراح حتى هذه اللحظة، فيمكن للمُقترح اختيار القيمة التي أراد اقتراحها في الأصل، ولتكن x . [ 19 ]
يرسل المُقترح رسالة قبول ، (ن، ع) ، إلى نصاب المُستقبِلين، مُتضمنةً القيمة المُختارة لاقتراحه، ع، ورقم الاقتراح ن (وهو نفس الرقم الموجود في رسالة التحضير المُرسلة مُسبقًا إلى المُستقبِلين). لذا، تكون رسالة القبول إما (ن، ع=ع) أو، في حال لم يقبل أي من المُستقبِلين قيمةً مُسبقًا، (ن، ع=س) .

يجب تفسير رسالة القبول هذه على أنها "طلب"، كما في "اقبل هذا الاقتراح من فضلك!".

المرحلة 2ب: مقبول

إذا تلقى المُستقبِل رسالة قبول، (n، v) ، من المُقترح، فيجب عليه قبولها إذا وفقط إذا لم يكن قد وعد بالفعل (في المرحلة 1ب من بروتوكول Paxos) بالنظر فقط في المقترحات التي تحتوي على مُعرّف أكبر من n .
إذا لم يكن المُستقبِل قد وعد مسبقًا (في المرحلة 1ب) بالنظر فقط في المقترحات التي تحمل مُعرِّفًا أكبر من n ، فعليه تسجيل القيمة v (من رسالة القبول المُستلمة للتو ) كقيمة مقبولة (للبروتوكول)، وإرسال رسالة قبول إلى المُقترح وكل مُتعلِّم (والذي قد يكون عادةً المُقترحين أنفسهم). لن يتعرف المُتعلِّمون على القيمة المُقررة إلا بعد استلام رسائل قبول من أغلبية المُستقبِلين، أي ليس بعد استلام رسالة القبول الأولى فقط.
وإلا، فإنه يمكنه تجاهل رسالة أو طلب القبول.

لاحظ أن الإجماع يتحقق عندما تقبل أغلبية المُستقبِلين نفس رقم المُعرِّف (بدلاً من نفس القيمة ). ولأن كل مُعرِّف فريد لكل مُقترح، ولا يُمكن اقتراح سوى قيمة واحدة لكل مُعرِّف، فإن جميع المُستقبِلين الذين يقبلون نفس المُعرِّف يقبلون بالتالي نفس القيمة. تُؤدي هذه الحقائق إلى بعض السيناريوهات غير البديهية التي لا تُؤثر على صحة العملية: يُمكن للمُستقبِلين قبول قيم مُتعددة ، وقد تحصل قيمة ما على أغلبية بين المُستقبِلين (ذوي مُعرِّفات مُختلفة) ليتم تغييرها لاحقًا ، وقد يستمر المُستقبِلون في قبول المقترحات بعد أن يحصل مُعرِّف ما على أغلبية . ومع ذلك، يضمن بروتوكول باكسوس أن الإجماع دائم وأن القيمة المُختارة غير قابلة للتغيير.

عندما تفشل الجولات

تفشل الجولات عندما يرسل عدة مقدمي مقترحات رسائل تحضير متضاربة ، أو عندما لا يتلقى مقدم المقترح النصاب القانوني من الردود ( وعد أو قبول ). في هذه الحالات، يجب بدء جولة أخرى برقم مقترح أعلى.

يمكن استخدام باكسوس لاختيار قائد

لاحظ أن المُقترح في بروتوكول باكسوس يمكنه أن يقترح "أنا القائد" (أو، على سبيل المثال، "المُقترح س هو القائد"). [ 20 ] وبفضل ضمانات الاتفاق والصحة في باكسوس، إذا قُبل الاقتراح من قِبل النصاب القانوني، يصبح المُقترح معروفًا بأنه القائد لجميع العُقد الأخرى. وهذا يُلبي متطلبات انتخاب القائد [ 21 ] لأنه توجد عقدة واحدة تعتقد أنها القائد، وعقدة واحدة معروفة بأنها القائد في جميع الأوقات.

تمثيل بياني لتدفق الرسائل في بروتوكول باكسوس الأساسي

تُمثل المخططات التالية عدة حالات/مواقف لتطبيق بروتوكول باكسوس الأساسي. تُظهر بعض الحالات كيف يتعامل بروتوكول باكسوس الأساسي مع تعطل بعض المكونات (الاحتياطية) للنظام الموزع.

لاحظ أن القيم التي تم إرجاعها في رسالة Promise تكون "null" في المرة الأولى التي يتم فيها تقديم اقتراح (حيث لم يقبل أي متلق قيمة من قبل في هذه الجولة).

باكسوس الأساسي بدون أعطال

في الرسم البياني أدناه، يوجد عميل واحد، ومقترح واحد، وثلاثة موافقين (أي أن النصاب القانوني هو 3)، ومتعلمان (ممثلان بالخطين الرأسيين). يمثل هذا الرسم البياني حالة الجولة الأولى، وهي ناجحة (أي لم تفشل أي عملية في الشبكة).

هنا، V هو الأخير من (Va، Vb، Vc).

حالات الخطأ في Paxos الأساسي

أبسط حالات الخطأ هي فشل أحد المُستقبِلين (مع بقاء نصاب المُستقبِلين) وفشل مُتعلِّم زائد. في هذه الحالات، لا يتطلب البروتوكول أي "استعادة" (أي أنه ينجح): لا حاجة لجولات أو رسائل إضافية، كما هو موضح أدناه (في الرسمين/الحالتين التاليتين).

بروتوكول Paxos الأساسي عند فشل جهاز الاستقبال

في الرسم التخطيطي التالي، يفشل أحد المستلمين في النصاب، وبالتالي يصبح حجم النصاب 2. في هذه الحالة، لا يزال بروتوكول Paxos الأساسي ناجحًا.

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | X-------->| | | | | | طلب | X--------->|->|->| | | Prepare(1) | | | | ! | | !! فشل !! | |<---------X--X | | Promise(1,{Va, Vb, null}) | X--------->|->| | | قبول!(1,V) | |<---------X--X--------->|->| مقبول (1، V) |<---------------------------------X--X استجابة | | | | | |

باكسوس الأساسي عند فشل المتعلم الزائد

في الحالة التالية، يفشل أحد المتعلمين (الزائدين)، لكن بروتوكول Paxos الأساسي لا يزال ينجح.

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | X-------->| | | | | | طلب | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | قبول!(1,V) | |<---------X--X--X------>|->| مقبول (1، V) | | | | | | ! !! فشل !! |<---------------------------------X استجابة | | | | | |

بروتوكول باكسوس الأساسي عند فشل المُقترح

في هذه الحالة، يفشل المُقترح بعد اقتراح قيمة، ولكن قبل التوصل إلى اتفاق. تحديدًا، يفشل في منتصف رسالة القبول، لذا يتلقى مُوافق واحد فقط من النصاب القيمة. في هذه الأثناء، يتم انتخاب قائد جديد (مُقترح) (لكن هذا غير موضح بالتفصيل). تجدر الإشارة إلى وجود جولتين في هذه الحالة (تجري الجولات عموديًا، من الأعلى إلى الأسفل).

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | X----->| | | | | | طلب | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! فشل القائد أثناء البث !! | X------------>| | | | | قبول!(1,V) | ! | | | | | | | | | | | | !! قائد جديد !! | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{V, null, null}) | X--------->|->|->| | | قبول!(2,V) | |<---------X--X------>|->| مقبول (2، V) |<---------------------------------X--X استجابة | | | | | | |

باكسوس الأساسي عند تعارض عدة مقترحين

تُعدّ الحالة الأكثر تعقيدًا هي عندما يعتقد أكثر من مُقترح أن نفسه قائدًا. على سبيل المثال، قد يفشل القائد الحالي ثم يتعافى لاحقًا، لكن المُقترحين الآخرين قد أعادوا اختيار قائد جديد. لم يدرك القائد المُتعافي هذا الأمر بعد، ويحاول بدء جولة واحدة في صراع مع القائد الحالي. يُظهر الرسم البياني أدناه أربع جولات غير ناجحة، ولكن قد يكون هناك المزيد (كما هو مُقترح في أسفل الرسم البياني).

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | X----->| | | | | | طلب | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{null,null,null}) | ! | | | | | !! فشل القائد | | | | | | | !! قائد جديد (يعلم أن الرقم الأخير كان 1) | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{null,null,null}) | | | | | | | | !! الزعيم القديم يتعافى | | | | | | | | !! الزعيم المخضرم يحاول مرتين، لكن محاولته باءت بالفشل | X------------>|->|->| | | Prepare(2) | |<------------X--X--X | | Nack(2) | | | | | | | | !! الزعيم العجوز يحاول 3 | X------------>|->|->| | | Prepare(3) | |<------------X--X--X | | Promise(3,{null,null,null}) | | | | | | | | !! زعيم جديد يقترح، ويرفض | | X--------->|->|->| | | قبول!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | | !! قائد جديد يجرب 4 | | X--------->|->|->| | | Prepare(4) | | |<---------X--X--X | | Promise(4,{null,null,null}) | | | | | | | | !! زعيم قديم يقترح، يُرفض | X------------>|->|->| | | قبول!(3,Vb) | |<------------X--X--X | | Nack(4) | | | | | | | | ... وهكذا دواليك ...

بروتوكول Paxos الأساسي حيث يقبل المُستقبِل قيمتين مختلفتين

في الحالة التالية، يحصل أحد المُقترحين على قبول القيمة V1 من قِبل مُستقبِل واحد قبل أن يفشل. يقوم مُقترح جديد بتجهيز المُستقبِلين الذين لم يقبلوا V1 مُطلقًا، مما يسمح له باقتراح V2. ثم يتم قبول V2 من قِبل جميع المُستقبِلين، بما في ذلك المُستقبِل الذي قبل V1 في البداية.

مُقترح مُتقبّل مُتعلّم | | | | | | | X--------->|->|->| | | Prepare(1) |<---------X--X--X | | Promise(1,{null,null,null}) x--------->| | | | | قبول!(1,V1) | | X------------>|->| مقبول (1، الإصدار 1) ! | | | | | | !! فشل !! | | | | | | X--------->|->| | | Prepare(2) |<---------X--X | | Promise(2,{null,null}) X------>|->|->| | | قبول!(2,V2) |<------X--X--X------>|->| مقبول (2، الإصدار 2) | | | | | |

بروتوكول باكسوس الأساسي حيث لا تكفي أغلبية المعرفات المتعددة

في الحالة التالية، يحصل أحد المُقترحين على قبول القيمة V1 من أحد المُستقبِلين قبل أن يفشل. يقوم مُقترح جديد بتجهيز المُستقبِلين الذين لم يقبلوا V1، مما يسمح له باقتراح V2. يتمكن هذا المُقترح من إقناع مُستقبِل واحد بقبول V2 قبل أن يفشل. يجد مُقترح جديد أغلبية تضم المُستقبِل الذي قبل V1، ويجب عليه اقتراحها. ينجح المُقترح في إقناع مُستقبِلين اثنين بقبولها قبل أن يفشل. عند هذه النقطة، يكون ثلاثة مُستقبِلين قد قبلوا V1، ولكن ليس لنفس المُعرِّف. أخيرًا، يقوم مُقترح جديد بتجهيز الأغلبية التي لم ترَ أكبر مُعرِّف مقبول. القيمة المرتبطة بأكبر مُعرِّف في تلك الأغلبية هي V2، لذلك يجب عليه اقتراحها. ثم يُقنع هذا المُقترح جميع المُستقبِلين بقبول V2، مُحققًا بذلك الإجماع.

 مُقترح مُتقبّل مُتعلّم | | | | | | | | | | | X---------------->|->|->|->|->| | | Prepare(1) |<---------------X--X--X--X--X | | Promise(1,{null,null,null,null,null}) x--------------->| | | | | | | قبول!(1,V1) | | | | X------------------>|->| مقبول (1، الإصدار 1) ! | | | | | | | | | | !! فشل !! | | | | | | | | | | X--------------->|->|->|->| | | Prepare(2) |<---------------X--X--X--X | | Promise(2,{null,null,null,null}) X--------------->| | | | | | قبول!(2,V2) | | | | X--------------->|->| مقبول (2، الإصدار 2) ! | | | | | | | | | !! فشل !! | | | | | | | | | X--------->|---->|->|->| | | Prepare(3) |<---------X-----X--X--X | | Promise(3,{V1,null,null,null}) X--------------->|->| | | | قبول!(3,V1) | | | | X--X--------->|->| مقبول (3، الإصدار 1) ! | | | | | | | | !! فشل !! | | | | | | | | X------>|->|------->| | | Prepare(4) |<------X--X--|--|--X | | Promise(4,{V1(1),V2(2),null}) X------>|->|->|->|->| | | قبول!(4,V2) | X--X--X--X--X------>|->| مقبول (4، الإصدار 2)

بروتوكول باكسوس الأساسي حيث لا يستطيع مقدمو الاقتراحات الجدد تغيير الإجماع الحالي

في الحالة التالية، يحصل أحد المُقترحين على قبول القيمة V1 من اثنين من المُوافقين قبل أن يفشل. يمكن لمُقترح جديد بدء جولة أخرى، لكن يستحيل عليه الآن إعداد أغلبية لا تضم ​​مُوافقًا واحدًا على الأقل قبل V1. وبالتالي، حتى وإن لم يرَ المُقترح الإجماع الحالي، فإن خياره الوحيد هو اقتراح القيمة المتفق عليها مسبقًا. يمكن للمُقترحين الجدد زيادة المُعرّف باستمرار لإعادة تشغيل العملية، لكن لا يمكن تغيير الإجماع أبدًا.

مُقترح مُتقبّل مُتعلّم | | | | | | | X--------->|->|->| | | Prepare(1) |<---------X--X--X | | Promise(1,{null,null,null}) x--------->|->| | | | قبول!(1,V1) | | X--X--------->|->| مقبول (1، الإصدار 1) ! | | | | | | !! فشل !! | | | | | | X--------->|->| | | Prepare(2) |<---------X--X | | Promise(2,{V1,null}) X------>|->|->| | | قبول!(2، الإصدار 1) |<------X--X--X------>|->| مقبول (2، الإصدار 1) | | | | | |

متعدد الباكسوس

يتطلب النشر النموذجي لبروتوكول Paxos تدفقًا مستمرًا من القيم المتفق عليها التي تعمل كأوامر لآلة حالة موزعة. إذا كان كل أمر ناتجًا عن نسخة واحدة من بروتوكول Paxos الأساسي ، فسينتج عن ذلك قدر كبير من الحمل الزائد.

إذا كان القائد مستقرًا نسبيًا، تصبح المرحلة الأولى غير ضرورية. وبالتالي، من الممكن تخطي المرحلة الأولى في الحالات اللاحقة للبروتوكول مع نفس القائد.

لتحقيق ذلك، يُضاف رقم الجولة I إلى كل قيمة، ويتم زيادته في كل جولة بواسطة نفس القائد. يقلل بروتوكول Multi-Paxos زمن تأخير الرسائل الخالية من الأخطاء (من الاقتراح إلى التعلم) من 4 تأخيرات إلى تأخيرين.

تمثيل بياني لتدفق الرسائل في نظام Multi-Paxos

باكسوس متعدد بدون أعطال

يوضح الرسم التخطيطي التالي حالة واحدة فقط (أو "تنفيذًا") لبروتوكول باكسوس الأساسي، مع قائد أولي (مقترح). تجدر الإشارة إلى أن بروتوكول باكسوس المتعدد يتكون من عدة حالات من بروتوكول باكسوس الأساسي.

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | --- الطلب الأول --- X-------->| | | | | | طلب | X--------->|->|->| | | Prepare(N) | |<---------X--X--X | | Promise(N,I,{Va,Vb,Vc}) | X--------->|->|->| | | قبول!(N,I,V) | |<---------X--X------>|->| مقبول (N,I,V) |<---------------------------------X--X استجابة | | | | | | |

حيث V = آخر (Va، Vb، Vc).

تعدد الباكسوس عندما يمكن تخطي المرحلة 1

في هذه الحالة، تستخدم النسخ اللاحقة من بروتوكول Paxos الأساسي (المُمثَّل بـ I+1 ) نفس القائد، لذا يتم تخطي المرحلة الأولى (من هذه النسخ اللاحقة من بروتوكول Paxos الأساسي)، والتي تتكون من مرحلتي الإعداد والوعد الفرعيتين. تجدر الإشارة إلى أن القائد يجب أن يكون مستقرًا، أي لا ينبغي أن يتعطل أو يتغير.

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | --- تلبية الطلبات --- X-------->| | | | | | طلب | X--------->|->|->| | | قبول!(N,I+1,W) | |<---------X--X------>|->| مقبول(N,I+1,W) |<---------------------------------X--X استجابة | | | | | | |

باكسوس متعددة عند دمج الأدوار

يتمثل أحد أساليب نشر Multi-Paxos الشائعة في دمج أدوار المُقترحين والمُستقبلين والمتعلمين في "خوادم". وبالتالي، في النهاية، لا يوجد سوى "عملاء" و"خوادم".

يمثل الرسم التخطيطي التالي أول "مثال" لبروتوكول Paxos الأساسي، عندما يتم دمج أدوار المُقترح والمُستقبل والمتعلم في دور واحد يسمى "الخادم".

خوادم العميل | | | | --- الطلب الأول --- X-------->| | | طلب | X->|->| Prepare(N) | |<-X--X Promise(N, I, {Va, Vb}) | X->|->| قبول!(N, I, Vn) | X<>X<>X مقبول(N, I) |<--------X | | رد | | | |

تعدد الأدوار عندما تتداخل الأدوار ويكون القائد ثابتًا

في الحالات اللاحقة من بروتوكول Paxos الأساسي، مع نفس القائد كما في الحالات السابقة من بروتوكول Paxos الأساسي، يمكن تخطي المرحلة 1.

خوادم العميل X-------->| | | طلب | X->|->| قبول!(N,I+1,W) | X<>X<>X مقبول(N,I+1) |<--------X | | رد | | | |

التحسينات

يمكن إجراء عدد من التحسينات لتقليل عدد الرسائل المتبادلة، ولتحسين أداء البروتوكول، وما إلى ذلك. يتم الإبلاغ عن بعض هذه التحسينات أدناه.

يمكننا توفير الرسائل على حساب تأخير إضافي في إرسالها، وذلك من خلال وجود مُتعلّم متميز واحد يُبلغ المُتعلّمين الآخرين عند اكتشافه اختيار قيمة معينة. ثم تُرسل وحدات الاستقبال رسائل " مقبول " إلى المُتعلّم المتميز فقط. في معظم التطبيقات، يؤدي المعالج نفسه دوري القائد والمُتعلّم المتميز. [ 22 ]
يمكن للقائد أن يرسل رسائل " استعد واقبل !" إلى نصاب من المقبولين. وطالما أن جميع المقبولين في هذا النصاب يعملون ويمكنهم التواصل مع القائد والمتعلمين، فلا حاجة للمقبولين غير الموجودين في النصاب للقيام بأي شيء. [ 22 ]
لا يكترث المُستقبِلون بالقيمة المُختارة. فهم ببساطة يستجيبون لرسائل "التحضير " و "القبول" لضمان اختيار قيمة واحدة فقط، حتى في حال حدوث أعطال. مع ذلك، إذا علم المُستقبِل بالقيمة المُختارة، فبإمكانه تخزينها في وحدة تخزين ثابتة ومسح أي معلومات أخرى مُخزّنة فيها. إذا تلقى المُستقبِل لاحقًا رسالة " التحضير " أو "القبول" ، فبدلًا من تنفيذ إجراء المرحلة 1ب أو المرحلة 2ب، يُمكنه ببساطة إبلاغ القائد بالقيمة المُختارة. [ 22 ]
بدلاً من إرسال القيمة v، يمكن للقائد إرسال تجزئة v إلى بعض المُستقبِلين في رسائل Accept! الخاصة به . سيتعلم المُتعلِّم أن v قد تم اختيارها إذا تلقى رسائل Accepted إما لـ v أو لتجزئتها من مجموعة من المُستقبِلين، وكانت إحدى هذه الرسائل على الأقل تحتوي على v بدلاً من تجزئتها. مع ذلك، قد يتلقى القائد رسائل Promise تُخبره بتجزئة القيمة v التي يجب عليه استخدامها في إجراء Phase2a الخاص به دون إخباره بالقيمة الفعلية لـ v. في هذه الحالة، لا يستطيع القائد تنفيذ إجراء Phase2a الخاص به حتى يتواصل مع عملية تعرف v. [ 22 ]
يمكن للمقترح إرسال اقتراحه إلى القائد فقط بدلاً من جميع المنسقين. ومع ذلك، يتطلب هذا بث نتيجة خوارزمية اختيار القائد إلى المقترحين، وهو ما قد يكون مكلفًا. لذا، قد يكون من الأفضل السماح للمقترح بإرسال اقتراحه إلى جميع المنسقين. (في هذه الحالة، يحتاج المنسقون أنفسهم فقط إلى معرفة من هو القائد). [ 15 ]
بدلاً من أن يرسل كل مُستقبِل رسائل قبول إلى كل مُتعلِّم، يمكن للمُستقبِلين إرسال رسائل قبولهم إلى القائد، ويمكن للقائد إبلاغ المُتعلِّمين عند اختيار قيمة. ومع ذلك، يُضيف هذا تأخيرًا إضافيًا في الرسائل. [ 15 ]
"وأخيرًا، لاحظ أن المرحلة 1 غير ضرورية للجولة 1 .. يمكن لقائد الجولة 1 أن يبدأ الجولة بإرسال رسالة قبول! مع أي قيمة مقترحة." [ 15 ]

باكسوس رخيصة

يقوم Cheap Paxos بتوسيع Basic Paxos لتحمل حالات الفشل F مع F+1 معالج رئيسي و F معالج مساعد عن طريق إعادة التكوين الديناميكي بعد كل حالة فشل.

يأتي هذا الانخفاض في متطلبات المعالج على حساب استمرارية النظام؛ فإذا تعطل عدد كبير من المعالجات الرئيسية في فترة وجيزة، يجب أن يتوقف النظام حتى تتمكن المعالجات المساعدة من إعادة تهيئته. وخلال فترات الاستقرار، لا تشارك المعالجات المساعدة في البروتوكول.

"مع وجود معالجين فقط، p و q، لا يستطيع أيٌّ منهما التمييز بين تعطل المعالج الآخر وتعطل وسيط الاتصال. لذا، يلزم وجود معالج ثالث. مع ذلك، لا يُشترط أن يشارك هذا المعالج الثالث في اختيار تسلسل الأوامر. يجب أن يتخذ إجراءً فقط في حالة تعطل p أو q، وبعد ذلك يتوقف عن العمل بينما يستمر p أو q في تشغيل النظام بمفرده. وبالتالي، يمكن أن يكون المعالج الثالث صغيرًا/بطيئًا/رخيصًا، أو معالجًا مُخصصًا في المقام الأول لمهام أخرى." [ 22 ]

تدفق الرسائل: باكسوس متعددة رخيصة

مثال يتضمن ثلاثة مستقبلين رئيسيين، ومستقبل مساعد واحد، وحجم نصاب يبلغ ثلاثة، يوضح فشل معالج رئيسي واحد وإعادة التكوين اللاحقة:

 {المُستقبِلون} المُقترح الرئيسي المساعد المتعلم | | | | | | -- المرحلة الثانية -- X----------->|->|->| | | موافق!(N,I,V) | | | ! | | --- فشل! --- |<-----------X--X--------------->| مقبول (N,I,V) | | | | | -- تم اكتشاف خطأ (تم قبول 2 فقط) X----------->|->|------->| | قبول! (N,I,V) (إعادة الإرسال، بما في ذلك Aux) |<-----------X--X--------X------>| مقبول (N,I,V) | | | | | -- إعادة التكوين : النصاب = 2 -- X----------->|->| | | قبول!(N,I+1,W) (المساعد غير مشارك) |<-----------X--X--------------->| مقبول(N,I+1,W) | | | | |

فاست باكسوس

يُعمم بروتوكول Fast Paxos بروتوكول Basic Paxos لتقليل تأخير الرسائل من البداية إلى النهاية. في بروتوكول Basic Paxos، يبلغ تأخير الرسائل من طلب العميل إلى لحظة الاستجابة ثلاثة أضعاف تأخير الرسائل. يسمح بروتوكول Fast Paxos بتأخيرين فقط، ولكنه يتطلب ما يلي: (1) أن يتكون النظام من 3f+1 مُستقبِل لتحمّل ما يصل إلى f من الأعطال (بدلاً من 2f+1 في البروتوكول التقليدي)، و(2) أن يُرسل العميل طلبه إلى وجهات متعددة.

بشكل بديهي، إذا لم يكن لدى القائد أي قيمة ليقترحها، فيمكن للعميل إرسال رسالة قبول مباشرةً إلى المُستقبِلين. سيرد المُستقبِلون كما في بروتوكول باكسوس الأساسي، مُرسلين رسائل قبول إلى القائد وكل مُتعلّم، مما يُحقق تأخيرًا في الرسائل بمقدار رسالتين من العميل إلى المُتعلّم.

إذا اكتشف القائد تصادمًا، فإنه يحلّه بإرسال رسائل قبول لجولة جديدة، والتي تُقبل كالمعتاد. تتطلب تقنية الاسترداد المنسقة هذه تأخيرًا في الرسائل من العميل إلى المتعلم بمقدار أربع رسائل.

تتحقق عملية التحسين النهائية عندما يحدد القائد أسلوب استعادة مسبقًا، مما يسمح للمستقبلين بتنفيذ عملية استعادة التصادم بأنفسهم. وبالتالي، يمكن أن تتم عملية استعادة التصادم غير المنسقة في ثلاث فترات تأخير للرسائل (وفترتين فقط إذا كان جميع المتعلمين مستقبلين أيضًا).

تدفق الرسائل: باكسوس سريع، غير متضارب

عميل قائد متقبل متعلم | | | | | | | | | X--------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | X------------------->|->|->|->| | | قبول!(شمال، شرق، غرب) | |<---------X--X--X------>|->| مقبول (شمال، شرق، غرب) |<------------------------------------X--X الاستجابة (W) | | | | | | | |

تدفق الرسائل: بروتوكول باكسوس السريع، مقترحات متضاربة

مقترحات متضاربة مع عملية استعادة منسقة. ملاحظة: لا يحدد البروتوكول كيفية التعامل مع طلب العميل المرفوض.

عميل قائد متقبل متعلم | | | | | | | | | | | | | | | | | | | | | | | | | | | !! مقترحات متضاربة متزامنة | | | | | | | | | !! تم استلامها بترتيب مختلف | | | | | | | | | !! بواسطة المقبولين | X--------------?|-?|-?|-?| | | موافق!(N,I,V) X-----------------؟|-؟|-؟|-؟| | | موافق!(شمال، شرق، غرب) | | | | | | | | | | | | | | | | | | !! يختلف المتقبلون حول القيمة | | |<-------X--X->|->|----->|->| مقبول (لا، أ، هـ) | | |<-------|<-|<-X--X----->|->| مقبول (شمال، شرق، غرب) | | | | | | | | | | | | | | | | | | !! اكتشاف التصادم والتعافي | | X------->|->|->|->| | | قبول!(N+1,I,W) | | |<-------X--X--X----->|->| مقبول (N+1، I، W) |<---------------------------------X--X الاستجابة (W) | | | | | | | | |

مقترحات متضاربة مع تعافٍ غير منسق.

عميل قائد متقبل متعلم | | | | | | | | | | | X------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | | | | | | | | | | | !! مقترحات متضاربة متزامنة | | | | | | | | | !! تم استلامها بترتيب مختلف | | | | | | | | | !! بواسطة المقبولين | X--------------?|-?|-?|-?| | | موافق!(N,I,V) X-----------------؟|-؟|-؟|-؟| | | موافق!(شمال، شرق، غرب) | | | | | | | | | | | | | | | | | | !! يختلف المتقبلون حول القيمة | | |<-------X--X->|->|----->|->| مقبول (لا، أ، هـ) | | |<-------|<-|<-X--X----->|->| مقبول (شمال، شرق، غرب) | | | | | | | | | | | | | | | | | | !! اكتشاف التصادم والتعافي | | |<-------X--X--X----->|->| مقبول (N+1، I، W) |<---------------------------------X--X الاستجابة (W) | | | | | | | | |

تدفق الرسائل: بروتوكول Paxos سريع مع استعادة غير منسقة، وأدوار مدمجة

(دمج أدوار المُستقبِل/المُتعلِّم)

خوادم العميل | | | | | | | | X->|->|->| Any(N,I,Recovery) | | | | | | | | | | | | !! مقترحات متضاربة متزامنة | | | | | | !! تم استلامها بترتيب مختلف | | | | | | !! بواسطة الخوادم | X--------?|-?|-?|-?| موافق!(N,I,V) X-----------?|-?|-?|-?| موافق!(شمال، شرق، غرب) | | | | | | | | | | | | !! تختلف الخوادم حول القيمة | | X<>X->|->| مقبول (N,I,V) | | |<-|<-X<>X مقبول (شمال، شرق، غرب) | | | | | | | | | | | | !! اكتشاف التصادم والتعافي | | X<>X<>X<>X مقبول(N+1,I,W) |<-----------X--X--X--X الاستجابة (W) | | | | | |

باكسوس المعمم

يستكشف التوافق المعمم العلاقة بين عمليات آلة الحالة المُستنسخة وبروتوكول التوافق الذي يُنفذها. [ 16 ] يتمثل الاكتشاف الرئيسي في تحسينات بروتوكول Paxos عندما يُمكن تطبيق المقترحات المتضاربة بأي ترتيب، أي عندما تكون العمليات المقترحة عمليات تبادلية لآلة الحالة. في مثل هذه الحالات، يُمكن قبول العمليات المتضاربة معًا، مما يُجنب التأخيرات اللازمة لحل التعارضات وإعادة اقتراح العمليات المرفوضة.

يُعمَّم هذا المفهوم ليشمل سلاسل متنامية باستمرار من العمليات التبادلية، بعضها معروف باستقراره (وبالتالي يمكن تنفيذه). يتتبع البروتوكول هذه السلاسل، ويضمن استقرار جميع العمليات المقترحة في سلسلة واحدة قبل السماح لأي عملية غير تبادلية معها بالاستقرار.

مثال

من أجل توضيح بروتوكول Paxos المعمم، يوضح المثال أدناه تدفق الرسائل بين عميلين يعملان في وقت واحد وآلة حالة متكررة تنفذ عمليات القراءة/الكتابة على سجلين متميزين A و B.

جدول التبديل
اقرأ (أ)اكتب (أ)اقرأ (ب)اكتب (ب)
اقرأ (أ) لا
اكتب (أ) لالا
اقرأ (ب) لا
اكتب (ب) لالا

لاحظ أن هذا الجدول يشير إلى العمليات غير التبادلية.

تسلسل محتمل للعمليات  :

<1: قراءة (أ)، 2: قراءة (ب)، 3: كتابة (ب)، 4: قراءة (ب)، 5: قراءة (أ)، 6: كتابة (أ)>

بما أن 5:Read(A)يتبادل مع كل من 3:Write(B)و 4:Read(B)، فإن أحد التبديلات الممكنة المكافئة للترتيب السابق هو التالي:

<1: قراءة (أ)، 2: قراءة (ب)، 5: قراءة (أ)، 3: كتابة (ب)، 4: قراءة (ب)، 6: كتابة (أ)>

من الناحية العملية، لا يحدث التنقل إلا عندما يتم اقتراح العمليات في وقت واحد.

تدفق الرسائل: باكسوس المعمم (مثال)

لم يتم عرض الردود. ملاحظة: تختلف اختصارات الرسائل عن تدفقات الرسائل السابقة بسبب خصوصيات البروتوكول، انظر [ 23 ] لمناقشة كاملة.

عميل قائد متقبل متعلم | | | | | | | | !! يبدأ قائد جديد الجولة | | X----->|->|->| | | Prepare(N) | | |<-----X- X- X | | Promise(N,null) | | X----->|->|->| | | Phase2Start(N,null) | | | | | | | | | | | | | | | | !! مقترحات التنقل المتزامن | X------- ؟|-----؟|-؟|-؟| | | اقتراح (قراءة أ) X-----------?|-----?|-?|-?| | | اقتراح(قراءة ب) | | X------X-------------->|->| مقبول(N,<ReadA,ReadB>) | | |<--------X--X-------->|->| مقبول(N,<ReadB,ReadA>) | | | | | | | | | | | | | | | | !! لا يوجد تعارض، كلا الطرفين مقبولان | | | | | | | | مستقر = <ReadA، ReadB> | | | | | | | | | | | | | | | | !! مقترحات متضاربة متزامنة X-----------?|-----?|-?|-?| | | اقتراح(<كتابة ب، قراءة أ>) | X--------?|-----?|-?|-?| | | اقتراح(قراءة ب) | | | | | | | | | | X------X-------------->|->| تم القبول (N، <WriteB، ReadA> . <ReadB>) | | |<--------X--X-------->|->| تم القبول (N، <قراءة B> . <كتابة B، قراءة A>) | | | | | | | | | | | | | | | | !! تم رصد تعارض، القائد يختار | | | | | | | | الترتيب التبادلي: | | | | | | | | V = <ReadA, WriteB, ReadB> | | | | | | | | | | X----->|->|->| | | Phase2Start(N+1,V) | | |<-----X- X- X-------->|->| مقبول (N+1، V) | | | | | | | | مستقر = <ReadA, ReadB> . | | | | | | | | <قراءة أ، كتابة ب، قراءة ب> | | | | | | | | | | | | | | | | !! المزيد من المقترحات المتضاربة X-----------?|-----?|-?|-?| | | اقتراح (اكتب أ) | X--------?|-----?|-?|-?| | | اقتراح (اقرأ أ) | | | | | | | | | | X------X-------------->|->| تم القبول (N+1، <كتابة A> . <قراءة A>) | | |<--------X- X-------->|->| تم القبول (N+1، <قراءة A> . <كتابة A>) | | | | | | | | | | | | | | | | !! القائد يختار النظام: | | | | | | | | W = <WriteA, ReadA> | | | | | | | | | | X----->|->|->| | | Phase2Start(N+2,W) | | |<-----X- X- X-------->|->| مقبول (شمال + 2، غرب) | | | | | | | | مستقر = <ReadA, ReadB> . | | | | | | | | <ReadA, WriteB, ReadB> . | | | | | | | | <اكتب أ، اقرأ أ> | | | | | | | |

أداء

يوضح لنا تدفق الرسائل أعلاه أن بروتوكول باكسوس المعمم يستفيد من دلالات العمليات لتجنب التصادمات عند فشل الترتيب التلقائي للشبكة. وهذا ما يجعل البروتوكول عمليًا أسرع من بروتوكول باكسوس السريع. مع ذلك، عند حدوث تصادم، يحتاج بروتوكول باكسوس المعمم إلى جولتين إضافيتين للتعافي. يوضح المخطط أعلاه هذه الحالة من خلال العمليتين WriteB و ReadB.

في الحالة العامة، تُعدّ هذه الرحلات ذهابًا وإيابًا أمرًا لا مفر منه، وهي ناتجة عن إمكانية قبول أوامر متعددة خلال جولة واحدة. وهذا ما يجعل البروتوكول أكثر تكلفة من بروتوكول Paxos عند تكرار التعارضات. ومن المأمول أن يكون من الممكن إدخال تحسينين على بروتوكول Paxos المعمم لتحسين وقت الاسترداد. [ 24 ]

  • أولاً، إذا كان المنسق جزءًا من كل نصاب من المقبولين (يقال إن الجولة N مركزية )، فإنه للتعافي في الجولة N+1 من تصادم في الجولة N، يتخطى المنسق المرحلة 1 ويقترح في المرحلة 2 التسلسل الذي قبله آخر مرة خلال الجولة N. وهذا يقلل من تكلفة التعافي إلى رحلة ذهاب وإياب واحدة.
  • ثانيًا، إذا استخدمت الجولتان N و N+1 نصابًا مركزيًا فريدًا ومتطابقًا، فعندما يكتشف المُستقبِل تصادمًا في الجولة N، فإنه يقترح تلقائيًا في الجولة N+1 تسلسلًا يُلحق كلًا من (أ) التسلسل الذي قبله المنسق في الجولة N و(ب) أكبر بادئة غير متضاربة قبلها في الجولة N. على سبيل المثال، إذا قبل المنسق والمُستقبِل على التوالي في الجولة N التسلسلين <WriteB, ReadB> و <ReadB, ReadA>، فسيقبل المُستقبِل تلقائيًا التسلسل <WriteB, ReadB, ReadA> في الجولة N+1. مع هذا التغيير، تكون تكلفة الاسترداد تأخير رسالة واحدة، وهو الأمثل بوضوح. تجدر الإشارة هنا إلى أن استخدام نصاب فريد في جولة ما لا يضر بالحيوية. ويعود ذلك إلى حقيقة أن أي عملية في هذا النصاب تُعد نصاب قراءة لمرحلة التحضير في الجولات التالية. [ 25 ]

باكسوس البيزنطية

يمكن أيضًا توسيع نطاق بروتوكول باكسوس ليشمل حالات الفشل التعسفية للمشاركين، بما في ذلك الكذب، وتلفيق الرسائل، والتواطؤ مع مشاركين آخرين، وعدم المشاركة الانتقائية، وما إلى ذلك. تُسمى هذه الأنواع من حالات الفشل بالفشل البيزنطي ، نسبةً إلى الحل الذي شاع استخدامه من قبل لامبورت. [ 26 ]

يضيف بروتوكول Paxos البيزنطي [ 27 ] الذي قدمه كاسترو وليسكوف رسالة إضافية (التحقق) تعمل على توزيع المعرفة والتحقق من إجراءات المعالجات الأخرى:

تدفق الرسائل: بروتوكول باكسوس متعدد البيزنطي، حالة مستقرة

العميل، مقدم العرض، المتقبل، المتعلم | | | | | | | X-------->| | | | | | طلب | X--------->|->|->| | | قبول!(N,I,V) | | X<>X<>X | | التحقق (N,I,V) - بث | |<---------X--X--X------>|->| مقبول (N,V) |<---------------------------------X--X الاستجابة (V) | | | | | | |

يقوم بروتوكول باكسوس البيزنطي السريع [ 28 ] الذي قدمه مارتن وألفيسي بإزالة هذا التأخير الإضافي، حيث يرسل العميل الأوامر مباشرة إلى المستلمين.

لاحظ أن رسالة القبول في نظام باكسوس البيزنطي السريع تُرسل إلى جميع المُستقبِلين وجميع المُتعلّمين، بينما يُرسل نظام باكسوس السريع رسائل القبول إلى المُتعلّمين فقط:

تدفق الرسائل: بروتوكول باكسوس متعدد الباكسوس البيزنطي السريع، حالة مستقرة

متعلم متقبل للعميل | | | | | | X----->|->|->| | | قبول!(N,I,V) | X<>X<>X------>|->| مقبول (N,I,V) - بث |<-------------------X--X الاستجابة (V) | | | | | |

سيناريو الفشل واحد في كلا البروتوكولين؛ ينتظر كل مُتعلِّم استلام F+1 رسالة متطابقة من مُستقبِلين مختلفين. إذا لم يحدث ذلك، فسيكون المُستقبِلون أنفسهم على دراية بذلك (لأنهم تبادلوا رسائل بعضهم البعض في جولة البث)، وسيعيد المُستقبِلون الصحيحون بث القيمة المتفق عليها.

تدفق الرسائل: بروتوكول باكسوس متعدد الباكسوس البيزنطي السريع، فشل

متعلم متقبل للعميل | | | ! | | !! أحد أجهزة الاستقبال معطل X----->|->|->! | | قبول!(N,I,V) | X<>X<>X------>|->| مقبول (N,I,{V,W}) - بث | | | ! | | !! يتلقى المتعلمون أمرين مختلفين | | | ! | | !! يلاحظ المصححون الخطأ ويختارون | X<>X<>X------>|->| مقبول (N,I,V) - بث |<-------------------X--X الاستجابة (V) | | | ! | |

تكييف بروتوكول Paxos لشبكات RDMA

مع ظهور شبكات مراكز البيانات عالية السرعة والموثوقية التي تدعم الوصول المباشر للذاكرة عن بُعد ( RDMA )، ازداد الاهتمام بتحسين بروتوكول Paxos للاستفادة من تفريغ العتاد، حيث توفر بطاقة واجهة الشبكة وموجهات الشبكة الموثوقية والتحكم في ازدحام طبقة الشبكة، مما يتيح لوحدة المعالجة المركزية المضيفة القيام بمهام أخرى. مكتبة Derecho C++ Paxos هي تطبيق مفتوح المصدر لبروتوكول Paxos يستكشف هذا الخيار. [ 12 ]

يُقدّم Derecho نوعين من بروتوكولات Paxos: بروتوكول Paxos الكلاسيكي، الذي يضمن استمرارية البيانات حتى بعد إيقاف التشغيل وإعادة التشغيل، وبروتوكول Paxos العمودي (البث المتعدد الذري)، الذي يُتيح نسخ البيانات في الذاكرة ومزامنة آلة الحالة. وقد استلزم الأمر تعديل بروتوكولات Paxos المُستخدمة في Derecho لزيادة تدفق البيانات غير المتزامن إلى أقصى حد، وإزالة مصادر التأخير الأخرى على المسار الحرج للوحدة الرئيسية. وبذلك، يتمكّن Derecho من الحفاظ على معدل نقل البيانات ثنائي الاتجاه الكامل لتقنية RDMA. في المقابل، ورغم إمكانية نقل بروتوكولات Paxos التقليدية إلى شبكة RDMA ببساطة عن طريق ربط عمليات إرسال الرسائل بعمليات RDMA الأصلية، إلا أن ذلك يُخلّف تأخيرات ذهابًا وإيابًا على المسار الحرج. في شبكات RDMA عالية السرعة، حتى التأخيرات الصغيرة قد تكون كافية لمنع الاستفادة الكاملة من عرض النطاق الترددي المُتاح.

استخدام باكسوس في الإنتاج

انظر أيضاً

مراجع

  1. ↑ بيس، مارشال؛ شوستاك، روبرت؛ لامبورت، ليزلي (أبريل 1980). "التوصل إلى اتفاق في ظل وجود أعطال" . مجلة رابطة آلات الحوسبة . 27 (2): 228-234 . doi : 10.1145/322186.322188 . S2CID 6429068. تاريخ الاسترجاع: 2007-02-02 . 
  2. ↑ لامبورت، ليزلي (يوليو 1978). "الوقت والساعات وترتيب الأحداث في نظام موزع" . اتصالات رابطة آلات الحوسبة . 21 (7): 558-565 . doi : 10.1145/359545.359563 . S2CID 215822405. تاريخ الاسترجاع : 2007-02-02 . 
  3. ↑ شنايدر، فريد (1990). "تنفيذ خدمات مقاومة للأعطال باستخدام منهج آلة الحالة: دليل تعليمي" (ملف PDF) . مجلة ACM Computing Surveys . 22 (4): 299-319 . CiteSeerX 10.1.1.69.1536 . doi : 10.1145/98163.98167 . S2CID 678818 .  
  4. ↑ تاريخ ليزلي لامبورت للصحيفة
  5. ↑ لامبورت، ليزلي (مايو 1998). "البرلمان بدوام جزئي" . معاملات ACM لأنظمة الحاسوب . 16 (2): 133-169 . doi : 10.1145/279227.279229 . S2CID 421028. تاريخ الاسترجاع: 2007-02-02 . 
  6. 1 2 فيشر، م. (أبريل 1985). "استحالة التوافق الموزع مع وجود عملية معيبة واحدة" . مجلة ACM . 32 (2): 374-382 . doi : 10.1145/3149.214121 . hdl : 1721.1/149560 . S2CID 207660233 . 
  7. ↑ دورك، سينثيا؛ لينش، نانسي؛ ستوكمير، لاري (أبريل 1988). "التوافق في ظل التزامن الجزئي" (ملف PDF) . مجلة ACM . 35 (2): 288-323 . CiteSeerX 10.1.1.13.3423 . doi : 10.1145/42282.42283 . S2CID 17007235 .  
  8. ↑ أوكي، برايان؛ ليسكوف، باربرا (1988). "النسخ المتماثل المُختوم: طريقة جديدة للنسخ الأساسي لدعم الأنظمة الموزعة عالية التوافر" . وقائع ندوة ACM السنوية السابعة حول مبادئ الحوسبة الموزعة (PODC '88) . الصفحات 8-17 . doi : 10.1145/62546.62549 . 
  9. ↑ بيرمان، كينيث؛ جوزيف، توماس (فبراير 1987). "الاتصال الموثوق في ظل وجود الأعطال". معاملات ACM لأنظمة الحاسوب . 5 : 47-76 . doi : 10.1145/7351.7478 . hdl : 1813/6534 . S2CID 11224827 . 
  10. ↑ لامبورت، ليزلي؛ مالخي، داليا؛ تشو، ليدونغ (مارس 2010). "إعادة تكوين آلة الحالة". أخبار SIGACT . 41 (1): 63-73 . CiteSeerX 10.1.1.212.2168 . doi : 10.1145/1753171.1753191 . S2CID 15189602 .  
  11. ↑ كيدار، إيديت ؛ شراير، ألكسندر (2006). "التوقيت، وكاشفات الأعطال، وأداء الإجماع". وقائع ندوة ACM السنوية الخامسة والعشرين حول مبادئ الحوسبة الموزعة (PODC '06) . doi : 10.1145/1146381.1146408 .
  12. 1 2 جها، ساجار؛ بيرنز، جوناثان؛ غكونتوفاس، ثيو؛ ميلانو، ماثيو؛ سونغ، ويجيا؛ تريمل، إدوارد؛ فان رينيس، روبرت؛ زينك، سيدني؛ بيرمان، كين (أبريل 2019). "ديريتشو: نسخ سريع لآلة الحالة لخدمات الحوسبة السحابية". معاملات ACM لأنظمة الحاسوب . 36 (2). doi : 10.1145/3302258 . S2CID 218482757 . 
  13. ↑ لامبورت، ليزلي (2004). "الحدود الدنيا للتوافق غير المتزامن" .
  14. ^ فان رينيسي، روبرت. ألتنبوكين ، دنيز (2015/02/17). "صنع باكسوس معقد إلى حد ما" . مسوحات الحوسبة ACM . 47 (3): 42:1-42:36. دوى : 10.1145/2673577 . ISSN 0360-0300 . 
  15. 1 2 3 4 5 لامبورت، ليزلي (2005). "باكسوس سريع" .
  16. 1 2 3 4 لامبورت، ليزلي (2005). "الإجماع المعمم وباكسوس" .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
  17. ↑ تشاندرا، توشار؛ غريسمر، روبرت؛ ريدستون، جوشوا (2007). "باكسوس مُفعّل". وقائع الندوة السنوية السادسة والعشرين لجمعية آلات الحوسبة حول مبادئ الحوسبة الموزعة . الصفحات 398-407 . doi : 10.1145/1281100.1281103 . ISBN  9781595936165. S2CID 207164635 . 
  18. ^ كيسادا توريس، لويس (2018). خوارزمية باكسوس . محادثات جوجل التقنية.
  19. ↑ لامبورت، ليزلي (2001). باكسوس ببساطة، أخبار ACM SIGACT (عمود الحوسبة الموزعة) 32 ، 4 (العدد الكامل 121، ديسمبر 2001) 51-58.
  20. ↑ "انتخابات القائد، لماذا يجب أن أهتم؟" . مدونة إيلاستيك . 13 سبتمبر 2013. تم الاطلاع عليه بتاريخ 27 فبراير 2021 .
  21. ↑ آي. غوبتا، آر. فان رينيس، وكيه بي بيرمان، 2000، بروتوكول انتخاب قائد صحيح احتماليًا للمجموعات الكبيرة، تقرير فني ، جامعة كورنيل
  22. 1 2 3 4 5 لامبورت، ليزلي؛ ماسا، مايك (2004). "باكسوس الرخيص" . وقائع المؤتمر الدولي حول الأنظمة والشبكات الموثوقة (DSN 2004) .
  23. ↑ تيرنر، برايان (2007). "عائلة بروتوكولات الإجماع باكسوس" .
  24. ↑ بيير، سوترا؛ مارك، شابيرو (2011). "التوافق المعمم الحقيقي السريع" (ملف PDF) . SRDS'11: الندوة الثلاثون لمعهد مهندسي الكهرباء والإلكترونيات حول الأنظمة الموزعة الموثوقة .
  25. ↑ لامبورت، ليزلي؛ مالخي، داليا؛ تشو، ليدونغ (2009). "باكسوس العمودي والنسخ الاحتياطي الأساسي". وقائع الندوة الثامنة والعشرين لجمعية الحوسبة الآلية (ACM) حول مبادئ الحوسبة الموزعة . PODC '09. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 312-313 . CiteSeerX 10.1.1.150.1791 . doi : 10.1145/1582716.1582783 . ISBN   9781605583969. S2CID 2763624 . 
  26. ↑ لامبورت، ليزلي؛ شوستاك، روبرت؛ بيس، مارشال (يوليو 1982). "مشكلة الجنرالات البيزنطيين" . معاملات ACM في لغات البرمجة والأنظمة . 4 (3): 382-401 . CiteSeerX 10.1.1.64.2312 . doi : 10.1145/357172.357176 . S2CID 55899582. تاريخ الاسترجاع: 2007-02-02 .  
  27. ↑ كاسترو، ميغيل؛ ليسكوف، باربرا (فبراير 1999). " التسامح العملي مع الأخطاء البيزنطية" (ملف PDF) . وقائع الندوة الثالثة حول تصميم وتنفيذ أنظمة التشغيل : 173-186 . تم الاطلاع عليه في 5 مارس 2018 .
  28. ↑ مارتن، جان فيليب؛ ألفيسي، لورينزو (يوليو 2006). "التوافق البيزنطي السريع" (ملف PDF) . معاملات IEEE في الحوسبة الموثوقة والآمنة . 3 (3): 202-215 . رمز Bibcode : 2006ITDSC...3..202M . doi : 10.1109/TDSC.2006.35 . تاريخ الاسترجاع: 5 مارس 2018 .
  29. ↑ بوروز، مايك. "خدمة قفل تشابي للأنظمة الموزعة ذات الترابط الضعيف" (ملف PDF) . OSDI.
  30. ↑ "التوافق في ظل التزامن الجزئي" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 19 أبريل 2011. تم الاطلاع عليه بتاريخ 31 أغسطس 2019 .
  31. ↑ "أبحاث مايكروسوفت - أبحاث التكنولوجيا الناشئة والحاسوب والبرمجيات" . مايكروسوفت للأبحاث . تم الاطلاع عليه بتاريخ 19-09-2024 .
  32. ↑ أهلاد وآخرون (2011). "محرك التنسيق الموزع (DConE)". مؤرشف بتاريخ 15 أبريل 2016 في أرشيف الإنترنت . ورقة بيضاء من WANdisco.
  33. ↑ كولبيك، بيورن؛ هوغكفيست، ميكائيل؛ ستيندر، يان؛ هوبفيلد، فيليكس (2011). "Flease - تنسيق التأجير بدون خادم قفل" . المؤتمر الدولي الخامس والعشرون للمعالجة المتوازية والموزعة التابع لمعهد مهندسي الكهرباء والإلكترونيات (IPDPS 2011).
  34. ↑ "الاتساق، وتحمل الأعطال، والتوافر مع MariaDB Xpand — وثائق MariaDB" . MariaDB . تم الاطلاع عليه بتاريخ 19-09-2024 .
  35. ↑ "المعاملات الخفيفة في كاساندرا 2.0" . داتا ستاكس . تم الاطلاع عليه بتاريخ 19-09-2024 .
  36. ↑ "المعاملات الخفيفة | وثائق ScyllaDB" . opensource.docs.scylladb.com . تم الاطلاع عليه بتاريخ 19-09-2024 .
  37. ↑ فوغلز، د. فيرنر (20 يوليو 2015). "نظرة معمقة على خدمة حاويات أمازون EC2" . www.allthingsdistributed.com . تاريخ الاسترجاع: 19 سبتمبر 2024 .
  38. ↑ "Amazon DynamoDB: خدمة قواعد بيانات NoSQL قابلة للتوسع، ذات أداء متوقع، ومدارة بالكامل" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 19 يوليو 2022.