Kollaboratives Editieren ist schwerer als gedacht

Google Docs bewältigt Echtzeit-Zusammenarbeit beim Editieren für Millionen von Nutzern. Es wirkt mühelos: Du tippst, dein Cursor bewegt sich, und die Änderungen deines Kollegen erscheinen sofort. Diese Einfachheit täuscht. Unter der Haube ist kollaboratives Editieren eines der schwierigsten Probleme verteilter Systeme, und die beiden wichtigsten Lösungsansätze (Operational Transformation und CRDTs) haben Trade-offs, die erst sichtbar werden, wenn man selbst damit etwas baut.

Das Versprechen von CRDTs (Conflict-free Replicated Data Types) ist verlockend: Datenstrukturen, die sich ohne Konflikte automatisch zusammenführen, kein zentraler Server nötig, und Konvergenz dank Mathematik garantiert. Die Realität ist allerdings chaotischer, wie mehrere Teams feststellen mussten, nachdem sie sich für CRDTs in ihren kollaborativen Editoren entschieden hatten. Die Theorie ist wunderschön. Die Umsetzung ist brutal.

Das Problem: Gleichzeitige Änderungen

Die grundlegende Herausforderung: Zwei Nutzer bearbeiten dasselbe Dokument gleichzeitig, und zwischen ihnen liegt Netzwerklatenz. Nutzer A fügt „Hello“ an Position 5 ein. Nutzer B, der A’s Änderung noch nicht gesehen hat, löscht das Zeichen an Position 5. Wie sollte das Endergebnis aussehen?

Das ist mehrdeutig. Soll sich B’s Löschung auf das Zeichen beziehen, das vor A’s Einfügung an Position 5 stand, oder auf das danach? Im ersten Fall wird das ursprüngliche Zeichen entfernt, und „Hello“ bleibt stehen. Im zweiten Fall verschwindet das „H“ aus „Hello“. Beide Interpretationen sind vertretbar. Das System muss sich für eine entscheiden und sicherstellen, dass alle Clients zum selben Ergebnis konvergieren. Divergenz bedeutet, dass zwei Nutzer unterschiedliche Dokumente sehen, und genau dieser Fehler ist unverzeihlich.

The convergence problem:
Initial document: "The quick brown fox"
^ position 10
User A (at time T):  Insert "very " at position 10
User B (at time T):  Delete character at position 10
A sees locally: "The quick very brown fox"
B sees locally: "The quick rown fox"  (deleted 'b')
Now A receives B's operation: delete at position 10
But A already inserted 5 chars at position 10...
Should B's delete now apply at position 10? (deletes 'v' from 'very')
Or at position 15? (deletes 'b' from 'brown' — the original target)
Both A and B must arrive at the same document.
This is the problem OT and CRDTs solve differently.

Operational Transformation (OT)

OT, der ältere Ansatz (1989), löst das Problem, indem Operationen gegeneinander transformiert werden. Wenn A eine Operation „Löschen an Position 10“ von B erhält, prüft das System von A, welche Operationen A bereits angewendet hat, die B noch nicht kennt. Es transformiert B’s Operation entsprechend: Da A an Position 10 fünf Zeichen eingefügt hat, muss B’s Löschung nun an Position 15 greifen, weil sich das ursprüngliche Zielzeichen nach rechts verschoben hat.

Das funktioniert, und Google Docs setzt darauf. Das Problem sind die Transformationsfunktionen. Bei einem Texteditor mit Einfüge- und Löschoperationen musst du für jedes Paar von Operationen festlegen, wie sie sich gegeneinander transformieren. Bei zwei Operationstypen sind das vier Fälle. Kommen Formatierungen, Tabellen, Bilder, Listen und Kommentare hinzu, explodiert die Zahl der Fälle kombinatorisch. Jeder Fall muss korrekt sein, und subtile Fehler führen zu Dokumentdivergenz, die sich kaum reproduzieren und debuggen lässt.

OT erfordert außerdem traditionell einen zentralen Server, der eine totale Reihenfolge der Operationen festlegt. Ohne Server können gleichzeitige Operationen von verschiedenen Clients in unterschiedlicher Reihenfolge transformiert werden, was zu unterschiedlichen Ergebnissen führt. Google kann sich einen zentralen Server für Docs leisten. Eine Peer-to-Peer-Anwendung kann OT nicht ohne Weiteres nutzen.

CRDTs: Das theoretische Versprechen

CRDTs verfolgen einen grundlegend anderen Ansatz. Statt Operationen zu transformieren, nutzen sie Datenstrukturen, bei denen alle möglichen Reihenfolgen beim Zusammenführen dasselbe Ergebnis liefern. Das ist eine mathematische Garantie: Ist die Datenstruktur ein gültiger CRDT, ist Konvergenz automatisch gegeben. Keine Transformationsfunktionen, kein zentraler Server, keine Abhängigkeit von einer Reihenfolge.

Für Texteditoren sind die wichtigsten CRDT-Varianten RGA (Replicated Growable Array) und ähnliche Sequenz-CRDTs. Statt Positionen zu verfolgen, die sich bei jeder Änderung verschieben, weist jedes Zeichen eine eindeutige, global geordnete ID zu. Einfügungen erzeugen neue IDs zwischen bestehenden. Löschungen markieren eine ID als Tombstone, sie wird also nicht entfernt. Dazu später mehr.

CRDT sequence representation:
Document: "cat"
Internal representation (simplified):
ID: (A,1) → 'c'   (user A, logical clock 1)
ID: (A,2) → 'a'   (user A, logical clock 2)
ID: (A,3) → 't'   (user A, logical clock 3)
User B inserts 'h' between 'c' and 'a':
ID: (B,1) → 'h'   position: between (A,1) and (A,2)
Document: "chat"
User A (concurrently) inserts 'r' between 'c' and 'a':
ID: (A,4) → 'r'   position: between (A,1) and (A,2)
Both IDs go between the same characters.
The CRDT uses a deterministic tie-breaking rule
(e.g., higher user ID wins) to order them.
Final document: "chart" or "chrat"
(deterministic — all clients get the same result)

CRDTs: Die praktische Realität

Das CRDT-Versprechen, also konfliktfrei, dezentral und mathematisch garantierte Konvergenz, ist real. Die technischen Herausforderungen sind aber erheblich.

Tombstones häufen sich an. Wenn du ein Zeichen in einem CRDT löschst, kann es nicht aus der Datenstruktur entfernt werden. Andere Replikate haben die Löschung womöglich noch nicht gesehen und brauchen die ID, um ihre eigenen Änderungen korrekt einzuordnen. Gelöschte Zeichen werden daher als Tombstones markiert: unsichtbar, aber weiterhin vorhanden. Ein stark bearbeitetes Dokument sammelt Tausende Tombstones an. Ein Dokument mit 1000 Zeichen kann durch die Editierhistorie 50.000 Tombstones haben. Das blpress Speicher auf und bremst Operationen aus.

Der Metadaten-Overhead ist enorm. Jedes Zeichen braucht eine eindeutige ID (Nutzerkennung plus logischer Zeitstempel), Zeiger auf benachbarte IDs und ein Tombstone-Flag. Die Metadaten pro Zeichen können 50 bis 100 Byte groß sein. Bei einem Dokument von 100 KB kann die CRDT-Repräsentation 5 bis 10 MB umfassen. Das ist beim Synchronisieren relevant, denn den vollständigen CRDT-Zustand über das Netzwerk zu schicken, ist teuer.

Die Performance sinkt mit der Historie. Operationen auf einem Sequenz-CRDT sind nicht O(1). Das Einfügen eines Zeichens erfordert, die richtige Position in der nach IDs sortierten Sequenz zu finden, und das hängt von der Gesamtzahl der IDs ab, Tombstones eingeschlossen. Bei Dokumenten mit langer Editierhistorie wird das messbar langsam.

Intention zu bewahren ist schwer. CRDTs garantieren Konvergenz, also dass alle Replikate denselben Zustand erreichen. Aber erreichen sie den richtigen Zustand? Bearbeiten zwei Nutzer gleichzeitig dasselbe Wort, verschachtelt das CRDT deren Zeichen deterministisch. Das Ergebnis ist konvergent, kann aber unsinnig sein. OT lässt sich so entwerfen, dass die Änderung eines Nutzers intakt bleibt und die des anderen drumherum angewendet wird. CRDTs führen mechanisch zusammen.

Yjs und der praktische Mittelweg

Yjs ist die beliebteste CRDT-Bibliothek für JavaScript und steckt in den kollaborativen Funktionen vieler Webanwendungen. Sie ist sauber umgesetzt und begegnet vielen theoretischen CRDT-Problemen mit praktischen Optimierungen. Eine kompakte binäre Kodierung reduziert den Metadaten-Overhead, und das Aufräumen von Tombstones funktioniert, solange alle Clients online sind.

Yjs ist aber kein Zauberwerk. Teams, die es einsetzen, merken schnell, dass eine CRDT-Bibliothek das Konvergenzproblem löst, nicht aber das Kollaborationsproblem. Du brauchst trotzdem: einen Signaling-Server für die Peer-Erkennung, eine Persistenzschicht für Offline-Änderungen, Konfliktlösung für High-Level-Operationen (was passiert, wenn zwei Nutzer denselben Abschnitt umstrukturieren?), Präsenz-Tracking (Cursor, Markierungen), Undo/Redo, das die Änderungen anderer Nutzer respektiert, und Rechteverwaltung.

Manche Teams sind nach dem Bau eines kollaborativen Editors auf Yjs zu dem Schluss gekommen, dass der CRDT-Ansatz mehr Komplexität bringt, als sie brauchen. Hat deine Anwendung einen zentralen Server (und die meisten haben einen), sind OT oder noch einfachere Ansätze wie Last-Write-Wins mit Konflikterkennung oft praktikabler. CRDTs glänzen bei echten Peer-to-Peer-Szenarien: Offline-first-Anwendungen, Local-first-Software und Systeme, in denen keine zentrale Instanz vorausgesetzt werden kann.

Was die meisten Anwendungen tun sollten

Wenn du kollaboratives Editieren in deine Anwendung einbaust, hilft dir dieser pragmatische Entscheidungsrahmen.

• Du hast einen zentralen Server und kleine Dokumente: Nimm OT. Googles Ansatz funktioniert. Bibliotheken wie ShareDB implementieren OT für Node.js. Der zentrale Server vereinfacht fast alles: Reihenfolge, Persistenz, Konfliktlösung, Rechte.
• Du brauchst Offline-Unterstützung oder Peer-to-Peer: Nimm CRDTs (Yjs oder Automerge). CRDTs sind der einzige Ansatz, der echtes Offline-Editieren und Peer-to-Peer-Synchronisation korrekt abdeckt. Den Metadaten-Overhead und die Ansammlung von Tombstones nimmst du als Preis der Dezentralisierung in Kauf.
• Deine Mitarbeiter bearbeiten selten dieselbe Stelle gleichzeitig: Du brauchst womöglich keines von beiden. Einfaches Sperren (nur ein Editor pro Abschnitt) oder Last-Write-Wins mit einer guten Konfliktoberfläche deckt viele reale Zusammenarbeitsszenarien ab, ohne die Komplexität von OT oder CRDTs.
• Du baust einen Google-Docs-Konkurrenten: Dafür brauchst du ein Team verteilter Systemingenieure und jahrelange Entwicklungszeit. Das ist kein Wochenendprojekt. Die scheinbare Einfachheit kollaborativen Editierens verbirgt außergewöhnliche Komplexität.

Die ehrliche Bilanz

Kollaboratives Editieren gehört zu den Problemen, bei denen die Schwierigkeit nicht offensichtlich ist. Der Normalfall, zwei Nutzer mit nicht überlappenden Änderungen, funktioniert mit fast jedem Ansatz. Die harten Fälle, also gleichzeitige Änderungen an derselben Stelle, Offline-Editieren mit späterer Synchronisation oder komplexe Dokumentstrukturen wie Tabellen, verschachtelte Listen und eingebettete Objekte, erfordern ein tiefes Verständnis der Trade-offs zwischen OT und CRDTs.

Keiner der beiden Ansätze ist eindeutig besser. OT ist mit Server einfacher, ohne Server schwerer. CRDTs funktionieren ohne Server, bringen aber Metadaten-Overhead und Tombstone-Ansammlung mit sich. Beide brauchen sorgfältige Technik jenseits des Kernalgorithmus, und diese Technik (Präsenz, Persistenz, Rechte, Undo) ist oft schwerer als das Konvergenzproblem selbst.

Die Branche bewegt sich langsam auf einen pragmatischen Hybrid zu: CRDTs für das Datenmodell (automatische Zusammenführung mit Garantien), ergänzt um einen Server für die Koordination (Präsenz, Rechte, Garbage Collection). Das bietet die Vorteile beider Welten, mathematische Konvergenz plus praktische Infrastruktur. Aber es bringt auch die Komplexität beider Welten mit sich, und deshalb bleibt kollaboratives Editieren nach 35 Jahren Forschung ein schweres Problem.