لقد نفّذت خوارزمية الإجماع Raft (المثال الأبرز للخوارزميات الموزعة) بلغة Python. إنه تنفيذ سيئ جدًا! لكنه أيضًا صحيح (إلى حد ما).
إليك بعض الملاحظات التي أود مشاركتها مع أي شخص آخر مهتم بخوض تحدٍّ مماثل.
بالنظر إلى التجربة الآن، كانت هذه أكثر الموارد فائدة لتعلّم Raft وتنفيذه على نحو صحيح.
- ورقة Raft البحثية (اقرأ حتى القسم 5، وارجع كثيرًا إلى الشكل 2)
- دليل الطلاب إلى Raft
- أحد أكثر تطبيقات Raft استخدامًا
- استنسخ المستودع، وألقِ نظرة سريعة على
raft.go، وتحاور مع نموذج لغوي كبير لفهم قاعدة الشيفرة وقرارات التصميم
- استنسخ المستودع، وألقِ نظرة سريعة على
- سلسلة مقالات إيلي بندرسكي
أقترح تخصيص ساعة تقريبًا لقراءة الورقة أولًا، ثم كتابة هيكل أولي لشيفرة خادم UDP أو TCP يقرأ البايتات الواردة ويضيفها إلى مصفوفة. ثم تابعت تنفيذ إيلي خطوة بخطوة، وأضفت الميزات إلى تنفيذي لخوارزمية Raft بالترتيب نفسه.
بعد أن جعلت شيئًا يشبه آلية انتخاب القائد يعمل، بدأت أبحث عن الأخطاء البرمجية والأخطاء في فهمي للخوارزمية. كنت أتنقّل بين دليل الطلاب والشكل 2 في ورقة Raft البحثية وتنفيذي، وأفكر بعناية في المواضع التي يتطابق فيها تنفيذي مع ما ورد فيهما (أو يختلف عنه). واستعنت أيضًا كثيرًا بنموذج لغوي كبير لمراجعة هذه الشيفرة، مع إضافة مواد من الموارد المذكورة أعلاه إلى السياق.
كرّر العملية السابقة لنسخ السجل والحفظ الدائم، وما إلى ذلك.
بخصوص التنفيذ
اتخذت بعض القرارات التصميمية لتبسيط تنفيذي. دون ترتيب معيّن:
- تعمل كل عقدة وتعالج الرسائل ضمن خيط تنفيذ واحد
- استخدام "ساعة منطقية" لتتبّع "الوقت" المحلي في النظام (مثلًا، استدعاء
tick()وزيادة عدّاد محلي لكل عقدة بدلًا من استخدام وقت النظام) - جعل التنفيذ "فوضويًا" بوضع كل شيء في ملف واحد، مثل تحليل بيانات الشبكة، والتخزين/الحفظ الدائم، وجوهر خوارزمية Raft، والأدوات/الأوامر للتحكّم في العقدة نفسها
يبدو الخيار 2 سليمًا وصحيحًا من حيث التصميم (فالساعات المنطقية هي ما يُستخدم في تنفيذ etcd). ويمكن القول إن الخيار 3 أفضل للتعلّم/التدريس. من الجيد أن يكون كل شيء في ملف واحد لتتمكّن من رؤيته دفعة واحدة، فهذا يمنحك تنفيذًا جيدًا يمكنك تفكيكه لترى أي التجريدات يناسب الخوارزمية على أفضل وجه.
أما الخيار 1 فأراه خيارًا سيئًا إلى حدٍّ لافت. صحيح أنه يجعل التنفيذ أبسط بكثير (إذ يقلّ انشغالك باحتمال الوقوع في حالات جمود وبضمان ذرّية تحديثات الحالة الداخلية للعقدة)، لكنك تنتهي أيضًا بشيء لا يطابق Raft تمامًا. بالنسبة إلى تنفيذ أول، يبدو هذا مقبولًا. فالخوارزمية معقّدة بما يكفي، وأعتقد أنك ستفضّل قضاء وقتك في تصحيح الأخطاء المنطقية في جوهر خوارزمية Raft على الانشغال بتفاصيل أقفال الاستبعاد المتبادل.
أعدّ تنفيذ Raft بهذه الطريقة مشروعًا يستغرق نحو 30 ساعة. من المفترض أن تستغرق القراءة الأولية لورقة Raft ومراجعة المواد ذات الصلة بضع ساعات. أنجزت معظم البرمجة خلال نحو 3 أيام في العطلة، بمعدّل 6-8 ساعات من البرمجة يوميًا تقريبًا. لا تزال لديّ بعض الأمور التي أحتاج إلى صقلها وتحسينها (مثل إصلاح بعض الأخطاء الدقيقة) في التنفيذ الحالي، وقد يتطلّب ذلك نصف يوم آخر من العمل.
عمومًا، ليست حصيلة سيئة لفهم إحدى الخوارزميات الأساسية التي تُشغِّل هذا القدر الكبير من البنية التحتية.