كيف تتفاوض الخوادم مع بعضها البعض: تقوم الطوافة بتوزيع خوارزمية الإجماع

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

كاتب المقال: ديمتري بافلوشين (مطور دودو بيتزا للهندسة).

تعد Raft خوارزمية إجماعية موزعة مطلوبة حتى يتمكن العديد من المشاركين من تحديد ما إذا كان الحدث قد وقع أم لا وما الذي تبعه.

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


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

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

المفاهيم الأساسية

1. حالات الخادم في مجموعة Raft ، يكون كل خادم في أي وقت محدد في إحدى الحالات الثلاث:
   
   • Leader (leader) - يقوم بمعالجة جميع طلبات العميل ، وهو مصدر الحقيقة لجميع البيانات في السجل ، ويدعم سجل المتابعين.
   • التابع (التابع) هو خادم غير فعال "يستمع" فقط إلى إدخالات السجل الجديدة من القائد ويعيد توجيه جميع الطلبات الواردة من العملاء إلى القائد. في الواقع ، إنها نسخة طبق الأصل في وضع الاستعداد للزعيم.
   • المرشح (المرشح) هو حالة خاصة للخادم ، لا يمكن تحقيقه إلا أثناء اختيار قائد جديد.
   
   أثناء التشغيل العادي في الكتلة ، هناك خادم واحد فقط هو الرائد ، والباقي متابعون له.
   
   
   حول عدم التزامن

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

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

خوارزمية العمل

1. اختيار زعيم

لتحديد الوقت المناسب لبدء انتخابات جديدة ، تعتمد Raft على نبضات القلب. يظل التابع تابعًا حتى يتلقى رسائل من القائد أو المرشح الحالي. يرسل الزعيم بشكل دوري نبضات إلى جميع الخوادم الأخرى.

إذا لم يتلق المتابِع أي رسائل لبعض الوقت ، فسوف يفترض بطبيعة الحال أن الزعيم قد مات ، مما يعني أن الوقت قد حان لأخذ زمام المبادرة في يديه. في هذه المرحلة ، يبدأ التابع السابق في الانتخابات.

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

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

2. نحن تكرار السجلات

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

عندما يتم نسخ السجل بنجاح على معظم الخوادم ، يبدأ القائد في اعتبار السجل مغلقًا ويستجيب للعميل. الزعيم يتتبع أي سجل هو الأخير. يرسل رقم هذا السجل إلى AppendEntries (بما في ذلك نبضات القلب) حتى يتمكن المتابعون من الالتزام بالسجل لأنفسهم.

في حال لم يتمكن الزعيم من الوصول إلى بعض المتابعين ، فسوف يتتبع AppendEntries إلى ما لا نهاية. توضح الصورة التالية كيفية تنظيم السجلات في مجموعة Raft:



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

3. نحن نضمن موثوقية الخوارزمية

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

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

  الحث الرياضي هو وسيلة لإثبات عندما تكون الخطوة الأولى هي إثبات بيان لحالة بسيطة. في الخطوة الثانية ، نحن نقبل العبارة الحقيقية لبعض الحالات X. وبناءً على ذلك ، نحاول إثبات البيان لبعض الحالات المجاورة X + 1. تساعد هاتان الخطوتان معًا في إثبات البيان لجميع الحالات.
  
  في وضعنا ، حالة بسيطة هي سجلات فارغة. لا توجد سجلات ، وبالتالي لا يوجد شيء ينتهك الممتلكات.
  
  الآن دعونا نحاول أن نفترض أن هناك بعض الإدخالات في السجلات التي تتوافق مع ممتلكاتنا. يحتوي Raft على آلية تمنع الخاصية من الانقطاع عند تغيير أي سجل. تسمى هذه الآلية التحقق من التناسق . دعونا نلقي نظرة على الأمثلة على الفور.
  
  مثال جيد هناك زعيم ، على سبيل المثال ، من الفصل الرابع ، هناك تابع. كلاهما لديه سجلات مطابقة من ثلاثة إدخالات.
  
  
  
  طلب مقدم من العميل يأتي إلى القائد ، ويضيف مدخلاً إلى سجله.
  
  
  
  يرسل الزعيم AppendEntries إلى التابع. ولكن ، بالإضافة إلى السجل الأكثر إضافة ، يشير القائد أيضًا في الطلب إلى ضرورة إضافة السجل في الفهرس 4 ، وعند الفهرس 3 ، أمامه ، يجب أن يكون هناك سجل من الفصل 2.
  
  
  
  يطابق إدخال السجل في الفهرس 3 في سجل المتابع المدخل المحدد في الطلب ، لذلك يضيف المتابع الإدخال إلى سجله ويستجيب بنجاح للزعيم. النهاية.
  
  
  
  أيضا مثال جيد ، ولكن مع بداية مأساوية. الآن سجل المتابعين يختلف عن سجل الزعيم الحالي.
  
  
  
  عندما يتلقى الزعيم طلبًا بإضافة إدخال إلى السجل ، فسيرسل نفس AppendEntries كما في المثال السابق.
  
  
  
  ومع ذلك ، هذه المرة ، بما أن المتابع لا يطابق السجل السابق ، فإن المتابع يفشل.
  
  
  
  ماذا يفعل القائد في هذه الحالة؟ يقوم القائد ببساطة بالرجوع قليلاً ويحاول إمداد التابع بالسجل الذي يعتبره هو نفسه يقف في الفهرس 3. كما يتضمن السجل السابق في الطلب.
  
  
  
  يستجيب المتابع الآن بنجاح ويقوم بالكتابة فوق الإدخالات في سجله ، بدءًا من الفهرس 3.
  
  
  
  قد يختلف سجل التابع عن سجل الزعيم كما يحلو لك. قد لا يكون هناك ما يكفي من الإدخالات فيه ، وقد يكون هناك إدخالات إضافية فيه. في أي حال ، يضمن التحقق من التناسق أن سجلات المتابعين ستتزامن عاجلاً أو آجلاً مع سجل الزعيم.
  
  
  
• اكتمال العميل : إذا تم الالتزام بإدخال السجل في وقت معين ، فسوف تتضمن سجلات القادة في جميع الفترات اللاحقة هذا السجل. هذه الخاصية توفر لنا ضمانات المتانة.
  
  
  والدليل على الصور

  خذ بعين الاعتبار الموقف التالي: ثلاثة خوادم في كتلة. Server S1 هو زعيم الفصل الأول الحالي. جميع الخوادم لديها ثلاثة إدخالات السجل.
  
  
  
  يتلقى Leader S1 طلبًا من العميل ويضيف سجلًا جديدًا إلى سجله ، ويرسل AppendEntries إلى خوادم S2 و S3 الأخرى.
  
  
  
  سجل بنجاح يصل إلى S2 ، ولكن الشبكة بين S1 و S3 يومض ، ويتم فقد الطلب. نظرًا لأن S1 يعرف أن السجل موجود على اثنين من الخوادم الثلاثة ، فيمكنه تحديد أن السجل قد تم الالتزام به والرد عليه بنجاح.
  
  ستعيد S1 أيضًا محاولة إضافة إدخال إلى S3 حتى تنجح. ولكن ماذا يحدث إذا فشل S1 وتوقف؟ علاوة على ذلك ، ماذا سيحدث إذا كان S3 هو أول من سئم من الانتظار وأصبح مرشحًا؟ S2 سوف يصوت لذلك ، S3 سيصبح زعيم الفترة الثانية ، وعلى الطلب التالي لإضافة سجل ، سوف S3 الكتابة فوق سجلنا المسجل؟
  
  
  
  في الواقع ، لا يمكن أن يحدث هذا الموقف في مجموعة الطوافة. المهم هنا هو أن S2 لن يصوت لصالح S3. لماذا؟ لأن سجل خادم S3 في وقت التصويت أقل أهمية من سجل خادم S2. تسمى هذه الآلية تقييد الانتخابات - سيصوت الخادم لخادم آخر فقط إذا كان سجل المرشح أقل صلة بسجل الناخب.
  
  تقارن الطوافة أهمية السجلات بطريقتين:
  
  

  • تاريخ آخر رقم قياسي
  • طول السجل

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

روابط لمواد لمزيد من الدراسة

• خوارزمية توافق الطوافة
• بحثا عن خوارزمية توافق مفهومة
• الإجماع: سد النظرية والتطبيق
• القط شرودنجر دون مربع: مشكلة التوافق في النظم الموزعة