الوقت والساعات و الترتيب.

المقال الأصلي :https://dean.eigenmann.me/blog/2020/01/06/time-clocks-and-order/

سيشرح هذا المقال المفاهيم الموجودة في ورقة بحثية كتبها ليزلي لامبورت بعنوان “الوقت والساعات وترتيب الأحداث في نظام موزع”. بالنسبة لأولئك الذين ليسوا على دراية بـ Leslie Lamport ، فهو معروف بإنشاء LaTeX و TLA + و Paxos ، ووصف مشكلة الجنرالات البيزنطيين وبالطبع ساعات Lamport التي سنبحثها في هذا المقال.

قبل أن نبدأ ، دعنا نحدد ما هو النظام الموزع. سوف نستخدم تعريف Lamport من الورقة مباشرة:

    “يعتبر النظام موزع  إذا كان تأخير إرسال الرسائل غير مهم مقارنة بالوقت بين الأحداث في عملية واحدة.”

يعجبني هذا التعريف لأنه لا يقدم أي تعليقات على أي شيء بخلاف زمن الانتقال بين إرسال الرسائل واستلامها.

الآن نحن جاهزون للبدء.

الترتيب

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

ومع ذلك ، فإن المشكلة تزداد صعوبة في سياق النظام الموزع.

لماذا هذا هو الحال؟

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

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

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

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

الساعات

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

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

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

ولكن ماذا يعني هذا في الواقع؟

دعونا نفككها : استخدمنا السهم → للدلالة على العلاقة “حدث من قبل” و C هي وظيفة الساعة. مع ذلك ، يمكننا ترجمة الشرط أعلاه على النحو التالي: لكل حدث a، b ، إذا حدث a قبل b ، فإن وقتa أصغر من b

رسم تخطيطي يوضح العلاقة السببية بين الأحداث وعلامات الوقت للساعات.

العكس لا يصح ، لمجرد أن وقت الحدث أصغر من وقت آخر ، لا يعني أن الحدث وقع من قبل ، يمكن أن يكون متزامنًا. في الصورة أعلاه ، يمكننا أن نرى الأحداث على Node α حدثت في الوقت 1 والوقت 2. Node β كان لها حدث في وقتها الخاص 1. لذلك ، الأحداث على α خلال الوقت 1 و 2 متزامنة مع الحدث في β في الوقت 1 لأنهم لم يكونوا مرتبطين سببيًا.

يتم استيفاء حالة الساعة هذه بالشروط التالية:

  • اذا كان a و b هي أحداث على عقدة واحدة ، وحدث a قبل b ، فيجب أن يكون وقت a أصغر من وقت b

.

  • اذا كان a هي عقدة ترسل رسالة ، و b تستلم تلك الرسالة على عقدة أخرى ،  فيجب أن يظل وقت a أصغر من ذلك من ب

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

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

في الممارسه

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

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

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

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

  • يتم استلام جميع الرسائل بترتيب إرسالها.
  • يتم استلام جميع الرسائل في النهاية.
  • نفترض أن كل عقدة يمكنها إرسال رسالة مباشرة إلى جميع العقد الأخرى في النظام.

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

الآن  ، يمكننا تحديد الخوارزمية التي تلبي شروطنا الثلاثة وتعرض فائدة الساعات عمليًا:

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

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

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

إضافة تعليق