الساعات المتجهة والسببية

تُسجّل الساعات المتجهة الأحداث بطابع زمني بحيث تكشف مقارنة طابعين زمنيين بدقة ما إذا كان أحدهما يسبق الآخر سببيًا أو ما إذا كان الاثنان متزامنين.

Definition

تُسند الساعة المتجهة لكل حدث متجهًا من العدادات، واحدًا لكل عملية؛ يسبق حدثٌ آخرَ سببيًا إذا وفقط إذا كان متجه الأول أقل من أو يساوي متجه الثاني من حيث المكونات وأقل تمامًا في مكون واحد على الأقل، وتكون الأحداث متزامنة بخلاف ذلك.

Scope

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

Core questions

• كيف يمكن للطوابع الزمنية أن تلتقط السببية بدقة بدلاً من الاتساق فقط؟
• كيف يتم تمييز الأحداث المتزامنة (غير المرتبطة سببيًا) عن الأحداث المرتبة؟
• كيف تكتشف متجهات الإصدار التحديثات المتعارضة بين النسخ المتماثلة؟

Key theories

توصيف الساعة المتجهة للسببية

من خلال الحفاظ على متجه عداد لكل عملية يتم تعظيمه نقطيًا عند استلام الرسائل، تجعل الساعات المتجهة الترتيب المكوني على الطوابع الزمنية مساويًا تمامًا لعلاقة "حدث قبل" (happened-before)، وبالتالي يمكن الكشف عن التزامن.

متجهات الإصدار للكشف عن تعارض النسخ المتماثلة

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

العلاقة بالساعات المنطقية

تُحسن الساعات المتجهة بشكل صارم الساعات المنطقية القياسية للامبورت: تضمن الطوابع الزمنية القياسية فقط أن الترتيب متسق مع السببية، بينما تحدد الطوابع الزمنية المتجهة السببية بدقة على حساب تكلفة مكانية من رتبة O(n) لكل طابع زمني.

Clinical relevance

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

History

بناءً على الوقت المنطقي للامبورت (Lamport)، قدم فيدج (Fidge) وماترن (Mattern) بشكل مستقل الساعات المتجهة في 1988-1989؛ وكانت متجهات الإصدار وثيقة الصلة قد ظهرت بالفعل في عام 1983 للكشف عن عدم الاتساق بين النسخ المتماثلة، وتظل هذه الهياكل مركزية في أنظمة البيانات المنسوخة الحديثة.

Debates

التكلفة المكانية للتتبع الدقيق للسببية

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

Key figures

• Colin Fidge
• Friedemann Mattern
• Leslie Lamport

Seminal works

• fidge1988
• mattern1989
• parker1983

Frequently asked questions

كيف تُحسن الساعات المتجهة ساعات لامبورت؟

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