الأنظمة الموزعة والموثوقية
الاتساق والتوفر والتوافق
الأنظمة الموزعة هي العمود الفقري لكل نظام خلفي واسع النطاق. يغطي هذا الدرس النظريات الأساسية ونماذج الاتساق وخوارزميات التوافق التي يتوقع المحاورون في مستوى L5+ أن تتحدث عنها بطلاقة.
نظرية CAP بعمق
تنص نظرية CAP (Brewer, 2000) على أن مخزن البيانات الموزع يمكنه ضمان خاصيتين فقط من ثلاث في وقت واحد:
- الاتساق (C): كل قراءة تحصل على أحدث كتابة أو خطأ
- التوفر (A): كل طلب يحصل على استجابة بدون خطأ (بدون ضمان أنها تحتوي على أحدث كتابة)
- تحمل التقسيم (P): النظام يستمر في العمل رغم انقطاع الشبكة بين العقد
تحمل التقسيم ليس اختياريًا
في أي نظام موزع، انقطاعات الشبكة ستحدث. الكابلات تُقطع والمبدلات تتعطل ومناطق التوفر السحابية تفقد الاتصال. بما أنه لا يمكنك تجنب التقسيمات، فالاختيار الحقيقي هو بين CP و AP عند حدوث تقسيم.
نظرية CAP
C ─────────────────────── A
│ يمكنك اختيار │
│ اثنين │
│ │
│ ┌──────────┐ │
│ │ CA │ │
│ │ (عقدة │ │
│ │ واحدة │ │
│ │ فقط) │ │
│ └──────────┘ │
│ │
└──────────── P ───────────┘
(موجود دائمًا
في الأنظمة
الموزعة)
أنظمة CP — اختيار الاتساق على التوفر
عند حدوث تقسيم، ترفض أنظمة CP الطلبات بدلاً من إرجاع بيانات قديمة.
| النظام | كيف يحقق CP |
|---|---|
| Google Spanner | واجهة TrueTime (GPS + ساعات ذرية) توفر اتساقًا خارجيًا. عمليات الإيداع تنتظر انتهاء فترة عدم اليقين، مما يضمن ترتيبًا عالميًا. |
| HBase | سيد واحد لكل منطقة. أثناء التقسيم، المناطق على الجانب الخطأ تصبح غير متوفرة. |
| ZooKeeper | توافق قائم على القائد (بروتوكول ZAB). الكتابات تمر عبر القائد؛ إذا انفصل القائد، لا يمكن لتقسيم الأقلية خدمة الكتابات. |
| etcd | توافق Raft. يتطلب نصاب الأغلبية للكتابات. تقسيم الأقلية يصبح للقراءة فقط. |
أنظمة AP — اختيار التوفر على الاتساق
عند حدوث تقسيم، تستمر أنظمة AP في خدمة الطلبات لكن قد تُرجع بيانات قديمة أو متعارضة.
| النظام | كيف يحقق AP |
|---|---|
| DynamoDB | نصاب مرن + تسليم بتلميح. الكتابات تنجح حتى لو كانت بعض النسخ غير قابلة للوصول. التعارضات تُحل عبر آخر كاتب يربح أو مصالحة على مستوى التطبيق. |
| Cassandra | اتساق قابل للضبط (ONE, QUORUM, ALL). عند مستوى اتساق ONE، يكون AP — أي نسخة واحدة يمكنها خدمة القراءات/الكتابات أثناء التقسيم. |
| CouchDB | نسخ متعدد الأسياد. يقبل الكتابات على أي عقدة أثناء التقسيم. يكتشف ويعرض التعارضات لحلها من التطبيق. |
CA خرافة في الأنظمة الموزعة
نظام CA يتطلب ألا تحدث أي تقسيمات أبدًا. هذا ممكن فقط على عقدة واحدة (مثلاً، نسخة PostgreSQL واحدة). لحظة إضافة عقدة ثانية، يجب التعامل مع التقسيمات.
واقع الطيف
معظم أنظمة الإنتاج ليست CP أو AP بشكل ثنائي. بل تقع على طيف مع اتساق قابل للضبط:
- Cassandra مع قراءات/كتابات
QUORUMتتصرف كـ CP لتلك العمليات - DynamoDB مع تمكين القراءات القوية تتصرف كـ CP للقراءات
- CockroachDB هو CP افتراضيًا لكن يمكنه التضحية بالاتساق من أجل التوفر مع قراءات المتابعين
نظرية PACELC
نظرية CAP تصف السلوك أثناء التقسيم فقط. نظرية PACELC (Abadi, 2012) توسعها: عندما لا يوجد تقسيم (E)، يجب الاختيار بين زمن الاستجابة والاتساق.
إذا تقسيم (P): وإلا (E):
اختر A أو C اختر L أو C
┌─────────────────┐ ┌─────────────────┐
│ PA: متوفر │ │ EL: زمن منخفض │
│ PC: متسق │ │ EC: متسق │
└─────────────────┘ └─────────────────┘
| النظام | سلوك التقسيم | السلوك العادي | PACELC |
|---|---|---|---|
| DynamoDB | PA (متوفر) | EL (زمن منخفض) | PA/EL |
| Cassandra | PA (متوفر) | EL (زمن منخفض) | PA/EL |
| Spanner | PC (متسق) | EC (متسق) | PC/EC |
| MongoDB | PA (متوفر) | EC (متسق) | PA/EC |
| CockroachDB | PC (متسق) | EL (زمن منخفض مع قراءات المتابعين) | PC/EL |
نصيحة للمقابلة: عند السؤال عن CAP، اذكر PACELC لإظهار فهم أعمق. معظم الأنظمة الحقيقية تُحسّن لحالة "لا تقسيم" لأن التقسيمات نادرة.
طيف نماذج الاتساق
من الأقوى إلى الأضعف:
| النموذج | الضمان | نظام مثال |
|---|---|---|
| الخطية (Linearizability) | ترتيب وقت حقيقي. بمجرد اكتمال كتابة، جميع القراءات اللاحقة (من أي عميل) تراها. | Spanner, etcd |
| الاتساق التسلسلي | جميع العمليات تظهر بترتيب كلي متسق مع ترتيب برنامج كل عميل. | ZooKeeper (لكل جلسة) |
| الاتساق السببي | العمليات المرتبطة سببيًا مرتبة. العمليات المتزامنة قد تظهر بأي ترتيب. | MongoDB (جلسات سببية) |
| اقرأ كتاباتك | العميل يرى كتاباته دائمًا. العملاء الآخرون قد يرون بيانات قديمة. | DynamoDB (قراءات قوية) |
| الاتساق النهائي | جميع النسخ تتقارب لنفس الحالة في النهاية. بدون ضمانات ترتيب أثناء التقارب. | DynamoDB (افتراضي), Cassandra (ONE), DNS |
تمييز مهم في المقابلة: الخطية تتعلق بترتيب الوقت الحقيقي (ساعة الحائط). الاتساق التسلسلي يتعلق بترتيب كلي منطقي متسق مع ترتيب البرنامج. كثير من المرشحين يخلطون بين الاثنين.
خوارزمية توافق Raft
Raft هي خوارزمية التوافق التي يتوقع معظم المحاورين أن تعرفها. هي مكافئة لـ Paxos في الأمان لكنها مصممة لتكون مفهومة.
ثلاثة أدوار
- القائد (Leader): يتعامل مع جميع طلبات العملاء وينسخ سجلات القيد للمتابعين
- المتابع (Follower): سلبي — يستجيب لاستدعاءات القائد ويصوت في الانتخابات
- المرشح (Candidate): متابع بدأ انتخابًا ليصبح قائدًا
انتخاب القائد
الفترة 1 الفترة 2 الفترة 3
┌────────┐ ┌────────┐ ┌────────┐
│القائد A│──X──────│انتخاب │───────────│القائد C│
│ │ (تعطل) │ B, C │ │ │
└────────┘ │ تصويت │ └────────┘
└────────┘
خطوة بخطوة:
1. القائد A يرسل نبضات كل 150 مللي ثانية
2. القائد A يتعطل — المتابعون يتوقفون عن استقبال النبضات
3. مهلة انتخاب المتابع C تنتهي (عشوائية: 150-300 مللي ثانية)
4. C يزيد الفترة إلى 2، ينتقل لمرشح، يصوت لنفسه
5. C يرسل استدعاءات RequestVote لجميع العقد الأخرى
6. كل عقدة تصوت لمرشح واحد على الأكثر لكل فترة
7. C يستقبل أصوات الأغلبية (بما في ذلك صوته) ← يصبح قائدًا
8. C يرسل نبضات لتثبيت سلطته ومنع انتخابات جديدة
القواعد الأساسية:
- مهلة الانتخاب عشوائية (150-300 مللي ثانية) لتجنب تقسيم الأصوات
- العقدة تصوت للمرشح الأول الذي تسمع منه في فترة معينة
- المرشح يجب أن يملك سجلاً محدثًا على الأقل مثل سجل المصوت (قيد الانتخاب)
نسخ السجل
العميل القائد المتابع 1 المتابع 2
│ │ │ │
│──اكتب X=5────>│ │ │
│ │──AppendEntries─>│ │
│ │──AppendEntries──────────────────>│
│ │ │ │
│ │<──نجاح─────────│ │
│ │<──نجاح──────────────────────────│
│ │ │ │
│ │ الأغلبية أكدت (2/3) │
│ │ إيداع القيد، تقديم commitIndex │
│<──موافق───────│ │ │
│ │──نبضة (commitIndex)────────────>│
│ │ │ تطبيق القيد │
- العميل يرسل كتابة للقائد
- القائد يلحق القيد بسجله مع رقم الفترة الحالية
- القائد يرسل استدعاءات AppendEntries لجميع المتابعين
- عندما تؤكد الأغلبية، يصبح القيد مودعًا
- القائد يستجيب للعميل بعد الإيداع
- المتابعون يطبقون القيود المودعة في النبضة التالية
ضمانات الأمان
- قيد الانتخاب: فقط المرشح الذي يملك جميع القيود المودعة يمكنه الفوز بالانتخاب
- مطابقة السجل: إذا احتوى سجلان على قيد بنفس الفهرس والفترة، فجميع القيود السابقة متطابقة
- اكتمال القائد: القيد المودع موجود في سجل كل قائد مستقبلي
Paxos مقابل Raft
| الجانب | Raft | Paxos |
|---|---|---|
| قابلية الفهم | مصمم للوضوح | صعب الفهم بشكل ملحوظ |
| القائد | يتطلب قائدًا واحدًا | يمكن العمل بدون قائد (Multi-Paxos يستخدم قائدًا للأداء) |
| المراحل | مرحلتان: انتخاب + نسخ | ثلاث مراحل: تحضير، وعد، قبول |
| الاستخدام العملي | etcd, Consul, CockroachDB | Chubby (Google), Spanner (يستخدم مجموعات Paxos) |
نصيحة للمقابلة: "Raft مكافئ لـ Multi-Paxos من حيث الأمان والحيوية، لكنه يحلل المشكلة إلى انتخاب القائد ونسخ السجل والأمان — مما يجعله أسهل في التفكير."
الساعات المتجهية والطوابع الزمنية لـ Lamport
طوابع Lamport الزمنية
ساعة منطقية تؤسس ترتيب حدث قبل:
العقدة A: [1] ──────── [2] ──────── [4]
│ ▲
│ إرسال(رسالة) │
▼ │
العقدة B: [1] ── [3] ──────── [5] ───┘
│
▼ إرسال(رسالة)
العقدة C: [1] ──────── [2] ── [6]
القواعد:
1. قبل أي حدث، زد العداد المحلي
2. عند الإرسال: أرفق الطابع الزمني الحالي
3. عند الاستقبال: محلي = max(محلي، مستقبل) + 1
القيد: إذا كان timestamp(A) < timestamp(B)، لا يمكنك استنتاج أن A حدث قبل B. قد يكونان متزامنين. طوابع Lamport تضمن فقط: إذا حدث A قبل B، فإن timestamp(A) < timestamp(B) (العكس ليس صحيحًا).
الساعات المتجهية (Vector Clocks)
الساعات المتجهية تتبع الوقت المنطقي لكل عقدة، مما يسمح باكتشاف الأحداث المتزامنة:
العقدة A: [1,0,0] ─── [2,0,0] ──────────── [3,2,0]
▲ │
إرسال │ استقبال │
│ ▼
العقدة B: [0,1,0] ─── [0,2,0] ───────────── [3,3,0]
│
▼ إرسال
العقدة C: [0,0,1] ─── [0,2,2]
المقارنة:
- [2,0,0] مقابل [0,2,0] ← متزامنان (لا أحد يهيمن)
- [2,0,0] مقابل [3,2,0] ← [2,0,0] حدث قبل [3,2,0]
- VC1 < VC2 إذا وفقط إذا كل عنصر في VC1 <= VC2 وواحد على الأقل أصغر بشكل صارم
تُستخدم في ورقة Amazon Dynamo لاكتشاف التعارضات: عندما يكون لكتابتين ساعات متجهية متزامنة، يعرف النظام أن هناك تعارضًا ويمكنه تقديم كلا النسختين للمصالحة.
خلاصة المقابلة: طوابع Lamport تعطيك ترتيبًا كليًا (لكن لا تكتشف التزامن). الساعات المتجهية تكتشف التزامن (لكن لا تعطي ترتيبًا كليًا). اختر بناءً على ما تحتاجه.
التالي: التزامن والخيوط المتعددة — حالات السباق والجمود والأنماط الخاصة بكل لغة التي تهيمن على جولات البرمجة. :::