La convergencia no es suficiente
Convergence Is Not Enough
En el proyecto Livelymerge, el heap de un sistema vivo es un documento Automerge, pero fusionar el estado de un programa en ejecución puede violar invariantes. Un ejemplo con una lista enlazada muestra cómo dos intercambios concurrentes producen una lista truncada o un ciclo, porque Automerge reproduce escrituras, no intenciones. Aunque los tipos integrados de Automerge (arrays, mapas) se fusionan bien, la composición de estos tipos rompe invariantes como listas doblemente enlazadas o árboles. El autor explora la idea de tipos conscientes de la fusión, que registren operaciones de alto nivel en lugar de escrituras de bajo nivel, citando el trabajo de Kleppmann y Coln.
La fusión reproduce efectos, no intenciones, y los invariantes del programador —que cada nodo aparezca exactamente una vez, que no haya ciclos, que la lista termine— nunca se escribieron en ningún lugar que Automerge pudiera ver.
- wim
Estamos construyendo un IDE multijugador [1] pero para docs/planificación donde los docs necesitan ser árboles/grafos (para soportar esquemas, referencias, transclusiones, etc.)
No podemos simplemente fusionar cualquier tipo de operación reproduciéndolas incondicionalmente, porque eso puede causar ciclos en el árbol, por ejemplo. Como en la lista enlazada, ciertas operaciones pueden ser válidas localmente para un cliente sin conexión, pero no globalmente en el orden convergido.
Nuestro motor de sincronización distingue entre diferentes tipos de operaciones: operaciones incondicionales y operaciones con guardas.
Las operaciones incondicionales no pueden violar invariantes estructurales o del modelo de datos. Por ejemplo, SetCompleted(task_guid, true). Simplemente último escritor gana.
Las operaciones con guardas pueden mutar la topología, como InsertMove(node_guid, parent_guid, after_guid). Estas se comprueban contra el estado actual, no contra el estado en el que se crearon. Durante la reproducción, primero revertimos las operaciones locales optimistas y reproducimos las operaciones canónicas entrantes en orden. La función mutadora de cada operación valida el estado actual antes de aplicarla y si violara una condición (por ejemplo, creando un ciclo porque otro cliente hizo otro movimiento mientras tanto) se rechaza de forma determinista. En nuestro caso también tenemos un servidor autoritativo, así que podemos usar las mismas operaciones con guardas para condiciones más allá de la estructura de datos, como permisos, por lo que la función mutadora de AddUser(workspace_guid, user_guid) puede comprobar primero el estado de permisos, por ejemplo.
- alexisread
Artículo relevante sobre tipos de retículo (BloomL):
https://dsf.berkeley.edu/papers/UCB-lattice-tr.pdf
Además de esto, necesitarás un registro causal (reloj de Merkle por clave) para ordenar ediciones concurrentes, en lugar de descartar una.
Por último, es probable que necesites un VCS estilo Pijul para manejar fusiones semánticas.
- Animats
Esto aparentemente se basa en Automerge.[1] Suena como una muy buena idea. ¿Es una idea lo suficientemente buena como para sincronizar clientes y servidores de juegos MMO?
Artículo de 2012, última actualización del sitio de Automerge en 2025. ¿Por qué no está en todas partes?