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

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

## تعريف المشكلة

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

### آلة الحالة
بالنسبة للمناقشة اللاحقة، سيعرف *آلة الحالة* على أنها مجموعة القيم التالية (انظر أيضًا آلة Mealy وآلة Moore):

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

تبدأ آلة الحالة عند الحالة المسماة "البدء". تُمرر كل مدخلات أُستلمت من خلال وظيفة الانتقال والإخراج لإنتاج حالة جديدة وإخراج جديد. تظل الحالة مستقرة حتى تُلقى إدخال جديد، بينما يوصل الإخراج إلى المتلقي المناسب.

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

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

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

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

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

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

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

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

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

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

## نهج آلة الدولة
تتضمن المناقشة البديهية السابقة تقنية بسيطة لتنفيذ خدمة مقاومة للأخطاء من حيث آلة الحالة:

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

يتناول الجزء المتبقي من هذه المقالة تفاصيل هذه التقنية.

* الخطوتان 1 و 2 خارج نطاق هذه المقالة.
* الخطوة 3 هي العملية الحرجة، راجع طلب المدخلات.
* الخطوة 4 مغطاة بتعريف آلة الحالة.
* الخطوة 5، راجع إرسال المخرجات.
* الخطوة 6، راجع التدقيق واكتشاف الفشل.

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

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

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

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

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

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

تسمى مشكلة التصويت على قيمة *واحدة* من قبل مجموعة من الكيانات المستقلة **[[توافق (علوم الحاسوب)|بالإجماع]]**. بالتوسع، من الممكن اختيار *سلسلة* من القيم من خلال سلسلة من حالات الإجماع. تصبح هذه المشكلة صعبة عندما يواجه المشاركون أو وسيلة الاتصال الخاصة بهم إخفاقات.

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

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

: تتوفر تحسينات إضافية عند مراعاة دلالات عمليات آلة الحالة (مثل عمليات القراءة مقابل الكتابة). انظر المراجع المعممة Paxos.

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

### فشل النظام

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

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

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

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

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

## الملحق: الامتدادات
في نظام خالٍ من الأعطال، قد تُهمَل المُدخلات بعد معالجتها بواسطة آلة الحالة. يجب أن تُعوّض عمليات النشر الواقعية عن السلوكيات غير المُؤقتة للنظام، مثل فقدان الرسائل، وأقسام الشبكة، وبطء المُعالجات.

إحدى التقنيات هي تخزين سلسلة المدخلات في سجل. خلال فترات السلوك المؤقت، قد تطلب النسخ المتماثلة نسخًا من إدخال سجل من نسخة متماثلة أخرى لملء المدخلات المفقودة.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### انتخاب الزعيم (لباكسوس)
**Paxos** هو بروتوكول لحل الإجماع، ويمكن استخدامه كبروتوكول لتنفيذ أمر الإجماع.

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

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

عندما تُقترح عمليات متضاربة، يعمل القائد كالسلطة الوحيدة لتوضيح الأمور، وتحديد ترتيب العمليات، مما يسمح للنظام بإحراز التقدم.

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

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

قام كين بيرمان بتطوير نموذج التزامن الافتراضي في سلسلة من الأوراق البحثية المنشورة بين عامي 1985 و1987. المرجع الأساسي لهذا العمل هو "استغلال التزامن الافتراضي في الأنظمة الموزعة"، والذي يصف مجموعة أدوات Isis، وهو النظام الذي تم استخدامه لبناء بورصتي نيويورك وسويسرا، ونظام مراقبة الحركة الجوية الفرنسي، وسفن الحرب AEGIS التابعة للبحرية الأمريكية، وتطبيقات أخرى.

استخدمت الأعمال الأخيرة التي أجراها ميغيل كاسترو وباربرا ليسكوف نهج آلة الحالة في ما أطلقوا عليه اسم "هندسة التسامح العملي مع الأخطاء البيزنطية" التي تحاكي الخدمات الحساسة بشكل خاص باستخدام نسخة من نهج آلة الحالة الأصلي الخاص بـ Lamport، ولكن مع التحسينات التي تعمل على تحسين الأداء بشكل كبير.

مؤخرًا، طُوّرت مكتبة BFT-SMaRt، وهي مكتبة نسخ متماثل عالية الأداء لآلات الحالة، مقاومة للأخطاء، ومبنية على لغة البرمجة بيزنطية، ومطوّرة بلغة جافا. تُطبّق هذه المكتبة بروتوكولًا مشابهًا جدًا لبروتوكول PBFT، بالإضافة إلى بروتوكولات مُكمّلة تُتيح نقل الحالة وإعادة تهيئة المضيفين تلقائيًا (مثل عمليتي JOIN وLEAVE). تُعدّ BFT-SMaRt أحدث جهد لتطبيق نسخ متماثل لآلات الحالة، ولا تزال قيد الصيانة.

طورت Raft، وهي خوارزمية تعتمد على الإجماع، في عام 2013.

بدافع من PBFT، قُدم Tendermint BFT للشبكات غير المتزامنة الجزئية ويُستخدم بشكل أساسي في سلاسل الكتل Proof of Stake.

## مراجع



## روابط خارجية

* فيديو آلات الحالة المتماثلة على MIT TechTV
* Apache Bookkeeper هي خدمة سجل متماثلة يمكن استخدامها لبناء آلات حالة متماثلة

تصنيف:نظم حاسوب متحملة للأخطاء
تصنيف:مسائل الحوسبة الموزعة
تصنيف:صفحات بترجمات غير مراجعة