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

1. مقدمة

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

الإصدار القديم من محرر مستندات Google

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

في كثير من الأحيان ، لا يعمل هذا النهج بشكل جيد للغاية. على سبيل المثال ، افترض أن Petya و Vasya والخادم يبدأان بمستند متزامن مع النص " الثعلب البني السريع ".

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

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

نسخة جديدة من مستندات جوجل

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

حسنًا ، نحتاج الآن إلى فهم وقت تطبيق التغييرات - نحتاج إلى بروتوكول تعاون .

في محرّر مستندات Google ، تتلخص جميع تعديلات المستندات في ثلاث عمليات مختلفة:

إدراج نص
حذف النص
تطبيق الأنماط على النص

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

ملاحظة صغيرة: كان أول منتج من منتجات Google (العامة) بدعم OT هو ، على ما يبدو ، Google Wave. أيد مجموعة واسعة من العمليات.

مثال

فلتبدأ بيتيا وفاسيا من نفس حالة "هبر 2017".
يغير بيتيا 2017 إلى 2018 ، وهذا يخلق عمليتين:

في نفس الوقت ، يغير Vasya النص إلى "HELLO HABR 2017":

يتلقى Vasya عملية Petin لحذفها ، إذا قام بتطبيقها للتو ، فسيتم الحصول على النص الخاطئ (كان يجب حذف الرقم 7):

لتجنب ذلك ، يجب على Vasya تحويل عملية Petin وفقًا للتغيرات المحلية الحالية (بمعنى آخر ، العمليات حساسة للسياق):

\ {Delete \ \ @ 8 \} \ rightarrow \ {Delete \ \ @ 15 \}

$\ {Delete \ \ @ 8 \} \ rightarrow \ {Delete \ \ @ 15 \}$

عند التحدث بشكل أكثر رسمية ، ضع في اعتبارك هذا المثال:

ثم:

$O1 ’(O2 (X)) = O2’ (O1 (X))$

فويلا! تسمى الخوارزمية الموصوفة التحول التشغيلي.

2. التحول التشغيلي

نموذج الاتساق

لضمان الاتساق ، تم تطوير العديد من نماذج الاتساق ، والنظر في واحد منهم - CCI.

يوفر نموذج CCI ثلاث خصائص:

التقارب: يجب أن تكون جميع النسخ المتماثلة لمستند مشترك متطابقة بعد اكتمال جميع العمليات:

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

ضع في اعتبارك مثالاً حيث فشلت هذه الخاصية:

يبدأ كلا العملاء بنفس النسخ المتماثلة ، ثم يقوم كلاهما بإجراء التغييرات. بالنسبة ل Petya ، فإن نيته في العملية هي إدراج "12" في الفهرس الأول ، وبالنسبة لـ Vasya ، قم بحذف الأحرف ذات المؤشرين 2 و 3. بعد التزامن مع Petya Vasino ، تم انتهاك النية ومع Vasya Petino. لاحظ أيضًا أن النسخ المتماثلة قد تباعدت ، ولكن هذا ليس شرطًا للخاصية المعنية. تم اقتراح النسخة النهائية الصحيحة لتعريف القارئ على أنه تمرين صغير.
الحفاظ على السببية: يجب تنفيذ العمليات بترتيب سببي (بناءً على العلاقة التي حدثت قبل ).

ضع في اعتبارك مثالاً حيث فشلت هذه الخاصية:

كما ترون ، أرسل Petya Vasya والوكيل سميث تغييره للمستند ، تلقى Vasya أولاً وحذف الحرف الأخير. نظرًا لتأخر الشبكة ، يتلقى سميث أول عملية لـ Vasin لحذف حرف غير موجود بعد.

لا تستطيع OT التأكد من استيفاء خاصية الحفاظ على السببية ؛ وبالتالي ، يتم استخدام الخوارزميات مثل ساعة المتجه لهذه الأغراض.

تصميم OT

إحدى إستراتيجيات التصميم لنظام OT هي التقسيم إلى ثلاثة أجزاء:

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

وظائف التحويل

يمكن تقسيم وظائف التحويل إلى نوعين:

الدمج / التحويل إلى الأمام: تحويل العملية $O_a$ قبل الجراحة $O_b$ بحيث أثر $O_b$ (مثل إدخالين)
الإقصاء / التحول العكسي: تحويل العملية $O_a$ قبل الجراحة $O_b$ بحيث أثر $O_b$ مستبعد (مثل إدراج بعد الحذف)

مثال لعمليات الإدراج / الحذف الرمزية (i - insert، d - delete):

Tii(Ins[p1, c1], Ins[p2, c2]) { if (p1 < p2) || ((p1 == p2) && (order() == -1)) // order() –   return Ins[p1, c1]; // Tii(Ins[3, 'a'], Ins[4, 'b']) = Ins[3, 'a'] else return Ins[p1 + 1, c1]; // Tii(Ins[3, 'a'], Ins[1, 'b']) = Ins[4, 'a'] } Tid(Ins[p1, c1], Del[p2]) { if (p1 <= p2) return Ins[p1, c1]; // Tid(Ins[3, 'a'], Del[4]) = Ins[3, 'a'] else return Ins[p1 – 1, c1]; // Tid(Ins[3, 'a'], Del[1]) = Ins[2, 'a'] } Tdi(Del[p1], Ins[p2, c1]) { //   ,    } Tdd(Del[p1], Del[p2]) { if (p1 < p2) return Del[p1]; // Tdd(Del[3], Del[4]) = Del[3] else if (p1 > p2) return Del[p1 – 1]; // Tdd(Del[3], Del[1]) = Del[2] else return Id; // Id –   }

3. بروتوكول التفاعل في مستندات جوجل

دعونا نلقي نظرة على كيفية عمل بروتوكول التفاعل في محرر مستندات Google بمزيد من التفصيل. لنفترض أن لدينا خادمًا ، Petya و Vasya ، ولديهما نسخة متزامنة من مستند فارغ.

يتذكر كل عميل المعلومات التالية:

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

يتذكر الخادم بدوره:

قائمة بجميع التغييرات المستلمة ولكن غير المعالجة (المعالجة المعلقة).
سجل كامل لجميع التغييرات التي تمت معالجتها (سجل المراجعة).
حالة المستند في وقت آخر تغيير تمت معالجته.

لذا ، يبدأ بيتيا بكلمة "مرحبًا" في بداية المستند:

أضاف العميل أولاً هذا التغيير إلى قائمة الانتظار ، ثم أرسله إلى الخادم ونقل التغييرات إلى القائمة المرسلة.

تستمر بتيا في الكتابة وقد أضافت بالفعل كلمة "حبر". في نفس الوقت ، كتب Vasya "!" في مستنده الفارغ (لم يتلق تغييرات بيتينا بعد).

بيتينو

\ {Insert \ \ 'Habr'، \ @ 5 \}

$\ {Insert \ \ 'Habr'، \ @ 5 \}$ تمت إضافته إلى القائمة المعلقة ، ولكن لم يتم إرساله بعد ، لأننا لا نرسل أكثر من تغيير واحد في كل مرة ، ولم يتم تأكيد التغيير السابق بعد . نلاحظ أيضًا أن الخادم حفظ تغييرات بيتيت في سجل المراجعة الخاص به. ثم يرسلهم الخادم إلى Vasya ويرسل تأكيدًا إلى Petya (تمت معالجة تغييرات Petina الأولى بنجاح)

يتلقى عميل Vasya تغييرات Petina من الخادم ويطبق OT فيما يتعلق بإرسالها المعلق إلى الخادم

\ {Insert \ \ '!'، \ @ 0 \}

$\ {Insert \ \ '!'، \ @ 0 \}$ . والنتيجة هي تغيير في فهرس الإدراج من 0 إلى 5. ونلاحظ أيضًا أن كلا العميلين قاما بتحديث رقم آخر مراجعة متزامنة مع الخادم إلى 1. وأخيرًا ، يزيل عميل Petin التغيير المقابل من قائمة التأكيد المعلق من الخادم.

ثم يرسل بيتيا وفاسيا تغييراتهما إلى الخادم.

يتلقى الخادم تغييرات Petina قبل (بخصوص الأمر الذي تم إدخاله) Vasinykh ، لذا يقوم بمعالجتها أولاً ، ويرسل تأكيدًا إلى Petya. يرسلهم أيضًا إلى Vasya ، ويحولهم عميله بخصوص التغييرات التي لم يتم تأكيدها بعد

\ {Insert \ \ '!'، \ @ 5 \}

$\ {Insert \ \ '!'، \ @ 5 \}$ .

ثم تأتي النقطة المهمة. يبدأ الخادم في معالجة تغييرات Vasya ، تلك التي ، وفقًا لـ Vasya ، لديها مراجعة رقم 2. لكن الخادم قد قام بالفعل بتنفيذ التغييرات على الرقم 2 ، لذلك يطبق التحويل على جميع التغييرات التي لم يعرفها عميل Vasya بعد (في هذه الحالة -

\ {Insert \ \ 'Habr'، \ @ 5 \}

$\ {Insert \ \ 'Habr'، \ @ 5 \}$ ) ، ويحفظ النتيجة بالرقم 3.

كما نرى ، تمت زيادة الفهرس في تغيير Vasin بمقدار 5 لاستيعاب نص Petin.

اكتملت العملية لـ Petya ، وتحتاج Vasya إلى تلقي تغيير جديد من الخادم وإرسال تأكيد.

4. Etherpad

دعونا نلقي نظرة على تطبيق آخر مشابه حيث يتم استخدام OT - مشروع مفتوح المصدر للمحرر عبر الإنترنت مع التحرير المشترك etherpad.org

في Etherpad ، تختلف وظائف التحويل قليلاً - يتم إرسال التغييرات إلى الخادم كمجموعة من التغييرات (مجموعة التغييرات) ، ويتم تعريفها على أنها

، ، ، ،

$(\ ell_1 \ rightarrow \ ell_2) [c_1 ، c_2 ، c_3 ، ...] ،$

أين

$\ ell_1$ : طول الوثيقة قبل التحرير.
$\ ell_2$ : طول الوثيقة بعد التحرير.
c1،c2،c3،... - وصف الوثيقة بعد التحرير. إذا ci هو رقم (أو نطاق من الأرقام) ، فهذه هي مؤشرات أحرف المستند الأصلي التي ستبقى بعد التحرير (محتفظ بها) ، وإذا ci - حرف (أو سلسلة) ، فهذا هو الإدراج.

مثال:
1. $ inline $ `` "+ \ (0 \ rightarrow 6) [` `Hello '' =` `Hello" $ inline $
2. $ inline $ `` Beaver "+ (4 \ rightarrow 4) [` `Ha"، \ 2-3] = `` Habr '$ inline $

كما تفهم بالفعل ، يتم تشكيل المستند النهائي كتسلسل لمثل هذه التغييرات المطبقة من أجل مستند فارغ.

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

$A = (n \ rightarrow n_a) [\ cdots] \\ B = (n \ rightarrow n_b) [\ cdots]،$

ثم

$A (B)$ مستحيل ، لأن

$A$ يتطلب طول المستند

$n$ وبعد ذلك

$B$ سيكون طويلا

$n_b$ .
لحل هذه الحالة ، يستخدم Etherpad آلية دمج : وهي دالة يُشار إليها بـ

$م (أ ، ب)$ ، يقبل تغييرين على الإدخال على نفس حالة المستند (المشار إليها فيما يلي باسم

$X$ ) ويقوم بتغيير جديد.

مطلوب ذلك

$م (أ ، ب) = م (ب ، أ)$

لاحظ أنه بالنسبة للعميل مع التغييرات

$A$ الذي حصل على التغيير

$B$ لا معنى للحساب

$م (أ ، ب)$ منذ ذلك الحين

$م (أ ، ب)$ ينطبق على

$X$ و

$A$ الوضع الحالي

$A (X)$ . في الواقع ، نحن بحاجة إلى الحساب

$A ’$ و

$B ’$ مثل هذا

$B ’(A (X)) = A’ (B (X)) = m (A، B) (X)$

حساب الوظيفة

$A ’$ و

$B ’$ يُدعى "متابعة" ويتم تعريفه كما يلي:

$f (A، B) (A) = f (B، A) (B) = m (A، B) = m (B، A)$
خوارزمية البناء

$f (أ ، ب)$ ما يلي:

يصبح الإدخال في A المؤشرات في $f (أ ، ب)$
يصبح الإدخال في B هو الإدخال في $f (أ ، ب)$
تطابق المؤشرات في A و B إلى $f (أ ، ب)$

مثال:

$$ display $$ X = (0 \ rightarrow 8) ["baseball"] \\ A = (8 \ rightarrow 5) [0 - 1، `` si "، 7] \ / \! \! / == `` basil ”\\ B = (8 \ rightarrow 5) [0،` `e"، 6، `` ow "] \ / \! \ !! / ==` `أدناه" $$ display $$

نحسب:

$A '= f (B، A) = (5 \ rightarrow 6) [0، 1، `` si "، 3، 4] \\ B' = f (A، B) = (5 \ rightarrow 6) [ 0، “e”، 2، 3، `` ow "] \\ m (A، B) = m (B، A) = A (B ') = B (A') = (8 \ rightarrow 6) [ 0 ، `` esiow "] \\$

احسب

$م (أ ، ب) (س)$ عرضت كتمرين.

بروتوكول التفاعل هو نفسه تمامًا مثل محرر مستندات Google ، ما لم تكن الحسابات أكثر تعقيدًا.

5. نقد OT

يعد تنفيذ الوقت الإضافي مهمة صعبة للغاية من حيث البرمجة. نقلاً عن ويكيبيديا : قال جوزيف جنتل ، مطور مكتبة Share.JS ومهندس Google Wave السابق ، "لسوء الحظ ، تنفيذ OT سيء. هناك مليون خوارزمية مع مقايضات مختلفة ، معظمهم محاصرون في الأوراق الأكاديمية. الخوارزميات صعبة حقًا وتستغرق وقتًا طويلاً لتنفيذها بشكل صحيح. [...] استغرق Wave عامين من الكتابة ، وإذا أعادنا كتابتها اليوم ، فسيستغرق الأمر وقتًا طويلاً للكتابة للمرة الثانية. "

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

حل الصراع التلقائي باستخدام التحولات التشغيلية