تكرار آلة الحالة

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

في المناقشة اللاحقة، سيتم تعريف آلة الحالة على أنها مجموعة القيم التالية ^{[ 2 ]} (انظر أيضًا آلة ميلي وآلة مور ):

• مجموعة من الولايات
• مجموعة من المدخلات
• مجموعة من المخرجات
• دالة انتقالية (المدخل × الحالة → الحالة)
• دالة الإخراج (المدخلات × الحالة ← المخرجات)
• ولاية متميزة تُدعى ستارت.

تبدأ آلة الحالة من الحالة المسماة "البداية". يمر كل مدخل يتم استقباله عبر دالة الانتقال والإخراج لإنتاج حالة جديدة ومخرج. تبقى الحالة مستقرة حتى يتم استقبال مدخل جديد، بينما يتم إرسال المخرج إلى جهاز الاستقبال المناسب.

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

عادةً، تقوم الأنظمة القائمة على تكرار آلة الحالة بتقييد تطبيقاتها طواعيةً لاستخدام آلات الحالة المحدودة لتبسيط عملية استعادة الأخطاء.

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

الحد الأدنى لعدد النسخ اللازمة لتحمل الأعطال هو ثلاث نسخ؛ نسخة واحدة بها عطل، ونسختان أخريان نقارن بهما الحالة والمخرجات. نسختان غير كافيتين لأنه لا توجد طريقة لتحديد النسخة المعيبة.

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

بشكل عام، يجب أن يحتوي النظام الذي يدعم F من حالات الفشل على 2F+1 نسخة (تُسمى أيضًا نسخًا متماثلة). ^{[ 3 ]} تُستخدم النسخ الإضافية كدليل لتحديد أي النسخ صحيحة وأيها معيبة. يمكن لبعض الحالات الخاصة تحسين هذه الحدود. ^{[ 4 ]}

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

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

تُعدّ الخطوة الحاسمة في بناء نظام موزّع لآلات الحالة هي اختيار ترتيب معالجة المدخلات. بما أن جميع النسخ غير المعيبة ستصل إلى نفس الحالة والمخرجات إذا ما أُعطيت نفس المدخلات، فمن الضروري تقديم المدخلات بترتيب مكافئ في كل نسخة. وقد طُرحت العديد من الحلول في الأدبيات. ^{[ 2 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]}

القناة المرئية هي مسار اتصال بين كيانين يشاركان بنشاط في النظام (مثل العملاء والخوادم). مثال: من العميل إلى الخادم، ومن الخادم إلى الخادم

القناة المخفية هي مسار اتصال لا يُكشف عنه للنظام. مثال: عادةً ما تكون قنوات الاتصال بين العملاء مخفية؛ مثل المستخدمين الذين يتواصلون عبر الهاتف، أو عملية تكتب ملفات على القرص وتقرأها عملية أخرى.

عندما تكون جميع مسارات الاتصال قنوات مرئية ولا توجد قنوات مخفية، يمكن استنتاج ترتيب عالمي جزئي ( ترتيب سببي ) من نمط الاتصالات. ^{[ 8 ] [ 10 ]} يمكن لكل خادم استخلاص الترتيب السببي بشكل مستقل. يمكن تنفيذ مدخلات آلة الحالة وفقًا للترتيب السببي، مما يضمن اتساق الحالة والمخرجات لجميع النسخ غير المعيبة.

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

تُسمى مشكلة التصويت على قيمة واحدة من قِبل مجموعة من الكيانات المستقلة بالتوافق . وبشكل أوسع، يمكن اختيار سلسلة من القيم من خلال سلسلة من حالات التوافق. وتزداد هذه المشكلة تعقيدًا عندما يتعرض المشاركون أو وسيلة الاتصال الخاصة بهم لأعطال. ^{[ 3 ]}

يمكن ترتيب المدخلات حسب موقعها في سلسلة حالات الإجماع ( ترتيب الإجماع ). ^{[ 7 ]} يمكن لكل خادم استخلاص ترتيب الإجماع بشكل مستقل. يمكن تنفيذ مدخلات آلة الحالة وفقًا لترتيب الإجماع، مما يضمن اتساق الحالة والمخرجات لجميع النسخ غير المعيبة.

تحسين الترتيب السببي والتوافقي

في بعض الحالات، تتوفر معلومات إضافية (مثل الساعات الزمنية الحقيقية). في هذه الحالات، يُمكن تحقيق ترتيب سببي أو توافقي أكثر كفاءة للمدخلات، مع تقليل عدد الرسائل، أو تقليل عدد جولات الرسائل، أو تصغير حجم الرسائل. راجع المراجع لمزيد من التفاصيل ^{[ 1 ] [ 4 ] [ 6 ] [ 11 ] .}

تتوفر تحسينات إضافية عند مراعاة دلالات عمليات آلة الحالة (مثل عمليات القراءة مقابل عمليات الكتابة). انظر المراجع: باكسوس المعمم . ^{[ 2 ] [ 12 ]}

بينما يفرض نظام إدارة السجلات الموزعة التقليدي عادةً ترتيبًا كليًا للطلبات، تُظهر الأبحاث الحديثة في مجال السجلات الموزعة المجزأة أن الترتيب الجزئي كافٍ لتحقيق الاتساق عندما لا تتعارض المعاملات. تسمح نماذج التبعية القائمة على الرسوم البيانية، كتلك المستخدمة في بروتوكول سيربيروس، بانتقالات الحالة غير المتعارضة بالتوازي عبر نسخ متعددة، متجاوزةً بذلك قيود الإنتاجية لسجل خطي واحد. ^{[ 13 ]}

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

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

يُطلق على الاختراق الدائم وغير المخطط له للنسخة اسم الفشل . ويصعب الحصول على دليل على الفشل، إذ قد تكون النسخة بطيئة الاستجابة فحسب، ^{[ 14 ]} أو حتى تكذب بشأن حالتها. ^{[ 5 ]}

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

تتمثل إحدى الطرق الشائعة في تمرير قيم التحقق من حالة النسخة المتماثلة الحالية والمخرجات الأخيرة بين الخوادم. وفي حال اكتشاف أي انحراف، تُعيد عملية تدقيق في كل خادم تشغيل النسخة المتماثلة المحلية. ^{[ 15 ]} ولا يُشترط استخدام التشفير لأغراض التحقق من الحالة.

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

في نظام خالٍ من الأعطال، يمكن تجاهل المدخلات بعد معالجتها بواسطة آلة الحالة. يجب أن تعوض عمليات النشر الواقعية عن السلوكيات العابرة غير المرتبطة بالأعطال في النظام، مثل فقدان الرسائل، وانقطاعات الشبكة، وبطء المعالجات. ^{[ 15 ]}

تتمثل إحدى التقنيات في تخزين سلسلة المدخلات في سجل. خلال فترات السلوك العابر، قد تطلب النسخ المتماثلة نسخًا من إدخال السجل من نسخة متماثلة أخرى لملء المدخلات المفقودة. ^{[ 7 ]}

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

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

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

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

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

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

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

تمت إضافة مدخل جديد إلى آلة الحالة يُسمى QUIT . ^{[ 2 ] [ 6 ]} تُرسل النسخة المتماثلة هذا الأمر إلى النظام تمامًا كما لو كانت طلبًا من العميل. تقوم جميع النسخ المتماثلة السليمة بإزالة النسخة المتماثلة التي تُنهي عملها من النظام عند معالجة هذا المدخل. خلال هذه الفترة، قد تتجاهل النسخة المتماثلة جميع رسائل البروتوكول. إذا بقيت أغلبية النسخ المتماثلة السليمة، يكون إنهاء العمل ناجحًا. وإلا، يحدث عطل في النظام .

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

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

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

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

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

Paxos ^{[ 7 ]} هو بروتوكول لحل الإجماع، ويمكن استخدامه كبروتوكول لتنفيذ نظام الإجماع.

يتطلب بروتوكول باكسوس قائدًا واحدًا لضمان استمرارية عمل النظام. ^{[ 7 ]} أي أن إحدى النسخ المتماثلة يجب أن تبقى قائدة لفترة كافية لتحقيق توافق في الآراء بشأن العملية التالية لآلة الحالة. لا يتأثر سلوك النظام إذا تغير القائد بعد كل عملية، أو إذا تغير عدة مرات في العملية الواحدة. الشرط الوحيد هو أن تبقى نسخة متماثلة واحدة قائدة لفترة كافية لدفع النظام قدمًا.