Die automatische Konfliktlösung in einer Umgebung mit mehr als einem führenden Knoten (in diesem Artikel bezieht sich ein führender Knoten auf einen Knoten, der Datenänderungsanforderungen akzeptiert) ist ein sehr interessantes Forschungsgebiet. Je nach Anwendung gibt es verschiedene Ansätze und Algorithmen. In diesem Artikel wird die OT-Technologie (Operational Transformations) zur Lösung von Konflikten in kollaborativen Bearbeitungsanwendungen wie Google Text & Tabellen und Etherpad erläutert.

1. Einleitung

Die Zusammenarbeit ist aus technischer Sicht schwierig, da mehrere Personen zu fast denselben Zeitpunkten unterschiedliche Änderungen an demselben Textabschnitt vornehmen können. Da die Datenübertragung über das Internet nicht sofort erfolgt (die Datenübertragungsgeschwindigkeit in der Glasfaser unterliegt Einschränkungen), arbeitet jeder Client mit einer lokalen Version (Replikat) des bearbeiteten Dokuments, um eine sofortige Antwort zu simulieren, die von den Versionen anderer Teilnehmer abweichen kann. Der wichtigste Haken besteht darin, die Konsistenz zwischen lokalen Versionen sicherzustellen, oder mit anderen Worten, wie sichergestellt werden kann, dass alle lokalen Versionen früher oder später zu derselben korrekten Version eines Dokuments konvergieren (dies kann nicht von allen Clients verlangt werden) Einige Momente gleichzeitig hatten dieselbe Version, da der Bearbeitungsprozess endlos sein kann.

Alte Version von Google Text & Tabellen

Zunächst verwendete Google Text & Tabellen wie viele andere kollaborative Dokumentbearbeitungsanwendungen einen einfachen Vergleich des Inhalts verschiedener Versionen eines Dokuments. Angenommen, wir haben zwei Clients - Petya und Vasya - und der aktuelle Status des Dokuments wird zwischen ihnen synchronisiert. In der alten Version des Google-Servers von Google berechnet es nach Erhalt eines Updates von Petya die Differenz (diff) zwischen seiner und seiner eigenen Version und versucht, die beiden Versionen bestmöglich zu einer zusammenzuführen. Dann sendet der Server die empfangene Version an Vasya. Wenn in Vasya keine Änderungen an den Server gesendet wurden, wird der Vorgang wiederholt. Sie müssen die Version vom Server mit der lokalen Vasina zusammenführen und an den Server zurücksenden.

Sehr oft funktioniert dieser Ansatz nicht sehr gut. Angenommen, Petya, Vasya und der Server beginnen mit einem synchronisierten Dokument mit dem Text „ Der schnelle braune Fuchs “.

Petja hebt die Wörter Brauner Fuchs fett hervor, während Vasya das Wort Fuchs durch Hund ersetzt . Lassen Sie Petina zuerst zum Server wechseln und er sendet die aktualisierte Version von Vasya. Es ist klar, dass das Endergebnis Der schnelle braune Hund sein sollte , aber es gibt nicht genügend Informationen für die Zusammenführungsalgorithmen, um dies zu verstehen. Die Optionen Der schnelle braune Fuchshund , Der schnelle braune Hund , Der schnelle braune Fuchs sind absolut korrekt. (In git kommt es beispielsweise in solchen Fällen zu einem Zusammenführungskonflikt, und Sie müssen mit Ihren Händen regieren.) Dies ist das Hauptproblem dieses Ansatzes. Sie können sich über die Ergebnisse der Fusion nicht sicher sein, wenn Sie sich nur auf den Inhalt des Dokuments verlassen.

Sie können versuchen, die Situation zu verbessern und die Fähigkeit anderer Teilnehmer zu blockieren, Textabschnitte zu bearbeiten, die bereits von jemandem regiert werden. Dies ist jedoch nicht das, was wir wollen - dieser Ansatz versucht lediglich, die Lösung eines technischen Problems zu vermeiden, indem die Benutzererfahrung verschlechtert wird, und es kann auch vorkommen, dass zwei Teilnehmer gleichzeitig denselben Satz bearbeiten - und dann verliert einer von ihnen entweder die Änderungen oder er muss die Änderungen im Falle der oben genannten Konflikte manuell kombinieren.

Neue Version von Google Text & Tabellen

In der neuen Version von Google Text & Tabellen wurde ein völlig anderer Ansatz verwendet: Dokumente werden als Folge von Änderungen gespeichert, und anstatt den Inhalt zu vergleichen, rollen wir die Änderungen in der Reihenfolge (im Folgenden als Bestellbeziehung bezeichnet ). Wenn wir wissen, wie der Benutzer das Dokument geändert hat, und seine Absichten berücksichtigen , können wir die endgültige Version korrekt bestimmen, nachdem wir alle Änderungen kombiniert haben.

Okay, jetzt müssen wir verstehen, wann wir die Änderungen anwenden müssen - wir brauchen ein Kollaborationsprotokoll .

In Google Text & Tabellen beschränken sich alle Dokumentbearbeitungen auf drei verschiedene Vorgänge :

Texteinfügung
Text löschen
Anwenden von Stilen auf Text

Wenn Sie ein Dokument bearbeiten, werden alle Ihre Aktionen genau in diesem Satz von Vorgängen gespeichert und am Ende des Änderungsprotokolls hinzugefügt. Wenn das Dokument angezeigt wird, wird das Änderungsprotokoll mit den aufgezeichneten Vorgängen ausgeführt.

Eine kleine Bemerkung: Das erste (öffentliche) Google-Produkt mit OT-Unterstützung war anscheinend Google Wave. Er unterstützte ein viel breiteres Spektrum von Operationen.

Beispiel

Lassen Sie Petya und Vasya vom gleichen Stand der „HABR 2017“ ausgehen.
Petya ändert 2017 bis 2018, dies schafft tatsächlich 2 Operationen:

Gleichzeitig ändert Vasya den Text in „HELLO HABR 2017“:

Vasya erhält Petins Löschvorgang. Wenn er ihn nur anwendet, wird der falsche Text erhalten (die Nummer 7 hätte gelöscht werden müssen):

Um dies zu vermeiden, muss Vasya Petins Betrieb entsprechend seinen aktuellen lokalen Änderungen umwandeln (mit anderen Worten, die Vorgänge sind kontextsensitiv):

\ {Löschen \ \ @ 8 \} \ rightarrow \ {Löschen \ \ @ 15 \}

$\ {Löschen \ \ @ 8 \} \ rightarrow \ {Löschen \ \ @ 15 \}$

Betrachten Sie dieses Beispiel etwas formeller:

Dann:

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

Voila! Der beschriebene Algorithmus heißt Operational Transformation.

2. Operative Transformation

Konsistenzmodell

Um die Konsistenz zu gewährleisten, wurden mehrere Konsistenzmodelle entwickelt. Betrachten Sie eines davon - CCI.

Das CCI-Modell bietet drei Eigenschaften:

Konvergenz: Alle Replikate eines gemeinsamen Dokuments müssen nach Abschluss aller Vorgänge identisch sein:

In diesem Beispiel beginnen beide Benutzer mit identischen Replikaten. Dann ändern sie das Dokument und die Replikate weichen voneinander ab - auf diese Weise wird die minimale Antwortzeit erreicht. Nach dem Senden lokaler Änderungen an andere Clients erfordert die Konvergenzeigenschaft, dass der endgültige Status des Dokuments für alle Clients identisch wird.
Absichtserhaltung: Die Absicht eines Vorgangs muss auf allen Replikaten gespeichert werden, unabhängig davon, ob sie sich überschneiden, um mehrere Vorgänge gleichzeitig auszuführen. Die Absicht einer Operation ist definiert als die Auswirkung ihrer Ausführung auf die Kopie, in der sie erstellt wurde.

Stellen Sie sich ein Beispiel vor, bei dem diese Eigenschaft fehlschlägt:

Beide Clients beginnen mit denselben Replikaten und nehmen dann die Änderungen vor. Für Petya besteht die Absicht seiner Operation darin, '12' in den ersten Index einzufügen, und für Vasya werden die Zeichen mit den Indizes 2 und 3 gelöscht. Nach der Synchronisation mit Petya Vasino werden die Absicht und die Absicht von Vasya Petino verletzt. Beachten Sie auch, dass die Replikate auseinander gegangen sind, dies ist jedoch keine Voraussetzung für die betreffende Eigenschaft. Die richtige endgültige Version wird vorgeschlagen, um den Leser als kleine Übung zu identifizieren.
Kausalitätserhaltung: Operationen müssen in einer kausalen Reihenfolge ausgeführt werden (basierend auf der Beziehung, die zuvor aufgetreten ist).

Stellen Sie sich ein Beispiel vor, bei dem diese Eigenschaft fehlschlägt:

Wie Sie sehen können, schickte Petya Vasya und Agent Smith seine Änderung des Dokuments, Vasya erhielt es zuerst und löschte das letzte Zeichen. Aufgrund der Netzwerkverzögerung erhält Smith die erste Operation für Vasin, um ein noch nicht vorhandenes Zeichen zu löschen.

OT kann nicht sicherstellen, dass die Kausalitätserhaltungseigenschaft erfüllt ist, daher werden für diese Zwecke Algorithmen wie eine Vektortaktung verwendet.

OT Design

Eine der Entwurfsstrategien des OT-Systems ist die Unterteilung in drei Teile:

Transformationssteuerungsalgorithmen: Bestimmen Sie, wann die Operation (Ziel) zur Transformation bereit ist, welche Operationen (Referenz) die Transformationen ausgeführt werden sollen und in welcher Reihenfolge sie ausgeführt werden sollen.
Transformationsfunktionen: Transformiert die Zieloperation unter Berücksichtigung der Auswirkungen von Referenzoperationen.
Anforderungen und Eigenschaften von Transformationen (Eigenschaften und Bedingungen): Stellen Sie eine Verbindung zwischen diesen Komponenten her und führen Sie Überprüfungen auf Richtigkeit durch.

Konvertierungsfunktionen

Konvertierungsfunktionen können in zwei Typen unterteilt werden:

Inclusion / Forward Transformation: Transformieren einer Operation $O_a$ vor der Operation $O_b$ so dass die Wirkung von $O_b$ (z. B. zwei Einsätze)
Ausschluss / Rückwärtstransformation: Transformation einer Operation $O_a$ vor der Operation $O_b$ so dass die Wirkung von $O_b$ ausgeschlossen (z. B. nach Löschung einfügen)

Ein Beispiel für symbolische Einfüge- / Löschvorgänge (i-Einfügen, d-Löschen):

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. Interaktionsprotokoll in Google Text & Tabellen

Schauen wir uns genauer an, wie das Interaktionsprotokoll in Google Text & Tabellen funktioniert. Angenommen, wir haben einen Server, Petya und Vasya, und sie haben eine synchronisierte Version eines leeren Dokuments.

Jeder Kunde merkt sich folgende Informationen:

Version (ID, Revision) der letzten vom Server empfangenen Änderung.
Alle Änderungen, die lokal vorgenommen, aber nicht an den Server gesendet wurden (ausstehender Versand)
Alle lokal vorgenommenen Änderungen werden an den Server gesendet, jedoch ohne Bestätigung vom Server.
Der aktuelle Status des Dokuments, den der Benutzer sieht.

Der Server erinnert sich wiederum an:

Eine Liste aller empfangenen, aber nicht verarbeiteten Änderungen (ausstehende Verarbeitung).
Vollständiger Verlauf aller verarbeiteten Änderungen (Revisionsprotokoll).
Der Status des Dokuments zum Zeitpunkt der letzten verarbeiteten Änderung.

Also beginnt Petja mit dem Wort „Hallo“ am Anfang des Dokuments:

Der Client hat diese Änderung zuerst zur Warteliste hinzugefügt, sie dann an den Server gesendet und die Änderungen in die gesendete Liste verschoben.

Petya tippt weiter und hat bereits das Wort "Habr" hinzugefügt. Zur gleichen Zeit tippte Vasya "!" in seinem leeren Dokument (er hat Petinas Änderungen noch nicht erhalten).

Petino

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

$\ {Insert \ \ 'Habr', \ @ 5 \}$ wurde zur ausstehenden Liste hinzugefügt, aber noch nicht gesendet, da nicht mehr als eine Änderung gleichzeitig gesendet wird und die vorherige noch nicht bestätigt wurde . Wir stellen außerdem fest, dass der Server die Änderungen von Petit in seinem Revisionsprotokoll gespeichert hat. Dann sendet der Server sie an Vasya und sendet eine Bestätigung an Petya (dass Petinas erste Änderungen erfolgreich verarbeitet wurden).

Der Client von Vasya empfängt die Änderungen von Petina vom Server und wendet OT hinsichtlich des ausstehenden Sendens an den Server an

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

$\ {Insert \ \ '!', \ @ 0 \}$ . Das Ergebnis ist eine Änderung des Einfügeindex von 0 auf 5. Wir stellen außerdem fest, dass beide Clients die Nummer der letzten synchronisierten Revision mit dem Server auf 1 aktualisiert haben. Schließlich entfernt der Petin-Client die entsprechende Änderung aus der Liste der ausstehenden Bestätigungen vom Server.

Dann senden Petya und Vasya ihre Änderungen an den Server.

Der Server empfängt Petinas Änderungen vor (in Bezug auf die eingegebene Bestellung) Vasinykh, verarbeitet sie also zuerst und sendet eine Bestätigung an Petya. Er sendet sie auch an Vasya und sein Kunde konvertiert sie in Bezug auf Änderungen, die noch nicht bestätigt wurden

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

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

Dann kommt der wichtige Punkt. Der Server beginnt mit der Verarbeitung der Änderungen von Vasya, die laut Vasya die Revisionsnummer 2 haben. Der Server hat die Änderungen jedoch bereits bei Nummer 2 festgeschrieben, sodass die Konvertierung auf alle Änderungen angewendet wird, die dem Vasya-Client noch nicht bekannt sind (in diesem Fall) - -

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

$\ {Insert \ \ 'Habr', \ @ 5 \}$ ) und speichert das Ergebnis unter Nummer 3.

Wie wir sehen können, wurde der Index in Vasins Änderung um 5 erhöht, um Petins Text zu berücksichtigen.

Der Vorgang ist für Petja abgeschlossen, und Vasya muss eine neue Änderung vom Server erhalten und eine Bestätigung senden.

4. Etherpad

Schauen wir uns eine andere ähnliche Anwendung an, in der OT verwendet wird - das Open-Source-Projekt des Online-Editors mit der gemeinsamen Bearbeitung von etherpad.org

In Etherpad unterscheiden sich die Konvertierungsfunktionen geringfügig - Änderungen werden als eine Reihe von Änderungen (Änderungssatz) an den Server gesendet , definiert als

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

$\ ell_1$ : Länge des Dokuments vor der Bearbeitung.
$\ ell_2$ : Länge des Dokuments nach der Bearbeitung.
c1,c2,c3,... - Beschreibung des Dokuments nach der Bearbeitung. Wenn ci Ist eine Zahl (oder ein Zahlenbereich), dann sind dies die Indizes der Zeichen des Originaldokuments, die nach der Bearbeitung verbleiben (beibehalten), und wenn ci - ein Zeichen (oder eine Zeichenfolge), dann ist dies das Einfügen.

Ein Beispiel:
1. $ inline $ `` "+ \ (0 \ rightarrow 6) [` `Hallo”] = `` Hallo "$ inline $
2. $ inline $ `` Beaver ”+ (4 \ rightarrow 4) [` `Ha”, \ 2-3] = `` Habr '$ inline $

Wie Sie bereits verstehen, wird das endgültige Dokument als eine Folge solcher Änderungen gebildet, die auf ein leeres Dokument angewendet werden.

Beachten Sie, dass wir nicht nur Änderungen von anderen Teilnehmern übernehmen können (dies ist im Prinzip in Google Text & Tabellen möglich), da die Gesamtlänge der Dokumente unterschiedlich sein kann.
Zum Beispiel, wenn das Quelldokument die Länge n hatte und wir zwei Änderungen haben:

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

dann

$A (B)$ unmöglich, weil

$A$ erfordert Dokumentlänge

$n$ und danach

$B$ er wird von Länge sein

$n_b$ .
Um diese Situation zu beheben, verwendet Etherpad einen Zusammenführungsmechanismus : Es ist eine Funktion, die mit gekennzeichnet ist

$m (A, B)$ akzeptiert zwei Änderungen an der Eingabe im selben Status des Dokuments (im Folgenden als bezeichnet

$X$ ) und nimmt eine neue Änderung vor.

Benötigt das

$m (A, B) = m (B, A)$

Beachten Sie dies für einen Kunden mit Änderungen

$A$ wer hat die Änderung erhalten

$B$ es macht keinen Sinn zu berechnen

$m (A, B)$ , als

$m (A, B)$ gilt für

$X$ und

$A$ aktueller Zustand

$A (X)$ . In der Tat müssen wir berechnen

$A ’$ und

$B ’$ so dass

$B '(A (X)) = A' (B (X)) = m (A, B) (X)$

Funktionsberechnung

$A ’$ und

$B ’$ heißt follow und ist wie folgt definiert:

$f (A, B) (A) = f (B, A) (B) = m (A, B) = m (B, A)$
Konstruktionsalgorithmus

$f (A, B)$ Folgendes:

Die Einfügung in A wird zu den Indizes in $f (A, B)$
Die Einfügung in B wird zur Einfügung in $f (A, B)$
Übereinstimmende Indizes in A und B übertragen sich auf $f (A, B)$

Ein Beispiel:

$$ display $$ X = (0 \ rightarrow 8) [`` baseball ”] \\ A = (8 \ rightarrow 5) [0 - 1,` `si”, 7] \ / \! \! / == `` Basilikum ”\\ B = (8 \ rightarrow 5) [0,` `e", 6, `` ow "] \ / \! \! / ==` `unter" $$ display $$

Wir berechnen:

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

Berechnen

$m (A, B) (X)$ als Übung angeboten.

Das Interaktionsprotokoll ist im Wesentlichen dasselbe wie in Google Text & Tabellen, es sei denn, die Berechnungen sind etwas komplizierter.

5. Kritik an OT

Die Implementierung von OT ist eine sehr schwierige Aufgabe in Bezug auf die Programmierung. Zitat aus Wikipedia : Joseph Gentle, Entwickler der Share.JS-Bibliothek und ehemaliger Google Wave-Ingenieur, sagte: „Die Implementierung von OT ist leider zum Kotzen. Es gibt eine Million Algorithmen mit unterschiedlichen Kompromissen, die meist in wissenschaftlichen Arbeiten gefangen sind. Die Algorithmen sind sehr schwer und zeitaufwändig zu implementieren. [...] Wave hat 2 Jahre gebraucht, um zu schreiben, und wenn wir es heute umschreiben würden, würde es fast genauso lange dauern, ein zweites Mal zu schreiben. “

(Leider ist das Schreiben von OT sehr schwierig. Es gibt eine Million Algorithmen mit ihren Vor- und Nachteilen, aber die meisten davon sind nur akademische Studien. Die Algorithmen sind tatsächlich sehr komplex und erfordern viel Zeit für ihre korrekte Implementierung. [...] Wir haben 2 Jahre damit verbracht Wave schreiben, und wenn wir es heute noch einmal schreiben müssten, würden wir genauso viel Zeit brauchen)
Sie müssen unbedingt jede Änderung am Dokument speichern

Automatische Konfliktlösung mithilfe operativer Transformationen