التوافق الموزَّع: مقدمة في Raft و Paxos

التوافق الموزَّع: مقدمة في Raft و Paxos

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

التوافق هو المحرّك الكامن خلف كل ضمان تناسق قوي تعلّمته حتى الآن: انتخاب القادة في Kafka، وسجل الإيداعات في etcd، وإدارة الإعدادات في Zookeeper، وقائد الكتابة الوحيد في CockroachDB — كلّها تعتمد على خوارزمية توافق.

لماذا التوافق صعب؟

الاتفاق في غرفة مجتمعين أمر يسير، أما الاتفاق عبر شبكة فلا، لأن:

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

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

Paxos — الخوارزمية الكلاسيكية

Paxos (ليزلي لامبورت، 1989/1998) هي أول خوارزمية توافق عملية. تعمل في مرحلتين:

1. مرحلة التحضير (Prepare) — يُرسل المقترِح رسالة Prepare(n) برقم اقتراع n إلى أغلبية المقبِلين. يعد كل مقبِل بعدم قبول أي اقتراح برقم أقل من n، ويُعيد أعلى اقتراح قبِله سابقاً إن وجد.
2. مرحلة القبول (Accept) — إذا جمع المقترِح وعوداً من أغلبية، أرسل Accept(n, v) حيث v إما قيمته الخاصة أو أعلى قيمة مقبولة مسبقاً تلقّاها. يقبل المقبِلون الاقتراح ما لم يكونوا قد وعدوا باقتراع أعلى. بمجرد قبول الأغلبية تُعدّ القيمة مختارة.

Paxos صحيحة رياضياً لكنها صعبة التنفيذ عملياً. تضمّ متغيّرات كـMulti-Paxos وFast Paxos وFlexible Paxos، كل منها يزيد من تعقيد التنفيذ. من التطبيقات الحقيقية: خدمة القفل Chubby من Google، وApache Zookeeper (بروتوكول ZAB، وهو متغيّر من Paxos).

Raft — التوافق المفهوم

صُمِّم Raft (أونغارو وأوستيرهاوت، 2014) ليكون أسهل في الفهم من Paxos مع تقديم ضمانات مكافئة. يُحلّل المشكلة إلى ثلاثة مشاكل فرعية مستقلة:

• انتخاب القائد — يوجد قائد واحد بالضبط لكل فترة.
• نسخ السجل — يستقبل القائد طلبات العملاء، يُلحقها بسجله، ثم يُرسلها للمتابعين.
• الأمان — إذا أُيِّد إدخال في سجل عقدة ما، سيظهر في سجلات جميع القادة المستقبلين.

الفترات والانتخابات

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

نسخ السجل

بعد انتخابه، يُسلسل القائد جميع عمليات الكتابة. يُلحق القائد الكتابة بسجله ثم يُرسلها للمتابعين عبر RPC من نوع AppendEntries. حين تُقرّ الأغلبية الإدخال، يصبح مؤيَّداً، يُطبَّق على آلة الحالة، ويُردّ على العميل. يُطبّق المتابعون الإدخالات المؤيَّدة بالترتيب، مما يُبقي حالتهم مطابقة لحالة القائد.

Raft مقابل Paxos — مقارنة عملية

تتحمّل كلتا الخوارزميتين ما يصل إلى ⌊(N−1)/2⌋ عطلاً في كتلة من N عقدة — كتلة من 3 عقد تتحمّل عطلاً واحداً، وكتلة من 5 عقد تتحمّل عطلين. الفرق الرئيسي في تعقيد التنفيذ ووضوح التشغيل:

أين تلتقي بالتوافق في الإنتاج

نادراً ما تنفّذ خوارزمية توافق بنفسك — بل تستخدم خدمة تنسيق مبنية فوقها:

• etcd (مخزن حالة Kubernetes) — يستخدم Raft. يُوصى بكتلة من 3 أو 5 عقد.
• Apache Zookeeper — يستخدم ZAB (متغيّر من Paxos). يُستخدم في Kafka لبيانات الوسطاء (يُستبدل بنظام KRaft المبني على Raft).
• Consul — يستخدم Raft. للاكتشاف الخدمي والأقفال الموزّعة.
• CockroachDB / TiDB — Raft لكل نطاق/منطقة. SQL جغرافي الموزّع بتناسق قوي.
• Google Spanner — Paxos لكل شريحة، مقترن بـTrueTime لتناسق خارجي.

الدرس العملي للمهندس: عند الحاجة إلى قائد واحد موثوق أو سجل موزّع متناسق، استخدم etcd أو Zookeeper بدلاً من كتابة خوارزميتك الخاصة. أخطاء التوافق خفيّة بشكل مدهش وتستلزم سنوات من الاختبار الإنتاجي لتستقرّ.

خصائص الأداء

يُضيف التوافق زمن استجابة لأن كل عملية كتابة يجب أن تستكمل جولة واحدة على الأقل إلى أغلبية العقد قبل التأكيد. في كتلة من 3 عقد داخل مركز بيانات واحد يكون هذا عادةً 1–5 مللي ثانية. عبر مراكز بيانات أو مناطق توفر مختلفة (مثلاً 50 مللي ثانية RTT بين المناطق) تستغرق الكتابة المؤيَّدة على الأقل 50–100 مللي ثانية. لهذا تظل كتل Raft/Paxos في منطقة واحدة، بينما يستخدم التوزيع الجغرافي استراتيجيات نسخ غير متزامنة فوقها.

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