مرحبا بالجميع!
نود اليوم أن نتطرق مرة أخرى إلى موضوع التنفيذ المتزامن والمتسلسل في البرامج المختلفة ، وخاصة في الأنظمة الموزعة. في شهر سبتمبر ، نشرنا مقالة "
التزامن أسطورة " حول هذا الموضوع ، وننشر الآن ترجمة لدراسة أكثر جدية ، نأمل أن تساعدك على التنقل بشكل أفضل مع الأنظمة الموزعة.
هناك مشكلة حقيقية واحدة فقط في علوم الكمبيوتر: الاعتراف بأن أخطاء إبطال ذاكرة التخزين المؤقت تم تسميتها بشكل غير صحيح. هذه ليست سوى أخطاء في الوحدة تتعلق باستخدام الوقت.
- مؤلف غير معروف
الوقت شيء غريب
هذه المرة غريبة للغاية ، لأننا نريد حقًا أن نصدق أنها مبسطة تمامًا. يبدو لنا أن أي حدث في الساعة 15.00 يحدث (كما نقول) قبل أي حدث في الساعة 16.00 - بدون استثناءات أو حجج أو تنازلات.
ومع ذلك ، فإن علوم الكمبيوتر تعرف الكثير من الأمثلة عندما يكون من الضروري التعامل مع هذا المطلب بشكل صارم. يتجلى على مستوى المعالجات والمترجمين وعقد الشبكة. مرارًا وتكرارًا في الحسابات ، على مستويات مختلفة من المكدس ، نجد أنفسنا في مواقف نواجه فيها حدثين ، ولا نعرف بأي ترتيب حدث. من الواضح أن الوقت ليس كليًا. هي مجزأة.
لماذا؟ والحقيقة أننا لا نعرف ذلك ، لأن مستوى التجريد الذي نعيش عليه لا يوفر إجابة على هذا السؤال. سواء كان عرضيًا أم لا ، فإن ملخصاتنا الحسابية لا تقدم ضمانات فيما يتعلق بالإجراء. غالبًا ما تتيح لك حرية إعادة ترتيب الأحداث إنشاء أنظمة أكثر إنتاجية وبأسعار معقولة.
قد يكون لدى المعالج
نموذج طلب ذاكرة ؛ إنه يعكس الضمانات التي لا يريد المعالج أن يمنحك أي ضمانات في مرحلة التجميع - على سبيل المثال ، أي تعليمات تم تنفيذها في وقت سابق وأيها في وقت لاحق. يقرر المعالج بالضبط كيفية نقل التعليمات وتنفيذها خارج الترتيب - أي أنه يستخدم رقائقه بكفاءة أكبر مما كنت أعتقد.
قد يكون للغة
نموذج مطابق للذاكرة ("نموذج الذاكرة" باختصار) ؛ إنه يعكس ما يضمن أن اللغة لا تمنحك عند إنشاء تجميع ، على سبيل المثال ، عند توزيع الإرشادات عبر سلاسل رسائل متعددة. إن إعادة الترتيب هذه متأصلة في نموذج أجهزة الذاكرة وإلى حد كبير تفسر لماذا يتم توفير مفهوم "ضعيف" للوقت في المترجمات. إنه في إطار نموذج الذاكرة هذا الذي يتم تنفيذه باللغة التي تقوم ببرمجتها عند كتابة رمز غير مانع.
من الأمثلة الشهيرة لنموذج الذاكرة المطبق على مستوى اللغة
نموذج الذاكرة القوي والضعيف في معيار C ++ 11. بشكل افتراضي ، يوفر C ++ عمليات ذرية مع التزامن ، ولكنه يمكن أيضًا أن يضعف نموذج الوصول إلى الذاكرة لتحسين الأداء. الغرض من السلوك المقدم بهذه الطريقة هو أن يكون بمثابة تجريد على بنيات المعالج الرئيسية المستخدمة اليوم (x86 و POWER و ARM).
وأخيراً ، قد يكون للنظام الموزع نموذج الاتساق الخاص به ؛ إنه يعكس ما يضمن أن النظام لن يمنحك فيما يتعلق بترتيب الأحداث على العملاء والنسخ المتماثلة في شبكة الكمبيوتر العالمية. تفسر إعادة الطلب المرتبطة مباشرة بوقت استجابة الاتصالات أو عدم التزامن بشكل أساسي السبب في أنه لا يمكنك الاستغناء عن نظام الوقت الضعيف المذكور في النظام الموزع. هذا هو نموذج الاتساق الذي تقوم ببرمجته عند كتابة تطبيق موزع.
من الناحية العملية ، هناك
حديقة حيوانات ضخمة من نماذج الاتساق التي يمكنك استخدامها عند برمجة نظام موزع. في جميع هذه الحالات ، تصف هذه النماذج السلوك (المطلوب) للنظام المرصود من خارج ذلك النظام. إذا كنت - عميل معين أو دفق معين - أكتب قيمة ، ثم أقرأها على الفور ، فهل من المؤكد أنني سأرى بالتأكيد سجلًا لا يتجاوز عمره؟ إذا لم يكن الوقت مجزأًا ، أو إذا كانت لدينا دائمًا فكرة واضحة عن ترتيب العمليات في نظامنا - بطبيعة الحال ، فإن الإجابة على هذا السؤال ستكون بالإيجاب. سيكون من الغريب طرح مثل هذا السؤال على الإطلاق.
لكن الوقت متجزئ - لذلك من الضروري طرح مثل هذا السؤال.
نماذج الاتساق - أعني نماذج الذاكرة
غالبًا ما يكون التحدث عن مثل هذا النظام المجزأ صعبًا وغير سارٍ دائمًا. نود أن نبدأ من حقيقة أنه على جميع مستويات المكدس ، يكون الوقت دائمًا مطلقًا - سواء مع معاملات ACID أو العمليات / الأقفال الذرية. فكلما كانت الضمانات أكثر صرامة ، كان من الأسهل بطبيعة الحال البرمجة معها!
لكننا جميعا نسعى جاهدين من أجل السرعة. سواء كان الأمر يتعلق بأنظمة موزعة حيث يجب التضحية بالتناسق الصارم من أجل الوصول ، أو حول البرمجة غير المحظورة ، حيث يتم استخدام نموذج ذاكرة ضعيف لتجنب تكاليف المزامنة ، فمن المستحسن عادة للمبرمج الذي يعمل مع أي مستوى من المكدس أن يذهب إلى هذه الحجج المعقدة .
اتساق نماذج الذاكرة المشتركة واتساق نماذج الذاكرة الموزعة
مجردة . يصفون المبرمج الذي يعمل مع النظام ، واجهة هذا النظام. إنها تجعل من الممكن فهم أنواع السلوك التي تتوافق مع نموذج الذاكرة الضعيف ، بالنظر إلى أن الخصائص العامة لترتيب الأحداث في النظام ، والتي نعتبرها أمرًا مسلمًا به ، لم تعد تعمل فيه. قد يبدو أن نموذجي الذاكرة هذين متشابهين ، ومع ذلك ، فقد طورت كلتا الطائفتين خطاباتها الخاصة للمناقشة. تختلف القيم المستخدمة فيها ، على الرغم من أنها تتداخل.
نتخيل بالفعل كيف يمكن أن يكون هذا الخلط. ماذا تفعل؟
وصف الوقت ككيان ، مما يعني في مكان ما من نوعين إلى ثمانية أنواع من الترتيب الجزئي
في
كتابه لعام 2014 ، يسعى سيباستيان بوركهاردت إلى تقديم وصف شامل للخيارات العديدة لنماذج الاتساق. باستخدام هذه الخاصية ، إلى جانب الهياكل الرياضية الأخرى ، يتم استخدام نوعين مختلفين من الترتيب المنطقي للأحداث: "الرؤية" و "التحكيم" ، كما تم ذكرهما سابقًا في أعمال أخرى لبوركهاردت وآخرون ، انظر ، على سبيل المثال ،
المقالة المتعلقة بالإشارة والتحقق أنواع البيانات المكررة (2014).
"الرؤية" هي أمر جزئي متأصل في التكييف المحتمل. يسمح لك بتتبع الأحداث (ربما في النسخ المتماثلة الأخرى) المرئية للأحداث الأخرى. لا توجد متطلبات للرؤية بخلاف الحلقية ؛ يمكن أن تكون الأحداث في كائن مرئية للأحداث في كائن آخر ، ولا تؤثر عملية قراءة أو كتابة حدث على رؤيته للأحداث الأخرى.
"التعسف" هو أمر عام يسمح لك بتتبع الطريقة التي سيحكم فيها النظام الموزع الذي تنشأ فيه حالة الاختيار على أي حدث يحدث في وقت سابق ، وأي حدث لاحق.
نظرًا لأن نماذج الاتساق الموزع تشبه نماذج الذاكرة ، فقد اتضح أن مثل هذه الظواهر للرؤية والعشوائية يمكن أن تكون مفيدة أيضًا عند مناقشة نماذج الذاكرة. على وجه الخصوص ،
في ملحق مقالته لعام 2014 ، يوضح بوركهاردت "مدى قرب" نموذج الذاكرة الضعيف من C ++ 11 إلى الاتساق بين العناصر ، ولكن مع بعض الانحرافات المثيرة للاهتمام. هذا سيتم مناقشته في بقية المنشور.
بادئ ذي بدء ، دعونا نحقق الرؤية والعشوائية ، مع مراعاة "القراءة" و "ترتيب التغييرات". عند "القراءة" ، ستؤخذ الرؤية بين أي شيئين في الاعتبار فقط في المواقف التي تتلامس فيها القراءة والكتابة مع نفس الكائن ، وعند قراءة سجل واحد فقط (أو أكثر من واحد) يمكن رؤيته.
يتوافق هذا مع الموقف الذي يمكن فيه للمعالج الذي لديه ذاكرة مشتركة في أي وقت تسجيل المعلومات في خلية ذاكرة واحدة فقط لأي كائن معين ، حتى إذا كان يمكن لخيوط مختلفة الوصول إليها في لحظات سبب وتأثير مختلفة (من ناحية أخرى ، في النظام الموزع ، المنطقي يمكن تسجيل كائن على الفور في العديد من النسخ المتماثلة المنفصلة).
يتوافق "أمر التعديل" مع نفس المرحلة عند تجسيد التعسف ، فهو موضوعي ويسمح بالتسجيلات فقط. مرة أخرى ، يعتمد هذا التخصص على حقيقة أنه ، مع مواصفات الذاكرة الضعيفة ، يتم منح الضمانات القاطعة فقط على مستوى كائن واحد.
بعد ذلك ، دعونا نناقش بديهيات الاتساق التي صاغها بوركهاردت وآخرون ، ونرى كيف تنطبق على نموذج الذاكرة الضعيف. يرجى ملاحظة: حتى على الرغم من كلمة "البديهيات" ، فهي ببساطة خصائص قد يتم توفيرها أو قد لا يتم توفيرها في نماذج ذاكرة مختلفة. تركز مقالة Burkhardt على الخصائص التي تحدد السببية عبر الأشياء.
التماسك في نهاية المطاف
بالنسبة لأي حدث معين ، لا يمكن أن يكون هناك عدد غير محدد من الأحداث التي لا تراها. أي أن أي حدث مرئي في
نهاية المطاف للنظام.
يجب أن يكون بناء مثل هذه الظروف منطقياً في نظام ذي نموذج ذاكرة ضعيف أكثر صعوبة إلى حد ما: يجب القول أنه بالنسبة لأي
سجل معين لا يمكن أن يكون هناك عدد لا نهائي من عمليات القراءة التي لن تقرأ هذا السجل أو السجلات السابقة (في ترتيب التعديل).
في مواصفات C ++ 11 ، لا يتم ضمان الامتثال لهذه البديهية ، على الرغم من أنه من الصعب عمليًا العثور على مثال مضاد.
الاتساق الأثيري
عند تتبع "المشروطية المحتملة" على مستوى التدفقات / عمليات العملاء وفيما يتعلق بالرؤية / إمكانية القراءة ، عليك أن تفهم أنه لا يوجد وقت عودة. هذا هو السبب في أنه من المطلوب أن تكون عمليات الإغلاق عند طلب التدفقات التي تعني القراءة غير دورية. كقاعدة ، ليس هناك شك في أنه سيتم ملاحظة هذه الخاصية في الأنظمة الموزعة ، ومع ذلك ، فهذه الخاصية لا تسمح برؤية المستخدم في بعض الإصدارات المضاربة إذا كان النظام يحتوي على نموذج ذاكرة ضعيف.
يشير بوركهاردت وزملاؤه إلى أن هذه البديهية "غير مؤكدة" في مواصفات C ++ 11 ، وأنه من غير الواضح "لا يثبت" ما إذا كانت "دورات مرضية" يمكن
ملاحظتها عمليًا .
المسلمات الشرطية
لتحديد ما تعنيه ظاهرة المشروطية بالضبط في ظل نموذج الذاكرة الضعيف ، يجب أن نحدد بدقة الأحداث التي قد تؤثر على نتائج الأحداث الأخرى. للبدء ، ضع في اعتبارك بديهياتنا القياسية للسبب والنتيجة:
ضمانات الجلسة . هذه هي أربع صفات مترابطة تعكس خصائص التماسك لعمليات القراءة والكتابة التي تحدث في تيارات مختلفة ، علاوة على ذلك ، يجب تحديدها على مستوى كل كائن (انظر
Burkhardt وآخرون الشكل 23 ).
- RYW (قراءة السجلات الخاصة بك): تتم عملية القراءة التي تلي عملية الكتابة في نفس الخلية ، في نفس الدفق / النسخة المتماثلة / الجلسة ، يجب أن تقرأ البيانات التي لا تقل صلة عن السجل. يتم تحديد متغير هذه الخاصية للأنظمة الموزعة حصريًا من حيث الرؤية ، بينما يجب أن يعتمد متغير نموذج الذاكرة الضعيفة على كل من ترتيب القراءة وترتيب التغيير.
- MR (قراءات متجانسة): يجب أن ترى القراءات اللاحقة (ضمن نفس الدفق ، في نفس الخلية) بيانات أقل صلة في المستقبل.
- WFR (القراءة الأولى ، ثم الكتابة): إذا كانت الكتابة تتبع القراءة داخل الدفق ، في نفس الخلية ، فيجب أن يتم ترتيبها بعد عملية القراءة بعد ترتيب التغييرات.
- MW (سجلات متجانسة): يجب أن تذهب السجلات اللاحقة (داخل الدفق ، في نفس الخلية) لاحقًا في ترتيب التعديل.
توجد الإصدارات الأصلية من WFR و MW في نسختين ، للعشوائية والرؤية ؛ ولكن هذا مهم فقط عند العمل مع خلايا بيانات أكثر تعقيدًا من التسجيلات للأعداد الصحيحة.
تعكس هذه الخصائص مفاهيم الشرطية ، بما يتفق مع الحس السليم لدينا ؛ ومع ذلك ، يفتقدون الأكثر إثارة للاهتمام. على وجه الخصوص ، عند التحليل في نموذج ذاكرة ضعيف ، فإن مثل هذه الظواهر الشرطية محدودة بحدود التدفق / النسخة المتماثلة / الجلسة والخلية / الكائن المحدد حيث يتم الدخول:
في مقال بقلم Burkhardt وآخرون . في هذه الحالة يقال عن "الرؤية الشرطية موضوعية بشروط" و "تعسفية تعسفية موضوعية مشروطة" ، انظر أيضًا الشكل. 23. هذه الظواهر لا تحد تماما من سلوك النظام عندما تيارات مختلفة تكتب المعلومات إلى خلايا مختلفة.
ثم تصف بديهيات التكييف عبر الأشياء تأثير علاقات السبب والنتيجة على مستوى الكائنات / خلايا الذاكرة المختلفة.
- COCV (الرؤية الشرطية عبر الكائنات): نفس حالة RYW ، ولكن بدون شرط أن تتم القراءة النهائية كلها في نفس سلسلة المحادثات / النسخة المتماثلة / الجلسة. يجب أن تأخذ القراءات من كائن متأخر بشكل موضوعي عن السجلات في هذا الكائن بيانات لا تقل أهمية عن تلك التي تم إدخالها أثناء التسجيل.
تعكس مواصفات C ++ 11 هذه الخصائص. يرجى ملاحظة ما يلي: يتم تعريفها بطريقة لا تعكس فيها قيود تسجيل الرؤية والتعسف في أمر التعديل كثيرًا في هذه التعريفات.
ولكن هذا لا ينطبق على الممتلكات الأخيرة.
- COCA (التعسفي المشروط عبر الكائنات): يشبه السجلات المتجانسة ، ولكنه ينطبق على التدفقات المختلفة ، على غرار COCV - إنه RYW للتدفقات المختلفة. ومع ذلك ، نظرًا لأن ترتيب التعديل يؤثر على السجلات في كائن واحد فقط ، فإن صياغة نموذج ذاكرة ضعيفة تسمح للنظام بتوزيع غير متناسق لأحداث التسجيل في كائنات مختلفة ، وقد لا تتوافق السجلات مع القراءات أو مع الترتيب داخل الدفق.
على وجه التحديد ، يعد COCA في نموذج ذاكرة ضعيف خاصية أضعف بكثير. هذا هو السبب في وجود نموذج ذاكرة ضعيف ، قد ترجع التعليمات البرمجية التالية
{x ≡ 0, y ≡ 0} .
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return yقد يكون الترتيب داخل كل دفق غير متناسق مع ترتيب كل أمر على حدة وترتيب التعديل. يرجى ملاحظة ما يلي: مع RYW لا يوجد
x := 0 → x := 1 في ترتيب التعديل و
y هو نفسه ؛ وبالتالي ، يجب أن يحتوي ترتيب التعديل على
x := 1 → x := 0 و
y := 1 → y := 0 . وبالتالي ، من الواضح أن ترتيب التعديل يشكل دورة في ترتيب التدفقات.
يُسمح بمثل هذه الحلقة في COCA مع نموذج ذاكرة ضعيف. لا يعني ذلك أن ترتيب التدفقات / القراءات يتعارض مع ترتيب التعديل ، ولكن يرى كل دفق سجل تسجيل ثابت. تتوافق هذه القصص مع قصص التدفقات الأخرى فقط إذا حددنا بموضوعية نطاق تطبيقها.
ماذا يعني كل هذا؟
الوقت مجزأ.
على الرغم من أنه يبدو لنا أن الوقت يتدفق بطريقة منظمة ، فإن دراسة النظم الموزعة ونموذج الذاكرة الضعيف يظهر لك بوضوح أن الأمر ليس كذلك. هذا هو السبب في كلتا الحالتين ، فإن تقديرنا الزائد القياسي ، وفقًا للوقت الإجمالي ، يحد من الأداء - والذي لا يمكننا تحمله.
بعد ذلك ، إدراكًا بأن الوقت مجزأ حقًا ، نجد العديد من الاختلافات الصغيرة ولكنها مهمة بين أصناف مثل هذا التحيز. حتى الحقلين المذكورين أعلاه ، اللذان يبدوان متشابهين للوهلة الأولى ، في العديد من الفروق الدقيقة الدقيقة ، يمكن التمييز بين أنواع معينة من الأحداث التي تعتبر مؤثرة بشكل متبادل.
من الضروري أن نفهم بمزيد من التفصيل التفاصيل الفنية لمختلف الخصائص بالفعل بعد أن يتمكن شخص ما من التعبير عن خصائص حقل واحد بلغة حقل آخر.
الوقت مجزأ. ربما نحتاج فقط إلى التعود عليها.