Die Optimierungsreise, die CRDT 5000-mal schneller machte (2021)

 (josephg.com)
3 Punkte von GN⁺ 2024-08-28 | 1 Kommentare | Auf WhatsApp teilen
  • Die Einschätzung, dass CRDTs beim kollaborativen Bearbeiten langsam seien, ist oft das Ergebnis davon, den Algorithmus selbst und die Art der Implementierung zu vermischen; schon Datenstrukturen und Speicherlayout können die Performance stark verändern
  • Automerge v1.0.0-preview2 benötigte für die Verarbeitung von 260.000 Bearbeitungen 291 Sekunden und 880 MB RAM, während Diamond types native dieselbe Aufgabe in 56 ms mit 1,1 MB RAM erledigte
  • Yjs reduzierte denselben Trace mithilfe einer flachen Liste statt eines Baums, Positions-Caches, doppelt verketteter Listen und span-basierter Speicherung auf 0,97 Sekunden und 3,3 MB RAM
  • Diamond types verwendet in Rust eine auf Range Tree/B-Tree basierende Struktur, verarbeitet Positionsabfragen, Einfügungen und Löschungen in log(n) Zeit und erreichte auch in WebAssembly unter Node.js 193 ms
  • Dieser Benchmark betrachtete nur die Wiedergabe lokaler Bearbeitungen eines einzelnen Nutzers und den RAM-Verbrauch; für die tatsächliche Auswahl sollte man daher auch Speicher- und Ladezeiten, Netzwerk-/Datenträgergröße, binary encoding, Protokoll, Presence und Editor-Binding berücksichtigen

Algorithmus und Implementierungsleistung sind getrennte Dinge

  • Ein wissenschaftlicher Vergleich implementierte Echtzeit-Kollaboration wie in Google Docs mit mehreren CRDT- und OT-Algorithmen und benchmarkete diese; einige Algorithmen brauchten für ein einfaches Paste mehr als 3 Sekunden
  • Die langsamen Varianten nutzten Algorithmen aus ShareJS und Google Wave, aber die betreffende Implementierung zerlegte ein Paste von 1000 Zeichen in 1000 einzelne Operationen
  • Dieses Beispiel zeigt, dass man das Verhalten bei gleichzeitiger Bearbeitung und die Implementierungsweise getrennt betrachten muss
    • Das Verhalten bezeichnet, nach welcher Reihenfolge und nach welchen Regeln zusammengeführt wird, wenn gleichzeitige Bearbeitungen denselben Bereich betreffen
    • Die Implementierung umfasst Programmiersprache, Datenstrukturen und den Grad der Optimierung
  • Dieselbe text-OT-transform-Funktion läuft in JavaScript etwa 100.000-mal pro Sekunde, in C aber 20 Mio.-mal pro Sekunde — also mit einem Unterschied von rund 200×
  • Eine einzelne langsame Implementierung ist kein Beleg dafür, dass alle Implementierungen dieses Systems langsam sind; schnellere Implementierungen sind möglich

Grundmodell von CRDT und Automerge

  • CRDT ermöglicht es mehreren Nutzern, dieselben Daten gleichzeitig zu bearbeiten, lokal ohne Verzögerung zu arbeiten und später zu synchronisieren, um eventual consistency zu erreichen
  • Automerge ist eine von Martin Kleppmann entwickelte Bibliothek für kollaboratives Bearbeiten und basiert auf dem RGA-Algorithmus
  • CRDTs wie Automerge und Yjs betrachten ein gemeinsames Dokument als Liste von Zeichen und vergeben jedem Zeichen eine eindeutige ID
    • Gibt man in ein leeres Dokument abc ein, werden IDs wie (seph, 0), (seph, 1), (seph, 2) vergeben
    • Bei neuen Zeichen wird zusätzlich gespeichert, „hinter welchem Element sie eingefügt werden“
  • Automerge/RGA fügt jedem Element eine sequence number hinzu
    • Ein neues Element erhält einen Wert, der um 1 größer ist als die bisher größte bekannte sequence number
    • Gibt es mehrere Kind-Elemente, werden sie nach absteigender sequence number sortiert, bei Gleichstand nach agent ID
  • Das Verhalten von Automerge/RGA lässt sich in drei Schritte zerlegen
    • Jedes Element wird mit seinem parent verbunden, sodass ein Baum entsteht
    • Elemente mit mehreren Kindern werden nach sequence number und ID sortiert
    • Der Baum wird per depth-first traversal abgeflacht, um die finale Liste bzw. das Textdokument zu erzeugen

Automerge-Benchmarks und Engpässe

  • Für den Benchmark wurde der Bearbeitungstrace aus automerge-perf verwendet
    • Es handelt sich um einen Trace auf Zeichenebene, der aufzeichnet, wie Martin Kleppmann einen wissenschaftlichen Artikel getippt hat
    • Der Trace enthält 260.000 Bearbeitungen und das finale Dokument ist etwa 100.000 Zeichen groß
    • Gleichzeitige Bearbeitung ist nicht enthalten
    • Gemessen wurde nur die Zeit, um den Trace lokal anzuwenden
    • Die Umgebung bestand aus einer Ryzen-5800x-Workstation, Nodejs v16.1 und Rust 1.52
  • Automerge v1.0.0-preview2 brauchte für die Verarbeitung dieses Trace 291 Sekunden, der RAM-Verbrauch am Ende lag bei 880 MB
    • Das entspricht ungefähr 10 KB RAM pro Tasteneingabe
    • Der RAM-Peak lag bei 2,6 GB
    • In langsamen Spikes dauerte die Verarbeitung einer einzelnen Bearbeitung 1,8 Sekunden
  • Ein Baseline-Test mit direktem Splice auf JavaScript-Strings verarbeitete dieselben Bearbeitungen in 0,61 Sekunden mit 0,1 MB RAM, war aber nur eine Vergleichsbasis, die sämtliche für kollaboratives Bearbeiten nötigen Informationen verwirft
  • Dass Automerge langsam ist, hat mehrere implementierungsbedingte Gründe
    • Mit wachsendem Dokument werden die baumartigen Datenstrukturen größer und langsamer
    • Der starke Einsatz von Immutablejs erschwert V8-Optimizer und GC die Optimierung
    • Jedes eingefügte Zeichen wird als separates Element behandelt, sodass selbst Paste-Vorgänge viele Elemente erzeugen
  • Das Automerge-Team arbeitete damals an einer alternativen Implementierung, die die Rust-Version automerge-rs über WASM nutzt
    • Auf Basis des damaligen master branch wurde die durchschnittliche Performance in diesem Test zwar nicht besser, aber der Speicherverbrauch halbierte sich und die Performance-Schwankungen wurden flacher

Yjs-artige Implementierung mit flacher Liste

  • Yjs ist eine Open-Source-CRDT-Implementierung von Kevin Jahns und speichert statt eines Baums alle Elemente in einer einzigen flachen Liste
  • Der Zugriff auf die flache Liste findet die Einfügeposition, indem ab direkt hinter dem parent nach dem neuen Element gescannt wird; es ist also eine Implementierung eines List-CRDT als Liste
  • Das experimentelle reference-crdts implementiert Yjs’ YATA und Automerges RGA auf dieselbe Weise
    • Die insert-Funktion verarbeitet Yjs- und Automerge-Verhalten bis auf kleine Unterschiede praktisch im selben codepath
    • Die semantische Gleichheit wird mit einem fuzzer verifiziert
  • Dieser Ansatz hat drei Vorteile
    • Statt eines unausgeglichenen Baums wird ein flat array verwendet, das kleiner und schneller ist
    • Der Code ist einfach
    • Er lässt sich auf mehrere List-CRDTs wie Yjs, Automerge und Sync9 anwenden
  • Theoretisch kann dieser Ansatz langsam werden, wenn es viele gleichzeitige Einfügungen an derselben Position gibt, in realen Bearbeitungen wird aber meist direkt hinter dem parent eingefügt
  • Die Implementierung in reference-crdts war etwa 10-mal schneller als Automerge und benötigte rund 30-mal weniger RAM
Test Verarbeitungszeit RAM-Verbrauch
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Plain string edits in JS 0.61s 0.1MB

Scan- und Einfügekosten senken

  • Bei der Implementierung mit flachem Array bleiben zwei Engpässe bestehen
    • Das Dokument muss gescannt werden, um die Einfügeposition zu finden
    • Beim Einfügen in die Mitte des Arrays mit doc.content.splice(destIdx, 0, newItem) müssen die nachfolgenden Elemente verschoben werden
  • Gelöschte Elemente können nicht aus dem Array entfernt werden, weil andere Einfügungen noch auf sie verweisen können; stattdessen muss eine Markierung wie isDeleted erhalten bleiben
    • Selbst wenn das aktuelle Dokument 100.000 Zeichen hat, kann das Array inklusive vergangener Elemente 150.000 Einträge enthalten
    • Um an Dokumentposition 50.000 einzufügen, müssen beim Überspringen gelöschter Elemente womöglich etwa 75.000 Einträge gescannt werden
  • In einer solchen Struktur kostet das Einfügen in ein Dokument mit n Elementen ungefähr n Schritte, und das Einfügen von n Zeichen wird zu O(n²)
  • Yjs cacht passend zur Art, wie Menschen Dokumente bearbeiten, das (index, position)-Paar der letzten Bearbeitungsposition
    • Da die nächste Bearbeitung wahrscheinlich in der Nähe der vorherigen liegt, wird nur kurz vor- oder rückwärts gescannt
    • Damit mehrere Nutzer an unterschiedlichen Positionen bearbeiten können, wird eine Menge gecachter Positionen gespeichert
  • Yjs verwendet statt eines Arrays eine doppelt verkettete Liste und fügt nach dem Finden der Position in konstanter Zeit ein
  • Außerdem nutzt es aus, dass Menschen Zeichen fortlaufend eintippen, und speichert hello nicht als 5 Zeichen-Elemente, sondern als eine Span
    • Ein Collapse ist nur möglich, wenn ID und Parent lückenlos sequenziell verbunden sind
    • In diesem Datensatz sinkt die Zahl der Array-Einträge dadurch von 180.000 auf 12.000, also eine 14-fache Reduktion
Test Verarbeitungszeit RAM-Nutzung
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Plain string edits in JS 0.61s 0.1MB

Rust und der Range-Tree-Ansatz von Diamond types

  • JavaScript-Objekte für content, Lösch-Flag, ID, seq, parent usw. werden leicht zu einer Struktur, deren Pointer verstreut im Speicher liegen, was Speicherfragmentierung und Cache-Miss-Kosten erhöht
  • Rust erlaubt direkte Kontrolle über das Memory-Layout und kann über WebAssembly auch im Web genutzt werden
  • Diamond types ist eine in Rust geschriebene CRDT-Implementierung, die Yjs sehr ähnlich ist, intern aber statt einer verketteten Liste einen Range Tree verwendet
  • Der interne Range Tree ist ein leicht modifizierter B-tree
    • Statt wie eine gewöhnliche BTreeMap Keys zu speichern, speichern die inneren Knoten die Summe der in ihren Kindern enthaltenen Zeichen
    • Beliebige Positionsabfragen, Einfügungen und Löschungen im Dokument werden in log(n) Zeit verarbeitet
  • Ein Trace mit 260.000 Edits wird in diesem Baum mit etwa 3 Leaf-Node-Ebenen gespeichert, sodass sich jedes Item mit ungefähr 3 Memory-Reads finden lässt
  • Für das Mergen entfernter Edits gibt es außerdem einen kleinen Index, der per ID im B-tree sucht; dieser Codepfad ist in diesem Benchmark nicht enthalten
  • Leaf Nodes speichern Blöcke mit 32 Einträgen dicht gepackt in einem Fixed-Size-Array
    • Laut Autor funktionierte eine Bucket-Größe von 32 in Benchmarks mit verschiedenen Größen gut, warum sie optimal ist, sei aber unklar
  • Wenn Diamond mit diamond-js zu WASM kompiliert und in Node.js aufgerufen wird, verarbeitet es denselben Trace in 193ms
    • Etwa 5-mal schneller als Yjs
    • Etwa 3-mal schneller als die JavaScript-String-Baseline
  • Die native Rust-Ausführung erreicht im Benchmark 56ms
    • Mehr als 5000-mal schneller als Automerge
    • Verarbeitet 4.6M Operationen pro Sekunde
    • Während der Verarbeitung aller 260.000 Edits wurde malloc insgesamt 1394-mal aufgerufen
Test Verarbeitungszeit RAM-Nutzung
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Plain string edits in JS 0.61s 0.1MB
Diamond WASM via Node.js 0.19s unbekannt
Diamond native 0.056s 1.1MB

Ropey-Auslagerung und Trade-offs

  • Die Diamond-Implementierung speichert den eigentlichen Dokumenttext nicht direkt in der CRDT-Item-Liste, sondern in einer separaten Datenstruktur
  • Für den Textinhalt wird die Rust-Bibliothek Ropey verwendet, die für Textverwaltung ebenfalls einen B-tree implementiert
  • Dieser Ansatz bringt Engineering-Trade-offs mit sich
    • Ropey nutzt Byte-Packing speziell für Text und kann so den RAM-Verbrauch senken
    • Beim Einfügen müssen zwei Datenstrukturen aktualisiert werden, was die Geschwindigkeit um mehr als das Doppelte verringert und das WASM-Bundle von 60KB auf 120KB anwachsen lässt
    • Bei der Anbindung an einen Editor wie VS Code hält der Editor ohnehin eine Kopie des Dokuments, sodass der Dokumentinhalt möglicherweise nicht innerhalb der CRDT-Struktur gespeichert werden muss
  • Wenn der Trace nur mit Ropey verarbeitet wird, dauert das 29ms
  • Wenn bei Diamond native die Aktualisierung des Dokumentinhalts deaktiviert wird, ergibt das 23ms und 0.96MB RAM
    • Etwa 14.000-mal schneller als Automerge
    • Verarbeitet 11M Operationen pro Sekunde
    • Dieses Ergebnis ist eher ein Experiment zur Auslotung der Grenzen der Verarbeitung von CRDT-Metadaten als eine nützliche Konfiguration
Test Verarbeitungszeit RAM-Nutzung Datenstruktur
automerge v1.0.0-preview2 291s 880MB naiver Baum
reference-crdts Automerge/Yjs 31s 28MB Array
Yjs v13.5.5 0.97s 3.3MB verkettete Liste
Plain string edits in JS 0.61s 0.1MB keine
Diamond WASM via Node.js 0.20s unbekannt B-tree
Diamond native 0.056s 1.1MB B-tree
Ropey Rust baseline 0.029s 0.2MB keine
Diamond native, no doc content 0.023s 0.96MB B-tree

Kriterien für die Auswahl einer echten Bibliothek

  • Wenn man jetzt eine dokumentbasierte Kollaborations-App bauen würde, wäre Yjs die vorteilhaftere Wahl
    • Yjs bietet gute Performance, geringen Speicherverbrauch und ein starkes Support-Ökosystem
    • Kevin Jahns bietet auch kostenpflichtigen Support für Yjs-Integrationen an
  • Das Automerge-Team hatte Performance 2021 ebenfalls als höchste Priorität gesetzt und plante, Automerge mit verschiedenen Techniken zu beschleunigen
  • Diamond ist extrem schnell, aber bis zur Feature-Parität mit Yjs und Automerge ist noch viel Arbeit nötig
    • Eine CRDT-Bibliothek braucht neben der Operationsgeschwindigkeit auch Binary Encoding, Netzwerkprotokoll, Nicht-Listen-Datenstrukturen, Presence, Editor-Binding usw.
  • Wenn Datenbank-Semantik benötigt wird, ist keine ausgereifte Implementierung auf Basis von CRDT bekannt; stattdessen kann man das OT-basierte ShareDB verwenden
  • Redwood ist ein Projekt mit Unterstützung für P2P-Editing und plant vollständigen CRDT-Support

Einschränkungen der Messmethode

  • Dieser Benchmark misst nur die Wiedergabezeit lokaler Bearbeitungs-Trace-Daten und die RAM-Nutzung
  • Lokale Benutzereingaben müssen nur schnell genug sein; wenn ein CRDT eine einzelne lokale Bearbeitung in etwa 1 ms oder weniger verarbeitet, ist noch mehr Geschwindigkeit möglicherweise nicht besonders wichtig
    • Auch Automerge erfüllt dieses Niveau im Großen und Ganzen, abgesehen von unglücklichen GC-Pausen
  • Tatsächlich gibt es andere Kennzahlen, die wichtiger sind
    • die Anzahl der Bytes, die ein Dokument auf Datenträger oder im Netzwerk belegt
    • die Zeit, die zum Speichern und Laden benötigt wird
    • die Zeit, die zum Aktualisieren eines gespeicherten Dokuments in einer Datenbank benötigt wird
  • Der verwendete Trace enthält nur Bearbeitungen eines einzelnen Benutzers, daher könnten pathologische Fälle mit viel gleichzeitiger Bearbeitung noch offen sein
  • Um derzeit mit Yjs oder Automerge ein einzelnes Objekt in einer Datenbank zu aktualisieren, muss man normalerweise das gesamte Dokument in den RAM laden, ändern und dann das gesamte Dokument erneut speichern, was langsam sein kann
    • Kevin sagt, dass sich das mit einem passend angepassten Yjs-Provider auf sinnvolle Weise umsetzen lässt
  • List-CRDTs wachsen wegen der Tombstones gelöschter Einträge grundsätzlich immer weiter; Pruning ist ein separater Ansatz
    • Als Beispiele werden der GC-Algorithmus von Yjs und Antimatter genannt
    • Pruning ist ein Problem, das orthogonal zu den im Artikel behandelten Optimierungen der Datenstrukturen steht

Kein vollständig kontrolliertes Vergleichsexperiment

  • In jeder Optimierungsstufe wurden mehrere Variablen gleichzeitig verändert, daher werden die genauen Ursachen der Geschwindigkeitssteigerung nicht isoliert
  • Beim Übergang von Automerge zu reference-crdts haben sich mehrere Faktoren geändert
    • die zentrale Datenstruktur wechselte von einem Baum zu einer Liste
    • Immutablejs wurde entfernt
    • das Frontend/Backend-Protokoll von Automerge und mehrere Uint8Array-Strukturen verschwanden
    • der JavaScript-Stil wechselte von funktional zu imperativ
  • Auch beim Übergang von reference-crdts zu Yjs und von Yjs zu Diamond lassen sich die Änderungen nicht auf eine einzelne Ursache zurückführen
  • Dass automerge-rs in diesem Test nicht schneller als Automerge war, ist ein Hinweis darauf, dass die Leistung von Diamond nicht nur auf Rust zurückzuführen ist, aber der genaue Anteil ist nicht bekannt
  • Auch der Vergleich von RGA und YATA mit derselben Implementierungsweise beruht auf der Annahme, dass „das Verhalten bei gleichzeitiger Zusammenführung praktisch ähnlich ist und die Implementierungsleistung auch bei verändertem Verhalten erhalten bleibt“
    • In der reference CRDT implementation zeigen Yjs- und Automerge-Verhalten nahezu denselben Codepfad und dieselbe Leistung
    • Bei konfliktlastigen Traces könnte es Leistungsunterschiede geben, in der Praxis gelten solche Fälle jedoch als sehr selten
  • Yjs speichert nicht, wann jedes Item gelöscht wurde, sondern nur, ob es gelöscht wurde
    • Wenn in Diamond der Löschzeitpunkt gespeichert wird, steigt der Speicherverbrauch von 1,12 MB auf 2,34 MB und es wird etwa 5 % langsamer
    • Alle Diamond-Benchmarks in diesem Artikel verwenden den yjs-style branch, der an die Arbeitsweise von Yjs angepasst ist

Benchmark-Code und Reproduktionsmaterial

  • Der Testcode für die JS-String-Baseline, Yjs, Automerge und reference-crdts befindet sich in diesem GitHub gist
  • Für die meisten Tests wird automerge-paper.json.gz aus josephg/crdt-benchmarks benötigt
  • Der reference-crdts-Benchmark hängt von dieser Version von josephg/reference-crdts ab
  • Der Diamond-Benchmark wurde mit dieser Version von josephg/diamond-types ausgeführt
    • Der Ausführungsbefehl ist RUSTFLAGS='-C target-cpu=native' cargo criterion yjs
    • Speicherstatistiken werden mit cargo run --release --features memusage --example stats überprüft
  • Der Diamond-WASM-Wrapper verwendet diamond-js, und das WASM-Bundle wurde mit wasm-opt optimiert
  • Die Diagramme wurden auf ObservableHQ erstellt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-08-28
Hacker-News-Kommentare

  • Wenn 2-Byte-Integer verwendet wurden, lag das wahrscheinlich an der Cache-Line von 64 Byte.
    32 Einträge ergeben genau eine Cache-Line, sodass jede Cache-Line einen ganzen Bucket enthalten und teure Transfers aus dem Hauptspeicher reduziert haben dürfte.

    • Ich mochte die Art, wie Knuth spätere Programme benchmarkte.
      Im Grunde fügt man einen Zähler ein, der zählt, wie oft etwas aus dem Speicher gelesen werden muss; ich frage mich, ob man ähnlich näherungsweise erfassen könnte, wie oft Cache-Lines geleert werden müssen.
    • Wenn man nach Batch-Größe benchmarked, sieht man häufig große Sprünge im Zusammenhang mit der Speicherhierarchie.
      Es gibt Ausschläge an Grenzen wie Wortgröße (64 Bit), Größe ausgerichteter Cache-Fetches (meist die oben erwähnten 64 Byte), OS-Page-Größe (4–16 KB), L1-Größe (etwa 80 KB pro Core) und L2 (einige MB).

  • Ich frage mich, welche Apps im realen Betrieb CRDTs einsetzen und dabei eine sehr gute Erfahrung bieten.
    Ich erinnere mich, dass Notion eine davon war, aber realistisch gesehen ist gemeinsames Mitschreiben zu zweit in Notion im Vergleich zu Google Docs nahezu unbrauchbar.

    • Thymer[1] verwendet CRDTs für alles.
      Es ist eine IDE für Aufgaben und Planung, eine Mehrbenutzer-App, unterstützt Ende-zu-Ende-Verschlüsselung, Offline-first und optionales Self-Hosting, und da der gesamte Workspace ein einzelner Graph ist, waren CRDTs eine natürliche Wahl.
      Alle Aktionen in Thymer lassen sich auf eine kleine Zahl von CRDT-Transformationen reduzieren. Verschieben/Kopieren von Text, Änderungen an „frontmatter“-Eigenschaften, Draggen von Karten, Datei-Uploads und das Hinzufügen von Tags werden alle mit denselben wenigen CRDT-Operationen verarbeitet.
      Anfangs war es ohne Bibliothek viel Arbeit, aber wenn der Anwendungszustand ein einzelner Graph ist, kann man Funktionen wie das Verschieben von Text zwischen Seiten, Seitenlinks mit Backlinks und Transklusion bauen, ohne sich um Synchronisierung sorgen zu müssen; das war den Aufwand wert.
      CRDTs garantieren, dass alle Clients in denselben Zustand konvergieren, und weil sie im Wesentlichen append-only sind, bekommt man Versionierung zu bestimmten Zeitpunkten gratis dazu.
      Allerdings mussten wir aus Performance-Gründen einige Kompromisse eingehen. Die Versionshistorie wird offline nicht angeboten, weil es zu viele Daten sind, und in manchen Fällen nutzen wir Last-Writer-Wins zur Konfliktlösung.
      Insgesamt ist es sehr lohnend, besonders wenn man die App von Anfang an mit CRDTs im Hinterkopf entwirft. Wenn man einer traditionelleren AJAX-App später Mehrbenutzerfunktionen hinzufügen wollte, würde ich CRDTs wohl nicht verwenden.
      CRDT-Änderungen werden zunächst optimistisch angewendet; sobald die autoritative Event-Reihenfolge feststeht, müssen alle Clients zum letzten gemeinsamen Zustand zurückkehren und dann alle Events in der richtigen Reihenfolge erneut anwenden.
      War man lange offline, muss man womöglich Änderungen mehrerer Tage zurückrollen und erneut anwenden. Nutzer sehen nicht, wie viele Baumtransformationen im Hintergrund stattfinden, aber CRDTs beeinflussen das gesamte Anwendungsdesign.
      Die meisten heute beliebten Apps wurden zu einer Zeit entworfen, als CRDT-Transformationen noch nicht gut verstanden waren.
      [1] https://thymer.com (fast bereit für die Beta)
    • Notion ist heute ein Last-Writer-Wins-System, das nur eine begrenzte Zahl intentionswahrender Operationen besitzt, etwa die Blockreihenfolge in Listendaten.
      Text ist Last-Writer-Wins, und der Text oder die Eigenschaften jedes Blocks sind Last-Writer-Wins-Register. An einem neuen CRDT-Format für Blocktext wird gearbeitet.
    • Soweit ich weiß, verwenden die meisten iCloud-Dienste intern CRDTs.
      Dazu gehören Notes und Reminders, möglicherweise auch Photos. Dass FoundationDB ebenfalls als Teil des Backends verwendet wird, habe ich in einer Bar von einem betrunkenen ehemaligen Apple-SRE gehört.
    • Linear: https://linear.app/
      Der Vortrag auf der Local First Conf ist ebenfalls sehenswert: https://youtu.be/VLgmjzERT08
    • Wenn man weiter darüber nachdenkt, gibt es noch ein Beispiel, das einem nicht sofort einfällt.
      Alle Netzwerkspiele, die in irgendeiner Form Rollback oder Korrektur verwenden, liegen nahe daran. Best-Effort mit Rollback als Ausweichpfad könnte unter den verbreiteten CRDT-ähnlichen Ansätzen die beste Nutzererfahrung bieten.
      Es ist kein CRDT im strengen akademischen Sinn. Technisch gesehen wird der Spielzustand nicht vollständig auf alle Clients repliziert, und jeder Client erhält nur einen Teilzustand des Spiels.
      Außerdem brauchen Game-Clients Synchronisierung mit niedriger Latenz, was akademisch vielleicht als „Koordination“ gelten würde. In der Praxis akzeptiert und rendert der Client die Eingabeauswirkungen probabilistisch lokal, bevor Konfliktlösung oder Rollback-Korrektur zurückkommen.
      Manche werden da pingelig sein, aber spätestens beim dritten Beispiel erkennt man das gemeinsame Thema: Die beliebtesten, benutzerfreundlichsten und am besten umgesetzten CRDTs brechen tatsächlich akademische Regeln.
      Das ist eine typische Falle übermäßig akademischer Denkmodelle. Algorithmen und Datentypen in der realen Welt sind oft viel kreativer als akademische „Regelbücher“. Timsort ist ein Beispiel dafür.
      Wenn man ein Produkt für echte Nutzer baut und nicht für ein Paper-Review, sollte man nicht in Overengineering- oder akademische Fallen tappen. Man sollte die akademischen Regeln lernen, sie aber bewusst brechen, und statt Konzepte perfekt umzusetzen, die so streng definiert sind, dass sie nur für Akademiker nützlich sind, echten Mehrwert schaffen und etwas gut Benutzbares bauen.

  • CRDTs sind mächtig, aber schade ist, dass sie – ob operationsbasiert oder zustandsbasiert – Spuren früherer Operationen oder Elemente hinterlassen.
    Selbst mit Kompression bleibt das ein Nachteil und ein Punkt, der einen bei der Einführung zögern lässt.
    Trotzdem hat diese Diskussion mein Interesse an der Möglichkeit geweckt, auf dateibasierten Speichern wie Dropbox oder Syncthing konfliktfreie Algorithmen oder fein granularere Konfliktlösungsalgorithmen zu implementieren.

    • Ich bin der Autor. Ich habe diese Diskussion schon oft geführt, und auch in CRDT-Kreisen kommt sie häufig auf, aber in der Praxis ist der Overhead zumindest beim Text-Editing so gering, dass er in der realen Welt wohl kein Problem wird.
      Mein Post-CRDT-Projekt Diamond Types wächst grundsätzlich mit der Zeit unbegrenzt, aber der Overhead liegt normalerweise bei weniger als 1 Byte pro bisher eingegebenem Zeichen.
      Wenn man für den gespeicherten Text LZ4-Kompression aktiviert, sind mit Diamond Types bearbeitete Dokumente oft kleiner als der endgültige Dokumentzustand, obwohl die komplette Bearbeitungshistorie gespeichert wird.
      Technisch kenne ich mehrere Wege, das zu lösen, aber ich bin nicht sicher, ob es in den meisten Systemen ein tatsächliches Problem ist.
      Ich habe von jemandem gehört, der yjs in einem 3D-Modellierungs-Tool eingesetzt hat und Probleme bekam, weil beim Ziehen eines Objekts jedes Mal eine persistente Bearbeitung erzeugt wurde, wenn sich die Maus um ein Pixel bewegte.
      Für solche Vorgänge ist es meiner Ansicht nach klüger, temporäre Edits zu verwenden, die die meisten CRDT-Bibliotheken nicht unterstützen.
      Nebenbei hat Git dasselbe Problem. Repositories werden mit der Zeit größer, und zwar deutlich schneller als bei modernen CRDT-Bibliotheken. Aber anscheinend stört das kaum jemanden.
      Shallow Clones sind in Git zwar möglich, aber fast niemand nutzt sie. Wenn man wollte, könnte man dasselbe auch bei CRDTs machen.
    • Wenn man kein vollständig dezentrales System baut, kann man einen Teil der von CRDTs verlangten Einschränkungen lockern.
      Wenn man zum Beispiel garantieren kann, dass alle Clients Änderungen nach Datum X erhalten haben, kann man Operationen vor diesem Datum sicher verwerfen.
    • Ein vollständiges Operations-Log und deterministisches Merging passen gut zu unveränderlichen Blockspeichern und können auch Vorteile bei Sicherheit, Performance und Kosten haben.
      Um die aktuelle Forschung in diesem Bereich zu nutzen, bauen wir Fireproof[1].
      Wenn unveränderliche Daten content-addressed werden, ergibt sich der zusätzliche Vorteil, dass jede Operation auf einen kryptografisch abgesicherten Beweis oder Diff hinausläuft. Damit lässt sich kausale Konsistenz erzwingen und es lassen sich stabile Referenzen auf Snapshots erzeugen.
      Das heißt, man kann eine interaktive, offlinefähige und verlustfrei mergende Datenbank am Edge oder im Browser betreiben und trotzdem die Integrität haben, die man früher von einer zentralen Datenbank oder einer Blockchain erwartet hätte.
      Zum Beispiel kann man eine Snapshot-CID in ein zu signierendes PDF oder in einen Smart Contract einfügen, um jede Mehrdeutigkeit über den referenzierten Zustand zu beseitigen.
      [1] https://github.com/fireproof-storage/fireproof
    • Der Begriff CRDT selbst verlangt nicht, dass Spuren früherer Operationen oder Elemente zurückbleiben müssen.
      Letztlich ist es treffender, konkrete Implementierungen zu kritisieren, statt pauschal über eine Menge mathematischer Gesetze zu sprechen, denen bestimmte Datentypen oder Datenbanken folgen.
    • Wenn man die Historie löschen kann, frage ich mich, worüber man sich Sorgen macht.

  • Der Artikel ist von 2021 und scheint auch die Rust-Implementierung von Automerge einzubeziehen; aktualisierte Benchmarks wären daher interessant.

    • Ich bin der Autor. Für Yjs gibt es ebenfalls yrs, eine Neufassung in Rust, und sie ist viel schneller als die JavaScript-Version.
      Ich habe auch einen völlig anderen neuen Ansatz, um dieses Problem zu lösen.
      Es wäre definitiv gut, die Benchmarks zu aktualisieren. Alles ist schneller geworden.

  • Ich habe vieles davon nur schwer verstanden, aber der Text ist so gut geschrieben, dass es einer der seltenen Artikel ist, die man ohne Unterbrechung weiterliest.

  • Frühere verwandte Diskussionen:
    https://news.ycombinator.com/item?id=28017204 (vor 3 Jahren, 151 Kommentare)
    https://news.ycombinator.com/item?id=33903563 (vor 2 Jahren, 22 Kommentare)
    https://news.ycombinator.com/item?id=41372833 (aktueller Beitrag)
    https://news.ycombinator.com/item?id=41373288 (aktueller Kommentar)

  • Wenn man das aktuelle GitHub-Readme[0] zitiert, heißt es, die Performance habe sich seit diesem Blogpost noch einmal um 10- bis 80-fach verbessert.
    [0] https://github.com/josephg/diamond-types

  • Es wäre schön, wenn jemand erklären könnte, warum CRDTs langsam sind.
    Dieser Artikel scheint die Zukunft zu zeigen: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
    Es wäre interessant, das mit Y.js oder Automerge zu vergleichen: https://github.com/canvasxyz/okra-js

    • Ich bin der Autor. Der Hauptgrund ist, dass viele CRDT-Bibliotheken von Wissenschaftlern geschrieben wurden, denen die Zeit, die Fähigkeiten oder das Interesse zur Optimierung fehlten.
      Seit ich diesen Artikel vor einigen Jahren geschrieben habe, sind alle wichtigen CRDT-Bibliotheken um mehrere Größenordnungen schneller geworden.

  • Ich erinnere mich, diesen Artikel vor ein paar Jahren zufällig gesehen zu haben.
    Ein wirklich unterhaltsamer Text und einer meiner Lieblingsartikel der letzten Jahre.

    • Ich glaube, der Titel war damals CRDTs go brrr.

  • Zu „Warum ist WASM viermal langsamer als native Ausführung?“: Ich dachte, der Grund sei, dass alle String-Operationen erst in den WASM-Speicher kopiert werden und, sobald das Ergebnis berechnet ist, wieder zurück nach JS kopiert werden müssen.
    Liege ich da falsch? Habe ich den Kontext missverstanden? Ich frage wirklich aus Interesse.

    • Ich bin der Autor. Der Artikel ist zwar ein paar Jahre alt, aber soweit ich mich erinnere, hatte ich diesen Teil kontrolliert. Das Problem war also nicht FFI.
      Vor der Zeitmessung habe ich die gesamte Historie in wasm geladen und sie in einer inneren Schleife verarbeitet, die in Rust geschrieben war und im wasm-Kontext selbst lief. Es gab nur etwa zwei wasm-Aufrufe.
      Die Ursache für den Faktor 4 war nicht FFI, sondern dass der Algorithmus-Code selbst tatsächlich viermal langsamer ausgeführt wurde.
      Es wäre interessant, den Benchmark heute noch einmal laufen zu lassen. Die wasm-Ausgabe der Compiler dürfte besser geworden sein, und die wasm-Runtimes dürften auch schneller sein. Der Benchmark-Code liegt vermutlich noch irgendwo.
    • Das klingt nach einer plausiblen Ursache.
      Ein Problem, über das ich in einem anderen Bereich immer wieder stolpere, ist, dass Multithreading nicht einfach ist und die Unterstützung durch Bibliotheken und Tools ebenfalls nicht vollständig ist.
      Ich habe Game-Engines oder Utility-Binaries wie ffmpeg und zip im Browser laufen lassen, und aus diesem Grund waren sie sehr langsam.
    • Die bessere Frage ist wohl, warum man erwartet, dass beide gleich schnell sind.
      Ich habe nie mit WASM-Interpretern oder JITs gearbeitet, aber wie oft ist es schon besser, durch mehrere Übersetzungsschichten zu gehen, statt nur durch eine?
      Wenn man High-Level-Code nach WASM oder in irgendeine Assemblersprache übersetzt, verliert man viel von der im High-Level-Code enthaltenen Absicht.
      In Low-Level-Code sieht man häufig eine Aneinanderreihung sprachspezifischer Idiome, um ein Ziel zu erreichen; manche davon haben vielleicht eine direkte Entsprechung auf der realen Maschine, andere nicht.
      Moderne x86-64-Prozessoren haben sehr viele Instruktionen, die deutlich mächtiger sind als das, was man in WASM tun kann.
      Natürlich gibt es auch Decompiler, und ein WASM-JIT könnte eine Liste von Makro-Operation-Fusionen haben, mit denen sich über relativ simples Pattern Matching guter nativer Code erzeugen lässt. Wahrscheinlich ist das nicht der Fall, und Cross-Plattform-Optimierung ist noch schwieriger, aber dennoch.
      Auch LLVM ist nicht perfekt; es gibt sicher einfache Stellen, die ein nachgelagerter Optimierer verbessern könnte. Daher ist es theoretisch nicht unmöglich, WASM schneller zu machen als LLVMs native Ausgabe.
      Aber ohne einen sehr gut ausgearbeiteten Plan – oder ohne einen Instruktionssatz zu schaffen, der faktisch eine Obermenge dessen ist, was die Ziel-Instruction-Set-Architecture unterstützt – halte ich es für sehr schwierig, Ergebnisse auf demselben Niveau zu erzielen.
      Aus meiner Sicht ist WASM eher eine Teilmenge, daher ist es nicht einfach, Operationen zu standardisieren und sie in Echtzeit wieder zusammenzufügen. Ganz unmöglich ist es nicht, aber es erfordert eine erhebliche Engineering-Leistung.
      Intuitiv: Wenn man ein auf Englisch geschriebenes Buch in eine ganz andere Sprache übersetzt, die zudem auf ein paar tausend Wörter beschränkt ist, und es dann wieder ins Englische zurückübersetzt, kommt nicht exakt derselbe Text heraus.
      Es wird Fälle geben, in denen man ein Konzept, das im Englischen mit einem einzigen Wort erledigt wäre, in einem ganzen Absatz erklären muss. Um das ursprüngliche Englisch wiederzubekommen, bräuchte man entweder eine 1:1-Übersetzung für alles oder eine zwischen den beiden Übersetzern abgestimmte Liste von Absatz→Ein-Wort-Übersetzungen.