Synchronisationsalgorithmen verstehen

Know-how  –  2 Kommentare

Im Zeitalter von EtherPad und Google Docs ist Echtzeit-Kollaboration allgegenwärtig. Aber was passiert hinter den Kulissen, wenn mehrere Nutzer parallel am selben Dokument scheinbar ohne Zeitverzögerung arbeiten? Wie werden Konflikte, hervorgerufen durch Endanwender, die gleiche Textpassagen oder Grafiken ändern, automatisch aufgelöst? Der Artikel beleuchtet diese Fragen im Detail und erläutert, wie Synchronisationsalgorithmen funktionieren.

Mit Echtzeit-Kollaboration befassen sich Forscher und Unternehmen seit mehr als vier Jahrzehnten. Bereits 1968 zeigte das Team um Douglas Engelbart in Stanford erstmalig einen kollaborativen Texteditor, der es mehreren räumlich verteilten Mitarbeitern ermöglichte, Texte in Echtzeit zu editieren. Die damals gehegten Erwartungen konnten allerdings lange Zeit nicht erfüllt werden, und die Echtzeit-Kollaboration führte über Jahre hinweg ein Nischendasein. Ausschließlich im akademischen Bereich fand das Thema größere Beachtung.

Erst mit der Verbreitung des WWW schaffte es Google, die Echtzeit-Kollaboration der breiten Masse zugänglich zu machen. Besonders durch die Popularität von Google Docs oder EtherPad kamen viele Internetnutzer mit Echtzeitanwendungen erstmalig in Kontakt. Deren Anwender schätzen das unkomplizierte Erstellen von Office-Dokumenten, Präsentationen und Diagrammen, da der Zugriff über beliebige Endgeräte (PCs, Tablets, Smartphones) möglich ist und verteilte Teams trotz räumlicher Trennung effizient gemeinsam arbeiten können.

Mittlerweile gibt es eine Vielzahl von Produkten, die das kollaborative Bearbeiten unterschiedlicher Dokumente ermöglichen. Codoxware stellt beispielsweise Plug-ins für Microsoft Office bereit, damit Anwender Word-, Excel- oder PowerPoint-Dokumente mit anderen Office-Nutzern in Echtzeit editieren können. Ein weiteres kommerziell erhältliches Produkt ist der in SAP StreamWork integrierte Process Flow Editor, mit dem sich BPMN-Geschäftsprozesse (Business Process Model and Notation) gemeinsam erstellen lassen. Die Echtzeit-Kollaboration ist natürlich nicht auf Office-Dokumente und BPMN-Diagramme beschränkt. Andere Werkzeuge gestatten beispielsweise das gemeinsame Bearbeiten von Quellcode, Grafiken oder Mindmaps.

Für Konflikte, die bei der parallelen Bearbeitung gleicher Dokumentenbausteine (Wörter, Grafiken usw.) entstehen können, gibt es zwei etablierte Strategien. Einerseits lassen sich Schreibberechtigungen über eine zentrale Instanz verwalten, was die Entstehung von Konflikten bereits im Voraus ausschließt. Diese sogenannten pessimistischen Algorithmen sind entweder rundenbasiert (ein Schreib-Token wandert von Client zu Client) oder setzen auf Sperrmechanismen (ein Client mit Schreibrechten sperrt das Dokument, bis die Änderungen vollzogen sind, und anschließend werden die Schreibrechte wieder freigegeben).

Ein Beispiel für einen Sperrmechanismus, das jeder aus dem Alltag kennt, ist das Öffnen eines auf einem Netzwerk liegenden Office-Dokuments. Nur derjenige, der das Dokument zuerst öffnet, kann Änderungen vornehmen. Alle anderen können nur lesend auf das Dokument zugreifen und müssen sich mit dem Ändern so lange gedulden, bis das Dokument wieder freigegeben ist.

Das Beispiel offenbart, dass pessimistische Algorithmen für die Echtzeitkommunikation denkbar ungeeignet sind. Zusätzlich kann bereits das Anfordern von Schreibrechten beachtliche Latenzzeiten mit sich bringen. Temporäre Ausfälle des Netzwerks können minutenlange Verzögerungen verursachen, was im Bereich Echtzeit-Kollaboration inakzeptabel ist. Der Nutzer erwartet, dass das System umgehend auf Eingaben reagiert. Eine etablierte Zeitschranke besagt, dass alle Systemreaktionen mit einer Antwortzeit kleiner 0,1 Sekunden als unverzögert wahrgenommen werden.

Infolgedessen hat sich eine zweite Strategie zur Behandlung von Konflikten durchgesetzt, die auf den sogenannten optimistischen Algorithmen beruht. Im Gegensatz zu den pessimistischen erlauben es diese, Dokumente umgehend zu verändern, ohne über besondere Berechtigungen verfügen zu müssen. Alle Teilnehmer arbeiten auf dedizierten Dokumentkopien, die schnellstmöglich synchronisiert werden. Anders als bei pessimistischen Algorithmen können hier tatsächlich Konflikte auftreten.

Die optimistischen Algorithmen untergliedert man weiter in operations- und zustandsbasierte Vertreter. Während bei zustandsbasierten Algorithmen Dokumentunterschiede als Grundlage für die Synchronisation dienen, werden bei operationsbasierten nicht die Dokumente, sondern nur die Operationen auf dem Dokument an sich berücksichtigt. Ändert man beispielsweise den Text "Hallo" zu "Hallo-Welt" würde ein zustandsbasierter Algorithmus die Differenz "-Welt" berechnen. Differenzen lassen sich zwischen beliebigen Texten ohne jegliches Hintergrundwissen darüber berechnen, wie die Texte entstanden sind.

Ein operationsbasierter Algorithmus hingegen würde aufeinanderfolgende Einfüge-Operationen einzelner Zeichen aufzeichnen (z. B. ins("-",6); ins("W",7) usw.). Um das Zieldokument (etwa "Hallo-Welt") korrekt durch Editor-Operationen zu rekonstruieren, sind die Operationen kontinuierlich aufzuzeichnen. Die folgenden Abschnitte stellen sowohl einen operations- als auch einen zustandsbasierten Algorithmus im Detail vor.