Kollaborative Textbearbeitung: Umsetzung ohne CRDT oder OT

 (mattweidner.com)
4 Punkte von GN⁺ 2025-05-23 | 1 Kommentare | Auf WhatsApp teilen
  • In kollaborativen Apps mit zentralem Server verschieben sich bei gleichzeitiger Bearbeitung die Positionen, wenn Text über Array-Indizes editiert wird. Deshalb wird jedem Zeichen eine global eindeutige ID zugewiesen und der Serverzustand über Operationen wie „nach einer bestimmten ID einfügen“ aktualisiert.
  • CRDT und OT, wie sie in realen Diensten eingesetzt werden, sind mächtig, aber Total-Ordering-Algorithmen bzw. Regeln zur Operationstransformation sind komplex und ihre interne Funktionsweise lässt sich nur schwer an App-Anforderungen anpassen.
  • Der vorgeschlagene Ansatz lässt Client und Server eine ID-Liste der Form Array<{ id: ID; char?: string; isDeleted: boolean }> halten; auch gelöschte Zeichen bleiben wie tombstones erhalten, damit spätere Referenzen auf Einfügepositionen nicht brechen.
  • Optimistische lokale Updates werden per Server Reconciliation behandelt: Beim Empfang einer Remote-Operation werden ausstehende lokale Operationen zunächst zurückgenommen, danach die Remote-Operation und anschließend die noch nicht bestätigten lokalen Operationen der Reihe nach erneut angewendet.
  • Behandelt werden außerdem die Reihenfolge gleichzeitiger Einfügungen, Rich-Text-Formatierung, verteilte Varianten und die Bibliothek Articulated; der Server kann über Einfügen und Löschen hinaus flexible Operationen definieren, die zur app-spezifischen Bedeutung passen.

Warum indexbasierte Bearbeitung bei gleichzeitiger Bearbeitung kaputtgeht

  • Bei kollaborativer Textbearbeitung sendet der Client die vom Nutzer eingegebene Operation an den Server, und der Server muss seinen autoritativen Zustand aktualisieren.
  • Wenn man Text als Zeichen-Array betrachtet und Operationen wie " the" an index 17 einfügen sendet, kann derselbe Index bis zum Eintreffen beim Server wegen Einfügungen anderer Nutzer auf eine andere Position zeigen.
    • Fügt Alice zum Beispiel weiter vorne " gray" ein, ist Bobs index 17 nicht mehr die ursprüngliche Position.
    • Der Server muss Bobs Operation auf index 22 rebasen.
  • Entscheidend ist, welche Operation ein Client an den Server sendet und wie der Server sie interpretieren muss, damit der Text auf eine „offensichtlich korrekte“ Weise aktualisiert werden kann.
  • Dieses Index-Rebase-Problem tritt nicht nur in Echtzeit-Kollaborations-Apps wie Google Docs auf, sondern auch in Webformularen, die Listeneinträge einfügen, oder in single-threaded lokalen Apps, die Inline-Kommentare oder Bearbeitungshistorien verwalten.

Wo CRDT und OT in der Praxis schwergewichtig werden

  • Bestehende Lösungen lassen sich grob in CRDT und OT einteilen.
    • CRDTs geben jedem Zeichen eine unveränderliche ID oder „Position“ und sortieren IDs über eine mathematische Totalordnung, etwa eine spezielle Baumtraversierung.
    • OT transformiert die Operationen selbst unter Berücksichtigung gleichzeitiger Bearbeitungen; im Beispiel wird aus Einfügen an index 17 ein Einfügen an index 22.
  • Beide Ansätze werden bereits in realen Diensten eingesetzt.
    • Google Docs verwendet OT.
    • Die CRDT-Bibliothek Yjs wird in vielen Apps genutzt.
  • Die Belastung entsteht durch konzeptionelle Komplexität.
    • Die Totalordnung von CRDTs für Textbearbeitung ist oft ein subtiler Algorithmus, der in wissenschaftlichen Arbeiten definiert wird.
    • OT-Algorithmen müssen algebraische „Transformation Properties“ erfüllen; die Zahl der Fälle wächst quadratisch, und ohne formale Verifikation treten häufig Fehler auf.
  • Komplexe Algorithmen machen auch die Implementierung komplex und führen meist dazu, dass man eine von Experten erstellte Bibliothek wie eine Netzwerk-Blackbox nutzt.
  • Wenn eine Bibliothek eine benötigte Funktion nicht vorgesehen hat, wird ihre monolithische Struktur zum Hindernis.
    • Bei großen Dokumenten nur die benötigten Teile in den Speicher laden und den Rest auf der Festplatte lassen
    • Subdokument-Berechtigungen wie Bearbeitungsrechte pro Absatz oder Rechte zur Nutzung bestimmter Formate serverseitig erzwingen
    • Vorgeschlagene Änderungen im Stil von Google Docs im Text oder daneben anzeigen
    • Text in einer Darstellung speichern, die sich einfach mit einem Key-Value-Store wie Replicache synchronisieren lässt
    • Neben Einfügen und Löschen auch Operationen wie Verschieben von Text, Manipulation des Dokumentbaums sowie Teilen und Zusammenführen von Absätzen unterstützen

Zeichen-IDs und der „insert after“-Ansatz

  • Die Grundidee ist, statt Array-Indizes jedem Zeichen eine global eindeutige ID zuzuweisen.
    • Die zentrale Datenstruktur hat die Form Array<{ id: ID; char: string }>.
    • Der Client sendet dem Server statt an index 17 einfügen eine Operation wie " the" nach f1bdb70a einfügen.
    • Der Server sucht die Ziel-ID und fügt die neuen Zeichen direkt dahinter ein.
  • Auch die IDs der neuen Zeichen müssen vom Client mit angegeben werden.
    • Beispiel: " the" mit ids [...] nach f1bdb70a einfügen
    • Wenn der Client IDs erzeugt, kann er neue IDs in nachfolgenden insert after-Operationen referenzieren, bevor die Serverantwort eingetroffen ist.
  • Wenn gelöschte Zeichen vollständig entfernt werden, kann die Einfügeposition verloren gehen.
    • Während Bob nach 26085702 einfügen will, könnte ein anderer Nutzer das Zeichen 26085702 löschen; dann weiß der Server nicht, wo eingefügt werden soll.
    • Der Server muss auch gelöschte IDs in seiner internen Liste behalten.
  • Die korrigierte Zustandsdarstellung sieht so aus:
Array<{ id: ID; char?: string; isDeleted: boolean }>
  • Der für Nutzer sichtbare Text kann erzeugt werden, indem nur nicht gelöschte Einträge aneinandergereiht werden.
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')

Verarbeitung von Einfügen und Löschen

  • Beim Eingeben eines Zeichens ist das Verhalten von Client und Server einfach.
    • Der Client findet before, also die ID des Zeichens direkt vor der Einfügestelle.
    • Er erzeugt für das neue Zeichen eine global eindeutige ID id, etwa eine UUID.
    • Er sendet dem Server eine Operation, char mit id nach before einzufügen.
    • Der Server sucht before einschließlich gelöschter Einträge und fügt direkt dahinter { id, char, isDeleted: false } ein.
  • Auch das Löschen von Zeichen wird ID-basiert verarbeitet.
    • Der Client findet die id des zu löschenden Zeichens.
    • Er sendet dem Server eine Operation, den Eintrag mit dieser ID zu löschen.
    • Der Server sucht den Eintrag und setzt, falls er noch nicht gelöscht ist, entry.isDeleted = true.
  • Dieser Ansatz löst direkt das Positionsproblem von Bearbeitungsoperationen, die an den Server gesendet werden, ohne CRDT- oder OT-Papers zu folgen.
  • Eine einfache Array-Implementierung kann ineffizient sein, weil für jedes Zeichen eine UUID gespeichert werden muss; Optimierungen behandelt Articulated.

Optimistische Updates und Server Reconciliation

  • Bei kollaborativer Bearbeitung im Stil von Google Docs muss der Nutzer das Ergebnis seiner Eingabe sofort sehen, ohne auf die Serverantwort zu warten.
  • Schwierig wird es, wenn der Client noch ausstehende lokale Operationen hat, die der Server nicht bestätigt hat, und gleichzeitig eine damit konkurrierende Remote-Operation vom Server empfängt.
  • In diesem Fall ist nicht zwingend ein CRDT nötig; es lässt sich mit Server Reconciliation lösen.
    1. Alle ausstehenden lokalen Operationen zurücknehmen und den Clientzustand auf die Perspektive des früheren Serverzustands zurückspulen
    2. Die Remote-Operation anwenden und den Client an den Serverzustand angleichen
    3. Die noch nicht bestätigten lokalen Operationen erneut anwenden
  • Eine einfachere Strategie ist Wait for Ack, bei der Remote-Operationen nicht verarbeitet werden, solange lokale Operationen ausstehen.
    • Bobs Client kann die erste Servernachricht ignorieren, bis er den Serverzustand erhält, in dem seine eigene Nachricht verarbeitet wurde.
    • Wenn Bob weiter tippt oder die Netzwerklatenz hoch ist, kann die Verzögerung unbegrenzt wachsen; das ist weniger echtzeitfähig als Server Reconciliation.

Unterschiede zu CRDTs

  • Der vorgeschlagene Ansatz teilt einige Eigenschaften mit CRDTs, weil jedes Zeichen eine ID bekommt und isDeleted-Markierungen verwendet werden.
  • Der Unterschied liegt im Umgang mit der Reihenfolge.
    • In diesem Ansatz sagt der Client dem Server, X nach Y einzufügen, und der Server führt das entweder genau so aus oder verarbeitet es auf eine andere, vom Entwickler definierte Weise.
    • In CRDTs für Textbearbeitung werden IDs durch komplexe Algorithmen sortiert.
  • Der Kernunterschied zwischen verschiedenen CRDTs für Textbearbeitung liegt ebenfalls in diesem ID-Sortieralgorithmus; dieser Ansatz umgeht genau diesen Teil.

Ergebnisse gleichzeitiger Einfügungen

  • Wenn mehrere Nutzer gleichzeitig an derselben Position tippen, wird das Ergebnis in der umgekehrten Reihenfolge angeordnet, in der der Server die Operationen empfangen hat.
  • Angenommen, der Text lautet "My name is", und Charlie gibt gleichzeitig " Charlie" ein, während Dave " Dave" eingibt.
    • Trifft Charlies Operation zuerst ein, erzeugt der Server "My name is Charlie".
    • Auch Daves Operation fügt hinter derselben ID des s in is ein, daher wird das Ergebnis "My name is Dave Charlie".
  • insert after-Operationen hinter derselben Ziel-ID werden also selbst ohne Gleichzeitigkeit in umgekehrter Reihenfolge des Serverempfangs angeordnet.
  • Trotzdem werden von links nach rechts getippte Wörter nicht auf Zeichenebene durcheinandergewürfelt.
    • Selbst wenn Dave jedes Zeichen als eigene Operation sendet, wird a nach D eingefügt und v nach a.
    • Der Serverzustand verändert sich etwa von "My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie".
  • Beim Tippen von rechts nach links kann der Ergebnistest verschränkt werden, wenn die Operationen von Charlie und Dave in verschränkter Reihenfolge beim Server eintreffen.
    • In der Praxis kann das passieren, wenn zwei Nutzer gleichzeitig online sind und die laufenden Bearbeitungen des jeweils anderen ignorieren.

Der Server kann flexiblere Operationen definieren

  • Mit Server Reconciliation kann der Server Client-Operationen praktisch beliebig verarbeiten, und der Client erreicht am Ende denselben Zustand.
  • Das steht im Gegensatz zu CRDT und OT, die nur Operationen zulassen, die strenge algebraische Regeln erfüllen.
  • Bei gleichzeitigen Einfügungen an derselben Position kann der Server auf verschiedene Weise reagieren.
    • Die Operation ignorieren und als no-op behandeln
    • Die ID zwar in die interne Liste aufnehmen, sie aber sofort als gelöscht markieren, sodass spätere Operationen von Dave die vorherige ID referenzieren können
    • Den Text einfügen, aber beide Wörter mit einem speziellen Format zur Überprüfung versehen
    • Daves Bearbeitung in einen „Vorschlag“ umwandeln, der neben dem Haupttext angezeigt wird
    • Ein LLM fragen, wie der Text korrigiert werden soll
  • Der Client kann auch Operationen senden, die die Nutzerintention besser ausdrücken.
    • insert before kann genutzt werden, um beim Erstellen einer Überschrift über einem Absatz zu vermeiden, dass die Überschrift mitten in gleichzeitige Einfügungen am Ende des vorherigen Absatzes gerät.
    • Eine fix typo-Operation kann Bedingungen ausdrücken wie: füge u nach dem o in color mit ID X ein, aber nur, wenn das umgebende Wort weiterhin color ist.
  • Der Server kann auch Operationen definieren, deren Einfügeposition sich nach dem Eintreffen beim Server selbst noch ändert.
    • Gleichzeitige Einfügungen an derselben Position können alphabetisch neu sortiert werden.
    • Fügt man eine move-Operation für Drag-and-drop hinzu, können insert after-Operationen innerhalb des verschobenen Textes auf den verschobenen Text angewendet werden statt auf seine ursprüngliche Position.

Verarbeitung von Rich-Text-Formatierung

  • Rich Text behandelt Inline-Formate wie Fettdruck, Schriftgröße und Hyperlinks.
  • Auch Bereichsformatierungen können statt mit Indizes über Zeichen-IDs ausgedrückt werden.
    • Beispiel: bold von ID X bis ID Y anwenden
    • Definiert man es als von ID X inclusive bis ID Y exclusive, können auch gleichzeitige Einfügungen am Bereichsende fett formatiert werden.
  • Bei Verwendung mit einem Rich-Text-Editor wie ProseMirror kann der Server die aktuellen Array-Indizes von ID X und Y finden und den lokalen ProseMirror-Zustand anweisen, den entsprechenden Bereich fett zu formatieren.
  • ProseMirror kann Fettdruck anschließend auch für Text beibehalten, der innerhalb dieses Bereichs eingefügt wird.
    • Der Server könnte dies je nach Einfügeoperation wie bold set to false aber auch anders behandeln.
  • Zum Verständnis der Semantik kollaborativen Rich Texts ist der Peritext essay eine hilfreiche Referenz.

Verteilte Varianten und Verbindung zu CRDTs

  • Bisher wurde angenommen, dass ein zentraler Server die Totalordnung der Operationen nach Empfangsreihenfolge festlegt und den autoritativen Zustand aktualisiert.
  • In Apps ohne zentralen Server oder mit optionalem Server kann Operationen auch verteilt eine endgültige Totalordnung zugewiesen werden.
    • Zum Beispiel werden Operationen über Lamport timestamps sortiert.
    • Jeder Client betrachtet das Ergebnis der bisher empfangenen Operationen in dieser Reihenfolge als autoritativen Zustand.
  • In diesem Fall funktionieren Zeichen-IDs und insert after-Operationen auch bei verteilter, „serverloser“ Reconciliation.
  • Technisch wird das Ergebnis dadurch zu einem CRDT für Textbearbeitung.
    • Denn es ist ein verteilter, eventual-consistent Algorithmus für kollaborative Textbearbeitung.
  • Je nach gewählter Ordnungsmethode entsteht eine Verbindung zu bestehenden CRDTs.
    • Sortiert man Operationen per Lamport timestamp, entspricht die Reihenfolge der Ergebnisliste RGA / Causal Trees.
    • Kombiniert man Lamport timestamps mit Formatierungsoperationen, ähnelt das Verhalten stark Peritext.
    • Verwendet man eine topologische Tiefensortierung, entspricht die Reihenfolge der Ergebnisliste Fugue.
  • Ein detaillierter Beweis für diese Äquivalenzbehauptung wurde nicht ausgearbeitet.

Articulated: Hilfsbibliothek für die Implementierung

  • In einer realen Implementierung wird der eigentliche Text möglicherweise an anderer Stelle gespeichert, etwa im ProseMirror-Zustand; für diesen Ansatz kann nur eine ID-Liste folgender Form nötig sein:
Array<{ id: ID; isDeleted: boolean }>
  • Für diese Liste werden vier Operationen häufig benötigt.
    • Umwandlung zwischen ID und aktuellem Array-Index
    • Einfügen einer neuen ID hinter einer angegebenen ID
    • Markieren einer ID als gelöscht
    • Serialisieren und Wiederherstellen des Zustands zur Speicherung
  • Ein einfaches Array ist für diese Operationen ungeeignet.
    • Operationen 1 bis 3 benötigen lineare Zeit.
    • Weil pro Zeichen ein Objekt und eine UUID gespeichert werden, sind Speicher- und Platzbedarf hoch.
  • Articulated ist eine kleine npm-Bibliothek, die dieselbe Funktionalität wie dieses Array bereitstellt.
  • Die zentrale Datenstruktur IdList nutzt ähnliche Optimierungen wie populäre CRDT-Bibliotheken für Textbearbeitung.
    • IDs haben die Form { bunchId, counter }, wobei bunchId eine UUID ist, die mehrere IDs gemeinsam nutzen können.
    • Wenn IDs derselben bunch nebeneinander liegen, wie im typischen Fall von links-nach-rechts-Einfügungen, werden sie im Speicher und im serialisierten Zustand als ein einziges Objekt gespeichert.
    • Die zentrale Datenstruktur ist kein Array, sondern ein B+Tree; dadurch liegen Methodenaufrufe bei log oder log^2.
  • IdList ist außerdem eine persistente Datenstruktur.
    • Der Client kann den zuletzt vom Server empfangenen Zustand und den optimistischen Zustand kostengünstig gemeinsam speichern.
    • Beim Empfang einer Remote-Operation lässt sich leicht auf den letzten Serverzustand zurückrollen.
  • Als zusätzliche Ressourcen gibt es die docs, frühe demos und IdListSimple, eine einfache Implementierung mit weniger als 300 SLOC.
  • IdListSimple lässt Optimierungen und Persistenz weg, ist aber funktional identisch und durch fuzz tests verifiziert.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-05-23
Meinungen auf Hacker News

  • Ziemlich sauber. Der Algorithmus hängt an jedes Textzeichen eine global eindeutige ID wie eine UUID, sodass es über die Zeit hinweg konsistent referenziert werden kann, statt über sich ständig ändernde Array-Indizes.
    Clients schicken „insert after“-Operationen an den Server, die auf eine bestehende ID verweisen, und der Server sucht die Ziel-ID und fügt das neue Zeichen direkt dahinter ein. Beim Löschen wird das Zeichen nur in der Anzeige ausgeblendet; für die Berechnung der „insert after“-Position bleibt es erhalten. Auch außerhalb der Textbearbeitung scheint das Potenzial zu haben, etwa bei der Synchronisierung von Game Worlds.

    • Das ist buchstäblich ein degeneriertes CRDT. Dass ein zentraler Server die Reihenfolge von Konflikten festlegt, gibt es seit Google Wave.
    • Ich frage mich, ob das wirklich so neu ist. Einen zentralen Prozess zu verwenden, um ein verteiltes System zu serialisieren, ist doch praktisch der naheliegende Ausgangspunkt, bis man anfängt, sich über Netzwerkpartitionen und CAP Gedanken zu machen. Jetzt hat man außerdem einen Single Point of Failure. Ich habe es nur überflogen, aber ich frage mich, ob Performance irgendwo thematisiert wurde.
    • Ist das Beschriebene nicht ein CRDT?
    • Bei ctrl+a, ctrl+x, ctrl+v braucht man wohl Glück.

  • Schön, so einen Artikel zu sehen. Ich habe vor ein paar Jahren dieselbe Methode entdeckt und mich gefragt, warum man sie in der wissenschaftlichen Literatur kaum sieht.
    Allerdings habe ich sie in einem dezentralen Kontext als CRDT implementiert, sodass Eigenschaften wie Kommutativität, Idempotenz und Assoziativität erhalten bleiben.

    • Wenn die Idee war, eine Alternative zu CRDTs zu bauen: Was hat es gebracht, daraus ein CRDT zu machen?

  • Ich war überrascht, dass andere Datenstrukturen wie dict/map oder Arrays beliebiger Typen nicht erwähnt werden. Es wäre schön, wenn sich das leicht darauf erweitern ließe. Meiner Erfahrung nach brauchen Apps häufiger kollaborative Datenstrukturen als reine gemeinsame Textbearbeitung.
    Die im Beispiel für die Synchronisierung genannten Dinge — Update-Validierung, partielles Laden, High-Level-Operationen — sind interessant, aber es wirkt nicht besonders überzeugend, dass Yjs und Ähnliche solche Funktionen wegen der zugrunde liegenden CRDT-Implementierung nicht haben, oder weil solche Funktionen grundsätzlich schwer zu bauen wären.

    • Stimme völlig zu. Bei einem Array aus „atomaren“ Objekten, deren Eigenschaften sich nicht ändern lassen, müsste es wohl reichen, Strings einfach durch den eigenen Typ zu ersetzen. Änderungen innerhalb von Objekten wären schwieriger, aber vielleicht ist das eher ein Problem, Bäume effizient zu speichern und zu traversieren.
      In OP-Begriffen gesagt: Ich dachte immer, Nutzer einer Helper-Library sollten leichte Logik für ein semantisches Modell einhängen können, um ungültige Zustände zu verhindern oder zu verwalten. Zum Beispiel kann ein Todo-Element nicht gleichzeitig isDone: true und state: inProgress sein. Das ähnelt der im verlinkten Artikel angesprochenen Semantik von Rich-Text-Formatierung.
    • CRDTs funktionieren im Kern so, dass sie bei einem Konflikt deterministisch eine Seite auswählen. Das Problem ist, dass dies im Allgemeinen weder garantiert, dass keine Daten verloren gehen, noch dass die Daten gültig sind.
      Man stelle sich vor, jeder Git-Merge-Konflikt würde dadurch gelöst, dass automatisch eine Seite gewählt wird. Meist käme ein falsches Ergebnis heraus, und manchmal sogar Code, der nicht kompiliert. Wenn dann niemand sofort da ist, um es zu reparieren, führt das zu noch verworreneren Ergebnissen.
      Deshalb, denke ich, haben sich CRDTs nicht stärker verbreitet. CRDTs lösen nur das „Problem, von dem man dachte, dass man es hat“, aber nicht das eigentliche Problem: Konfliktlösung, die Daten, Gültigkeit und Bedeutung bewahrt. Man könnte sogar sagen, dass sie dieses Problem verschärfen, weil sie die möglichen Konfliktlösungen auf deterministisch replizierbare Verfahren beschränken.

  • Der entscheidende Unterschied zu CRDTs scheint zu sein: Wenn es einen zentralen Server gibt, sollte die Synchronisierung, also das Festlegen der Reihenfolge gleichzeitiger Events, nicht von der Datenstruktur selbst über eine lexikografische Ordnung erledigt werden, sondern vom Server.
    Da die gesamte Kommunikation nur zwischen Client und Server stattfindet und nicht zwischen Clients, kann der Server beim Verbinden eines Clients garantieren, dass er zuerst alle lokalen Operationen dieses Clients verarbeitet, bevor er neue Remote-Updates an ihn sendet.

  • Ist die Kernbotschaft dieses Artikels, dass die volle Komplexität von CRDT/OT nur nötig ist, wenn es keinen zentralen Server gibt?

    • Auch ohne zentralen Server lässt sich die Komplexität von CRDT/OT vermeiden, wenn es eine dezentrale Methode gibt, Operationen am Ende in eine totale Ordnung zu bringen und sie in dieser Reihenfolge anzuwenden: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      Wie andere Kommentare sagen, ist das technisch gesehen ebenfalls ein CRDT, und zwar eine ziemlich allgemeine Form. Außerdem ist auch die Implementierung von Undo und Replay von Operationen nicht trivial. Trotzdem hoffe ich, dass es einfacher ist, als für jeden Datentyp traditionelle CRDTs/OT zu verwenden.
    • Das ist der Kern von CRDTs. Mehrere Replikate derselben Datenstruktur werden über mehrere Nodes hinweg verwaltet, jedes Replikat wird unabhängig aktualisiert, und am Ende konvergieren alle.
    • OT braucht einen zentralen Server.

  • Ich bin kein Experte auf diesem Gebiet, aber der Hauptunterschied zu CRDTs wie Automerge scheint die Server-Koordination zu sein. In diesem Artikel [1] sieht man zum Beispiel, dass Automerge bei gleichzeitigen Einfügungen Sequenznummern verwendet und sich bei gleichzeitigen Inserts auf die vereinbarte Reihenfolge der Agent-IDs verlässt. Dieser Ansatz dagegen verlässt sich darauf, dass der Server in Ankunftsreihenfolge verarbeitet.
    Im Artikel steht sinngemäß: „Bei Textbearbeitungs-CRDTs legt ein ausgeklügelter Algorithmus die ID-Reihenfolge fest. Dieser Ordnungsalgorithmus unterscheidet die verschiedenen Textbearbeitungs-CRDTs voneinander und ist der komplexe Teil der CRDT-Paper. Wir umgehen das vollständig.“ Dass man diesen „ausgeklügelten Algorithmus“ vermeiden kann, weil viele Apps ohnehin einen zentralen Server haben, leuchtet ein. Allerdings erfordert Server-Koordination ein Zurücknehmen und erneutes Abspielen lokaler Edits, und ich bin nicht zu 100 % überzeugt, dass das viel einfacher ist. [1] https://josephg.com/blog/crdts-go-brrr/

    • Ich stimme zu, dass Undo und Replay auch nicht besonders einfach sind. Ein persistenter B+Tree ist ebenfalls kein besonders simples Ding.
    • Soweit ich weiß, speichert Automerge intern letztlich alle Operationen in einer konsistenten totalen Ordnung, und man könnte das bei der Server-Koordination als Ersatz für den Server verwenden: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      Automerge macht das in der Praxis aber nicht so, sondern verarbeitet Textoperationen mit RGA, einem traditionellen CRDT. Vermutlich, wie du angedeutet hast, weil die Implementierung von Undo und Replay von Operationen nicht leicht ist.

  • Also ein nicht optimiertes CRDT? Mit maximaler Set-Größe 1 und einfach durchgedrückt?

    • Das wirkt wie eine Art irreduzible Komplexität, und genau das macht es attraktiv. Es ist näher an dem, was tatsächlich passiert, und simpel. Wie gesagt, optimiert ist es wohl nicht.

  • Weil Server-Koordination verwendet wird, dürfte die clientseitige Koordination schwierig sein. Wie hält man eine flüssige Editor-UX aufrecht, während bei jedem eintreffenden Server-Update angewendet wird?
    Wenn zum Beispiel eine vom Client gesendete Anfrage zum Einfügen eines Zeichens fehlschlägt, versucht man es dann einfach erneut? Was, wenn inzwischen Updates eingetroffen sind? Edit: Im Abschnitt „Client-Side“ wird dieser Fall eingeräumt; vorgeschlagen werden Zurückspulen und anschließendes Replay, als einfachere Alternative auch das Blockieren, bis die Warteschlange ausstehender Operationen leer ist. Aus Frontend-Sicht können sich nicht explizit genannte UI/UX-Ausnahmen lange fortsetzen, sodass CRDTs insgesamt vielleicht einfacher wirken. Und ich frage mich auch, wie sich das Bearbeiten in der verbindungsanfälligen New Yorker U-Bahn anfühlen würde.