Verschiebbare Baum-CRDTs und Loros Implementierung

• Movable tree CRDTs and Loro's implementation

• Hintergrund

  • In verteilten Systemen und kollaborativer Software ist die Verwaltung hierarchischer Beziehungen komplex.
  • Wenn in Datenstrukturen Löschung und Einfügung kombiniert werden, um Verschiebungen zu modellieren, ist es schwierig, Konflikte aufzulösen und die Erwartungen der Nutzer zu erfüllen.
  • Wenn beispielsweise derselbe Knoten gleichzeitig zu unterschiedlichen Eltern verschoben wird, können doppelte Knoten mit identischem Inhalt entstehen.

• Konflikte in verschiebbaren Bäumen

  • Wichtige Operationen in verschiebbaren Bäumen: Erstellen, Löschen, Verschieben
  • Konflikte, die bei der Synchronisierung gleichzeitiger Operationen auftreten können:
    • Derselbe Knoten wird gelöscht und verschoben.
    • Derselbe Knoten wird unter verschiedene Knoten verschoben.
    • Andere Knoten werden verschoben, wodurch ein Zyklus entsteht.
    • Ein Nachfahrenknoten wird verschoben, während ein Vorfahrenknoten gelöscht wird.

• Löschen und Verschieben desselben Knotens

  • Relativ einfach zu lösen.
  • Abhängig von Zeitstempeln im verteilten System oder spezifischen Anforderungen der Anwendung wird eine Operation angewendet und die andere ignoriert.

• Verschieben desselben Knotens unter verschiedene Eltern

  • Das Zusammenführen gleichzeitiger Verschiebeoperationen ist komplexer.
  • Je nach Anwendung sind verschiedene Ansätze möglich:
    • Den Knoten löschen und unter einem anderen Elternknoten eine Kopie erstellen.
    • Zulassen, dass der Knoten mit zwei Eltern verbunden ist (in der Regel nicht erlaubt).
    • Alle Operationen sortieren und nacheinander anwenden.

• Entstehung von Zyklen durch das Verschieben anderer Knoten

  • Das Auflösen von Zyklen, die durch gleichzeitige Verschiebeoperationen entstehen, ist komplex.
  • Es gibt mehrere Lösungsansätze:
    • Einen Fehler auslösen
    • Zyklische Knoten in einem speziellen "Timeout"-Bereich rendern
    • Verschiebeoperationen auf dem Server verarbeiten
    • Topologische Sortierung verwenden
    • Die Kante verbergen, die den Zyklus verursacht

• Löschen eines Vorfahrenknotens und Verschieben eines Nachfahrenknotens

  • Das Verschieben eines Nachfahrenknotens beim Löschen eines Vorfahrenknotens wird leicht übersehen.
  • Wenn alle Nachfahrenknoten direkt gelöscht werden, kann das als Datenverlust missverstanden werden.

• Wie populäre Anwendungen Konflikte behandeln

  • Dropbox: Behandelte Dateiverschiebungen als Löschen plus Erstellen, was jedoch das Risiko von Datenverlust birgt.
  • Figma: Ein zentraler Server erkennt Zyklen und lehnt Operationen ab, um Konsistenz zu gewährleisten.

• Verschiebbare Baum-CRDTs

  • Verwendung von CRDTs anstelle zentralisierter Lösungen.
  • Frühe CRDT-basierte Algorithmen waren schwer zu implementieren und hatten hohen Speicher-Overhead.
  • Durch fortlaufende Optimierungen wurden einige CRDT-basierte Baum-Synchronisationsalgorithmen für Produktionsumgebungen geeignet.

• Hochverfügbare Verschiebeoperationen für replizierte Bäume

  • Die drei Baumoperationen (Erstellen, Löschen, Verschieben) werden in einer Verschiebeoperation zusammengeführt.
  • Die Verschiebeoperation wird als Move t p m c definiert.
  • Das Löschen eines Knotens wird behandelt, indem er in den TRASH-Knoten verschoben wird.

• Global sortierte logische Zeitstempel

  • Lamport-Zeitstempel werden verwendet, um in verteilten Systemen die kausale Reihenfolge von Ereignissen zu bestimmen.
  • Eine kleinere Zahl bedeutet ein früheres Ereignis.

• Anwenden entfernter Operationen

  • Die Sicherheit einer Operation hängt vom Zustand des Baums zum Zeitpunkt der Anwendung ab.
  • Bei der Verarbeitung entfernter Updates werden neuere Operationen zurückgesetzt, die neue Operation eingefügt und die zurückgesetzten Operationen anschließend erneut angewendet.

• CRDT: Veränderliche Baumhierarchie

  • Jeder Knoten verfolgt alle historischen Elternknoten und weist ihnen Zähler zu.
  • Wenn bei der Synchronisierung ein Zyklus entsteht, wird der Knoten wieder mit dem nächsten historischen Elternknoten verbunden.

• Implementierung verschiebbarer Baum-CRDTs in Loro

  • Implementiert den Algorithmus von Martin Kleppmann und bietet hohe Performance.
  • Integriert den Fractional Index-Algorithmus, um die Sortierung von Kindknoten zu ermöglichen.

• Potenzielle Konflikte bei der Sortierung von Kindknoten

  • Wenn mehrere Knoten an derselben Position eingefügt werden, kann derselbe Fractional Index zugewiesen werden.
  • Mit PeerID wird die relative Reihenfolge bei identischem Fractional Index bestimmt.

• Implementierung und Kodierungsgröße

  • Fractional Index liefert die Reihenfolge der Knoten.
  • Die Kodierungsgröße kann im schlimmsten Fall zusätzliche Bytes erfordern, was jedoch selten vorkommt.

• Verwandte Arbeiten

  • Neben Fractional Index gibt es auch CRDTs für verschiebbare Listen.
  • Fractional Index ist einfach zu implementieren und nützlich, wenn nur die relative Reihenfolge benötigt wird.

• Benchmarks

  • Es wurden Performance-Benchmarks für Loros Implementierung verschiebbarer Bäume durchgeführt.
  • Sie unterstützt Echtzeit-Kollaboration und einen reibungslosen Checkout historischer Versionen.

• Zusammenfassung

  • Stellt die Schwierigkeiten bei der Implementierung verschiebbarer Baum-CRDTs sowie zwei innovative Algorithmen vor.
  • Loro integriert den Algorithmus von Martin Kleppmann und Fractional Index, um verschiedene Anwendungsszenarien zu erfüllen.

• GN⁺-Zusammenfassung

  • Verschiebbare Baum-CRDTs spielen eine wichtige Rolle bei der Verwaltung hierarchischer Datenstrukturen in verteilten Systemen.
  • Loro bietet hohe Performance und effiziente Konfliktauflösung und eignet sich damit für Echtzeit-Kollaborationsanwendungen.
  • Mit Fractional Index wird das Sortierungsproblem von Kindknoten gelöst.
  • Andere Projekte mit ähnlichen Funktionen sind Figma und Dropbox.

[GN⁺]

Hacker-News-Kommentar

• Arbeite an einem neuen Multiplayer-Editor

  • Unterstützt Text- und Outliner-Arbeit
  • Dokumente werden in große Baumstrukturen umgewandelt
  • Synchronisierung erfolgt mit insmov-Operationen (Verschieben oder Einfügen)
  • Wenn der Server Änderungen sendet, wendet der Client sie erneut an
  • In den meisten Fällen müssen Operationen nicht rückgängig gemacht werden
  • Bei Echtzeit-Updates treten kaum Probleme auf

• Stelle die React Table Library als Open Source bereit

  • Verarbeitet Ordner-/Datei-Baumstrukturen
  • Unterstützt das Verschieben und Duplizieren von Ordnern/Dateien sowie Lazy Loading
  • Dadurch wurde verständlich, warum Google Drive Anzeige und Bearbeitung nur auf derselben Hierarchieebene erlaubt

• Bittet um Rat

  • Verwendet im Frontend einen großen denormalisierten Baum
  • Verwaltet Benutzerprofile in einem Kachel-Layout
  • Überträgt für sichere Updates nur minimale Datenmengen
  • Mit CRDT würde das State-Management wohl deutlich einfacher werden
  • Synchronisierung zwischen Browser-Tabs wäre möglich

• Bei der Arbeit mit formatierten Textinhalten wie in Google Docs/Zoho Writer ist Baum-Manipulation nötig

  • Das Lösen gleichzeitiger Konflikte ist schwierig
  • Eine Kombination aus Listen-CRDT und Baum-CRDT scheint möglich
  • Allen Operationen müsste eine zweidimensionale Adresse hinzugefügt werden

• Fragt sich, ob es praktische CRDTs für datenintensive Anwendungen wie Bilder (Pixel) und 3D-Modelle gibt

• Findet, dass der erste Absatz wie die Stimme von ChatGPT klingt