في الأنظمة الموزعة ، هناك عدد من المشاكل الأساسية: المعاملات الموزعة الفعالة ، ومعالجة البيانات لمرة واحدة بالضبط ، والمزامنة الدقيقة للساعات المادية. لحل المشكلة الأخيرة ، تم اختراع أنواع مختلفة من الساعات المنطقية .
ومع ذلك ، فإن ساعات المتجهات لها خصائص غير سارة: فهي تقدم اعتمادًا مشروطًا بين الأحداث التي لا توجد فيها ، وتفقدها في مكانها الفعلي.
ومع ذلك ، يمكنك الخروج بشيء أكثر موثوقية - كرونوس. في المقالة ، سنلقي نظرة على خوارزمية محاسبة العلاقة بين السبب والنتيجة وتطبيقها لبناء تخزين القيمة الرئيسية مع المعاملات الموزعة.
المشاكل
كما ذكرنا من قبل ، هناك عدد من المشاكل في الساعة المنطقية:
تنشأ تبعيات غير موجودة لأن الساعة المنطقية تقدم ترتيبًا كاملًا للأحداث - أي أنه يمكن القول أن أيًا من أي حدثين يمكن أن يكون مشروطًا في وقت سابق وأيهما مشروط لاحقًا. العقد مشروط ، لأنه من المستحيل تحديد العلاقة بين الأحداث في الوقت المحدد بدقة ، بما في ذلك بسبب النظرية النسبية الخاصة.
من ناحية أخرى ، فإن ساعة المنطق تراعي فقط التوصيل البيني من خلال الرسائل داخل النظام. إذا تم ربط أي حدثين ، ولكن خارج النظام ، على سبيل المثال ، من خلال المستخدم (إضافة سلع إلى السلة في جزء واحد من النظام -> الدفع مقابل الطلب) ، فقد تفقد الساعة المنطقية هذه العلاقة.
لا يمكن الوصول إلى الساعات المنطقية من الخارج ، ومن الصعب أيضًا ربط العديد من المكونات المستقلة (نظام الملفات الموزعة ، خدمات معالجة الطلبات ، التحليلات).
الحل
في مقال عام 2014 من Kronos: تصميم وتنفيذ خدمة ترتيب الأحداث ، تم اقتراح حل - خدمة قائمة بذاتها تتعامل مع علاقات السبب والنتيجة في الأحداث.
التجريد الرئيسي داخل كرونوس هو حدث يتم فيه تقديم ترتيب جزئي. علاقة السبب والنتيجة متعدية - أي ، إذا كنا ، على سبيل المثال ، نعرف أن إنشاء الملف يسبق تغييره ، والتغيير يسبق الحذف ، يمكننا أن نخلص إلى نتيجة منطقية بأن الخلق حدث قبل الحذف.
يمكن تحديد الحد الأدنى لواجهة برمجة التطبيقات من خلال مجموعة الأساليب التالية:
| الطريقة | النتيجة | تعليق |
|---|
create_event() | e | يخلق حدث جديد في كرونوس |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | لكل زوج من الطلب ، يقوم بإرجاع اتجاه علاقة السبب والنتيجة ، أو تزامن الأحداث |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | لكل زوج من الطلب ، يحدد اتجاه السببية |
acquire_ref(e) | OK | يزيد العداد المرجعي لهذا الحدث. |
release_ref(e) | OK | يقلل العدد المرجعي لهذا الحدث. |
التنفيذ
من المنطقي أن يقوم النظام على رسم بياني للأحداث موجه ، مع بحث فعال واسع النطاق للتحقق من علاقة الأحداث ، وآلية الاستقرار في حالة الفشل ، وجمع القمامة.
كما يمكن رؤيته من واجهة برمجة التطبيقات ، assign_order طلب assign_order نوع علاقة سببية: must أو prefer . must يتوافق مع الثوابت الصارمة - على سبيل المثال ، _->_ ، قد لا يتم تطبيق التفضيل إذا كان يتعارض مع العلاقات must . أحد الأمثلة على استخدام prefer هو أن الطلبات التي جاءت في وقت سابق أفضل من قبل ، ولكن هذا لا يؤثر على صحة.
BFS فعالة
في حالتنا ، قد يكون الرسم البياني كبيرًا ، ولكن غالبًا ما تكون الأحداث التي سيتم تنفيذ طلبات التحقق لها مغلقة. لذلك ، يجب تشغيل BFS بشكل أسرع لمثل هذه الحالات.
في التطبيق القياسي ، فإن أطول مكان هو تهيئة مجموعة من القمم التي تمت زيارتها ، والتي تستغرق دائمًا وقتًا يساوي عدد القمم في الرسم البياني. بدلاً من ذلك ، يمكنك استخدام جدول تجزئة أو تطبيق حيل أخرى.
جمع القمامة
كما ترى من الجدول ، هناك طريقتان acquire_ref : acquire_ref و release_ref .
داخل كرونوس ، يتم تخزين عداد مرجعي لكل حدث. بينما تقوم بعض الخدمات بمعالجة الحدث ، أو تحتفظ بالقدرة على إضافة أحداث جديدة تحدث بعد الحدث الحالي ، فإنها تخزن الرابط. عندما تختفي هذه الحاجة ، تستدعي الخدمة release_ref .
سيحذف Kronos الحدث عند استيفاء جميع الشروط:
- بلغ عدد الروابط صفر
- تم حذف جميع الأحداث التي تسبق ذلك بالفعل من الرسم البياني.
هذا النهج لا يحد من الاستعلامات المحتملة ، ولكنه يوفر الذاكرة داخل كرونوس.
التطبيقات
فكر في استخدام النظام باستخدام مثال تخزين القيمة الرئيسية مع المعاملات الموزعة.
افترض أن هناك عدة خوادم ، كل خادم مسؤول عن مجموعة من المفاتيح.
كل معاملة تقابل حدث في كرونوس. لكل مفتاح ، يجب أن يقوم الخادم بتخزين رقم آخر معاملة شارك فيها هذا المفتاح. ينشئ العميل حدثًا ويرسل رقمه إلى جميع الخوادم التي تتأثر مفاتيحها بهذه المعاملة. يحاول الخادم إنشاء تبعية في Kronos بين رقم المعاملة الحالية والحدث السابق الذي تم حفظه لهذا المفتاح. إذا لم تتمكن من إنشاء التبعية ، فسيتم الاعتراف بالمعاملة على أنها غير ناجحة (لاحظ أنه حتى الآن لا يوجد تفاعل مع البيانات حتى الآن).
في حالة اكتمال جميع عمليات التبعية الإضافية بنجاح - هذا يعني أن المعاملة ستتم ويمكن إجراؤها. تتعرف الخوادم على هذا من العميل وتبدأ في تنفيذ أجزاء من المعاملة.
لاحظ أن هذه المعاملات ستكون ACID :
- Atomicity : لن تتم جدولة المعاملة في Kronos ، أو سيتم جدولة تنفيذها على جميع العقد.
- الاتساق : تلقائيًا في مستودعات KV.
- العزلة : إذا تقاطع عمليتان وفقًا للبيانات ، فسيتم ربطهما بعلاقة سببية في كرونوس ، مما يعني أنه سيتم تنفيذ إحداها قبل الأخرى.
- المتانة : نظرًا لأن كرونوس مقاوم للسقوط ويفترض أن كل نسخة طبق الأصل من الخزنة مستقرة أيضًا ، فإن الشيء الوحيد الذي يجب إثباته هو استمرار بيانات المعاملات المعلقة. في الواقع ، إذا تم وضع علامة على المعاملة من قبل العميل على أنها ناجحة ، ولكن السجل لم يكتمل بعد على الخادم ، فمن السهل إثبات هذه الحقيقة ، حيث يتتبع الخادم أيضًا الأجزاء المكتملة من المعاملات.
الأداء
يمكن أن يكون تنفيذ تخزين KV هذا فعالاً بالفعل. تستشهد المقالة الأصلية بالبيانات التي تفيد بأن التنفيذ الموضح لتخزين KV أسرع 4 مرات من المعاملة القائمة على الأقفال.
علاوة على ذلك ، بالمقارنة مع MongoDB ، فإن النظام الموجود أعلى Kronos متأخر بنسبة 6 ٪ فقط ، على الرغم من حقيقة أن MongoDB لا يستخدم المعاملات الموزعة.
التحليل
ومع ذلك ، فإن تشغيل كرونوس له العديد من العيوب.
- أولاً ، هناك النفقات العامة للوصول إلى Kronos - سيتطلب كل طلب مكالمة واحدة على الأقل.
- ستكون كرونوس أيضًا نقطة فشل واحدة - لا يقدم مؤلفو المقالة طرقًا لتقسيم الرسم البياني للحدث.
- سيكون من الجيد إضافة عدد من الأساليب إلى النظام. على سبيل المثال ، في المثال باستخدام KV-storage ، سيكون من الجيد الحصول على رد اتصال لإعلام الخادم بحالة المعاملة - تمت إضافتها بنجاح إلى الرسم البياني مع جميع التبعيات الضرورية - أو ، على العكس من ذلك ، لا يمكن إتمام المعاملة.
ومع ذلك ، يسمح النظام الموصوف بالتحكم المرن في العلاقة السببية بين الأحداث ، مما يضمن الامتثال المتوقع للثوابت الضرورية.
الخلاصة
حول هذا ، نحن في مدرسة GoTo نعلم الطلاب وأطفال المدارس في اتجاه الأنظمة الموزعة.
وهناك خوارزميات وتطبيقات والبرمجة التطبيقية والمعلوماتية الحيوية وتحليل البيانات
تعال إلى مدرستنا الخريفية في 27 أكتوبر - 4 نوفمبر أو الشتاء في أوائل يناير.
وإذا لم تعد طالبًا أو تلميذًا - تعال للتدريس .