القط شرودنجر دون مربع: مشكلة التوافق في النظم الموزعة

هكذا تخيل. يتم قفل 5 قطط في الغرفة ، ولكي يتمكنوا من إيقاظ المالك ، يجب أن يتفقوا جميعًا على هذا معًا ، لأنهم لا يستطيعون فتح الباب إلا من خلال الاعتماد عليه خمسة منهم. إذا كانت إحدى القطط عبارة عن قطة شرودنجر ، وبقية القطط لا تعرف حلها ، فإن السؤال الذي يطرح نفسه هو: "كيف يمكنهم فعل ذلك؟"

في هذه المقالة ، سوف أخبرك بلغة بسيطة عن المكون النظري لعالم الأنظمة الموزعة ومبادئ تشغيلها. وكذلك النظر بشكل سطحي في الفكرة الرئيسية الكامنة وراء Paxos'a.



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

في الواقع ، الضمانات التي لدينا هي ضمانات المورد. يتم وصفها في الوثائق بالطريقة التالية تقريبًا: "هذه الخدمة موثوق بها تمامًا ، فهي تحتوي على اتفاقية مستوى الخدمة محددة مسبقًا ، لا تقلق ، كل شيء سيعمل بطريقة موزعة ، كما تتوقع".

نحن نميل إلى الإيمان بالأفضل ، لأن الأعمام الأذكياء من الشركات الكبرى أكدوا لنا أن كل شيء سيكون على ما يرام. نحن لا نسأل أنفسنا: لماذا ، في الواقع ، حتى يمكن أن تعمل؟ هل هناك أي مبرر رسمي للتشغيل الصحيح لهذه الأنظمة؟

لقد ذهبت مؤخرًا إلى مدرسة الحوسبة الموزعة وكانت مستوحاة للغاية من هذا الموضوع. بدت المحاضرات في المدرسة أشبه بفصول في التحليل الرياضي أكثر من كونها مرتبطة بأنظمة الكمبيوتر. ولكن هذا هو بالضبط كيف أثبتت الخوارزميات الأكثر أهمية التي نستخدمها كل يوم دون معرفة ذلك في وقت واحد.

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

نقدم مفهوم النظم الموزعة

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

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

لا يبدو التعريف نفسه معقدًا للغاية ، ولكن عليك أن تفكر في أن النظام الموزع به عدد من السمات التي ستكون مهمة بالنسبة لنا.

سمات النظام الموزع

1. التزامن - إمكانية الأحداث المتزامنة أو التنافسية في النظام. علاوة على ذلك ، سوف نعتبر أن الأحداث التي وقعت على عقدتين مختلفتين قد تكون منافسة طالما لم يكن لدينا ترتيب واضح لحدوث هذه الأحداث. وكقاعدة عامة ، ليس لدينا.
2. عدم وجود ساعة عالمية . ليس لدينا ترتيب واضح للأحداث بسبب عدم وجود ساعة عالمية. في عالم الناس العاديين ، اعتدنا على حقيقة أن لدينا ساعات ووقت على الإطلاق. كل شيء يتغير عندما يتعلق الأمر بالأنظمة الموزعة. حتى الساعات الذرية فائقة الدقة لها انجراف ، وقد تكون هناك حالات لا يمكننا فيها تحديد أي من الحدثين حدثا في وقت سابق. لذلك ، لا يمكننا أيضًا الاعتماد على الوقت.
3. فشل مستقل في عقد النظام . هناك مشكلة أخرى: قد لا يكون شيء ما بهذه البساطة لأن عقدنا ليست أبدية. قد يفشل محرك الأقراص الصلبة ، وسيتم إعادة تشغيل الجهاز الظاهري في السحابة ، وقد تغمض الشبكة وستفقد الرسائل. علاوة على ذلك ، تكون المواقف ممكنة عندما تعمل العقد ، لكن في نفس الوقت تعمل ضد النظام. تلقت الفئة الأخيرة من المشاكل اسمًا منفصلاً: مشكلة الجنرالات البيزنطيين . المثال الأكثر شعبية للنظام الموزع مع مثل هذه المشكلة هو Blockchain. لكن اليوم لن نفكر في هذه الفئة المعينة من المشاكل. سنهتم بالحالات التي يمكن أن تفشل فيها عقدة واحدة أو أكثر.
4. نماذج الاتصال (نماذج المراسلة) بين العقد . لقد اكتشفنا بالفعل أن العقد تتواصل من خلال المراسلة. يوجد نموذجان للمراسلة معروفان: متزامنان وغير متزامنان.

نماذج الاتصال بين العقد في النظم الموزعة

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

نموذج غير متزامن - في نماذج غير متزامنة ، نعتقد أن وقت الانتظار محدود ، ولكن لا يوجد وقت دلتا يمكن بعده ضمان أن العقدة غير صالحة. أي يمكن أن يكون وقت انتظار رسالة من العقدة طويلاً بشكل تعسفي. هذا هو تعريف مهم ، وسوف نتحدث عن هذا أبعد من ذلك.

مفهوم التوافق في النظم الموزعة

قبل تحديد مفهوم الإجماع بشكل رسمي ، دعونا ننظر في مثال على الموقف عندما نحتاج إليه ، ألا وهو State Machine Replication .

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

بمعنى آخر: لم تعترض أي من العقد على أن لديها معلومات أكثر صلة ، وأن القيمة المقترحة غير صحيحة. الاتفاق بين العقد والاتفاق على قيمة واحدة صحيحة مقبولة هو الإجماع في نظام موزع. علاوة على ذلك ، سنتحدث عن الخوارزميات التي تسمح للنظام الموزع بتحقيق التوافق مع الضمان.

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

خصائص خوارزمية التوافق

يجب أن تحتوي خوارزمية الإجماع على ثلاث خصائص حتى يستمر النظام في الوجود ولديه نوع من التقدم في الانتقال من حالة إلى أخرى:

1. الاتفاقية - يجب أن تأخذ جميع العقد التي تعمل بشكل صحيح نفس القيمة (في المقالات ، توجد هذه الخاصية أيضًا كخاصية أمان). يجب أن تتوصل جميع العقد التي تعمل الآن (وليس خارج نطاق النظام ولم تفقد الاتصال بالباقي) إلى اتفاق وتتخذ نوعًا من المعنى العام النهائي.
   
   من المهم أن نفهم هنا أن العقد في النظام الموزع الذي ندرسه تريد الموافقة عليه. أي أننا نتحدث الآن عن أنظمة قد تفشل للتو (على سبيل المثال ، أن تفشل عقدة) ، لكن هذا النظام بالتأكيد لا يحتوي على نقاط تعمل عن قصد ضد الآخرين (مهمة الجنرالات البيزنطيين). نظرًا لهذه الخاصية ، يظل النظام ثابتًا.
2. التكامل - إذا كانت جميع العقد التي تعمل بشكل صحيح تقدم نفس قيمة v ، فيجب أن تقبل كل عقدة تعمل بشكل صحيح هذه القيمة v .
3. الإنهاء - جميع العقد التي تعمل بشكل صحيح ستأخذ في النهاية بعض القيمة (خاصية الفاعلية) ، مما يسمح للخوارزمية بالتقدم في النظام. يجب على كل عقدة فردية تعمل بشكل صحيح قبول القيمة النهائية عاجلاً أو آجلاً وتأكيد ذلك: "بالنسبة لي ، هذه القيمة صحيحة ، أنا أتفق مع النظام بالكامل."

خوارزمية توافق الآراء

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

1. كل شيء يبدأ مع اقتراح الزواج (اقتراح). لنفترض أن العميل المتصل بعقدة تسمى "العقدة 1" وبدأ معاملة ، لتمرير قيمة جديدة إلى العقدة - O. من الآن فصاعدًا ، "العقدة 1" سوف نتصل بمقدم الطلب. كمقترح ، يجب على "Node 1" إبلاغ النظام بأكمله أنه يحتوي على بيانات جديدة ، وسوف يرسل رسائل إلى جميع العقد الأخرى: "Look! حصلت على القيمة "O" وأريد أن أكتبها! يرجى تأكيد أنك ستكتب أيضًا "O" في السجل الخاص بك. "
   
   
2. المرحلة التالية هي التصويت للقيمة المقترحة (التصويت). ما هذا؟ قد يحدث أن تلقت العقد الأخرى معلومات أكثر حداثة ولديها بيانات عن نفس المعاملة.
   
   
   
   عندما ترسل العقدة "Node 1" رسالتها الخاصة ، تتحقق العقد المتبقية من البيانات الخاصة بهذا الحدث في سجلاتها. إذا لم تكن هناك تناقضات ، فإن العقد تعلن: "نعم ، ليس لدي بيانات أخرى حول هذا الحدث. القيمة "O" هي أحدث المعلومات التي نستحقها. "
   
   في أي حال ، يمكن للعقد الإجابة على "العقدة 1": "استمع! لدي المزيد من البيانات الحديثة حول هذه الصفقة. ليس "أوه" ، ولكن شيء أفضل. "
   
   في مرحلة التصويت ، تتوصل النقاط إلى قرار: إما أن يأخذ الجميع نفس القيمة ، أو يصوت واحد منهم ، مما يشير إلى أن لديه بيانات أحدث.
3. إذا كانت جولة التصويت ناجحة ، وكان الجميع مؤيدين ، فإن النظام ينتقل إلى مرحلة جديدة - قبول القيمة (قبول). تجمع "العقدة 1" جميع استجابات العقد والتقارير الأخرى: "وافق الجميع على القيمة" O "! الآن أعلن رسميا أن "O" هو معنانا الجديد ، الشيء نفسه بالنسبة للجميع! اكتب نفسك في كتيب ، لا تنسى. اكتب إلى السجل الخاص بك!
   
   
4. ترسل العقد المتبقية تأكيدًا (مقبول) بأنهم قاموا بتدوين القيمة "O" ، ولم يتمكنوا من فعل أي شيء جديد خلال هذا الوقت (نوع من التزام على مرحلتين). بعد هذا الحدث الهام ، نعتقد أن المعاملة الموزعة قد اكتملت.
   

وبالتالي ، تتكون خوارزمية الإجماع في الحالة البسيطة من أربع خطوات: الاقتراح ، والتصويت ، والقبول ، وتأكيد القبول.

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

توافق الخوارزمية في نظام غير متزامن

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

والآن بعد أن عرفنا كيف تعمل خوارزمية الإجماع بشكل أساسي ، فإن السؤال المطروح هو بالنسبة للقراء الفضوليين الذين وصلوا إلى هذه النقطة: كم عدد العقد في نظام العقد N مع نموذج رسالة غير متزامن يمكن أن تفشل حتى يتمكن النظام من الوصول إلى الإجماع؟

نحن نتحدث الآن عن النظرية ، وعن الرياضيات. ماذا يعني "توافق لا يمكن التوصل إليه" ، ترجمة من لغة رياضية إلى لغتنا - الهندسة؟ هذا يعني أنه "لا يمكن تحقيقه دائمًا" ، أي هناك حالة حيث الإجماع غير ممكن. وما هي هذه الحالة؟

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

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

في الممارسة العملية ، نحن نتعامل مع نماذج الاتصالات متزامنة جزئيا. يُفهم التزامن الجزئي على النحو التالي: في الحالة العامة ، لدينا نموذج غير متزامن ، لكننا نقدم رسميًا مفهومًا معينًا "لوقت الاستقرار العالمي" للحظة معينة من الزمن.

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

خوارزمية باكسوس يحل قضايا التوافق

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

لكن الدليل كان تافهاً. تم إصدار المنشور الأول فقط في عام 1998 (33 صفحة) مع وصف الخوارزمية. كما اتضح ، كان من الصعب للغاية فهمه ، وفي عام 2001 تم نشر شرح للمقال ، الذي استغرق 14 صفحة. يتم تقديم مجلدات المنشورات من أجل إظهار أن مشكلة التوافق في الواقع ليست بسيطة على الإطلاق ، وأن هذه الخوارزميات تخضع لعمل هائل من أذكى الأشخاص.

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

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

الأدوار في باكسوس

باكسوس لديه مفهوم الأدوار. دعنا نفكر في ثلاثة أمور رئيسية (هناك تعديلات مع أدوار إضافية):

1. مقدمو العروض (يمكن أيضًا استخدام المصطلحات: القادة أو المنسقون) . هؤلاء هم الرجال الذين يتعلمون بعض المعنى الجديد من المستخدم ويضطلعون بدور القائد. مهمتهم هي إطلاق جولة من المقترحات ذات أهمية جديدة وتنسيق المزيد من الإجراءات للعقد. علاوة على ذلك ، يسمح Paxos بوجود العديد من القادة في مواقف معينة.
2. المتقبلون (الناخبون) . هذه هي النقاط التي تصوت لاعتماد أو رفض قيمة معينة. دورهم مهم للغاية ، لأن القرار يعتمد عليهم: في أي حالة سيذهب النظام (أو لا) بعد المرحلة التالية من خوارزمية الإجماع.
3. المتعلمين . العقد التي تقبل وتسجيل القيمة المقبولة الجديدة ببساطة عند تغير حالة النظام. إنهم لا يتخذون القرارات ، فهم ببساطة يتلقون البيانات ويمكنهم تقديمها إلى المستخدم النهائي.

يمكن أن تجمع عقدة واحدة بين عدة أدوار في مواقف مختلفة.

مفهوم النصاب

نحن نفترض أن لدينا نظام N العقد. ومنهم يمكن أن يفشل العقد F كحد أقصى . في حالة فشل العقد F ، يجب أن يكون لدينا على الأقل 2F + 1 متقبلات في المجموعة.

هذا ضروري حتى يكون لدينا دائمًا ، حتى في أسوأ الحالات ، أغلبية عقد "جيدة" تعمل بشكل صحيح. وهذا هو ، عقد F + 1 "جيدة" التي وافقت ، وسيتم قبول القيمة النهائية. خلاف ذلك ، قد يكون هناك موقف تتعامل فيه مجموعات محلية مختلفة معان مختلفة ولن تكون قادرة على الاتفاق فيما بينها. لذلك ، نحن بحاجة إلى أغلبية مطلقة للفوز في التصويت.

الفكرة العامة لخوارزمية توافق باكسوس

تتضمن خوارزمية باكسوس مرحلتين كبيرتين ، والتي تنقسم بدورها إلى خطوتين:

1. المرحلة 1 أ: تحضير . في مرحلة الإعداد ، يبلغ القائد (مقدم الاقتراح) جميع العقد: "لقد بدأنا مرحلة جديدة للتصويت. لدينا جولة جديدة. عدد هذه الجولة هو ن. الآن سنبدأ التصويت ". في الوقت الحالي ، يُبلغ عن بداية دورة جديدة ، ولكنه لا يُبلغ عن قيمة جديدة. مهمة هذه المرحلة هي بدء جولة جديدة وإخبار الجميع برقمه الفريد. رقم الجولة مهم ، يجب أن يكون قيمة أكبر من جميع أرقام التصويت السابقة من جميع القادة السابقين. نظرًا لأنه بفضل عدد الدقائق بدقة ، ستفهم العقد الأخرى في النظام مدى تحديث بيانات القائد. من المحتمل أن يكون للعقد الأخرى نتائج تصويت بالفعل من جولات متأخرة ، وسوف يخبرون القائد ببساطة أنه متأخر.
2. Phase 1b: Promise . -acceptor' , :
   
   • n , , acceptor. acceptor , , n. acceptor - (.. - ), , .
   • , acceptor , .
3. Phase 2a: Accept . ( ) , , :
   
   • acceptor' , . c . x, : «Accept (n, x)», – Propose, – , .. , , .
   • acceptor' , , , , . y. : «Accept (n, y)», .
4. Phase 2b: Accepted . , -acceptor', «Accept(...)», ( , ) , - () n' > n , .
   
   , , . ! , , .

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

تجدر الإشارة أيضًا إلى أن Paxos ليست فريدة من نوعها ، فهناك خوارزميات أخرى ، مثل Raft ، لكن هذا موضوع لمقال آخر .

روابط لمواد لمزيد من الدراسة

مستوى المبتدئين:

• كيف يعمل الإجماع الموزع؟ Preethi Kasireddy ، مقالة مدونة على المتوسطة
• قدمت باكسوس بسيطة. الحقيقي ، عدي Kancherla ، مقال بلوق على المتوسطة
• الأفكار اللامركزية ، إيتاي إبراهيم ، مدونة
• التزامن ، التزامن والتزامن الجزئي ، إيتاي إبراهيم ، مقال المدونة

المستوى:

• استحالة التوافق الموزع مع عملية واحدة معيبة (استحالة FLP) ، فيشر ، لينش وباترسون ، ورقة بحثية ، 1985
• البرلمان غير المتفرغ ، ليزلي لامبورت ، ورقة بحثية ، 1998
• أصبحت باكسوس بسيطة ، ليزلي لامبورت ، ورقة بحثية ، 2001