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

1. مقدمة

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

في مقال سابق ، نظرنا بالفعل في نهج لحل مثل هذه المشاكل - التحول التشغيلي ، وسوف يصف أيضًا طريقة مشابهة جدًا لها مزايا وعيوب (على سبيل المثال ، لم يتم اختراع CRDT لـ JSON بعد. التحديث : بفضل msvn للرابط ، هنا هنا مشروع من مؤلفي مقال بحثي حول تنفيذ JSON في CRDT)

2. اتساق قوي في نهاية المطاف

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

ينتقد السؤال الذي طرحه مؤلفو إحدى المقالات التعريف الحالي للاتساق النهائي: وفقًا لذلك ، إذا كان نظامك يجيب دائمًا على "42" لجميع الطلبات ، فإن كل شيء على ما يرام ، فهو في النهاية متسق.

دون انتهاك صحة هذه المقالة ، سأستخدم المصطلحات التالية ، بعد مؤلفي المقالات الأصلية (يرجى ملاحظة ، هذه ليست تعريفات صارمة ، هذه اختلافات):

تناسق قوي (SC): يتم ترتيب جميع عمليات الكتابة بدقة ، ويعيد طلب القراءة على أي نسخة متماثلة نفس النتيجة المسجلة الأخيرة. هناك حاجة إلى إجماع في الوقت الفعلي لحل التعارضات (مع العواقب الناتجة) ، يمكن أن تصمد أمام انخفاض إلى عقد n / 2 - 1.
الاتساق النهائي (EC): قم بتحديث البيانات محليًا ، وأرسل التحديث أيضًا. القراءة على النسخ المتماثلة المختلفة يمكن أن ترجع بيانات قديمة. في حالة حدوث تعارضات ، إما أن نتراجع ، أو نقرر بطريقة ما ما يجب فعله. T.O. لا يزال هناك حاجة إلى توافق في الآراء ، ولكن لم يعد في الوقت الحقيقي .
تناسق نهائي قوي (SEC): EC + لحل التعارضات ، تحتوي النسخ المتماثلة على خوارزمية محددة مسبقًا. T.O. ليس هناك حاجة إلى توافق في الآراء ؛ يمكن أن تصمد أمام انخفاض إلى عقد n - 1.

لاحظ أن SEC (كما كانت) تحل مشكلة نظرية CAP: جميع الخصائص الثلاثة راضية.

لذا ، نحن مستعدون للتبرع بـ SC ونريد أن يكون لدينا مجموعة معينة من أنواع البيانات الأساسية لنظامنا الموزع المحتمل أن يكون غير مستقر والذي سيحل تلقائيًا تعارضات الكتابة لنا (لا يلزم تفاعل المستخدم أو طلب بعض الحكم)

3. المهام حول الإعجابات والضربات

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

عدد نتائج Google.com:

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

إبداء إعجاب المستخدم:

المهمة مشابهة جدًا للمهمة السابقة ، فقط الآن تحتاج إلى حساب النتائج الفريدة.

4. المصطلحات

لفهم أكثر اكتمالاً للمقالة ، تحتاج إلى معرفة المصطلحات التالية:

المثالية
يقول أن تطبيق العملية عدة مرات لا يغير النتيجة.
أمثلة - تشغيل أو إضافة باستخدام صفر: $f (x) = x + 0$
تبادلية
$f (x، y) = f (y، x)$
أمر جزئي
الانعكاسية + الانتقالية + عدم التماثل
نصف شعرية
تم ترتيبه جزئيًا مع وجه علوي (سفلي) دقيق
ناقل الإصدار
يساوي متجه البعد عدد العقد ، وكل عقدة ، عند حدوث حدث معين ، تزيد قيمتها في المتجه. أثناء المزامنة ، يتم إرسال البيانات باستخدام هذا المتجه وهذا يقدم علاقة ترتيب ، والتي تتيح لك تحديد النسخة المتماثلة التي تحتوي على بيانات قديمة / جديدة.

5. نماذج المزامنة

على أساس الدولة:

يُطلق عليه أيضًا التزامن السلبي ، ويشكل نوع البيانات المتقاربة المتقاربة - CvRDT.
يتم استخدامه في أنظمة الملفات مثل NFS و AFS و Coda و KV-storeages Riak و Dynamo
في هذه الحالة ، حالات تبادل النسخ المتماثلة مباشرة ، تقوم النسخة المتماثلة المستلمة بدمج الحالة المستلمة مع حالتها الحالية.

لإجراء تقارب للنسخ المتماثلة باستخدام هذه المزامنة ، من الضروري أن:

شكلت البيانات نصف شبكة
أنتجت دالة الدمج حدًا أعلى دقيقًا
شكلت النسخ المتماثلة رسم بياني متصل.

مثال:

مجموعة البيانات: الأعداد الطبيعية $\ mathbb {N}$
الحد الأدنى للعنصر: $- \ infty$
$inline$

تعطينا هذه المتطلبات وظيفة دمج تبادلية وعاطفة تنمو بشكل رتيب على مجموعة بيانات معينة:

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

القائم على العملية:

وتسمى أيضًا التزامن النشط ، وهي تشكل نوع البيانات التبادلية المنسوخة - CmRDT.
تستخدم في الأنظمة التعاونية مثل Bayou و Rover و IceCube و Telex.

في هذه الحالة ، تبادل النسخ المتماثلة عمليات تحديث حالة. عند تحديث البيانات ، فإن النسخة المتماثلة الأصلية:

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

لتنفيذ تقارب النسخ المتماثلة ، يجب استيفاء الشروط التالية:

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

القائم على دلتا:

بالنظر إلى الحالة / العملية ، من السهل ملاحظة أنه إذا قام أحد التحديثات بتغيير جزء فقط من الحالة ، فلن يكون من المنطقي إرسال الحالة بأكملها ، وإذا كان عدد كبير من التغييرات يؤثر على حالة واحدة (على سبيل المثال ، عداد) ، فيمكنك حينئذٍ إرسال تغيير واحد ، وليس كل العمليات التغييرات.

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

طريقة التحسين التالية هي ضغط السجل التشغيلي ، إذا كان التأخير مسموحًا به.

القائم على عملية نقية:

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

مناهج الاستخدام القياسي:

إذا كان سيتم إرسال التحديثات على الفور في النظام ، فسيكون اختيار الحالة على مستوى الدولة خيارًا سيئًا ، نظرًا لأن إرسال الحالة بأكملها يعد أكثر تكلفة من مجرد عملية تحديث. يعمل نظام Delta بشكل أفضل ، ولكن في هذه الحالة بالذات ، سيكون الفرق مع الدولة محدودًا.
إذا كنت بحاجة إلى مزامنة النسخة المتماثلة بعد الفشل ، فإن الخيار القائم على الحالة والدلتا هو الخيار الأمثل. إذا كان عليك استخدام op-based ، فإن الخيارات هي:

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

العلاقة بين Op-Based و State-Based:

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

6. CRDT

6.1 عداد

عدد صحيح يدعم عمليتين: inc و dec. كمثال ، ضع في اعتبارك عمليات التنفيذ المحتملة لعمليات المزامنة القائمة على الدولة والحالة:

عداد قائم على المرجع:

من الواضح أنه يكفي فقط إرسال التحديثات. مثال عن المؤتمر الوطني العراقي:

function generator() { return function (counter) { counter += 1 } }

عداد على أساس الدولة:

لم يعد التنفيذ واضحًا جدًا ، نظرًا لأنه من غير الواضح كيف يجب أن تبدو وظيفة الدمج.

فكر في الخيارات التالية:

عداد متزايد رتيب (عداد الزيادة فقط ، عداد G):

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

ستأخذ وظيفة الدمج الحد الأقصى في المواضع المقابلة ، والقيمة النهائية هي مجموع جميع عناصر المتجه

$\ start {align} inc () &: V [id ()] = V [id ()] + 1 \\ value () &: \ sum_ {i = 0} ^ {n} V [i] \\ دمج (C_1، C_2) &: i \ in [1..n] \ النتيجة [i] = max (C_1.V [i]، C_2.V [i]) \ end {align}$

يمكنك أيضًا استخدام G-Set (انظر أدناه)

التطبيق:

عد النقرات / الزيارات (كذا!)

عداد مع دعم تناقص (عداد PN)

نبدأ جهازي عداد - واحد لعمليات الزيادة ، والثاني - للإنقاص

التطبيق:

عدد المستخدمين الذين قاموا بتسجيل الدخول في شبكة p2p ، مثل Skype

عداد غير سلبي

لا يوجد تطبيق بسيط حتى الآن. اقترح أفكارك في التعليقات ، وناقشها.

6.2 التسجيل

خلية ذاكرة ذات عمليتين - تعيين (كتابة) وقيمة (قراءة).
المشكلة هي أن التعيين ليس تبادليًا. هناك طريقتان لحل هذه المشكلة:

سجل Last-Write-Wins (LWW-Register):

نقوم بإدخال الأمر الكامل من خلال إنشاء معرف فريد لكل عملية (الطابع الزمني ، على سبيل المثال).

مثال على التزامن هو تبادل أزواج (قيمة ، معرف):

التطبيق:

أعمدة في كاساندرا
NFS - ملف كليا أو جزئيا

سجل بقيم متعددة (تسجيل متعدد القيم ، تسجيل MV):

يشبه هذا النهج عداد G - نقوم بتخزين المجموعة (القيمة ، متجه الإصدار). تسجيل القيمة - كل القيم ، عند الدمج - LWW بشكل منفصل لكل قيمة في المتجه.

التطبيق:

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

شرح الخلل في أمازون:

6.3 الكثير

المجموعة هي النوع الأساسي لبناء الحاويات والخرائط والرسوم البيانية وتدعم العمليات - إضافة و RMV ، وهي ليست تبادلية.

ضع في اعتبارك التنفيذ الساذج للمجموعة القائمة على المرجع ، والتي يتم فيها تنفيذ إضافة و rmv عند وصولها (تأتي الإضافة إلى نسختين متماثلتين و 2 في نفس الوقت ، ثم يذهب rmv إلى 1)

كما ترى ، تفرقت النسخ المتماثلة في النهاية. فكر في الخيارات المختلفة لإنشاء مجموعات خالية من الصراع:

مجموعة النمو (G-Set):

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

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

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

$\ start {align} lookup (e) &: e \ in A \ land e \ notin R \\ add (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ merge (S_1، S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {محاذاة}$

مجموعة عنصر LWW:

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

نحصل على مجموعتين - إضافة مجموعة وإزالة مجموعة ، عندما يتم استدعاء add () ، إضافة (element ، unique_id ()) ، عند التحقق مما إذا كان هناك عنصر في المجموعة - انظر حيث يكون الطابع الزمني أكبر - في إزالة المجموعة أو في المجموعة الإضافية

مجموعة PN:

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

لاحظ التأثير المثير للاهتمام - في النسخة المتماثلة الثالثة ، لا تؤدي إضافة عنصر إلى ظهوره.

لاحظ ، إزالة مجموعة ، مجموعة OR ، مجموعة Add-Win:

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

مجموعة إزالة الفوز:

على غرار السابق ، ولكن في نفس الوقت يضيف / rmv rmv انتصارات.

6.4 الرسم البياني

تم بناء هذا النوع على أساس الكثير. تكمن المشكلة في هذا: إذا كانت هناك عمليات متزامنة addEdge (u، v) و removeVertex (u) - فماذا أفعل؟ الخيارات التالية ممكنة:

إزالة RemoveVertex ، يتم حذف جميع حواف هذا الرأس
أولوية AddEdge ، استعادة القمم المحذوفة
نقوم بتأخير تنفيذ removeVertex حتى يتم تنفيذ كل addEdge المتزامن.

الخيار الأسهل هو الأول ، بالنسبة لتطبيقه (2P2P-Graph) ، يكفي الحصول على اثنين من 2P-Set ، أحدهما للقمم ، والثاني للحواف

6.5 الخريطة

خريطة الحرفيين:

مشكلتان لحلهما:

ماذا تفعل مع عمليات البيع المتزامن؟ قياسا على العدادات ، يمكنك اختيار دلالات LWW أو MV
ماذا تفعل مع وضع / rmv في وقت واحد؟ عن طريق القياس مع المجموعات ، يمكنك إما وضع انتصارات ، أو انتصارات rmv ، أو آخر دلالات الانتصارات.

رسم خرائط CRDT (خريطة CRDT):

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

إزالة الخريطة كإعادة تكرارية

تقوم عملية الإزالة بإعادة تعيين قيمة النوع إلى حالة بدء معينة. على سبيل المثال ، بالنسبة للعداد ، هذه قيمة صفرية.

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

إزالة الخريطة يفوز

عملية rmv لها الأسبقية.

مثال: في لعبة على الإنترنت ، يمتلك لاعب Alice 10 عملات معدنية ومطرقة. ثم يحدث حدثان في وقت واحد: في النسخة المتماثلة A ، أنتجت مسمارًا ، وفي النسخة المتماثلة B ، يتم حذف شخصيتها مع إزالة جميع الكائنات:

لاحظ أنه عند استخدام الإزالة كعودة متكررة ، سيظل الظفر في النهاية ، وهي ليست الحالة الصحيحة عند إزالة الشخصية.

تحديث - يفوز الخريطة

التحديثات لها الأسبقية ، أو بالأحرى ، إلغاء العمليات السابقة لحذف rmv المتزامن.

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

هناك تأثير واحد مثير للاهتمام عند العمل مع مثل هذا التطبيق - لنفترض أن لدينا نسختين متماثلتين ، A و B ، وأنهم يخزنون المجموعة بواسطة بعض المفاتيح الرئيسية ثم ، إذا حذف A قيمة المفتاح k ، وحذف B جميع عناصر المجموعة ، فستترك النسخ المتماثلة في النهاية مجموعة فارغة مع المفتاح k.

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

قائمة

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

7. رياك

كمثال ، ضع في اعتبارك CRDT في رياك:

العداد: عداد PN
تعيين: أو - تعيين
الخريطة: تحديث يفوز خريطة CRDTs
(منطقي) العلم: أو - تعيين حيث عنصر واحد كحد أقصى
التسجيل: أزواج (القيمة والطابع الزمني)

8. من يستخدم CRDT

يحتوي قسم ويكي على أمثلة جيدة.

CRDT: أنواع البيانات المنسوخة الخالية من التعارضات