- Wenn hierarchische Strukturen in Kollaborationssoftware gleichzeitig bearbeitet werden, entstehen Baumkonflikte wie doppelte Knoten, Zyklen oder das Verschieben von Unterknoten eines gelöschten Vorfahren; Loro setzt dies als verschiebbares Baum-CRDT um
- Der Ansatz von Martin Kleppmann u. a. vereinheitlicht Erzeugen, Löschen und Verschieben in
Move t p m c und behandelt Löschen als Verschieben in den Knoten TRASH, wodurch gleichzeitige Verschiebungen von Unterknoten erhalten bleiben
- Die globale Reihenfolge wird mit Lamport Timestamp und Peer ID erzeugt; wenn eine entfernte Operation in die Mitte der bestehenden Reihenfolge eingefügt wird, vermeidet undo-do-redo Zyklen
- Loro kombiniert zur Sortierung von Geschwisterknoten einen Fractional Index; wenn sich Indizes durch gleichzeitiges Einfügen an derselben Position überlappen, wird dies über PeerID, Jitter und Zurücksetzen der Indizes behandelt
- In Benchmarks führte Loro Movable Tree nach dem Erzeugen von 1000 Knoten 10000 zufällige Verschiebungen in 28 ms aus und zeigt damit eine für Echtzeit-Kollaboration und Checkout früherer Versionen ausreichende Performance
Konflikte in kollaborativen Bäumen
- Wenn man beim Verwalten hierarchischer Beziehungen in verteilten Systemen und Kollaborationssoftware eine Verschiebung als Kombination aus Löschen und Einfügen modelliert, geraten Nutzererwartungen und Konfliktauflösung leicht auseinander
- Wird derselbe Knoten auf mehreren Replicas gleichzeitig zu unterschiedlichen Eltern verschoben, kann ein Knoten zweimal gelöscht und unter zwei Eltern neu erzeugt werden, sodass doppelte Knoten mit demselben Inhalt entstehen
- Die Grundoperationen eines verschiebbaren Baums sind Erzeugen, Löschen und Verschieben
- Bei der Synchronisierung treten vor allem folgende problematische Situationen auf
- Derselbe Knoten wird gleichzeitig gelöscht und verschoben
- Derselbe Knoten wird unter unterschiedliche Eltern verschoben
- Verschiebungen unterschiedlicher Knoten werden zusammengeführt und erzeugen einen Zyklus
- Ein Unterknoten wird verschoben, während ein Vorfahr gelöscht wird
Umgang mit den Konflikttypen
- Wenn Löschen und Verschieben desselben Knotens kollidieren, kann je nach Timestamp des verteilten Systems oder Anforderung der Anwendung eine Operation angewendet und die andere ignoriert werden
- Wenn derselbe Knoten unter unterschiedliche Eltern verschoben wird, unterscheiden sich die Optionen je nach Anwendung
- Den Knoten löschen, anschließend unter unterschiedlichen Eltern Kopien erstellen und diese danach unabhängig behandeln
- Einen Knoten auf zwei Eltern zeigen lassen; das bricht jedoch die Baumstruktur und ist allgemein schwer akzeptabel
- Alle Operationen sortieren und der Reihe nach anwenden, um auf allen Peers dasselbe Ergebnis zu erzeugen
- Wenn Verschiebungen unterschiedlicher Knoten einen Zyklus erzeugen, wird die Konfliktauflösung in verschiebbaren Bäumen besonders komplex
- Matthew Weidner fasst unter anderem Fehlerbehandlung, Rendering eines „time-out“-Bereichs, serverbasierte Ablehnung, Überspringen zyklenerzeugender Operationen nach topologischer Sortierung, Ausblenden bestimmter Edges beim Rendering und Zurücksetzen auf den vorherigen Parent zusammen
- Auch die Situation, dass ein Unterknoten verschoben wird, während ein Vorfahr gelöscht wird, ist leicht zu übersehen
- Wenn alle Unterknoten eines Vorfahren sofort gelöscht werden, kann der Nutzer fälschlich annehmen, seine Daten seien verloren gegangen
Die Ansätze von Dropbox und Figma
- Dropbox behandelte das Verschieben von Dateien anfangs in zwei Schritten: Löschen am ursprünglichen Ort und Erzeugen am neuen Ort
- Wenn zwischen Löschen und Erzeugen ein Stromausfall oder System-Crash auftrat, bestand ein Risiko von Datenverlust
- Heute erkennt Dropbox Konflikte, wenn mehrere Personen dieselbe Datei gleichzeitig verschieben und speichern wollen; üblicherweise wird eine Version der Originaldatei gespeichert und für die Änderung eines Nutzers eine „conflicted copy“ erstellt
- Figma betrachtet die Baumstruktur als den komplexesten Teil seines Kollaborationssystems und versieht jedes Element mit einem Attribut
parent
- Ein zentraler Server überwacht Updates mehrerer Nutzer und lehnt eine Operation ab, wenn sie einen Zyklus erzeugen könnte
- Wegen Netzwerklatenz kann vor der Ablehnung durch den Server vorübergehend ein Zyklus entstehen
- In diesem Fall blendet Figma die am Zyklus beteiligten Elemente vorübergehend aus und bewahrt den Zustand, bis der Server die Operation offiziell ablehnt
- Die zugehörige Erklärung findet sich in Figmas Beitrag zur Multiplayer-Technologie
Zwei Ansätze für verschiebbare Baum-CRDTs
- Statt einer zentralisierten Lösung kann man kollaborative Baumstrukturen mit CRDTs behandeln
- Frühe CRDT-basierte Baumalgorithmen waren schwer zu implementieren und hatten hohen Speicher-Overhead, doch durch Optimierungen und Verbesserungen entstanden Baum-Synchronisationsalgorithmen, die für einige Produktionsumgebungen geeignet sind
- Es gibt zwei repräsentative CRDT-basierte Ansätze
Kleppmann-Ansatz: Alle Operationen als Move vereinheitlichen
- A highly-available move operation for replicated trees vereinheitlicht Erzeugen, Löschen und Verschieben in einem Baum zu einer einzigen move-Operation
- Eine move-Operation ist durch vier Werte
Move t p m c definiert
t: ein eindeutiger und sortierbarer Timestamp, etwa ein Lamport Timestampp: ID des Elternknotensm: mit dem Knoten verbundene metadatac: ID des Kindknotens
- Wenn
c noch nicht im Baum existiert, wird daraus eine Erzeugen-Operation, die unter Parent p das Kind c anlegt
- Wenn
c bereits existiert, wird daraus eine Verschieben-Operation, die den Knoten vom bisherigen Parent zum neuen Parent p verschiebt
- Löschen wird als Verschieben in einen festgelegten Knoten
TRASH behandelt
- Alle Unterknoten von
TRASH gelten als gelöscht
- Sie bleiben jedoch im Speicher, damit gleichzeitige Bearbeitungen diesen Knoten in einen anderen Knoten verschieben können
- Das ist ein Mechanismus, um Situationen zu behandeln, in denen das Löschen eines Vorfahren und das Verschieben eines Unterknotens gleichzeitig auftreten
Ordnung und unsafe operation
- Da auch Löschen als move-Operation definiert ist, wird „Löschen und Verschieben desselben Knotens“ zu einem Konflikt zweier move-Operationen
- Die verbleibenden Kernprobleme sind zwei
- Verschieben desselben Knotens unter unterschiedliche Eltern
- Verschieben unterschiedlicher Knoten und dadurch Erzeugen eines Zyklus
- Wenn alle Operationen mit Lamport Timestamp und Peer ID in eine lineare Reihenfolge gebracht werden, werden auch gleichzeitige Verschiebungen desselben Knotens als zwei geordnete Operationen dargestellt
- Modelliert man den Baum ausschließlich mit move-Operationen, reduziert sich der Ausnahmefall gleichzeitiger Bearbeitung auf die Erzeugung von Zyklen
- Eine Operation, die einen Zyklus erzeugt, wird als unsafe operation behandelt
- Der Algorithmus sortiert alle move-Operationen nach Timestamp
- Vor dem Anwenden jeder Operation wird ein Zyklus erkannt
- Würde ein Zyklus entstehen, wird diese unsafe operation ignoriert, um eine korrekte Baumstruktur zu erhalten
Lamport Timestamp und Anwenden entfernter Operationen
- Ein Lamport Timestamp ermöglicht es, die kausale Reihenfolge von Ereignissen in verteilten Systemen zu bestimmen
- Jeder Peer hat einen counter, der bei 0 beginnt
- Tritt ein lokales Ereignis auf, erhöht er den counter um 1 und verwendet diesen Wert als Timestamp
- Wenn Peer
A eine Nachricht an B sendet, hängt er den Timestamp an
B vergleicht seine logische Uhr mit dem empfangenen Timestamp und aktualisiert sie auf den größeren Wert
- Für die globale Sortierung wird zuerst der Lamport Timestamp verglichen; sind die Werte gleich, dient die eindeutige ID des Peers als Tie-Breaker
- Wenn ein entferntes Update in die Mitte der bereits sortierten Operationsfolge eingefügt wird, ist undo-do-redo erforderlich
- Die jüngsten Operationen werden rückgängig gemacht
- Die neue Operation wird eingefügt und angewendet
- Die rückgängig gemachten Operationen werden erneut angewendet
- Um move-Operationen schnell rückgängig zu machen, wird vor dem Anwenden jeder move-Operation der old parent des Zielknotens gecacht
- Auch wenn die Wirkung einer unsafe operation ignoriert wird, muss ihr Eintrag erhalten bleiben
- Die Sicherheit einer Operation wird dynamisch bestimmt
- Wenn später ein Update empfangen wird, bei dem ein anderer Knoten, der zuvor den Zyklus verursachte, zuerst gelöscht wird, kann eine früher unsafe Operation safe werden
- Im undo-Prozess ist eine Markierung als ineffective nötig, um den Ziel-Parent der letzten Operation zu finden, die tatsächlich wirksam war
undo-do-redo-Beispiel
- Wenn eine neue Operation von einer Operation abhängt, die lokal nicht vorhanden ist, fehlt noch ein Zwischenversions-Update; sie muss daher vorübergehend zwischengespeichert und erst nach Empfang des fehlenden Updates angewendet werden.
- Ist die neue
opId größer als die aller bestehenden Operationen, kann sie sofort angewendet werden.
- Ist sie safe, wird der aktuelle Parent des Zielknotens als old parent aufgezeichnet und der Move angewendet.
- Ist sie unsafe, wird sie als ineffective markiert und ihre Wirkung ignoriert.
- Wird die neue
opId in die Mitte der bestehenden Reihenfolge eingefügt, werden die nachfolgenden Operationen der Reihe nach herausgenommen und rückgängig gemacht; danach wird die neue Operation angewendet, und die rückgängig gemachten Operationen werden in Reihenfolge erneut angewendet.
- Im Beispielfluss verschiebt
Peer1 lokal C unter B und erhält anschließend von Peer0 die Operation, die B unter C verschiebt.
- Da
0:3 in der Lamport-Timestamp-Reihenfolge vor 1:3 liegt, wird zuerst 1:3 per Undo zurückgenommen, sodass C zu seinem old parent A zurückkehrt.
- Danach wird mit
0:3 B unter C verschoben.
- Anschließend wird
1:3 erneut per Redo angewendet und versucht, C unter B zu verschieben; dabei wird jedoch ein Zyklus erkannt, sodass die Operation nicht angewendet wird.
- Der Baumzustand bleibt unverändert, und der undo-do-redo-Prozess ist abgeschlossen.
Evan-Wallace-Ansatz: frühere Parents nachverfolgen
- Evan Wallace’ CRDT: Mutable Tree Hierarchy lässt jeden Knoten alle früheren Parent-Knoten nachverfolgen.
- Jeder aufgezeichnete Parent erhält einen Counter.
- Der count-Wert des neuen Parents ist um 1 größer als alle früheren Parent-counts dieses Knotens.
- Der Parent mit dem höchsten count wird zum aktuellen Parent.
- Bei der Synchronisierung werden auch die Parent-Aufzeichnungen synchronisiert.
- Wenn ein Zyklus entsteht, hängt ein heuristischer Algorithmus den Knoten, der den Zyklus verursacht hat, wieder an den nächstliegenden früheren Parent, der keinen Zyklus erzeugt und mit der root verbunden ist.
- Dieser Vorgang wird wiederholt, bis alle zyklischen Knoten wieder in den Baum eingehängt sind, wodurch die Baumstruktur zwischen Replicas synchronisiert wird.
- Dieser Ansatz benötigt keinen teuren undo-do-redo-Ablauf, kann aber bei vielen Knoten schlechte Performance haben, weil bei jedem eingehenden Remote-Move geprüft werden muss, ob alle Knoten mit der root verbunden sind, und zyklische Knoten wieder eingehängt werden müssen.
- Für den Performance-Vergleich wurde ein eigener Benchmark erstellt.
Loros Movable-Tree-Implementierung
- Loro implementiert den Algorithmus aus A highly-available move operation for replicated trees von Martin Kleppmann et al.
- Dieser Algorithmus liefert in den meisten realen Szenarien hohe Performance.
- Der zentrale undo-do-redo-Prozess ähnelt sehr der Art, wie in Loro der Eg-walker (Event Graph Walker) Remote-Updates anwendet.
- Ein verschiebbarer Baum allein löst das Problem der Reihenfolge von Geschwisterknoten nicht.
- Bei Outline-Notes oder der Layer-Verwaltung in Grafikdesign-Software müssen Child-Knoten sortiert werden.
- Nutzer müssen die Reihenfolge von Knoten anpassen und sie mit anderen Mitwirkenden oder Geräten synchronisieren.
- Loro integriert den
Fractional Index-Algorithmus, um Child-Knoten eines verschiebbaren Baums sortierbar zu machen.
Fractional Index und Konflikte bei gleichzeitigen Einfügungen
Fractional Index weist jedem Objekt einen sortierbaren Wert zu.
- Wird zwischen zwei Objekten etwas Neues eingefügt, liegt der
Fractional Index des neuen Objekts zwischen dem linken und dem rechten Wert.
- Erklärungen dazu finden sich im Figma-Blog und im Evan-Blog.
- Wenn in einer verteilten Umgebung mehrere Peers an derselben Position einen neuen Knoten einfügen, kann Knoten mit unterschiedlichen Inhalten derselbe
Fractional Index zugewiesen werden.
- Loro behält identische
Fractional Index-Werte bei; die relative Reihenfolge zwischen gleichen Indizes wird über die PeerID, die eindeutige ID jedes Peers, bestimmt.
- Befindet sich auf beiden Seiten derselbe
Fractional Index, kann dazwischen kein neuer Fractional Index erzeugt werden.
- Loro behandelt dieses Problem auf zwei Arten.
- Den erzeugten
Fractional Index-Werten wird eine gewisse Menge jitter hinzugefügt, um die Wahrscheinlichkeit identischer Indizes stark zu verringern.
- Wenn der Wert zwischen 0 und 1 ursprünglich etwa 0,5 wäre, kann er durch random jitter beispielsweise zu
0.52712, 0.58312 oder 0.52834 werden.
- Wenn zwischen
0.7@A und 0.7@B eingefügt werden muss, kann dies zurückgesetzt werden, indem zwischen 0,7 und 1 jeweils ein neuer Fractional Index für den neuen Knoten und den Knoten 0.7@B vergeben wird.
Encoding-Größe und jitter-Einstellung
- Loro verwendet die auf
Vec<u8> basierende Fractional Index-Implementierung von drifting-in-space.
- Diese Implementierung nutzt Basis 256.
- Bei den Default-Werten muss man fortlaufend 128 Werte nach vorne oder nach hinten einfügen, damit die Byte-Größe des
Fractional Index um 1 steigt.
- Der Worst-Case-Speicher-Overhead entsteht, wenn neue Werte jedes Mal abwechselnd eingefügt werden.
- Zum Beispiel, indem man bei
ab ein c zwischen a und b einfügt, dann d zwischen c und b, anschließend e zwischen c und d usw.
- In solchen Fällen kann eine neue Operation ein zusätzliches Byte benötigen, das ist jedoch sehr selten.
- Loro ergänzt die ursprüngliche Implementierung um eine einfache jitter-Lösung.
- An den
Fractional Index werden random bytes in der Länge des jitter-Werts angehängt.
- In JavaScript lässt sich jitter aktivieren, indem man eine positive Zahl an
doc.setFractionalIndexJitter(number) übergibt.
- Die Encoding-Größe wächst leicht; pro
Fractional Index kommen jitter bytes hinzu.
- Die Beziehung zwischen jitter und der maximalen Zahl gleichzeitiger Bearbeitungen
n, um bei der Erstellung eines Fractional Index an derselben Position mit 99 % Wahrscheinlichkeit Kollisionen zu vermeiden, ist wie folgt:
| jitter |
maximale Zahl gleichzeitiger Bearbeitungen |
| 1 |
3 |
| 2 |
37 |
| 3 |
582 |
- Viele sortierte
Fractional Index-Werte haben häufig gemeinsame Prefixe.
- Loro reduziert die gesamte Encoding-Größe durch eine Prefix-Optimierung, bei der beim Encoding nur die Zahl der Prefix-Bits gespeichert wird, die mit dem vorherigen Wert übereinstimmen, sowie die verbleibenden Bytes.
Verwandte Arbeiten und Gründe für die Wahl
- Neben
Fractional Index gibt es Movable-List-CRDTs, mit denen sich sibling-Knoten eines Baums ordnen lassen.
- Martin Kleppmanns Moving Elements in List CRDTs wird für Loros Movable List verwendet.
- Die
Fractional Index-Lösung ist einfacher zu implementieren.
- Wenn man beim Modellieren von Baumknoten den Child-Knoten keine stable position representation bietet, wird die gesamte Baumstruktur übermäßig komplex.
Fractional Index hat ein Interleaving-Problem.
- In Fällen wie Figma-Layer-Items oder Multi-Level-Bookmarks, in denen nur die relative Reihenfolge benötigt wird und keine strikte sequenzielle Semantik erforderlich ist, ist das akzeptabel.
Benchmark-Ergebnisse
- Loro hat für die Movable-Tree-Implementierung die Performance unter Extrembedingungen wie zufälligen Node-Verschiebungen, Wechseln zu früheren Versionen und sehr tiefen Baumstrukturen benchmarked
- Die Ergebnisse liegen auf einem Niveau, das Echtzeit-Kollaboration und ein reibungsloses Checkout früherer Versionen unterstützen kann
- Die Testumgebung ist eine M2 Max CPU, der Benchmark-Code befindet sich in tree.rs
| Vorgang |
Zeit |
Konfiguration |
| 10000 zufällige Verschiebungen |
28ms |
Zuerst 1000 Nodes erzeugt |
| 1000 Wechsel zu unterschiedlichen Versionen |
153ms |
Zuerst 1000 Nodes erzeugt, danach 1000 Verschiebungen |
| 1000 Wechsel zu unterschiedlichen Versionen in einem Baum mit Tiefe 300 |
701ms |
Jeder neue Node ist Kind des vorherigen Nodes |
Beispiele und Demo
LoroTree aus loro-crdt bietet das Erzeugen von Nodes, das Erzeugen an einer bestimmten Position, Verschieben, Verschieben zur Root, Verschieben vor oder nach andere Nodes, Abfragen des Index innerhalb des Elternknotens, Abfragen des Fractional Index sowie Zugriff auf die Data-Map eines Nodes
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
- Es wurde eine Todo-App-Demo erstellt, die mit Loro die Datensynchronisierung zwischen mehreren Peers simuliert
Movable Tree stellt Subtask-Beziehungen darMap stellt mehrere Eigenschaften eines Tasks darText stellt den Task-Titel dar- Neben Erstellen, Verschieben, Bearbeiten und Löschen ist auch ein auf Loro basierender Versionswechsel implementiert
- Durch Ziehen der Scrollbar kann zwischen allen ausgeführten früheren Versionen gewechselt werden
Fazit
- Die Implementierung eines verschiebbaren Baum-CRDT ist schwierig wegen gleichzeitiger Verschiebungen, Löschungen, Zyklen sowie Kombinationen aus dem Löschen von Vorfahren und dem Verschieben von Nachfahren
- Loro implementiert Verschiebungen in der Baumhierarchie mit dem hochverfügbaren Move-Operation-Algorithmus von Kleppmann et al.
- Verschiebungen und Sortierung zwischen Kind-Nodes werden durch Integration der
Fractional Index-Implementierung von drifting-in-space verarbeitet
- Diese Kombination kann die Anforderungen verschiedener Szenarien für kollaborative Anwendungen erfüllen
1 Kommentare
Meinungen auf Hacker News
Ich baue gerade einen neuen Multiplayer-Editor [1] für Aufgaben/Notizen, der sowohl Text- als auch Outliner-Operationen unterstützt.
Nach außen verhält er sich wie ein flaches Textdokument, wegen der Outliner-Funktionen ist er intern jedoch ein großer Baum. Für die Synchronisierung von Änderungen verwenden wir einen Ansatz, der hochverfügbaren Move-Operationen ähnelt. Es gibt nur eine Operation, die den Baum verändert:
insmov. Wenn der Client online ist, synchronisiert er die Änderungsmenge C mit dem Server. Hat der Server entfernte Änderungen, gibt er alle Änderungen R seit der letzten Synchronisierung in einer globalen linearen Reihenfolge zurück; dann werden dieinsmov-Operationen der lokalen Änderungen C rückgängig gemacht, und R sowie neue, noch nicht synchronisierte Änderungen werden erneut angewendet.Wir verwenden keine Fractional Indexes; das
insmov-Tupel enthält neben dem Parent P auch die vorherige Geschwister-guidA. Da alle Baumoperationen letztlich in der vom Server festgelegten globalen linearen Reihenfolge angewendet werden, wird die Sortierung durch dieinsmov-Operation selbst behandelt. Meist ist kein Rückgängigmachen nötig; eine korrekte Wiedergabe in der richtigen Reihenfolge ist nur erforderlich, wenn es auf dem Serverinsmov-Änderungen gibt, die ich nicht kenne, und ich gleichzeitig ein neuesinsmovsende. Das kann passieren, wenn man nach einem langen Flug wieder ins WLAN geht; online mit Echtzeit-Push über WebSocket ist es seltener und für Nicht-insmov-Operationen wie Text-Updates nicht nötig.[1] https://thymer.com
Zum Beispiel in der Form, dass statt Lamport-Zeitstempeln die Server-Reihenfolge genutzt wird.
[1] https://inria.hal.science/inria-00555588/
Als ich auf HN nach Thymer gesucht habe, fand ich ein Show HN[1] von 2009, und es sieht so aus, als wäre Thymer in den letzten 15 Jahren in privater Beta gewesen.
0. https://news.ycombinator.com/item?id=40786425
Diesen Artikel muss ich mir unbedingt ansehen. Bei einem Freelancer-Projekt für einen Kunden habe ich die React Table Library [0] als Open Source veröffentlicht und mich dabei auf Baumoperationen konzentriert.
Sie arbeiten mit Ordner-/Dateibaumstrukturen in der Größenordnung von 100.000 Knoten und handhaben das Verschieben und Duplizieren von Ordnern und Dateien sowie Lazy Loading auf oberster und verschachtelter Ebene innerhalb derselben Tabellenstruktur. Nachdem ich das Projekt abgeschlossen hatte, verstand ich, warum Google Drive Anzeige und Bearbeitung nur innerhalb derselben Hierarchieebene erlaubt. Wenn man das in einer verschachtelten Ansicht mit vielen Knoten umsetzen will, gibt es einfach zu viele Einschränkungen zu berücksichtigen.
[0] https://react-table-library.com/
Ich würde gern um Rat fragen. Es ist keine Multiplayer-App, aber im Frontend gibt es große, miteinander verknüpfte denormalisierte Bäume, die als Benutzerprofile dienen.
Man kann sich das wie ein kachelbasiertes Layout vorstellen: Nutzer können Kacheln hinzufügen/löschen/in der Größe ändern, mehreren Komponenten in jedem Kachel-Slot hinzufügen, und diese Komponenten haben wiederum jeweils eigene Profile. Es kann mehrere Layouts mit unterschiedlichen Kachelanordnungen geben, und zusätzlich wird es komplex, weil einzelne Kacheln auf andere Teile des globalen Zustands verweisen oder sie teilen können.
Mit gewöhnlichem REST lässt sich das nur schwer sicher aktualisieren. Man muss garantieren, dass derselbe Nutzer nicht zwei Tabs öffnet, in Tab 1 aktualisiert und dann in Tab 2 erneut aktualisiert, sodass das gesamte Profil ungültig wird. Insgesamt ist auch die Reihenfolge wichtig. Wenn der Server Updates überspringt, die auf dem Client korrekt angewendet wurden, kann alles kaputtgehen.
Als sehr einfache Lösung haben wir den minimalen Datensatz gesendet, mit dem sich ein bestimmtes Zustandsstück vollständig überschreiben lässt, und ihn hinten in eine Queue gestellt. Normalerweise ist das in Ordnung, aber manchmal ist die tatsächliche Änderung nur ein paar Bytes groß, während man 50 KB sendet, was verschwenderisch ist.
Die üblichen Gründe, warum man CRDTs braucht, haben wir nicht, aber selbst für einen einzelnen Nutzer scheint es die Zustandsverwaltung deutlich einfacher zu machen. Zum einen würde die Synchronisierung zwischen den Browser-Tabs des Nutzers funktionieren; wichtiger noch: Man könnte dem CRDT vertrauen, dass es Änderungen am Frontend-Zustand passend mit dem Server koordiniert. Man müsste das nicht mehr selbst erledigen. Ich frage mich, ob das sinnvoll ist oder ob der Overhead, etwas wie Yjs einzubauen, es nicht wert ist, wenn man weder Multiplayer noch Local-first braucht.
Wenn die Profilbearbeitung allerdings nur für einen einzelnen Nutzer gedacht ist, wirkt die Einführung eines CRDT übertrieben. Von außen betrachtet scheint das Szenario mit zwei geöffneten Tabs die größte Fehlerquelle zu sein; dafür könnte man
BroadcastChannelverwenden, um Update-Events an alle anderen Tabs zu melden.Gemeinsamen Zustand über REST-Aufrufe zu pflegen, die Teile des Serverzustands überschreiben, ist tatsächlich fragil und eignet sich im Grunde nur dafür, Felder in flachen Datensätzen zu überschreiben. Außerdem muss man die Abstimmung zwischen Server- und Client-Zustand immer sorgfältig bedenken, und auf Pfaden außerhalb des Normalfalls gerät die Synchronisierung leicht aus dem Takt.
Wie gesagt: Wenn ihr ein CRDT erstellt, das explizit beschreibt, wie Updates zusammengeführt werden, dürfte das die kognitive Belastung deutlich reduzieren.
Bei Rich-Text-Inhalten wie Google Docs oder Zoho Writer sind Vorgänge wie das Verschieben eines Listeneintrags nach unten oder das Hinzufügen einer neuen Spalte, also Tabellen-/Listenoperationen, im Kern Baum-Manipulationsoperationen.
Gleichzeitige Konflikte in solchen Fällen sind berüchtigt schwer zur Konvergenz zu bringen, wenn es keine kontextspezifische Sonderbehandlung gibt [1]. Ich frage mich, ob diese Implementierung auch für solche Use Cases eine verallgemeinerte Lösung bietet.
Vermutlich könnte man für Leaf Nodes, also Textblöcke, Listen- oder String-CRDTs verwenden und für Strukturknoten wie Listen und Tabellen dieses Tree-CRDT kombinieren. Dann müsste man aber jeder Operation eine zweidimensionale Adresse
(parent-id, index_offset_into_that_parent)anhängen.[1] https://github.com/inkandswitch/peritext/issues/27
Ein Text-CRDT ist im Grunde nur ein Listen-CRDT, das Zeichendaten enthält. Daher lassen sich eingebettete Elemente leicht als spezielle Einträge der Größe 1 modellieren, wie andere Einträge im String, also als eingebettete Child Nodes. Mit dem richtigen Ansatz kann man je nach Bedarf verschiedene CRDTs innerhalb des Baums mischen. Zum Beispiel eine Tabelle in Rich Text, und in einer ihrer Zellen ein Bild.
Ein
parent-crdt-id-Feld an jede Operation anzuhängen, ist unschön, scheint aber schwer zu vermeiden. Zum Glück dürften in den meisten realen Use Cases aufeinanderfolgende Operationen sehr häufig dasselbe Parent-CRDT teilen, sodass sich solche ID-Felder mit Run-Length-Encoding gut komprimieren lassen.Wie Seph aber gesagt hat, lassen sich aufeinanderfolgende Operationen unter demselben Parent effektiv komprimieren, sodass der amortisierte Overhead dieser Parent-IDs normalerweise nicht groß ist.
Ich frage mich, ob es praktische CRDTs für datenintensive Anwendungen wie Bildpixel oder 3D-Modelle gegeben hat.
Selbst wenn die konkrete Repräsentation des Dokuments datenintensiv ist, kann die Codierung einzelner Bearbeitungen und Operationen der Nutzer weiterhin klein sein.
Angenommen, man baut einen Bildeditor wie Photoshop: Ein unkomprimiertes Bild mit 102 Megapixeln und 16 Bit Farbtiefe pro Kanal, etwa ein Foto der Fujifilm GFX100, ist als TIFF ungefähr 610 MB groß. Wenn man jedes Pixel als separates Last-Write-Wins-Register darstellt, ist der Overhead groß, aber diese Darstellung passt in der Praxis nicht wirklich dazu, die Nutzerintention zu bewahren. Die Bearbeitungen, die Nutzer vornehmen, sind Dinge wie „Bildkontrast um 15 % erhöhen“ oder „Spline [(0,0), (1500, 1500)] mit Pinsel Q und Farbe #000 malen“. Wenn jedes Pixel per Lamport-Timestamp synchronisiert wird, wird die Kontraständerung von Nutzer 1 auf alle Pixel angewendet außer auf die von Nutzer 2 übermalten, sodass die übermalten Pixel merkwürdig aussehen können.
Besser ist es, Nutzerintention als Liste von Bearbeitungsoperationen darzustellen. Das ist viel kleiner als das gesamte 102-MB-Pixelraster. CRDT-Datenstrukturen sind ein möglicher technischer Mechanismus, um solche Nutzerintentionen zu synchronisieren, aber die Struktur sollte passend zur Semantik der Nutzerintention gewählt werden, nicht zur konkreten Datenanordnung der Ausgabe.
Trotzdem kann es Bearbeitungsoperationen geben, die große Datenmengen enthalten, etwa
"add new layer namedbgbelow layerfgwith pixelsdata:(10mb of pixels)at (1500, 1500)". Der Synchronisations-Overhead eines solchen Bearbeitungsbefehls ist aber sehr gering, und seine Größe ist O(1), nicht O(pixels) proportional zur Pixelzahl im Bearbeitungsbefehl.3D-Modelle sind ein anderes Problem, und ich habe noch kein kollaboratives 3D-Modellierungstool auf dem Markt gesehen. Aktiv danach gesucht habe ich allerdings nicht.
Ich habe es nicht selbst gebaut und bin auch nicht sicher, ob es in der Praxis brauchbar wäre. Aber zumindest könnte man damit die gesamte Historie des Dokuments bewahren.
Es stellt die Daten mit Yjs dar, speichert aber statt der Rohpixel die gesamte Historie der Transformationen.
https://digest.browsertech.com/archive/browsertech-digest-ho...
Ich frage mich, ob der Text mit GPT geprüft wurde. Im ersten Absatz spüre ich stark den ChatGPT-Stil.
This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.