Systemdesign für kollaboratives Editieren: OT vs. CRDT, Presence und Sync

Zwei Personen tippen im selben Moment in denselben Absatz. Nach einem Sekundenbruchteil zeigen beide Bildschirme denselben Text, und keine Eingabe ist verschwunden. Damit das funktioniert, muss man ein spezifisches Problem lösen, gleichzeitige Änderungen an gemeinsamem Zustand, plus eine Reihe gewöhnlicher Infrastrukturprobleme: Routing, Persistenz, Presence und Reconnect.

Dieser Beitrag entwirft einen kollaborativen Echtzeit-Editor: das Nebenläufigkeitsproblem an einem durchgerechneten Beispiel, Operational Transformation (OT) und Conflict-free Replicated Data Types (CRDTs) im Vergleich, den serverautoritativen Ansatz, den Figma nutzt, und die Architektur drumherum, mit einem Diagramm.

Das Kernproblem in fünf Zeichen

Fang mit dem Dokument ABC an. Positionen zählen ab null.

• Alice fügt X an Position 1 ein; auf ihrem Bildschirm steht AXBC.
• Im selben Moment löscht Bob Position 2, das C; auf seinem steht AB.

Jeder Client empfängt nun die Operation des anderen und wendet sie unverändert an:

• Bob wendet „füge X an 1 ein“ auf AB an und erhält AXB.
• Alice wendet „lösche Position 2“ auf AXBC an, löscht damit das B und erhält AXC.

Die Dokumente sind auseinandergelaufen, und Alices Kopie hat ein Zeichen verloren, das niemand gelöscht hat. Jeder kollaborative Editor existiert, um das zu verhindern. Es gibt zwei Familien von Lösungen.

Operational Transformation

OT behält Operationen als Positionen und transformiert jede eingehende Operation gegen die nebenläufigen Operationen, die sie noch nicht gesehen hat. Bobs „lösche Position 2“ entstand vor Alices Einfügung an Position 1, die alles dahinter um eine Stelle nach rechts verschiebt. Gegen die Einfügung transformiert, wird daraus „lösche Position 3“, und aus Alices AXBC wird AXB, genau wie bei Bob.

OT-Systeme in Produktion nutzen einen zentralen Server, der Operationen ordnet. Der Ansatz geht auf das Jupiter-System von 1995 zurück, und Google Docs beschrieb ihn, als es 2010 seinen Editor neu baute:

1. Jeder Client schickt seine Operationen mit der Server-Revision, auf der sie basieren.
2. Der Server transformiert jede Operation gegen alles, was er seit dieser Revision akzeptiert hat, vergibt die nächste Revisionsnummer und verteilt das Ergebnis.
3. Jeder Client transformiert eingehende Operationen gegen seine eigenen, noch unbestätigten.

OTs Stärken sind kompakte Operationen und eine lange Erfolgsgeschichte bei Text. Seine Schwäche sind die Transformationsfunktionen selbst: Bei Rich Text, Tabellen und verschachtelten Strukturen jedes Paar von Operationstypen richtig hinzubekommen, ist berüchtigt schwierig, und das Design braucht einen Server, der die Reihenfolge festlegt.

CRDTs

Ein CRDT ist ein Datentyp, der so entworfen ist, dass nebenläufige Updates in beliebiger Reihenfolge angewendet werden können und jede Replik trotzdem konvergiert; formalisiert wurde das 2011 von Shapiro und Kollegen. Bei Text bekommt jedes eingefügte Zeichen einen eindeutigen, geordneten Bezeichner, etwa eine Client-ID und einen Zähler, und eine Einfügung sagt „nach dem Zeichen mit der ID soundso“ statt „an Position 1“. Löschungen markieren Zeichen als entfernt und hinterlassen Tombstones. Weil Operationen auf stabile IDs statt auf wandernde Positionen verweisen, gibt es nichts zu transformieren.

Im Beispiel sagt Alices Einfügung „X kommt nach A“ und Bobs Löschung „entferne C“. In beliebiger Reihenfolge angewendet, landen beide Repliken bei AXB.

CRDT-Bibliotheken wie Yjs und Automerge machen das praxistauglich. Ihre Stärken: Es braucht keine zentrale Ordnung, also funktionieren Offline-Bearbeitung und Peer-to-Peer-Sync ganz natürlich, und Zusammenführen ist jederzeit möglich. Ihre Kosten: zusätzliche Metadaten pro Zeichen, Tombstones, die kompaktiert werden müssen, und Randfälle, in denen das zusammengeführte Ergebnis konsistent ist, aber nicht das, was einer der beiden Nutzer meinte. Ein Server bleibt nützlich für Zugriffskontrolle, Persistenz und Fan-out; er muss nur nicht die Reihenfolge festlegen.

Der serverautoritative Mittelweg

Nicht jeder Editor bearbeitet langen Text. Figma entschied sich weder für klassisches OT noch für echte CRDTs: Sein Server legt die Reihenfolge der Ereignisse fest, Dokumente sind Bäume aus Objekten mit Eigenschaften, und wenn zwei Personen dieselbe Eigenschaft desselben Objekts ändern, gewinnt der letzte Wert, den der Server empfängt. Seine Server betreiben für jedes Multiplayer-Dokument einen eigenen Prozess, und alle, die dieses Dokument bearbeiten, verbinden sich damit. Für Design-Tools, Tabellenkalkulationen und Boards, wo Konflikte pro Eigenschaft auftreten, ist das einfacher als beide Alternativen.

Die Architektur

Egal welchen Algorithmus du wählst, das System drumherum sieht ähnlich aus:

1. Clients verbinden sich per WebSocket mit einem Collaboration-Service und halten die Verbindung offen, solange das Dokument offen ist.
2. Jedes Dokument gehört genau einem Session-Server. Alle Clients von doc-123 müssen denselben Server erreichen, damit er Änderungen im Speicher ordnen oder zusammenführen kann. Ein Verzeichnis, zum Beispiel in Redis, ordnet Dokumente mit einem Lease Servern zu, und der Load Balancer oder eine Routing-Schicht schickt Verbindungen dorthin. Consistent Hashing auf der Dokument-ID funktioniert auch, solange nie zwei Server gleichzeitig glauben können, dass ihnen ein Dokument gehört.
3. Der Session-Server hält das Live-Dokument im Speicher, wendet jede eingehende Änderung an und verteilt sie an die anderen Clients.
4. Jede Änderung wird an ein dauerhaftes Op-Log angehängt, bevor der Server sie bestätigt. Ein regelmäßiger Snapshot des ganzen Dokuments geht in den Objektspeicher; ein Dokument zu laden heißt also, den neuesten Snapshot plus die Operationen danach zu lesen.
5. Berechtigungen werden beim Verbinden und bei jeder Operation geprüft; die Änderung eines Betrachters wird abgelehnt, nicht bloß ausgeblendet.

Kommentare, Versionsverlauf, Suche und Export sind separate Services, die das Op-Log konsumieren; sie gehören nicht auf den Echtzeitpfad.

Presence sind andere Daten

Cursor, Auswahlen und „wer ist hier“ ändern sich ständig, zählen nur im Moment und sind eine Minute später wertlos. Behandle Presence als flüchtig: Verteile sie über denselben Session-Server, drossle sie auf wenige Updates pro Sekunde und Nutzer, verwirf sie, wenn ein Client die Verbindung trennt, und schreib sie nie ins Op-Log. Yjs zum Beispiel hält Presence in einem separaten Awareness-Kanal neben dem Dokumentzustand.

Offline-Änderungen und Reconnect

Verbindungen brechen ständig ab, in Zügen und in Aufzügen. Der Client hält unbestätigte Operationen lokal und schickt sie beim Reconnect erneut:

• Mit OT schickt der Client seine ausstehenden Operationen mit der letzten Revision, die er gesehen hat; der Server transformiert sie gegen alles seitdem.
• Mit CRDTs tauschen Client und Server kompakte Zusammenfassungen dessen aus, was jeder gesehen hat, oft State Vectors genannt, und schicken einander nur die fehlenden Updates.

Lange Offline-Phasen sind die Stärke von CRDTs. Mit OT kann sich ein Client, der einen Tag offline war, zwar wieder verbinden, aber der Server muss seine Operationen gegen die eines ganzen Tages transformieren.

Skalierung und Ausfälle

• Heiße Dokumente. Ein Dokument mit Tausenden Betrachtern und wenigen Bearbeitern sollte den Session-Server nicht dazu bringen, jeden Tastendruck selbst an Tausende Sockets zu schicken; verteile an Betrachter über eine Pub/Sub-Schicht und bündle Updates.
• Absturz des Session-Servers. Clients verbinden sich neu, der Lease im Verzeichnis läuft ab, ein neuer Server lädt Snapshot und Op-Log, und Clients schicken ihre ausstehenden Operationen erneut. Dass nur dauerhaft protokollierte Änderungen bestätigt werden, macht das verlustfrei.
• Split Brain. Zwei Server, denen dasselbe Dokument gehört, würden widersprüchliche Reihenfolgen akzeptieren. Sichere die Eigentümerschaft mit dem Lease ab (Fencing) und lehne Schreibvorgänge eines Servers ab, dessen Lease abgelaufen ist.
• Undo muss deine eigene letzte Änderung rückgängig machen, nicht die deiner Kollegin, also wird es zu einer neuen inversen Operation, die wie jede andere transformiert oder zusammengeführt wird.

Das Collaboration-Diagramm

So liest du es:

• Zwei Clients verbinden sich per WebSocket über den Load Balancer.
• Das Redis-Verzeichnis sagt, welchem Session-Server doc-123 gehört; beide Verbindungen landen auf Server A.
• Server A ordnet Änderungen im Speicher oder führt sie zusammen und verteilt Änderungen und Presence an beide Clients zurück.
• Dauerhaftigkeit: Jede Änderung geht ins Op-Log in Postgres, bevor sie bestätigt wird; Snapshots gehen in den Objektspeicher.
• Der Identitätsanbieter prüft den Zugriff, wenn Clients sich verbinden; Server B besitzt andere Dokumente und zeigt, wie der Service horizontal skaliert.
• Der Markdown-Block vergleicht OT und CRDTs in drei Zeilen.

Echtzeitsysteme klar zeichnen

• Zeig die Eigentümerschaft. Die wichtigste einzelne Tatsache hier ist, dass ein Dokument genau einem Server gehört; zeichne das Verzeichnis und das Routing.
• Trenne dauerhafte und flüchtige Daten. Zeichne Op-Log und Snapshots, und beschrifte Presence als nicht persistiert.
• Zeichne mindestens zwei Clients. Nebenläufigkeit ist das ganze Problem; ein einzelner Client versteckt es.
• Markiere den Bestätigungspunkt: Eine Änderung ist sicher, sobald sie im Op-Log steht.

Für langlebige Verbindungen und Fan-out deckt das Architekturdiagramm einer Chat-App ähnliches Terrain ab. Dokumente zu Servern zu routen, wendet die Ideen aus dem Load-Balancer-Diagramm an, und die allgemeine Methode steht im System-Design-Diagramm-Beispiel.

In Archboard nachbauen

1. Melde dich mit Google oder GitHub an und leg ein Diagramm an.
2. Füge zwei Gerät-Nodes aus dem Netzwerk-Pack für die Clients hinzu und einen Cloud-Lastverteiler aus dem Cloud-Pack als WebSocket-Eingang.
3. Füge einen Rahmen aus dem Basis-Pack für den Collaboration-Service hinzu, darin zwei Recheninstanz-Nodes: Session-Server A, dem doc-123 gehört, und Session-Server B.
4. Füge einen Redis-Node aus dem Daten-Pack für das Dokumentverzeichnis hinzu, einen Postgres-Node für das Op-Log und einen Objektspeicher-Node aus dem Cloud-Pack für Snapshots.
5. Füge einen Identitätsanbieter aus dem Sicherheit-Pack hinzu und verbinde alles mit beschrifteten Kanten: WebSocket, Änderungen und Presence, Anhängen, Snapshot, Lease.
6. Füge einen Markdown-Block aus dem Basis-Pack mit der Zusammenfassung OT versus CRDT hinzu.

Das Beispiel nutzt 11 Diagramm-Nodes und bleibt damit im Free-Plan.

FAQ

Was ist der Unterschied zwischen OT und CRDT? OT transformiert nebenläufige Operationen gegeneinander, meist mit einem Server, der die Reihenfolge festlegt. CRDTs geben jedem Element eine stabile Identität, sodass Operationen kommutieren und Repliken in jeder Reihenfolge konvergieren, ohne zentrale Ordnung.

Nutzt Google Docs OT oder CRDTs? Google beschrieb die Neuentwicklung seines Editors 2010 als Operational Transformation, bei der ein Server Änderungen ordnet. Viele neuere Editoren nutzen CRDT-Bibliotheken wie Yjs oder Automerge.

Warum müssen sich alle Bearbeiter eines Dokuments mit demselben Server verbinden? Dieser Server hält das Live-Dokument und entscheidet über die Reihenfolge der Änderungen. Würden zwei Server Änderungen für ein Dokument unabhängig annehmen, müssten sie sich bei jedem Tastendruck abstimmen.

Wie wird Presence gespeichert? Meistens gar nicht. Cursor und Auswahlen werden in Echtzeit verteilt, gedrosselt und verworfen, wenn ein Client die Verbindung trennt. Sie zu persistieren erzeugt Last und keinen Nutzen.

Kann ein kollaborativer Editor offline funktionieren? Ja. Clients reihen Operationen lokal ein und synchronisieren beim Reconnect. CRDTs bewältigen lange Offline-Phasen am natürlichsten; OT funktioniert auch, transformiert bei der Rückkehr aber mehr Operationen.

Kostenlos starten — ein Seat, keine Kreditkarte.