مرجع
آخر الزيارات

نوع بيانات مكرر خال من التعارض

1٬975 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: في الحوسبة الموزعة، يُعد نوع البيانات المكررة الخالي من التعارض يُعرف اختصارًا بـ CRDT، بنية بيانات يتم تكرارها عبر عدة حواسيب في شبكة حاسوب، وتتمتع بالخصائص التالية:. تجد هنا «المقارنة»، «أنواع نوع البيانات المكررة الخالي من التعارض» و«نوع بيانات مكرر خال من التعارض التتابعية» ضمن 6 أقسام.
المحتويات
  1. المقارنة
  2. أنواع نوع البيانات المكررة الخالي من التعارض
  3. نوع بيانات مكرر خال من التعارض التتابعية
  4. الاستخدام الصناعي
  5. الخلفية
  6. نوع البيانات المكررة الخالي من التعارض المعروفة

تعريفًا بالموضوع، في الحوسبة الموزعة، يُعد نوع البيانات المكررة الخالي من التعارض يُعرف اختصارًا بـ CRDT، بنية بيانات يتم تكرارها عبر عدة حواسيب في شبكة حاسوب، وتتمتع بالخصائص التالية:

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

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

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

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

المقارنة

في هذا الإطار، CRDTs المعتمدة على الحالة غالبًا ما تكون أبسط في التصميم والتنفيذ؛ فهي تتطلب فقط نوعًا من بروتوكول الهمس. وعيبها أن الحالة الكاملة لكل CRDT يجب أن تُرسل في النهاية إلى جميع النسخ الأخرى، مما قد يكون مكلفًا.

علاوةً على ذلك، من الناحية النظرية، البديلان متكافئان، حيث يمكن لكل منهما محاكاة الآخر.

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

ومع ذلك، توجد فروقات عملية بينهما.

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

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

أنواع نوع البيانات المكررة الخالي من التعارض

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

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

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

إضافةً إلى ذلك، هناك منهجان لـ نوع البيانات المكررة الخالي من التعارض، وكلاهما يمكن أن يوفّر اتساقًا نهائيًا قويًا: نوع البيانات المكررة الخالي من التعارض المعتمدة على الحالة وCRDTs المعتمدة على العمليات.

ومن جهة أخرى، تُعرف نوع البيانات المكررة الخالي من التعارض المعتمدة على العمليات (وتُسمى كذلك أنواع البيانات المكررة التبادلية أو CmRDTs) بأنها تُعرّف بدون دالة دمج. بدلًا من إرسال الحالات، يتم إرسال إجراءات التحديث مباشرة إلى النسخ الأخرى وتطبيقها. مثلًا، قد تقوم CRDT معتمدة على العمليات لعدد صحيح بإرسال العمليات (+10) أو (−20). يجب أن تكون تطبيقات العمليات عملية تبديلية وعملية تجميعية. ومع ذلك، بدلًا من اشتراط تساوي القوى في العمليات، تتطلب هذه الطريقة افتراضات أقوى على بنية الاتصالات — إذ يجب تسليم جميع العمليات إلى النسخ الأخرى بدون تكرار.

نوع البيانات المكررة الخالي من التعارض المعتمدة على الحالة

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

من جهة ثانية، ولضمان التقارب النهائي، يجب أن تحقق هذه الدوال الخصائص التالية:

وفي السياق ذاته، نوع البيانات المكررة الخالي من التعارض المعتمدة على العمليات

وعلى صعيد آخر، تُعد نوع البيانات المكررة الخالي من التعارض المعتمدة على العمليات الخالصة نسخة من نوع البيانات المكررة الخالي من التعارض المعتمدة على العمليات تُقلل من حجم البيانات الوصفية.

نوع بيانات مكرر خال من التعارض التتابعية

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

ومن ناحية أخرى، نوع البيانات التتابعية الصناعية (بما فيها المفتوحة المصدر) أثبتت أنها تتفوق على نظيراتها الأكاديمية بفضل التحسينات ومنهجيات الاختبار الواقعية.

وفي السياق ذاته، CRATE هو محرر تعاوني لا مركزي مبني على LSEQSplit (امتداد لـ LSEQ) ويعمل على شبكة من المتصفحات باستخدام ويب آر تي سي.

من جانب آخر، تم اقتراح LogootSplit كامتداد لـ Logoot لتقليل البيانات الوصفية في نوع البيانات المكررة الخالي من التعارض التتابعية.

من جانب آخر، بعض أنواع نوع البيانات المكررة الخالي من التعارض التتابعية المعروفة: Treedoc، RGA، Woot، Logoot، LSEQ.

علاوةً على ذلك، MUTE هو محرر تعاوني عبر الويب يعتمد على خوارزمية LogootSplit.

وعلى صعيد آخر، من أبرز الأمثلة: Yjs CRDT، والذي يُعتبر رائدًا في استخدام قائمة عادية بدلاً من شجرة.

الاستخدام الصناعي

ومن ناحية أخرى، قامت ساوند كلاود بفتح مصدر Roshi، وهو CRDT من نوع LWW-element-set يُستعمل لبث SoundCloud، ومُنفذ فوق Redis.

وفي السياق ذاته، تخزن شركة بيت 365 مئات الميجابايتات من البيانات باستخدام تنفيذ OR-Set في Riak.

المراجع

علاوةً على ذلك، ريديس هو قاعدة بيانات موزعة وذات توافرية عالية وقابلة للتوسيع في الذاكرة، مع ميزة "قاعدة بيانات مدعومة بـ CRDT".

كذلك، يستعمل إطار العمل فوينكس، المكتوب بلغة إليكسير، نوع البيانات المكررة الخالي من التعارض لدعم مشاركة المعلومات في الزمن الحقيقي بين العقد في الإصدار 1.2.

علاوةً على ذلك، نيمبوس نوت هو تطبيق لتدوين الملاحظات بشكل تعاوني يستعمل Yjs CRDT من أجل التحرير التعاوني.

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

وفي هذا السياق، قدّمت نوفل (شركة) CRDT قائم على الحالة مع تكرار دلائل "متساهل التناسق" (NetWare Directory Services)، والموجود في NetWare 4.0 منذ عام 1995. وقدمت النسخة اللاحقة eDirectory تحسينات على عملية التكرار.

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

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

ومن ناحية أخرى، رياك هو متجر بيانات NoSQL موزّع قائم على نوع البيانات المكررة الخالي من التعارض. تستعمل لعبة ليغ أوف ليجيندز تنفيذ رياك لنوع البيانات لنظام المحادثة داخل اللعبة، والذي يتعامل مع 7.5 ملايين مستعمل متزامن و11,000 رسالة في الثانية.

وفي السياق ذاته، تستعمل فيسبوك كذلك نوع البيانات المكررة الخالي من التعارض في نظام متتبع الرحلات الجوية الخاص بإدارة رسم بياني فيسبوك داخليًا.

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

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

الخلفية

وفي هذا السياق، كمثال، تُعتبر إشارة حدث أحادية الاتجاه من نوع نوع البيانات المنطقية البسيط: بت واحدة بقيمة true أو false. تعني القيمة true أن حدثًا معينًا قد وقع مرة واحدة على الأقل، أما false فتعني أن الحدث لم يقع. وبمجرد أن تُضبط القيمة على true، لا يمكن تغييرها مرة أخرى إلى false (فوقوع الحدث لا يمكن "إلغاء" وقوعه). وطريقة الحل هي "تغليب true": فعند دمج نسخة يكون فيها العلم true (أي أن الحدث لوحظ)، ونسخة أخرى يكون فيها false (أي لم يُلاحظ الحدث)، تكون النتيجة النهائية هي true — أي أن الحدث قد تمّت ملاحظته.

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

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

نوع البيانات المكررة الخالي من التعارض المعروفة

مجموعة عناصر LWW (الأحدث يفوز)

مجموعة 2P (المجموعة ذات المرحلتين)

إضافةً إلى ذلك، إحدى الاستراتيجيات الشائعة في تطوير CRDT هي دمج عدة نوع البيانات المكررة الخالي من التعارض لإنشاء نوع بيانات أكثر تعقيدًا. في هذه الحالة، تم دمج عدادين من نوع G (يقبل الزيادة فقط) لإنشاء نوع بيانات يدعم عمليتي الزيادة والنقص. العداد "P" يحصي الزيادات، والعداد "N" يحصي النقصات. قيمة عداد PN هي الفرق بين قيمة العداد P وقيمة العداد N. تتم عملية الدمج بأخذ الحد الأقصى لكل عنصر في العدادات المتماثلة. لاحظ أن الحالة الداخلية لـ CRDT يجب أن تزداد بشكل أحادي الاتجاه، حتى إن كانت القيمة الخارجية التي تُرجعها دالة استعلام قد تعود لقيم سابقة.

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

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

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

وعلى صعيد آخر، يُعد هذا CRDT المعتمد على الحالة تنفيذًا لعداد في عنقود من n عقد. تُخصص لكل عقدة في العنقود معرف من 0 إلى n - 1، ويتم استرجاعه عبر نداء معرفي. وبالتالي، تُخصص لكل عقدة خانة خاصة بها في المصفوفة P، والتي تزيدها محليًا. تُنقل التحديثات في الخلفية، وتُدمج بأخذ max لكل عنصر في P. تُدرج دالة المقارنة لتوضيح ترتيب جزئي على الحالات. إن دالة الدمج تبادلية وتجميعية ومتساوية القوى. وتزيد دالة التحديث الحالة الداخلية بشكل رتيب بحسب دالة المقارنة. وبالتالي، فإن هذا CRDT معرّف بشكل صحيح ويوفر اتساقًا نهائيًا قويًا. أما النظير المعتمد على العمليات، فيقوم بإرسال عمليات الزيادة بمجرد استقبالها.

مجموعة OR (الإزالة المرصودة)

عداد PN (العداد الموجب-السالب)

مجموعة G (مجموعة تزايدية فقط)

ومن ناحية أخرى، يتم دمج مجموعتين من نوع G لإنشاء مجموعة 2P، حيث تضاف مجموعة حذف (تُعرف بمجموعة "شواهد القبور"). يمكن إضافة العناصر وحذفها، لكن لا يمكن إعادة إضافتها بعد حذفها. أي أن العنصر الذي يدخل مجموعة الحذف لن يتم اعتباره موجودًا في المجموعة مجددًا. تستعمل مجموعة 2P سياسة "الحذف يتغلب على الإضافة".

العداد المتزايد (G-Counter)

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.