Seite 3: Differenzielle Synchronisation

Inhaltsverzeichnis

Differenzielle Synchronisation

Neben operationsbasierten gibt es außerdem zustandsbasierte Algorithmen. Ein solcher Algorithmus ist beispielsweise die differenzielle Synchronisation (DS), die anfangs in Google Docs zum Einsatz kam. 2009 ersetzte Google das Verfahren allerdings durch den verbreiteteren OT-Algorithmus.

Die differenzielle Synchronisation [2] basiert auf zwei Verfahren, die jeder kennt, der mit Versionsverwaltungen vertraut ist: Diff und Patch. Diff berechnet die Differenz zwischen zwei Versionen einer Textdatei. Patch ist die Umkehrung von Diff, und das Verfahren integriert die berechnete Differenz in eine ältere Textdatei, um diese auf den aktuellen Stand zu heben. Adaptiert man den bekannten lokalen Ansatz auf ein verteiltes System, sodass Diff und Patch auf verschiedenen Rechnern ausgeführt werden und die von Diff erzeugte Differenz ausgetauscht wird, ergibt sich die Grundidee der differenziellen Synchronisation.

Damit zwei Teilnehmer A und B auf diese Weise zusammenarbeiten können, muss jede Partei zwei Versionen des zu bearbeitenden Dokuments vorhalten: die aktuelle Version und die vorherige. Zum Beispiel arbeiten Teilnehmer A und B an dem fehlerhaft benannten Dokument Fischers Fritze fischt fische Frische. Es stellt anfangs sowohl die aktuelle als auch die vorherige Version dar. Teilnehmer A behebt nun die Tippfehler und ändert das Dokument in Fischers Fritze fischt frische Fische. Per Diff wird (1) die Differenz zwischen vorheriger und aktueller Version gebildet (Abb. 5). Anschließend ersetzt man (2) die vorherige Version durch eine Kopie der aktuellen. Die Differenz sieht wie folgt aus:

ht f
+r
ische F
-r
isch

Die Differenz aus Schritt (1) wird an Teilnehmer B gesendet. Dieser wendet nun (3) die Differenz mit Patch auf seine aktuelle und vorherige Version an und erhält somit das konsistente Dokument Fischers Fritze fischt frische Fische. Da das Verhalten symmetrisch ist, ermittelt auch Teilnehmer B via Diff die Differenz, die seine Änderungen enthält, und schickt diese an Teilnehmer A.

Es ist wichtig, die Differenz auf beide Versionen anzuwenden. Geschieht das per Patch nur auf die vorherige Version und nicht auf die aktuelle, umfasst die von Teilnehmer B gebildete Differenz das Rückgängigmachen aller von A durchgeführten Änderungen. Würde die Differenz nur auf die aktuelle Version von Teilnehmer B angewandt, enthielte die von B erzeugte Differenz auch die Änderungen von Teilnehmer A, die somit dupliziert würden. Beides führt nicht zum gewünschten Ergebnis.

Die bisherige Beschreibung vernachlässigte ein entscheidendes Detail. Was passiert, wenn beide Teilnehmer gleichzeitig die aktuelle Version des Dokuments ändern? Konkret ist festzulegen, wie die von A erzeugte Differenz auf das bereits von B geänderte Dokument angewandt wird. Die von Teilnehmer A durchgeführte Änderung ist an einer anderen Stelle in das Dokument von B zu integrieren beziehungsweise zu verwerfen.

Das vorgestellte OT-Verfahren löst das Problem, indem es die Operationen von Teilnehmer A gegen die Operationen von B transformiert. Da das DS-Verfahren mit Differenzen arbeitet, gibt es diese Möglichkeit nicht. Daher werden robustere Varianten von Diff und Patch eingeführt, die einen gewissen Grad an Unschärfe beim Patch erlauben. Das lässt sich dadurch erreichen, dass neben der Änderungsposition der Differenz auch noch ein minimaler Kontext gespeichert wird, der einige Zeichen vor und nach der betreffenden Stelle enthält. Somit kann Patch auch noch Stellen finden, wenn sich der Inhalt des Dokuments seit dem Erstellen der Differenz etwas geändert hat. Vorgestellt sei nun, dass, während A die beiden Tippfehler behebt, B das Dokument in Fischers Fritze fischt täglich fische Frische ändert.

Da die von A gesendete Differenz auch Kontextinformationen enthält, lässt sie sich per Patch auf beide Versionen anwenden. In der Differenz von oben ist das Hinzufügen von r in den folgenden Kontext eingebettet: ht f(+r)ische, wobei ht die letzten beiden Zeichen von fischt sind. Durch diese
Kontextinformationen kann Patch die richtige Stelle im Dokument finden. Im obigen Beispiel ist das Szenario etwas komplexer, da sich durch das Einfügen von täglich durch B der Kontext geringfügig geändert hat. Damit das Verfahren trotzdem funktioniert, muss Patch eine gewisse Unschärfe zulassen.

Nach dem Patch mit den von A korrigierten Tippfehlern erhält Teilnehmer B nun die aktuelle Version Fischers Fritze fischt täglich frische Fische und die vorherige: Fischers Fritze fischt frische Fische.

Bei gravierenden Änderungen, wie dem Ersetzen des Inhalts durch einen anderen, schlägt Patch fehl, und die eingehenden Änderungen werden verworfen. Erwogen sei nun, dass B Frische durch Karpfen ersetzt. Der von A korrigierte Tippfehler in Frische lässt sich nun nicht mehr auf das aktuelle Dokument von B Fischers Fritze fischt fische Karpfen anwenden, da sich der Kontext zu stark verändert hat. Diese Änderung geht verloren und Fische wird nach dem nächsten Synchronisationszyklus durch Karpfen ersetzt.

Das DS-Verfahren besticht durch den einfachen Grundalgorithmus. Die Magie der differenziellen Synchronisation verbirgt sich in den robusten Varianten von Diff und Patch. Möchte man außer Textdokumenten auch andere Datenstrukturen kollaborativ bearbeiten, werden entsprechend angepasste Varianten von Diff und Patch benötigt. Das gilt beispielsweise für als XML-Datei serialisierte Dokumente.

Hier kann das Verwenden textbasierter Diffs und Patchs die XML-Struktur zerstören und damit die Semantik verändern. Etwa wenn zwei Teilnehmer zur gleichen Zeit eine Datenstruktur ändern, die eine Rechnung repräsentiert. Teilnehmer A korrigiert den Rechnungswert von 50 auf 59 Euro, während Teilnehmer B den neuen Wert auf 150 Euro setzt. Nach der Synchronisation würden daraus 159 Euro werden. Egal ob A oder B den richtigen Wert gesetzt haben, das Resultat der Synchronisation ist höchstwahrscheinlich falsch. Es ist also Vorsicht geboten, da es nicht immer sinnvoll ist, Diff und Patch auf alle Teile einer Datenstruktur anzuwenden. Deshalb ist es wichtig, dass zeitnah synchronisiert wird, sodass etwaige Synchronisationsfehler schnell auffallen und sich korrigieren lassen.

Bisher wurde ausschließlich die Kollaboration von genau zwei Teilnehmern berücksichtigt. Überdies sind Szenarien denkbar, in denen sich mehrere Teilnehmer mit einem zentralen Server verbinden. Auch eine solche Konstellation lässt sich bequem mit dem DS-Ansatz realisieren. Der Server verhält sich symmetrisch zu regulären Teilnehmern mit der Ausnahme, dass er eine vorherige Version pro Teilnehmer und nur eine zentrale aktuelle Version hält (Abb. 6). Auf diese Weise lassen sich auch mehrere Server miteinander verbinden, um die Last gleichmäßiger zu verteilen.