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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## نوع البيانات المكررة الخالي من التعارض المعروفة
### العداد المتزايد (G-Counter)

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

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

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

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

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

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

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

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

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

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

بعض أنواع نوع البيانات المكررة الخالي من التعارض التتابعية المعروفة: Treedoc، RGA، Woot، Logoot، LSEQ.
CRATE هو محرر تعاوني لا مركزي مبني على LSEQSplit (امتداد لـ LSEQ) ويعمل على شبكة من المتصفحات باستخدام ويب آر تي سي.
تم اقتراح LogootSplit كامتداد لـ Logoot لتقليل البيانات الوصفية في نوع البيانات المكررة الخالي من التعارض التتابعية.
MUTE هو محرر تعاوني عبر الويب يعتمد على خوارزمية LogootSplit.

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

## الاستخدام الصناعي
* الإطار السائل هو إطار عمل تعاوني مفتوح المصدر أنشأته مايكروسوفت، يوفّر تنفيذات مرجعية للخوادم وحزم تطوير برمجيات للعميل لإنشاء تطبيقات ويب حديثة في الزمن الحقيقي باستخدام نوع البيانات المكررة الخالي من التعارض.
* نيمبوس نوت هو تطبيق لتدوين الملاحظات بشكل تعاوني يستخدم Yjs CRDT من أجل التحرير التعاوني.
* ريديس هو قاعدة بيانات موزعة وذات توافرية عالية وقابلة للتوسيع في الذاكرة، مع ميزة "قاعدة بيانات مدعومة بـ CRDT".
* قامت ساوند كلاود بفتح مصدر Roshi، وهو CRDT من نوع LWW-element-set يُستخدم لبث SoundCloud، ومُنفذ فوق Redis.
* رياك هو متجر بيانات NoSQL موزّع قائم على نوع البيانات المكررة الخالي من التعارض. تستخدم لعبة *[[ليغ أوف ليجيندز]]* تنفيذ رياك لنوع البيانات لنظام المحادثة داخل اللعبة، والذي يتعامل مع 7.5 ملايين مستخدم متزامن و11,000 رسالة في الثانية.
* تخزن شركة بيت 365 مئات الميجابايتات من البيانات باستخدام تنفيذ OR-Set في Riak.
* تستخدم توم توم نوع البيانات المكررة الخالي من التعارض لمزامنة بيانات الملاحة بين أجهزة المستخدم.
* يستخدم إطار العمل فوينكس، المكتوب بلغة إليكسير، نوع البيانات المكررة الخالي من التعارض لدعم مشاركة المعلومات في الزمن الحقيقي بين العقد في الإصدار 1.2.
* تستخدم فيسبوك نوع البيانات المكررة الخالي من التعارض في قاعدة بيانات أبولو ذات الكمون المنخفض التي تحقق "التناسق على نطاق واسع".
* تستخدم فيسبوك أيضًا نوع البيانات المكررة الخالي من التعارض في نظام متتبع الرحلات الجوية الخاص بإدارة رسم بياني فيسبوك داخليًا.
* يستخدم تيليتايب لمحرر النصوص أتوم نوع البيانات المكررة الخالي من التعارض للسماح للمطورين بمشاركة مساحة العمل مع أعضاء الفريق والتعاون في تحرير الشيفرة البرمجية في الزمن الحقيقي.
* تطبّق أبل نوع البيانات المكررة الخالي من التعارض في تطبيق "الملاحظات" لمزامنة التعديلات غير المتصلة بالإنترنت بين الأجهزة المتعددة.
* قدّمت نوفل (شركة) CRDT قائم على الحالة مع تكرار دلائل "متساهل التناسق" (NetWare Directory Services)، والموجود في NetWare 4.0 منذ عام 1995. وقدمت النسخة اللاحقة eDirectory تحسينات على عملية التكرار.

## المراجع

## روابط خارجية
* مجموعة من الموارد والأبحاث حول نوع البيانات المكررة الخالي من التعارض
* "الاتساق القوي النهائي وأنواع البيانات المكررة الخالية من التعارضات" (محاضرة حول نوع البيانات المكررة الخالي من التعارض) من تقديم مارك شابيرو
* قراءات في أنواع البيانات المكررة الخالية من التعارضات بقلم كريستوفر ميكيلجون
* نظرية CAP وCRDTs: بعد 12 سنة، كيف تغيرت القواعد بقلم إريك بروير

تصنيف:نظم حاسوب متحملة للأخطاء