Synchronisationsalgorithmen verstehen
Seite 2: OT
Operational Transformation
Operational Transformation (OT) ist ein operationsbasierter Algorithmus, der in vielen Systemen zum Einsatz kommt. Dazu zählen beispielsweise Google Docs, SAP Process Flow oder die erwähnten Office-Plug-ins von Codoxware. OT wurde 1989 von C. A. Ellis und S. J. Gibbs erstmalig vorgestellt [1] und hat seitdem eine rasante Weiterentwicklung erfahren. Mehrere Forschergruppen haben den OT-Algorithmus in den letzten 20 Jahren immer wieder erweitert, um bekannte Konsistenzprobleme zu tilgen, weitere Dokumentstrukturen (z. B. XML) zu unterstützen beziehungsweise die Effizienz zu steigern. Hier sind etwa die Algorithmen adOPTed, GOTO, COT zu nennen. Mittlerweile ist OT der dominante Algorithmus in der Domäne der Echtzeit-Kollaboration.
Folgendes Beispiel eines primitiven Texteditors soll die Funktionsweise eines einfachen OT-Algorithmus verdeutlichen. Im Beispiel synchronisiert der OT-Algorithmus alle Instanzen eines einfachen Editors. Da der Texteditor ausschließlich die Bearbeitung von ASCII-Texten erlaubt, werden nur die folgenden Editor-Operationen angeboten:
- Operation Einfügen: ins(x, i), wobei x ein beliebiges ASCII-Zeichen darstellt und i den mit 1 beginnenden Index, der festlegt, wo x eingefügt werden soll.
- Operation Löschen: del(i), wobei i der mit 1 beginnende Index ist, der festlegt, wo man ein Zeichen entfernen soll.
Das folgende kollaborative Szenario erzeugt einen Konflikt, indem zwei Autoren das Wort "ABC" gleichzeitig ändern. Während Autor 1 an Position 2 ein "a" einfügt, erstellt Autor 2 an Position 3 ein "b". Die Änderungen des Dokuments lassen sich wie in Abbildung 1 über die Operationen o1 = ins('a', 2) und o2 = ins('b', 3) repräsentieren. Die auseinanderlaufenden Dokumente "AaBC" und "ABbC" sind anschließend zu synchronisieren, um die Konsistenz der Dokumentkopien wiederherzustellen. Folglich werden die Operationen o1, o2 an die anderen Teilnehmer verteilt. Die ursprüngliche Anwendung von o1, o2 auf die Zieldokumente führt allerdings nicht zum gewünschten Ergebnis, da "AabBC" und "AaBbC" nach wie vor inkonsistent sind (Abb. 1).
Um den Konflikt aufzulösen, lassen sich die übertragenen Operationen o1, o2 offensichtlich nicht ohne Anpassungen auf die Dokumentkopien anwenden. Wie der Name Operational Transformation suggeriert, sind die Operationen vorher zu transformieren. Die Funktion f in Abbildung 2 formalisiert die Transformation der Operationen o1, o2.
Die Funktion f ist einzig und allein dafür zuständig, den Index i anzupassen, der die Position beim Einfügen bestimmt. Ist der Index i1 der ersten Operation größer als der Index i2 der zweiten Operation, wird i1 um 1 erhöht. Andernfalls erhöht sich i2 um 1. Im Beispiel wird i2 auf 4 inkrementiert. Wendet man die transformierten Operationen o1', o2' auf die entsprechenden Dokumente an, ergibt sich der in Abbildung 3 illustrierte Fall. Nach Anpassung des Index i2 und der Anwendung der transformierten Operationen o1' und o2' sind die Dokumente letztlich wieder konsistent.
Um alle potenziell auftretenden Konfliktfälle auflösen zu können, sind alle parallel ausführbaren Operationen zu berücksichtigen. Im gewählten Beispiel beschränken sich die Operationen auf das Einfügen und das Löschen von Zeichen. Alle denkbaren Kombinationen von Operationen sind in der Transformationsmatrix in Abbildung 4 dargestellt.
Neben dem in Abbildung 2 definierten Fall f(ins1, ins2) der Transformationsfunktion sind demnach drei weitere Fälle zu berücksichtigen. Die verbleibenden sind ähnlich aufgebaut wie f(ins1, ins2) und werden daher nicht im Detail vorgestellt.
Von Interesse ist die Transformationsmatrix, da sie anzeigt, wie viel Aufwand die OT-Implementierung mit sich bringt. Große Matrizen mit zahlreichen Transformationsfällen sind ungleich aufwendiger als kleine, da alle in der Matrix abgebildeten Fälle auch tatsächlich zu implementieren sind. Zum Beispiel könnte ein grafischer UML-Editor Operationen zum Erstellen, Aktualisieren und Löschen von UML-Klassen, Assoziationen und Generalisierungen anbieten.
Da sich jedes der drei UML-Elemente durch jeweils drei Operationen manipulieren lässt, muss der UML-Editor mindestens neun Operationen unterstützen. Folglich würde die Transformationsmatrix 81 Operationskombinationen abbilden, die jeweils eine spezielle Implementierung erfordern. Daher sollte man die Anzahl der zu unterstützenden Editor-Operationen in Hinblick auf die OT-Implementierung minimal halten beziehungsweise komplexe Operationen durch mehrere primitive Operationen abbilden.
Ein weiterer wichtiger Aspekt bei der Konstruktion der Transformationsfunktionen ist das Prinzip der Intentionserhaltung, nach dem das Erwartungsbild aller Nutzer erfüllt werden sollte. Beispielsweise könnte man den in Abbildung 1 dargestellten Konflikt auch so auflösen, dass nur die Operation von Nutzer 1 auf beide Dokumentkopien angewandt und die von Nutzer 2 verworfen wird. Der Konflikt wäre somit aufgelöst und das Dokument wieder konsistent. Jedoch würde dieses Verhalten vollkommen der Erwartung von Nutzer 2 widersprechen, der sicherlich nicht damit rechnet, dass seine Änderung des Dokuments einfach verworfen wird. Demzufolge sollten, um die Nutzer bei der kollaborativen Arbeit nicht zu verwirren, die Erwartungen aller Teilnehmer erfüllt werden.
Um den beschriebenen OT-Algorithmus in der Praxis erfolgreich anwenden zu können, fehlt noch eine essenzielle Komponente: das Protokoll zum Nachrichtenaustausch. Hier ist anzumerken, dass sich OT sowohl in Peer-to-Peer- als auch in Client-Server-Szenarien einsetzen lässt.
