Schnellere CRDTs (2021)

5000-mal schnellere CRDTs: ein Abenteuer der Optimierung

Einleitung

• Vor einigen Jahren veröffentlichten französische Forschende eine Arbeit, die Algorithmen für kollaboratives Editieren in Echtzeit verglich
• Sie implementierten mehrere Algorithmen und benchmarkten deren Leistung
• Manche Algorithmen brauchten für einen einfachen Einfügevorgang mehr als 3 Sekunden
• Der problematische Algorithmus war derjenige, der in ShareJS verwendet wurde

Ursache des Problems

• In der Arbeit wurde beim Einfügen großer Textmengen die Verarbeitung in 1000 einzelne Operationen aufgeteilt
• Das war kein Problem des Algorithmus selbst, sondern der Implementierung

Reiz von CRDTs

• CRDTs (Conflict-Free Replicated Data Types) ermöglichen es mehreren Nutzern, Daten gleichzeitig zu bearbeiten
• Man kann lokal ohne Verzögerung arbeiten, und bei der Synchronisierung wird die Konsistenz automatisch gewahrt
• Sie können auch ohne zentralen Server funktionieren

Probleme von Automerge

• Automerge ist eine Bibliothek für kollaboratives Editieren und basiert auf dem RGA-Algorithmus
• Jedes Zeichen eines Dokuments wird mit einer eindeutigen ID verwaltet, und beim Einfügen wird ein Elternelement angegeben
• Aufgrund von Performance-Problemen dauerte die Verarbeitung von 260.000 Bearbeitungsvorgängen 5 Minuten
• Auch der Speicherverbrauch war sehr hoch

Performance-Optimierung

• Die Performance-Probleme von Automerge lagen an einer komplexen baumbasierten Datenstruktur und dem Einsatz von Immutablejs
• Yjs verbesserte die Leistung deutlich durch die Verwendung einer einzigen flachen Liste
• Yjs verwendet einen Cache, um Einfügepositionen zu finden, und verarbeitet Einfügungen effizient mit einer doppelt verketteten Liste
• Yjs ist 30-mal schneller und benötigt auch weniger Speicher

Umstieg auf Rust

• Rust ermöglicht mehr Kontrolle über das Memory-Layout und kann die Performance weiter verbessern
• Mit einer neuen CRDT-Implementierung namens Diamond types wurde eine 5-mal höhere Leistung als bei Yjs erreicht
• Das in Rust implementierte Diamond verarbeitet 260.000 Bearbeitungsvorgänge in nur 56 Millisekunden

Fazit

• Mit optimierten Datenstrukturen und effizientem Memory-Management lässt sich die Performance von CRDTs erheblich verbessern
• Mit Low-Level-Sprachen wie Rust lässt sich noch höhere Leistung erreichen

Zusammenfassung von GN⁺

• CRDTs sind die Zukunft des kollaborativen Editierens und ein leistungsfähiges Werkzeug, das auch ohne zentralen Server Konsistenz wahren kann
• Die Performance-Probleme von Automerge lagen an komplexen Datenstrukturen und ineffizienter Speichernutzung
• Yjs und Diamond types steigern die Leistung deutlich durch einfache und effiziente Datenstrukturen
• Mit Low-Level-Sprachen wie Rust lässt sich noch höhere Leistung erreichen
• Bei der Entwicklung kollaborativer Editierwerkzeuge lohnt es sich, Yjs und Diamond types in Betracht zu ziehen

[GN⁺]

Hacker-News-Kommentare

• Der Grund, warum 32 Einträge am effizientesten sind, ist die Cache-Line-Größe von 64 Byte

  • Bei Verwendung von 2-Byte-Ganzzahlen passen 32 Einträge genau in eine Cache Line, wodurch Übertragungen zum Hauptspeicher reduziert werden können

• Es ist schwer, reale Anwendungen mit CRDTs zu finden, die eine wirklich gute Nutzererfahrung bieten

  • Notion ist in der Nutzung schlechter als Google Docs, wenn zwei Personen gleichzeitig an einer Notiz schreiben

• CRDTs sind mächtig, haben aber den Nachteil, historische Operationen (oder Elemente) beizubehalten

  • Selbst mit Komprimierung bleibt das ein Nachteil und sorgt für Bedenken bei der Einführung
  • Trotzdem ist die Möglichkeit interessant, konfliktfreie Algorithmen bei dateibasierten Speicheranbietern (Dropbox, Syncthing usw.) zu implementieren

• Aktuelles Zitat aus dem GitHub-README:

  • Seit dem Blogbeitrag hat sich die Performance um das 10- bis 80-Fache verbessert

• Dieser Artikel ist gut geschrieben, und obwohl der Inhalt schwierig ist, konnte man nicht aufhören zu lesen

• Beim Einsatz einer Hierarchie stellte sich die Frage, warum stattdessen keine Nested Sets verwendet wurden

  • Es ist unklar, ob der Vorteil bei Leseoperationen den Nachteil bei Einfügeoperationen ausgleichen könnte

• Dieser Beitrag wurde vor einigen Jahren zufällig entdeckt

  • Er war einer der unterhaltsamsten Beiträge der letzten Jahre

• Es stellt sich die Frage, warum WASM viermal langsamer als native Ausführung ist

  • Vermutlich, weil alle String-Operationen in den WASM-Speicher kopiert werden müssen und die Ergebnisse nach der Berechnung wieder nach JS zurückkopiert werden
  • Es ist unklar, ob dieser Kontext missverstanden wurde

• Da die Rust-Implementierung von Automerge abgeschlossen ist, wäre es interessant, aktualisierte Benchmarks zu sehen