Currently this document is available in German only.
Vorstellung zweier Algorithmen zum Verteilten Bearbeiten von Dokumenten in Echtzeit
"Basics"
Zuerst sei der Begriff der "Operational Transformation" (OT) erklaert. Davon gibt es zweierlei Arten, die hier interessante ist die "Inclusion Transformation" (IT). Operationon sind dabei Dinge, die das bestehende Dokument aendern - allen voran die InsertOperation, die Text an einer Stelle im Dokument einfuegt und die DeleteOperation, die Text innerhalb eines bestimmten Bereiches entfernt. Operational Transformation meint jetzt, dass man eine bestehende Operation aus gegebenem Anlass aendert (transformiert). Inclusion Transformation heisst, den Effekt einer Operation in eine andere "einzubinden". Ein kleines Beispiel hierzu:
O1 sei eine Operation, die den Text "abc" an der Stelle 1 im Dokument einfuegt (Als Kurznotation sei ins(abc@1) gegeben). O2 sei eine weitere Operation, die den Text "def" an Stelle 0 im Dokument einfuegt (ins(def@0)). Transformiert man jetzt O1 gegen O2 (O2->O1), dann wird aus ins(abc@1) ins(abc@4), da der Effekt von O2 nun in O1 eingebunden ist: Wenn man naemlich O2 auf das Dokument anwenden wuerde, muesste man den Text von O1 an Stelle 4 anstatt 1 einfuegen, weil ja drei Buchstaben vor der Stelle eingefuegt wurden, an der urspruenglich der Text von O1 eingefuegt worden waere.
Urspruenglicher Algorithmus (obby < 0.3.0)
Jedes Dokument hat eine Revisionsnummer, die eine Version des Dokuments eindeutig identifiziert. Jedes Dokument beginnt dabei mit der Revisionsnummer 0. Unternimmt ein Client eine Aenderung im Dokument, so sendet er dem Server die Revisionsnummer, die seine Version des Dokumentes gerade hat zusammen mit der Aenderung. Ausserdem traegt er diese Operation in eine Liste aus so genannten nicht-synchronisierten Aenderungen (unsynced changes) ein.
Der Server, der ueber eine komplette Liste aller bisherigen Aenderungen verfuegt, transformiert die eingehende Aenderung gegen alle Operationen, deren Revisionsnummer groesser ist als die der neuen Operation (von denen hat der Client zur Zeit der Aenderung naemlich noch nichts gewusst), ausser gegen diejenigen vom selben Client (die hat er ja gekannt). Der Server erhoeht die aktuelle Revisionsnummer, fuegt die neue Operation in seine Liste ein und schickt sie an alle Clients (auch an den, von dem sie kam).
Erhaelt ein Client eine Operation vom Server, so macht er temporear alle seine "unsynced changes" rueckgaengig und wendet die einkommende Operation auf das Dokument an. Dann transformiert er alle "unsynced changes" gegen die neue Operation und stellt sie wieder her (da sie ja vorher rueckgaengig gemacht wurden). Handelt es sich dabei um eine Operation von ihm selbst, entfernt er sie aus der "unsynced changes"-Liste.
Jupiter (obby >= 0.3.0)
Statt der Revisionsnummer wird nun eine sogenannte "vector time" eingefuehrt, die aus zwei Komponenten besteht: Der "local count" (die die Anzahl an lokalen Aenderungen angibt) und der "remote count" (die die Anzahl an Aenderungen angibt, die uebers Netzwerk eingetroffen sind). Jeder Client hat eine solche "vector time", und der Server hat eine fuer jeden Client.
Begeht eine Client eine Operation, so sendet er diese mit seiner aktuellen vector time an den Server und erhoeht den "local count". Der Server hat diesmal fuer jeden Client eine Liste aus allen Operationen, von denen er noch nicht weiss, ob der Client sie bereits erhalten hat (acklist). Kommt also eine Opertion von einem Client an, so loescht der Server zuerst alle Operationen aus dieser Liste, deren vector time eine kleinere remote count hat als die local count der eingehenden Operation (die der Client somit also schon hat). Die eingehende Operation wird dann gegen die verbleibenden transformiert (da der Client von denen noch nichts wusste). Ausserdem wird der remote count fuer diesen Client erhoeht (Es wurde eine Operation uebers Netzwerk empfangen). Die daraus resultierende Operation wird dann auf das Dokument angewendet und an alle anderen Clients geschickt und in deren acklist gepackt (jedoch nicht mehr an den Client, von dem die Operation kam). Dabei wird auch der local count zu dem entsprechenden Client erhoeht.
Empfaengt ein Client eine Operation vom Server, so geht er im Prinzip genauso vor: Auch er hat eine acklist, in der die Operationen stehen, von denen er nicht sagen kann, ob der Server sie bereits kennt (und in die er jede Operation packt, die er an den Server schickt). Er loescht nun ebenfalls alle Operationen in dieser Liste, deren remote count unter dem local count der eingehenden Operation ist, transformiert die eingehende Operation gegen die Operationen in der Liste und erhoeht den eigenen remote count. Die Operation wird dann auf das Dokument angewandt.
Abschliessender Vergleich
urspruenglicher Algorithmus | Jupiter ================================================================================ Operation wird zum urspruenglichen | Operation wird nur zu den anderen Client zurueck geschickt | geschickt -------------------------------------------------------------------------------- Notwendigkeit, temporaer eine aeltere | Alles Notwendige wird ueber Version des Dokumentes herstellen zu | "Operational Transformations" (OT) muessen | geloest -------------------------------------------------------------------------------- Eindimensionale Revisionsnummer | Zweidimensionale vector time -------------------------------------------------------------------------------- Client kann genau feststellen, | Client erhaelt diese Zahl nur, wenn wieviele und welche Operationen noch | eine Operation ankommt. nicht vom Server bestaetigt sind | -------------------------------------------------------------------------------- Server benoetigt Liste aus allen | Alle brauchen eine solche Liste fuer Operationen, von denen er noch noch | die jeweilige Gegenseite (Server hat nicht sicher weiss, dass jeder Client | dabei N Listen fuer N Clients) sie bereits erhalten hat | -------------------------------------------------------------------------------- NoOp-Operationen mit aktueller | NoOp-Operationen mit aktueller vector Revisionsnummer um die Liste bei | time um die Listen bei einseitigem einseitigem Datenverkehr zu leeren | Datenverkehr zu leeren --------------------------------------------------------------------------------
Schlusswort
Wem das alles zu abstrakt ist, der ist an dieser Stelle herzlich dazu eingeladen, sich einige Faelle zu konstruieren und sie mit Papier und Blestift auf die hier vorgestellten Methoden nachzuvollziehen.
An dieser Stelle moechte ich noch darauf hinweisen, dass der urspruengliche Algorithmus in von mir selbst ausgedacht und keinstenfalls sonderlich optimiert ist. Er ist daher sicher an vielen Stellen verbesserungswuerdig, um diverse Unzulaenglichkeiten zu korrigieren. Aehnliches mag auf die momentane Jupiter-Implementation in obby zutreffen.
Verfasst von Armin Burgmeier am 4. Maerz 2006