Kollaborative Textbearbeitung: Implementierung ohne CRDT oder OT

• Vorstellung eines neuen Ansatzes zur Lösung des Problems kollaborativer Textbearbeitung, der sich auch ohne komplexe Algorithmen umsetzen lässt
• Vermeidet die Komplexität und Einschränkungen bestehender CRDT- und OT-Ansätze und nutzt stattdessen ein einfaches, ID-basiertes Einfügeverfahren
• Da der Server dabei direkt angewiesen wird, was wo eingefügt werden soll, ist dieser Ansatz besonders flexibel
• Zur optimistischen lokalen Aktualisierung wird eine Server-Reconciliation-Strategie verwendet, um Probleme bei der Zustandssynchronisierung zu lösen
• Mit seiner Skalierbarkeit und Verständlichkeit stellt dieser Ansatz eine direkt implementierbare Alternative für die Entwicklung kollaborativer Apps dar

---

Collaborative Text Editing without CRDTs or OT

Problemstellung

• Kollaborative Textbearbeitung ist eine sehr schwierige Funktion, insbesondere bei gleichzeitiger Bearbeitung tritt das Problem verzogener Textindizes (index rebasing) auf
• Die bisherigen Ansätze CRDT (Conflict-free Replicated Data Type) und OT (Operational Transformation) beruhen jeweils auf komplexen mathematischen Modellen
  • CRDT: Verfolgt jedes Zeichen per ID und sortiert auf Baum-Basis
  • OT: Passt Indizes dynamisch an, um Eingaben anderer Nutzer zu berücksichtigen
• Beide Ansätze sind stark von Bibliotheken abhängig und lassen sich nur schwer an individuelle Anforderungen von Entwicklern anpassen

Neuer Ansatz

Kernidee

• Jedes Zeichen erhält eine eindeutige ID (UUID), und der Client sendet dem Server den Befehl, „welches Zeichen nach welcher ID eingefügt werden soll“
• Beispiel: "insert ' the' after f1bdb70a" → f1bdb70a ist die ID des Zeichens, nach dem eingefügt wird
• Der Server interpretiert dies direkt und fügt entsprechend ein, wodurch Konflikte vermieden werden

Umgang mit Löschungen

• Auch beim Löschen eines Zeichens bleibt dessen ID in der internen Liste erhalten und wird über ein isDeleted-Flag verarbeitet
• Im sichtbaren Text erscheint es nicht mehr, Referenzen bleiben jedoch erhalten, sodass spätere Operationen weiterhin möglich sind

Client-Verarbeitung und optimistische Updates

• Nutzer müssen das Ergebnis direkt nach der Eingabe sehen können, daher wird es vor der Serverantwort lokal angewendet (optimistisches Update)
• Mithilfe einer Server-Reconciliation-Strategie wird dabei:
  1. jede lokale, noch unbestätigte Operation zurückgenommen
  2. die Server-Operation angewendet
  3. anschließend die lokalen Operationen erneut angewendet, um den final synchronisierten Zustand zu erhalten

Unterschiede zu bestehenden Ansätzen

• CRDT enthält einen Algorithmus zur automatischen ID-Sortierung, während dieser Ansatz dem Server nur die explizite Einfügeposition übermittelt
• Das Ergebnis ist insgesamt einfacher und sorgt für ein klar nachvollziehbares Verhalten

Behandlung gleichzeitiger Einfügungen

• Beispiel: In „My name is“ fügen zwei Nutzer gleichzeitig „ Charlie“ und „ Dave“ an derselben Stelle ein
  • Je nach Reihenfolge des Servereingangs wird daraus „My name is Dave Charlie“
• Das gilt als natürliches Verhalten; im Unterschied zu manchen CRDT-Ansätzen kommt es nicht zu einem Vermischen auf Zeichenebene (interleaving)

Unterstützung flexibler Operationen

• Über einfaches Insert/Delete hinaus lassen sich verschiedene weitere Operationen unterstützen:
  • insert-before
  • bedingtes Einfügen (z. B. „u“ nur hinzufügen, wenn „color“ vorhanden ist)
  • Neupositionierung bei Drag & Drop usw.
• Diese Flexibilität ist nicht an festgelegte mathematische Eigenschaften gebunden

Unterstützung für Rich Text

• Bereiche lassen sich ID-basiert definieren, um Formatierungen anzuwenden („fett von ID X bis ID Y“ usw.)
• Bei der Integration mit Editoren wie ProseMirror lassen sich Konflikte auf einfache Weise lösen
• Die Grundstruktur bleibt erhalten, während Rich-Text-Funktionen ergänzt werden können

Verteilte Version (Decentralized)

• Auch ohne zentralen Server kann der Ansatz funktionieren, wenn die Reihenfolge der Operationen über Lamport-Zeitstempel bestimmt wird
• In diesem Fall zeigt er ähnliche Ergebnisse wie CRDTs wie RGA, Peritext, Fugue
• Auch ohne Bäume oder mathematische Beweise lässt sich eine Konsistenz auf CRDT-Niveau erreichen

Begleitbibliothek: Articulated

• Eine Bibliothek für den effizienten Umgang mit Strukturen der Form Array<{ id, isDeleted }>
• Verwendet statt UUIDs eine Struktur aus { bunchId, counter }, um den Speicherverbrauch zu optimieren
• Eine B+Tree-basierte Struktur unterstützt schnelles Finden und Einfügen per ID
• Als persistente Datenstruktur passt sie gut zu Server-Reconciliation

Fazit

• Dieser Ansatz ist im Vergleich zu CRDT/OT leichter zu verstehen und direkt implementierbar
• Verschiedene Bearbeitungsfunktionen, Berechtigungen, Einschränkungen und Formatierungen lassen sich frei anwenden, was für die praktische Umsetzung kollaborativer Editoren vorteilhaft ist
• Die Bibliothek Articulated wird als Werkzeug bereitgestellt, um diesen Ansatz in der Praxis nutzbar zu machen

[GN⁺]

Hacker-News-Kommentare

• Der Algorithmus wirkt ziemlich clever. Es wird beschrieben, wie jedem Zeichen eine global eindeutige ID (z. B. UUID) zugewiesen wird, sodass es jederzeit konsistent referenziert werden kann; der Client teilt dem Server mit, dass ein Zeichen nach einer bestimmten ID eingefügt werden soll, der Server verarbeitet die Einfügung an dieser Position, Löschungen werden nur auf dem Bildschirm ausgeblendet und intern zur Positionsreferenz weiter aufbewahrt. Man kann sich vorstellen, dass sich dieser Ansatz nicht nur für Texteditoren, sondern auch für andere Bereiche wie die Synchronisierung von Spielwelten nutzen lässt.

  • Das ist im Wesentlichen wohl ein vereinfachtes CRDT; das Tie-Breaking und die Verwendung eines zentralen Servers erinnern an die Architektur aus der Google-Wave-Zeit.
  • Es wird die Frage aufgeworfen, ob das Beschriebene nicht einfach ein CRDT ist.
  • Die Reaktion lautet, dass daran eigentlich nichts besonders neu sei: Einen zentralen Prozess zu nutzen, um ein verteiltes System zu serialisieren, ist ein traditioneller Ansatz, und Probleme wie Netzwerkpartitionen (CAP usw.) oder ein Single Point of Failure bestehen weiterhin. Ergänzend wird gefragt, ob der Artikel etwas zur Performance sagt.
  • Ein scherzhafter Kommentar wünscht viel Glück bei Massenoperationen wie ctrl+a, ctrl+x und ctrl+v.

• Es wird die Sicht geteilt, dass sich der Unterschied zu CRDTs darin zeigt, dass ein zentraler Server Synchronisationsaufgaben wie die Sortierung der Reihenfolge übernimmt und man der eigentlichen Datenstruktur keine vorab festgelegte Ordnung geben muss. Da nur Kommunikation zwischen Client und Server stattfindet, kann der Server zunächst alle lokalen Operationen des Clients verarbeiten und erst danach Remote-Updates senden.

• Es überrascht jemanden, dass nicht über andere Datenstrukturen wie dict/map oder Arrays beliebiger Typen gesprochen wird. In realen Apps braucht man oft mehr verschiedene kollaborative Datenstrukturen als reine kollaborative Textbearbeitung. Es gibt interessante Beispiele wie Datenvalidierung, partielles Laden oder Operationen auf höherer Ebene, und es wird vermutet, dass solche Funktionen in Yjs usw. weniger wegen CRDTs selbst fehlen, sondern eher weil sie generell schwer umzusetzen sind.

  • Es wird den Ausführungen zu verschiedenen Datenstrukturen stark zugestimmt: Wenn man ein Array „atomarer“ Objekte erstellt und Änderungen an den Properties der Objekte nicht möglich sind, muss man statt Strings nur den Typ austauschen; Änderungen innerhalb eines Objekts seien lediglich wegen Problemen bei Traversierung/Speicherung von Bäumen etwas komplexer. Außerdem wird erwartet, dass Nutzer von Helper-Libraries eigene Logik für ein „semantisches Modell“ wie einen Hook anschließen können, um ungültige Zustände zu verhindern, etwa wenn ein Todo isDone: true und zugleich state: inProgress hat. Das stehe in einem ähnlichen Kontext wie die im verlinkten Beitrag erwähnte Rich-Text-Formatierung.

  • CRDTs führen bei Konflikten eine Zusammenführung durch, indem sie konsistent eine Seite auswählen. Das Problem ist, dass dabei Datenverlust oder ungültige Daten entstehen können. Man solle sich das wie einen git merge vorstellen, bei dem Konflikte immer einfach durch die Wahl einer Seite gelöst werden — das würde in den meisten Fällen zu falschen Ergebnissen oder Compilerfehlern führen. Es wird darauf hingewiesen, dass sich durch rein automatisierte Auflösung Originalität und Bedeutung der Daten womöglich nicht angemessen bewahren lassen; darin wird ein Grund gesehen, warum sich CRDTs bislang nicht breit durchgesetzt haben.

• Jemand fand den erklärenden Beitrag zu diesem Ansatz sehr interessant, habe selbst schon seit Langem dieselbe Methode verwendet und finde es bemerkenswert, dass sie in der Forschung fast nie erwähnt wird. Die Person sagt, sie habe das in einer dezentralisierten Umgebung als CRDT implementiert und dabei Eigenschaften wie Assoziativität, Immutability und Vertauschbarkeit erhalten können.

  • Es wird gefragt, welchen konkreten Vorteil man tatsächlich gewonnen hat, wenn dies als Alternative zu CRDTs entwickelt wurde.

• Es wird versucht, die Kernaussage des Artikels so zusammenzufassen, dass wirklich komplexe CRDTs/OT nur dann nötig sind, wenn es keinen zentralen Server gibt.

  • Auch ohne zentralen Server könne man die Komplexität von CRDT/OT vermeiden, wenn man in einem verteilten System einen Weg hat, sich auf eine globale Reihenfolge der Operationen zu einigen und diese anzuwenden. Ein verlinkter Beitrag wird genannt. Natürlich ist auch das wiederum eine Form von CRDT (in generalisierter Form), aber es wird betont, dass Undo/Replay nicht trivial zu implementieren ist und man es als Alternative in Betracht ziehen kann, wenn traditionelle CRDT/OT-Strukturen noch komplexer wirken.

  • Es wird angemerkt, dass OT (Operational Transformation) einen zentralen Server benötigt.

• Im Kern ist es ebenfalls ein CRDT, nur dass der zentrale Server die Reihenfolge der auf das Dokument angewandten Operationen festlegt. Google Docs und Zoho Writer arbeiten ebenfalls mit OT plus zentralem Server. Es wird eingeräumt, dass der vorgestellte Ansatz zwar nach CRDT-Stil aussieht, für einen tatsächlich serverbasierten Dienst aber praktischer ist.

• Eine Meinung lautet, dass der Hauptunterschied zu CRDTs wie Automerge in der Art der Server-Koordination liegt. Automerge sortiert gleichzeitige Einfügungen anhand einer definierten Ordnung aus Sequenznummern und Agent-ID, während der hier beschriebene Ansatz sie in der Reihenfolge des Eintreffens auf dem Server verarbeitet. Unter Verweis auf den beschriebenen Artikel wird zitiert: „Keine fancy Algorithmen nötig, also einfacher.“ Da viele Dienste ohnehin einen zentralen Server einsetzen, wirkt das praktisch, aber weil bei der Server-Koordination lokales Undo/Replay nötig ist, bleibt unklar, wie viel einfacher es in der Praxis wirklich ist.

  • Auch „rewind/replay“ wirke schon wie ein fancy Ansatz, und ein Persistent B+Tree sei ebenfalls nicht gerade simpel.

  • Auch Automerge kann intern letztlich eine globale Reihenfolge herstellen, verarbeitet Textoperationen in der Praxis jedoch mit traditionellen CRDT-Ansätzen (RGA usw.). Der Grund sei gerade, dass Undo/Replay nicht einfach ist.

• Es wirkt wie ein nicht optimiertes CRDT — der scherzhafte Vergleich lautet, als würde man einfach max set size=1 setzen und es dann drauflos benutzen.

  • Das Reduzieren der Komplexität sei im Gegenteil attraktiv, weil es näher an den tatsächlich auftretenden Operationen liege und dadurch einfacher wirke. Auch ohne Optimierung habe der Ansatz seinen Reiz.

• Wenn man Server-Reconciliation verwendet, besteht das Risiko, dass das Merge-Problem auf Client-Seite schwierig wird. Es wird gefragt, wie sich die UX des Editors flüssig halten lässt, wenn Server-Updates nacheinander eintreffen. Was passiert etwa, wenn eine Einfügeanfrage fehlschlägt — wird sie erneut versucht, und was macht man, wenn in der Zwischenzeit andere Updates eintreffen? Als vorgeschlagene Lösungen werden das Zurückspulen und erneute Anwenden des Edit-Verlaufs oder das Warten mit anschließendem Queue-Flush genannt. Aus Frontend-Sicht scheint es etliche nicht explizit behandelte UI/UX-Edge-Cases zu geben, weshalb CRDTs am Ende sogar einfacher sein könnten. Insbesondere wird gefragt, wie die Benutzererfahrung in instabilen Netzwerken wie etwa in der U-Bahn aussieht.

  • Es wird erklärt, dass ProseMirror und aktuelles CodeMirror Dokumentänderungen in Form von Steps verwalten und für jeden Schritt die Positionsinformationen (position map) aktualisieren, sodass sich die Schritte des Puffers auf das Dokument anwenden lassen. Es wird betont, dass das in realen kollaborativen Editoren praktisch gut funktioniert; außerdem wird ein weiterführender Link geteilt.

• Jemand schlägt vor, dass man mit einem LLM (z. B. einem 4b-Modell) versuchen könnte, Merge-Konflikte jenseits einfacher Fälle zu lösen, ohne besonders komplexe CRDTs oder OT zu verwenden. Die Energieeffizienz könnte zwar schlecht sein, aber überraschenderweise könnte es funktionieren.

  • Bei einem Konflikt wie im Beispiel, bei dem zu „My name is“ jeweils „Charlie“ und „Dave“ nach „is“ eingefügt werden, stellt sich die Frage, wie ein LLM das zusammenführen würde.