cola: Text-CRDT-Technik für kollaboratives Bearbeiten in Echtzeit

• cola ist ein in Rust geschriebenes Text-CRDT für kollaboratives Bearbeiten in Echtzeit und fokussiert sich darauf, dass von mehreren Peers gleichzeitig geänderte Dokumente auch ohne zentralen Koordinator in denselben Zustand konvergieren
• Dokumentpositionen werden nicht als einfache Offsets, sondern als Anchor in der Form ReplicaId.n fixiert, um Probleme zu vermeiden, bei denen die Bedeutung einer Position durch gleichzeitige Bearbeitungen instabil wird
• Einfügekonflikte werden konsistent mit Lamport timestamp und ReplicaId-Sortierung behandelt; Löschungen werden nicht physisch entfernt, sondern mit Tombstones und Version Vectoren über Integrationsbedingungen gesteuert
• In der Implementierung nutzt cola RLE auf Basis von EditRun und einen als Vec-Indizes dargestellten G-tree, um innerhalb von Rusts sicherem Ownership-Modell logarithmische Suche und Einfügung zu erreichen
• In Benchmarks wurde cola mit diamond-types, automerge und yrs verglichen; upstream ist es 1,4- bis 2-mal schneller als diamond-types und zeigt auch downstream sehr hohe Leistung

---

Das Problem des kollaborativen Bearbeitens, das cola adressiert

• cola ist ein in Rust geschriebenes Text-CRDT, das dafür ausgelegt ist, dass mehrere Replikate bei kollaborativer Bearbeitung in Echtzeit ohne zentrale Instanz in denselben Zustand konvergieren
• An die Netzwerkschicht wird nur die minimale Annahme gestellt, dass jede Bearbeitung letztlich alle Peers erreicht
  • Bearbeitungen können mehrfach übertragen werden
  • Bearbeitungen können in beliebiger Reihenfolge ankommen
  • Alle Peers müssen letztlich alle Bearbeitungen erhalten
• Ziel ist nicht nur, dass der Dokumentzustand nach Erhalt aller Bearbeitungen identisch ist, sondern auch, dass das resultierende Dokument aus Nutzersicht plausibel wirkt

Positionen mit Anchors statt Offsets fixieren

• Offset-basierte Bearbeitungen wie insert "abc" at offset 8 können ihre Bedeutung ändern, wenn andere Peers gleichzeitig davor liegende Bereiche bearbeiten, was dazu führen kann, dass Replikate auseinanderlaufen
• cola referenziert Dokumentpositionen nicht über Zeicheninhalt oder Offsets, sondern über stabile Identifikatoren
  • Jeder Peer versieht eingefügte Zeichen mit aufsteigenden Nummern
  • Peers haben einen eindeutigen Identifikator, ReplicaId
  • Das Paar ReplicaId.n wird zum eindeutigen Positionsidentifikator eines Zeichens, dem Anchor
• Der Wert n kann durch Erhöhen eines lokalen Zählers eindeutig gehalten werden, aber die globale Eindeutigkeit von ReplicaId ohne zentralen Server ist schwer sicherzustellen
  • cola geht deshalb von sehr großen Zufallszahlen aus, deren Kollisionswahrscheinlichkeit wie bei UUIDs vernachlässigbar ist
• Einfügungen geben ihre Position mit einem einzelnen Anchor an, Löschungen definieren einen Bereich mit einem Start- und End-Anchor

Einfügekonflikte in dieselbe Reihenfolge bringen

• Wenn mehrere Einfügungen an demselben Anchor eintreffen, bestimmt cola die Reihenfolge mit Lamport timestamp
• Die Lamport-Uhr wird nach folgenden Regeln aktualisiert
  • Beim lokalen Einfügen von Text wird die Uhr um 1 erhöht
  • Beim Empfang einer entfernten Einfügung wird sie auf max(current, remote_timestamp) + 1 gesetzt
• Wenn eine Einfügung A in einer Umgebung erzeugt wurde, in der Einfügung B bereits integriert war, dann ist der Lamport-Zeitstempel von A größer als der von B
• Konfligierende Einfügungen werden nach absteigendem Lamport-Zeitstempel sortiert
• Bei gleichzeitigen Einfügungen, bei denen sowohl Anchor als auch Lamport-Zeitstempel identisch sind, gibt es aus Nutzersicht keine eindeutig richtigere Reihenfolge; deshalb wird zur Konsistenz zwischen Peers nach ReplicaId aufsteigend sortiert

Löschungen mit Tombstones und Version Vectoren verarbeiten

• Löschungen werden nach der Umwandlung von Start- und End-Offset in Anchors an andere Peers weitergegeben
• Wenn zwei Peers denselben Bereich gleichzeitig löschen, ergibt sich – sofern Undo nicht berücksichtigt wird – dasselbe Resultat wie bei einer einmaligen Löschung
  • cola unterstützt derzeit kein Undo für Löschungen
• Die Verarbeitung von Löschungen bringt drei Schwierigkeiten mit sich
  • Wenn gelöschter Text vollständig entfernt wird, können Anchors noch nicht eingetroffener Bearbeitungen in diesem Bereich liegen
  • Wenn entfernte Löschungen zu früh integriert werden, kann sich der von dem löschenden Peer gesehene Inhalt vom Inhalt des empfangenden Peers unterscheiden, wodurch Replikate auseinanderlaufen
  • Auch innerhalb des Löschbereichs dürfen Zeichen, die der löschende Peer noch nicht gesehen hatte, nicht gelöscht werden
• Das erste Problem wird mit Tombstones gelöst
  • Gelöschte Zeichen bleiben im Dokument erhalten, sind aber als gelöscht markiert
  • Dieser Ansatz erhöht den Speicherverbrauch
• Die übrigen Probleme werden gelöst, indem Löschnachrichten einen Version Vector enthalten
  • Der Schlüssel ist ReplicaId, der Wert ist der Zeitstempel des letzten Zeichens, das der löschende Peer zu diesem Zeitpunkt gesehen hat
  • Der empfangende Peer wartet mit der Integration der Löschung, bis sein eigener Version Vector mindestens dem der Löschnachricht entspricht
  • Zeichen mit einem größeren Zeitstempel als im Lösch-Vector werden beim Löschen übersprungen
• In cola wird der Version Vector als Version Map bezeichnet

Trennung von Replica und Textpuffer

• Der lokale Dokumentzustand jedes Peers wird in cola durch Replica dargestellt
• Der CRDT-Algorithmus von cola muss den eigentlichen String-Inhalt nicht kennen
  • API-Funktionen nehmen keine Strings als Argumente entgegen
  • cola verarbeitet keine Dokumentinhalte, sondern nur numerische Blöcke
• Dieses Design trennt den CRDT-Mechanismus von der tatsächlichen Implementierung des Textpuffers

Metadaten mit RLE und EditRun reduzieren

• Da eine Metadatenstruktur pro Zeichen eine performante Implementierung erschwert, bündelt cola Blöcke mit fortlaufenden Zeitstempeln per run-length encoding
• Wenn man zum Beispiel die komplette Wikipedia-Seite zum Manhattan Project einfügt, kann sie statt als 107.000 Blöcke als ein einziger Block dargestellt werden
• Auch wenn ein Satz Zeichen für Zeichen eingegeben wird, ohne den Cursor zu bewegen oder zu löschen, muss nicht für jeden Tastendruck ein eigener Block entstehen, sondern alles kann als ein einzelner Run dargestellt werden
• In cola heißen solche zusammenhängenden Blöcke EditRun
  • Ein einmal aufgetrennter EditRun bleibt für die Lebensdauer des Dokuments fixiert und wird nicht mehr erweitert
  • Ein noch nicht aufgetrennter Run befindet sich im aktiven Zustand
• Wenn Text in die Mitte eines bestehenden EditRun eingefügt wird, wird der Run in zwei Teile geteilt und der neue Text dazwischen eingefügt
• Wenn Text gelöscht wird, wird der betreffende Abschnitt vom Run abgetrennt und als Tombstone markiert
  • Auch gelöschte Runs lassen sich auf dieselbe Weise per RLE komprimieren, was die Speicherlast von Tombstones reduziert

Von der verketteten Liste zum B-tree

• Der Upstream-Pfad lokaler Bearbeitungen ist der Prozess, offset-basierte Bearbeitungen in Bearbeitungen umzuwandeln, die an andere Peers gesendet werden können
  • Sowohl für Einfügungen als auch für Löschungen muss der Run gefunden werden, der den Offset enthält, um daraus einen Anchor zu bilden
  • Falls nötig, wird der Run bei Einfügungen in höchstens 2, bei Löschungen in höchstens 3 Teile aufgeteilt
• In einer verketteten Liste ist das Aufteilen eines Runs O(1), aber um den Run zu finden, der einen Offset enthält, muss vom Anfang an gescannt werden, was lineare Zeit kostet
• Wenn man den aktuell aktiven Run und seinen Offset cached, ist wiederholtes Bearbeiten an derselben Position schnell, aber im Worst Case bleibt es linear
• cola betrachtet für logarithmische Worst-Case-Leistung eine B-tree-Struktur
  • Runs werden als Blätter des B-tree dargestellt
  • Inodes speichern ihre Kinder und die Summe der Längen ihrer Kinder
  • Tombstone-Runs tragen mit Länge 0 bei
  • Die Länge der Wurzel entspricht der Gesamtlänge des Dokuments
• Ein B-tree kann Suche und Einfügung in O(log n) ausführen und damit lokale Bearbeitungen in logarithmischer Zeit verarbeiten
• Um bei entfernten Bearbeitungen die Umwandlung Anchor -> run effizient zu machen, muss allerdings das Blatt gefunden werden, das den Anchor enthält

G-tree: ein als Vec-Indizes dargestellter B-tree

• Mit bloßen Zeigern auf gewöhnliche B-tree-Blätter ist es im Top-down-Einfügeprozess schwer nachzuvollziehen, wie bis zu diesem Blatt abgestiegen werden soll
• Für Bottom-up-Operationen sind Elternzeiger pro Knoten nötig; in Rusts sicherem Ownership-Modell würde das Strukturen wie Rc<RefCell<_>> erfordern, was langsam und komplex werden kann
• cola speichert stattdessen alle Knoten in einem dynamischen Array wie Vec und repräsentiert Referenzen zwischen Knoten nicht mit Zeigern, sondern mit Indizes
  • Der Vektor besitzt alle Knoten
  • Jeder Knoten kann den Index seines Elternknotens speichern
  • Bidirektionale Traversierung ist ohne unsafe-Code möglich
• Diese Struktur beruht auf der Annahme, dass Knotenindizes sich nicht ändern
  • Neue Knoten werden am Ende des Vektors angehängt
  • cola entfernt Runs nicht, sondern markiert sie als Tombstones, daher entsteht kein Problem mit ungültigen Indizes
• Diese grow-only-Baumstruktur in einem Vektor nennt cola G-tree
• G-tree-Rust-Code verändert also nur die Speicherrepräsentation, während die Eltern-Kind-Struktur eines B-tree erhalten bleibt

Welche Leistungsmerkmale der G-tree erzeugt

• Der G-tree führt wie ein B-tree Top-down-Suche und Einfügung in logarithmischer Zeit aus
• LeafIdx, also der Vektorindex eines Blatts, kann als stabiler Blatt-Identifikator genutzt werden
• Der aktuell aktive Run kann nicht als Zeiger, sondern als LeafIdx gecached werden
  • Bei wiederholten Bearbeitungen an derselben Cursor-Position wird der aktive Run erweitert und nur die Längen der Vorfahren bis zur Wurzel aktualisiert
  • Das kann ohne Baumtraversierung und neue Allokationen mit wenigen Ganzzahlvergleichen und 2 bis 4 Ganzzahladditionen erledigt werden
• colas G-tree verwendet einen Verzweigungsfaktor von 32; die durchschnittliche Belegung von Inodes liegt bei etwa 20 Kindern
  • Schon 4 Ebenen reichen typischerweise aus, um etwa 160k verschiedene EditRun zu speichern
  • Nach der Verarbeitung des Bearbeitungs-Trace automerge-paper hat colas G-tree etwa 15k EditRun
  • Dieser Trace umfasst 260k Bearbeitungen und wurde über mehrere Tage aufgezeichnet
• Da die Knoten im G-tree bereits in linearem Speicher liegen, sind Serialisierung und Deserialisierung ebenfalls einfach

Umwandlung von Anchor in LeafIdx

• Der Downstream-Pfad entfernter Bearbeitungen ist der Prozess, Anchor-basierte Bearbeitungen wie insert 2.3..7 at 1.2 oder delete between 3.4 and 2.2 in lokale Dokument-Offset-Bearbeitungen umzuwandeln
• Weil der G-tree auf- und abwärts traversiert werden kann, lässt sich der betreffende Offset berechnen, wenn der LeafIdx des Runs bekannt ist, der einen bestimmten Anchor enthält
• Der Kernpunkt ist also die Umwandlung Anchor -> LeafIdx
• Ein einfaches Design wäre ein zusätzlicher G-tree oder B-tree, dessen Blätter ReplicaId, temporal range und LeafIdx des Haupt-G-tree speichern
  • Die Blätter sind vollständig nach ReplicaId und temporal range sortiert
  • Durch Abstieg im Baum anhand des Anchors kann der gewünschte LeafIdx gefunden werden
  • Suche und Einfügung sind beide O(log n)
• Der tatsächliche cola-Quellcode verwendet diesen zusätzlichen G-tree-Ansatz jedoch nicht direkt
  • In der realen Implementierung sind Suche und Einfügung O(log f)
  • f ist die Anzahl der Fragmente, in die ein EditRun, der den Anchor enthält, im Lauf der Zeit zerlegt wurde
  • f ist immer höchstens n und normalerweise deutlich kleiner

Aktueller Reifegrad und verbleibende Arbeit

• Das Design von cola bildet eine Grundlage mit Fokus auf Konvergenz, Intention Preservation und Performance
• Für Produktionsreife fehlen noch Undo/Redo-Unterstützung und einige weitere Arbeiten

Rust-CRDT-Benchmarks

• cola wurde mit drei Rust-basierten CRDTs verglichen
  • diamond-types
  • automerge
  • yrs
• Die Benchmarks messen die Zeit zur Verarbeitung echter character-by-character-Bearbeitungstraces
  • Verwendet wird die Rust-Benchmarking-Bibliothek criterion
  • Gemessen werden sowohl Upstream als auch Downstream
  • Der Benchmark-Code liegt in crdt-benches
• Die Grafiken setzen die Leistung von cola bei Faktor 100 als Basislinie; Messwerte, die mehr als 100-mal langsamer sind als cola, werden nicht angezeigt
• Die Ausführungsumgebung ist ein MacBook Pro von 2018 mit 2,2 GHz 6-Core Intel Core i7
  • Auf anderen Maschinen können die Zahlen abweichen, die relative Leistung dürfte aber ähnlich sein

Benchmark-Ergebnisse

• In Upstream-Richtung liegen yrs und automerge über der Basislinie
• Upstream ist cola 1,4- bis 2-mal schneller als diamond-types
• In Downstream-Richtung ist diamond-types bei allen Traces abgestürzt, sodass keine Messwerte vorliegen
  • Es wird ergänzt, dass die Ergebnisse aktualisiert würden, falls die Bibliothek falsch verwendet wurde
• Downstream ist cola etwa 2-mal langsamer als zuvor
  • Das ist erwartbar, weil die Integration entfernter Bearbeitungen im Allgemeinen teurer ist als das Erzeugen lokaler Bearbeitungen
• cola arbeitet in beiden Richtungen auf einem Niveau, das mit schnellen Rope-Bibliotheken vergleichbar oder schneller ist, und wird derzeit als die schnellste Implementierung eines Text-CRDT eingeschätzt

[GN⁺]

Meinungen auf Hacker News

• Ich sehe den G-tree weiterhin als B-tree mit zusätzlichen Parent-Pointern.
  Dass er in einem Array gespeichert wird, ist nur eine Frage der Darstellung und ändert die Struktur nicht grundlegend.
  Es werden weiterhin Pointer gespeichert, nur nicht in Byte-Einheiten, sondern in Einheiten der Knotengröße, und nur als relative Positionen bezogen auf das erste Array-Element statt auf den Anfang des Adressraums.
  Ein vollständiger Binärbaum, der ohne explizite Referenzen in einem Array gespeichert ist, wird zum Beispiel weiterhin Binärbaum genannt; dass die Kinder von Index x bei 2x + 1 und 2x + 2 liegen, ist nur eine implizite Darstellung.

  • Trotzdem ist es nützlich, über die Darstellungsform zu sprechen.
    Das gilt besonders für Sprachen, die eher zu relativen, selbstverwalteten Referenzen als zu absoluten Referenzen hinführen.
    Eine Baumdarstellung, die ich interessant fand, ist, die Knoten in Tiefensuch-Reihenfolge in einem flachen Array zu speichern.
    Wenn sie nur lesend verwendet wird und der Leser ohnehin in Tiefensuche traversieren will, kann das ziemlich effizient sein.
    Ich muss dabei an S-Expressions und HTML denken.

• Falls ich in der API nichts übersehen habe, scheint das keine Formatierungsbereiche wie fett oder kursiv zu unterstützen.
  Meines Wissens ist Peritext bei Rich-Text-CRDT-Algorithmen derzeit Stand der Technik: https://www.inkandswitch.com/peritext/
  Es wäre schön, wenn dieses Projekt auch die Rich-Text-Funktionen des Peritext-Algorithmus übernehmen würde.

  • Als jemand, der den CRDT-Bereich mit einigem Interesse verfolgt, habe ich mich immer gefragt, ob man allgemeinere CRDTs für strukturierte Daten bauen könnte.
    Also eine Art Modell oder Schema, mit dem Nutzer semantisch gültige Zustände beschreiben.
    Wenn man beispielsweise JSON einfach zusammenführt, kann ein syntaktisch gültiger, aber semantisch unsinniger Zustand entstehen.
    So wie der Peritext-Algorithmus weiß, dass Fett, Kursiv und Unterstrichen additive Operationen sind, Hervorhebungsfarben aber nicht, fände ich es gut, wenn Nutzer im Schema deklarieren könnten, dass state: notStarted und completionDate: 2023-09-04 nicht miteinander vereinbar sind.
  • Frage: Im Artikel heißt es, Cola behandle nur konfliktfreie Bearbeitungen für unbekannte Datentypen und kümmere sich im Grunde nur um Zeichenströme und Positionen.
    Könnte man Formatierung dann nicht wie bei HTML im Text selbst ausdrücken?
    Ich kenne andere Rich-Text-Darstellungen nicht gut genug, daher bin ich mir nicht sicher.
    Außerdem habe ich mir das oben verlinkte Peritext-Dokument angesehen; es behandelt genau diese RTF-spezifischen Schwierigkeiten und war ziemlich interessant zu lesen.

• Gibt es Leistungs- oder Funktionsunterschiede im Vergleich zu Automerge oder Y.js/Yrs?

  • Der „dritte Teil“ des Artikels beginnt mit „Ich habe Cola gegen drei andere in Rust implementierte CRDTs gebenchmarkt: diamond-types, automerge und yrs“.
    Diese Cola-Library scheint bei der Operationsgeschwindigkeit ziemlich gut dazustehen.
    Mich würde auch der Speicherverbrauch interessieren.

• Nicht mit Ian Piumartas gleichnamiger Arbeit verwechseln.
  https://www.piumarta.com/software/cola/
  https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

  • Oder auch Cache Oblivious Lookahead Arrays, die einmal als Alternative zu MergeTree (LSM) galten, heute aber nicht mehr verwendet werden: https://github.com/giannitedesco/cola
  • Es gibt auch eine App im Stil eines Notion-Klons namens coda.io.

• Gut gemachte Arbeit, aber es wirkt nicht wie ein fairer Benchmark.
  Sie berechnet und speichert keine Operationen und speichert auch nicht den tatsächlichen Text.
  Um daraus ein Text-CRDT mit Delta-Updates zu machen, müsste der Nutzer in einer separaten Struktur OpID => Text speichern, und diese Kosten sind nicht gering.

• Mit dem Crate slotmap (https://docs.rs/slotmap/latest/slotmap/) kann man Löschungen unterstützen, ohne sich Sorgen zu machen, dass Indizes verschoben werden oder ein „Index“ auf einen anderen Wert zeigt.
  In slotmap heißen sie Keys, und in einem Key steckt auch eine Versionsnummer.

  • Würde das auch im CRDT-Kontext funktionieren?
    Ich frage mich das, weil das Festlegen der Reihenfolge schwierig ist und Versionen möglicherweise nur lokal Bedeutung haben.

• Ich überlege, das einmal für ein Projekt auszuprobieren, mit dem Etherpad und Word nicht zurechtgekommen sind.

• Wenn man annimmt, dass alle verbundenen Clients alle Bearbeitungen erhalten: Könnte man nicht vor Offset und Einfüge-/Lösch-/Ersetz-Befehl den erwarteten Hash des bestehenden Textzustands setzen?
  Dann ließe sich nahezu garantieren, dass eine Bearbeitung nur auf den passenden Zustand angewendet wird, und spätere Änderungen könnten in einem Dictionary gesammelt werden, dessen Schlüssel der „Hash des Datenzustands ist, auf den die Anwendung erwartet wird“.
  Natürlich wäre das teuer, weil dieselben Daten mehrfach gehasht werden müssten, aber es wäre sehr einfach zu verstehen und zu implementieren.

  • Mit diesem Ansatz würden asynchrone Bearbeitungen nie angewendet.
    Wenn ich eine lokale Bearbeitung am Dokument mache und du eine entfernte Bearbeitung vornimmst, wird dein Hash des „erwarteten Zustands“ nie wieder zum Zustand meines Dokuments passen.
    Denn ich habe ja bereits eine lokale Änderung vorgenommen.
    Damit ein CRDT Konvergenz garantiert, müssen zwar alle Clients alle Bearbeitungen erhalten, aber die Eigenschaft, Updates nicht in einer bestimmten Reihenfolge anwenden zu müssen, ist für reale verteilte Anwendungsfälle wichtig.

• Ich frage mich, ob es eine einfache Möglichkeit gibt, gemeinsames Bearbeiten von Formularen im Browser zu aktivieren.
  Schön wäre, wenn zwei Personen dieselbe Seite oder dasselbe Formular öffnen und sehen könnten, welches Eingabefeld die andere Person gerade bearbeitet, während in Texteingabefeldern ein Text-CRDT verwendet wird.
  Ich habe versucht, etwas Ähnliches mit Yjs umzusetzen, aber es war ziemlich schwierig und hat nicht gut funktioniert.

  • Mich würde interessieren, warum Yjs dafür nicht gepasst hat.
    Für diesen Zweck sieht es eigentlich genau richtig aus.