Konvergenz ist nicht genug: Wenn Automerge-Merges Datenstrukturen zerbrechen
Convergence is not enough
Im Livelymerge-Projekt wird der Heap eines laufenden Systems als Automerge-Dokument behandelt. Doch wie ein Beispiel mit einer verketteten Liste zeigt, garantiert Automerge zwar Konvergenz, aber nicht die Einhaltung von Invarianten: Gleichzeitige Änderungen können zu Zyklen oder abgeschnittenen Listen führen. Das Problem liegt darin, dass Effekte statt Absichten zusammengeführt werden. Ein vielversprechender Ansatz sind merge-fähige Datentypen, die Operationen auf höherer Ebene aufzeichnen, ähnlich wie Automerge es für eingebaute Typen tut.
Konvergenz ist nicht genug.
- wim
Wir bauen eine Multiplayer-IDE [1], aber für Dokumente/Planung, wo Dokumente Bäume/Graphen sein müssen (um Outlines, Referenzen, Transklusionen usw. zu unterstützen).
Wir können nicht einfach jede Art von Operation bedingungslos durch Replay zusammenführen, weil das zum Beispiel Baumzyklen verursachen kann. Wie bei der verlinkten Liste können bestimmte Operationen lokal für einen Offline-Client gültig sein, aber nicht global in der konvergierten Reihenfolge.
Unsere Sync-Engine unterscheidet zwischen verschiedenen Arten von Operationen: unbedingte Operationen und bewachte Operationen.
Unbedingte Operationen können keine strukturellen/Datenmodell-Invarianten verletzen. Zum Beispiel SetCompleted(task_guid, true). Einfaches Last-Writer-Wins.
Bewachte Operationen können die Topologie verändern, wie InsertMove(node_guid, parent_guid, after_guid). Diese werden gegen den aktuellen Zustand geprüft, nicht gegen den Zustand, als sie erstellt wurden. Während des Replays machen wir zuerst optimistische lokale Operationen rückgängig und spielen dann die eingehenden kanonischen Operationen in der Reihenfolge ab. Die Mutator-Funktion für jede Operation validiert den aktuellen Zustand, bevor sie angewendet wird, und wenn sie eine Bedingung verletzen würde (zum Beispiel durch einen Zyklus, weil ein anderer Client in der Zwischenzeit eine andere Bewegung gemacht hat), wird sie deterministisch abgelehnt. In unserem Fall haben wir auch einen autoritativen Server, sodass wir dieselben bewachten Operationen auch für Bedingungen jenseits der Datenstruktur verwenden können, wie zum Beispiel Berechtigungen, sodass die Mutator-Funktion AddUser(workspace_guid, user_guid) zuerst den Berechtigungszustand prüfen kann.
- alexisread
Relevantes Papier zu Gittertypen (BloomL):
https://dsf.berkeley.edu/papers/UCB-lattice-tr.pdf
Zusätzlich benötigen Sie ein kausales Register (pro Schlüssel eine Merkle-Uhr), um gleichzeitige Änderungen zu ordnen, anstatt eine zu verwerfen.
Schließlich benötigen Sie wahrscheinlich ein Pijul-ähnliches VCS, um semantische Merges zu handhaben.
- Animats
Das basiert offenbar auf Automerge.[1] Es klingt nach einer wirklich guten Idee. Ist es eine gute genug Idee, um MMO-Spiel-Clients und -Server zu synchronisieren?
Papier von 2012, letzte Automerge-Website-Aktualisierung 2025. Warum ist das nicht überall?