- En software colaborativo, editar simultáneamente una estructura jerárquica puede provocar conflictos de árbol como nodos duplicados, ciclos o mover nodos hijos de ancestros eliminados, y Loro lo implementa con un CRDT de árbol movible
- El enfoque de Martin Kleppmann y otros unifica crear, eliminar y mover en
Move t p m c, y trata la eliminación como un movimiento al nodo TRASH, preservando los movimientos simultáneos de nodos hijos
- El orden global se construye con Lamport Timestamp y Peer ID, y cuando una operación remota entra en medio del orden existente se usa undo-do-redo para evitar ciclos
- Loro combina Fractional Index para ordenar nodos hermanos, y cuando los índices se superponen por inserciones simultáneas en la misma posición, lo resuelve con PeerID, jitter y reinicio de índices
- En benchmarks, Loro Movable Tree mostró rendimiento suficiente para colaboración en tiempo real y checkout de versiones anteriores al ejecutar 10,000 movimientos aleatorios en 28 ms después de crear 1,000 nodos
Conflictos que surgen en árboles colaborativos
- En sistemas distribuidos y software colaborativo, al gestionar relaciones jerárquicas, modelar un movimiento como una combinación de eliminación e inserción puede hacer que las expectativas del usuario y la resolución de conflictos no coincidan fácilmente
- Si el mismo nodo se mueve simultáneamente a distintos padres en varias réplicas, un nodo puede eliminarse dos veces y recrearse bajo ambos padres, generando nodos duplicados con el mismo contenido
- Las operaciones básicas de un árbol movible son tres: creación, eliminación y movimiento
- Las situaciones que más suelen causar problemas durante la sincronización son las siguientes
- El mismo nodo se elimina y se mueve al mismo tiempo
- El mismo nodo se mueve bajo padres distintos
- La combinación de movimientos de nodos distintos genera un ciclo
- Un nodo hijo se mueve mientras se elimina un nodo ancestro
Cómo se maneja cada tipo de conflicto
- Si entran en conflicto la eliminación y el movimiento del mismo nodo, según el timestamp del sistema distribuido o los requisitos de la aplicación, se puede aplicar una operación e ignorar la otra
- Cuando el mismo nodo se mueve bajo padres distintos, las opciones varían según la aplicación
- Eliminar el nodo y luego crear copias bajo padres distintos, tratándolas después de forma independiente
- Permitir que un nodo apunte a dos padres, aunque esto rompe la estructura de árbol y en general es difícil de aceptar
- Ordenar todas las operaciones y aplicarlas en secuencia para producir el mismo resultado en todos los peers
- Cuando movimientos de nodos distintos crean un ciclo, la resolución de conflictos en un árbol movible se vuelve especialmente compleja
- Matthew Weidner resume opciones como manejo de errores, renderizar una zona de “time-out”, rechazo desde el servidor, omitir operaciones que generen ciclos tras ordenamiento topológico, ocultar cierto edge al renderizar, o volver al padre anterior
- También es fácil pasar por alto el caso en que un nodo hijo se mueve mientras se elimina un nodo ancestro
- Si se eliminan de inmediato todos los descendientes del ancestro, el usuario puede pensar que sus datos se perdieron
El enfoque de Dropbox y Figma
- Dropbox al principio manejaba el movimiento de archivos en dos pasos: eliminar en la ubicación original y luego crear en la nueva ubicación
- Si ocurría un apagón o un fallo del sistema entre la eliminación y la creación, existía riesgo de pérdida de datos
- Actualmente detecta conflictos cuando varias personas intentan mover y guardar el mismo archivo al mismo tiempo, y por lo general guarda una versión del archivo original y crea una “conflicted copy” para los cambios de uno de los usuarios
- Figma considera que la estructura de árbol es la parte más compleja de un sistema colaborativo y asigna una propiedad
parent a cada elemento
- Un servidor central supervisa las actualizaciones de varios usuarios y rechaza cualquier operación que pueda crear un ciclo
- Debido a la latencia de red, puede surgir temporalmente un ciclo antes de que el servidor rechace la operación
- En ese caso, Figma oculta temporalmente los elementos incluidos en el ciclo y preserva el estado hasta que el servidor rechace oficialmente la operación
- La explicación relacionada puede verse en el artículo sobre la tecnología multijugador de Figma
Dos enfoques de CRDT para árboles movibles
- En lugar de una solución centralizada, la estructura de árbol colaborativa puede manejarse con CRDT
- Los primeros algoritmos de árbol basados en CRDT eran difíciles de implementar y tenían mucho overhead de almacenamiento, pero con optimizaciones y mejoras aparecieron algoritmos de sincronización de árboles aptos para algunos entornos de producción
- Hay dos enfoques representativos basados en CRDT
Enfoque de Kleppmann: unificar todas las operaciones como Move
- A highly-available move operation for replicated trees unifica creación, eliminación y movimiento del árbol en una sola operación move
- La operación move se define con cuatro valores:
Move t p m c
t: un timestamp único y ordenable, como Lamport timestampp: ID del nodo padrem: metadata asociada al nodoc: ID del nodo hijo
- Si
c no existe en el árbol, la operación actúa como creación, creando el hijo c bajo el padre p
- Si
c ya existe, la operación actúa como movimiento, trasladándolo desde su padre actual al nuevo padre p
- La eliminación se maneja como un movimiento al nodo
TRASH
- Todos los nodos descendientes de
TRASH se consideran eliminados
- Pero permanecen en memoria para permitir que una edición concurrente pueda mover ese nodo a otro lugar
- Es un mecanismo para manejar situaciones en las que coinciden la eliminación de un ancestro y el movimiento de un nodo hijo
Ordenamiento y unsafe operation
- Como la eliminación también se define como una operación move, el caso de “eliminar y mover el mismo nodo” se convierte en un conflicto entre dos operaciones move
- Quedan dos problemas centrales
- Mover el mismo nodo bajo padres distintos
- Mover nodos distintos para crear un ciclo
- Si todas las operaciones se ordenan linealmente con Lamport timestamp y Peer ID, incluso los movimientos simultáneos del mismo nodo se expresan como dos operaciones con orden
- Si el árbol se modela solo con operaciones move, las situaciones excepcionales de la edición concurrente se reducen a la creación de ciclos
- Las operaciones que crean ciclos se tratan como unsafe operation
- El algoritmo ordena todas las operaciones move por timestamp
- Antes de aplicar cada operación, detecta si se produciría un ciclo
- Si lo genera, ignora esa unsafe operation para mantener una estructura de árbol válida
Lamport Timestamp y aplicación de operaciones remotas
- Lamport Timestamp permite determinar el orden causal de los eventos en sistemas distribuidos
- Cada peer tiene un contador que comienza en 0
- Cuando ocurre un evento local, incrementa el contador en 1 y usa ese valor como timestamp
- Cuando el peer
A envía un mensaje a B, adjunta el timestamp
B compara su reloj lógico con el timestamp recibido y lo actualiza al valor mayor
- El orden global primero compara el Lamport Timestamp y, si los valores son iguales, usa el ID único del peer como tie-breaker
- Cuando una actualización remota entra en medio de la secuencia ya ordenada de operaciones, se necesita undo-do-redo
- Se revierten las operaciones recientes
- Se inserta y aplica la nueva operación
- Se vuelven a aplicar las operaciones revertidas
- Para deshacer rápidamente una operación move, se almacena en caché el old parent del nodo objetivo antes de aplicar cada move
- Las unsafe operation deben conservarse en el registro aunque se ignore su efecto
- La seguridad de una operación se determina dinámicamente
- Si después llega una actualización que primero elimina otro nodo que estaba causando el ciclo, una operación antes considerada unsafe puede volverse safe
- Durante el proceso de undo, se necesita una marca de ineffective para encontrar el padre objetivo de la última operación que sí tuvo efecto
Ejemplo de undo-do-redo
- Si una operación nueva depende de una operación que no existe localmente, la actualización de la versión intermedia todavía falta, así que primero debe guardarse en una caché temporal y aplicarse después de recibir la actualización faltante.
- Si el nuevo
opId es mayor que todas las operaciones existentes, puede aplicarse de inmediato.
- Si es safe, se registra el padre actual del nodo objetivo como old parent y se aplica el move.
- Si es unsafe, se marca como ineffective y se ignora su efecto.
- Si el nuevo
opId entra en medio del orden existente, se deshacen una por una las operaciones posteriores, se aplica la nueva operación y luego se reaplican en orden las operaciones deshechas.
- En el flujo de ejemplo,
Peer1 mueve localmente C debajo de B, y luego recibe una operación de Peer0 que mueve B debajo de C.
- Como en el orden del Lamport timestamp
0:3 va antes que 1:3, primero se hace undo de 1:3 para devolver C a su old parent A.
- Después, con
0:3, se mueve B debajo de C.
- Luego se hace redo de
1:3 para intentar mover C debajo de B, pero se detecta un ciclo y no se aplica.
- El estado del árbol no cambia y el proceso de undo-do-redo se completa.
Método de Evan Wallace: seguimiento de padres pasados
- CRDT: Mutable Tree Hierarchy de Evan Wallace hace que cada nodo rastree todos sus nodos padre históricos.
- A cada padre registrado se le asigna un contador.
- El valor count del nuevo padre es 1 mayor que el count de todos los padres históricos de ese nodo.
- El padre con el count más alto se convierte en el padre actual.
- Al sincronizar, también se sincronizan los registros de padres.
- Si ocurre un ciclo, un algoritmo heurístico vuelve a adjuntar el nodo que causó el ciclo al padre histórico más cercano que no genere un ciclo y que esté conectado al root.
- Este proceso se repite hasta que todos los nodos cíclicos queden nuevamente adjuntados al árbol, sincronizando así la estructura del árbol entre réplicas.
- Este método no requiere el costoso proceso de undo-do-redo, pero cada vez que llega un move remoto hay que verificar si todos los nodos están conectados al root y volver a adjuntar los nodos cíclicos, por lo que el rendimiento puede empeorar cuando hay muchos nodos.
- Se creó por separado un benchmark para comparar rendimiento.
Implementación de Movable Tree en Loro
- Loro implementa el algoritmo A highly-available move operation for replicated trees de Martin Kleppmann y otros.
- Este algoritmo ofrece alto rendimiento en la mayoría de los escenarios reales.
- El proceso clave de undo-do-redo es muy similar a cómo Eg-walker (Event Graph Walker) aplica actualizaciones remotas en Loro.
- Un árbol movible por sí solo no resuelve el problema del orden de los nodos hermanos.
- En outline notes o en la gestión de layers de software de diseño gráfico, se necesita ordenar los nodos hijos.
- Los usuarios deben poder ajustar el orden de los nodos y sincronizarlo con otros colaboradores o dispositivos.
- Loro integra el algoritmo
Fractional Index para hacer ordenables los nodos hijos de un árbol movible.
Fractional Index y conflictos de inserción concurrente
Fractional Index asigna a cada objeto un valor ordenable.
- Si se inserta un nuevo elemento entre dos objetos, el
Fractional Index del nuevo objeto queda entre el valor izquierdo y el derecho.
- La explicación relacionada puede verse en el blog de Figma y en el blog de Evan.
- En un entorno distribuido, si varios peers insertan nodos nuevos en la misma posición, a nodos con contenido distinto se les puede asignar el mismo
Fractional Index.
- Loro mantiene el mismo
Fractional Index, y el orden relativo entre índices iguales se determina con el PeerID, el ID único de cada peer.
- Si el mismo
Fractional Index está en ambos lados, no se puede crear un nuevo Fractional Index entre ellos.
- Loro maneja este problema de dos formas.
- Añade una cierta cantidad de jitter al
Fractional Index generado para reducir mucho la probabilidad de que aparezcan índices idénticos.
- Por ejemplo, si el valor entre 0 y 1 originalmente fuera 0.5, con random jitter podría convertirse en valores como
0.52712, 0.58312 o 0.52834.
- Si hay que insertar entre
0.7@A y 0.7@B, puede reajustarse asignando nuevos Fractional Index tanto al nuevo nodo como al nodo 0.7@B dentro del rango entre 0.7 y 1.
Tamaño de codificación y configuración de jitter
- Loro usa la implementación de
Fractional Index basada en Vec<u8> de drifting-in-space.
- Esta implementación usa base 256.
- Con la configuración predeterminada, el tamaño en bytes de
Fractional Index aumenta en 1 solo cuando hay que seguir insertando 128 valores hacia adelante o hacia atrás.
- El peor overhead de almacenamiento ocurre cuando se insertan alternadamente valores nuevos cada vez.
- Por ejemplo, insertar
c entre a y b en ab, luego d entre c y b, y después e entre c y d.
- En ese caso, una sola operación nueva podría requerir un byte adicional, pero es una situación muy rara.
- Loro añade una solución simple de jitter a la implementación original.
- Agrega random bytes al final del
Fractional Index según la longitud del valor de jitter.
- En JavaScript, se puede activar el jitter pasando un número positivo a
doc.setFractionalIndexJitter(number).
- El tamaño de codificación aumenta ligeramente, y se agregan bytes de
jitter a cada Fractional Index.
- La relación entre el jitter necesario para evitar colisiones con 99% de probabilidad al crear
Fractional Index en la misma posición y el número máximo de ediciones concurrentes n es la siguiente.
| jitter |
Número máximo de ediciones concurrentes |
| 1 |
3 |
| 2 |
37 |
| 3 |
582 |
- Cuando hay muchos
Fractional Index ordenados, tienden a compartir muchos prefijos comunes.
- Loro reduce el tamaño total de codificación con una optimización de prefijos que, al codificar, guarda el número de bits de prefijo iguales al valor anterior y solo los bytes restantes.
Trabajos relacionados y motivos de la elección
- Además de
Fractional Index, existen movable list CRDT que pueden ordenar nodos sibling en un árbol.
- Moving Elements in List CRDTs de Martin Kleppmann se usa en la Movable List de Loro.
- La solución con
Fractional Index es más simple de implementar.
- Al modelar nodos de árbol, si no se proporciona una representación estable de posición para los nodos hijos, toda la estructura del árbol se vuelve excesivamente compleja.
Fractional Index tiene un problema de interleaving.
- En casos como items de layers de Figma o bookmarks multinivel, donde solo se necesita orden relativo y no una semántica secuencial estricta, esto es aceptable.
Resultados del benchmark
- Loro hizo benchmarks de su implementación de Movable Tree con movimientos aleatorios de nodos, cambio a versiones anteriores y rendimiento en condiciones extremas con estructuras de árbol muy profundas
- Los resultados fueron suficientes para soportar colaboración en tiempo real y un checkout fluido de versiones anteriores
- El entorno de prueba fue una CPU M2 Max y el código del benchmark está en tree.rs
| Tarea |
Tiempo |
Configuración |
| 10000 movimientos aleatorios |
28ms |
Primero crear 1000 nodos |
| Cambiar 1000 veces entre versiones distintas |
153ms |
Primero crear 1000 nodos y luego moverlos 1000 veces |
| Cambiar 1000 veces entre versiones distintas en un árbol de profundidad 300 |
701ms |
Cada nuevo nodo es hijo del nodo anterior |
Ejemplos de uso y demo
LoroTree de loro-crdt ofrece creación de nodos, creación con posición especificada, mover, mover a root, mover antes o después de otros nodos, consultar el índice dentro del padre, consultar Fractional Index y acceder al data map del nodo
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;
- Se creó una demo de una app de tareas pendientes que simula la sincronización de datos entre varios peers con Loro
Movable Tree representa las relaciones entre subtareasMap representa varias propiedades de una tareaText representa el título de la tarea- Además de crear, mover, modificar y eliminar, también se implementó el cambio de versiones basado en Loro
- Se puede arrastrar la scrollbar para cambiar entre todas las versiones anteriores registradas
Resumen
- Implementar un CRDT de árbol movible es difícil por la combinación de movimientos concurrentes, eliminación, ciclos, eliminación de ancestros y movimientos de nodos descendientes
- Loro implementa el movimiento dentro de la jerarquía del árbol con el algoritmo de operación move altamente disponible de Kleppmann y otros
- El movimiento y ordenamiento entre nodos hijos se resuelven integrando la implementación de
Fractional Index de drifting-in-space
- Esta combinación puede satisfacer los requisitos de diversos escenarios de aplicaciones colaborativas
1 comentarios
Opiniones de Hacker News
Estamos creando un nuevo editor multijugador [1] para tareas/notas, y admite tanto operaciones de texto como de outliner.
Por fuera se comporta como un documento de texto plano, pero por sus funciones de outliner internamente termina siendo un árbol grande. Para sincronizar cambios usamos un enfoque similar a las operaciones de movimiento de alta disponibilidad. La única operación que modifica el árbol es
insmov, y si el cliente está en línea sincroniza el conjunto de cambios C con el servidor. Si el servidor tiene cambios remotos, devuelve todos los cambios R desde la última sincronización en un orden lineal global; luego se revierten losinsmovde los cambios locales C y se vuelven a aplicar R junto con los nuevos cambios que todavía no se habían sincronizado.No usamos índices fraccionarios; la tupla
insmovincluye no solo el padre P, sino también elguidA del hermano anterior. Como todas las operaciones del árbol finalmente se aplican en el orden lineal global que determina el servidor, el ordenamiento se maneja mediante la propia operacióninsmov. La mayoría de las veces no hace falta revertir nada; solo se necesita reproducir el orden correcto cuando el servidor tiene cambiosinsmovque yo desconozco y, al mismo tiempo, yo envío un nuevoinsmov. Puede pasar al reconectarse al wifi después de un vuelo largo, pero es menos común cuando se está en línea y se reciben pushes en tiempo real por WebSocket; además, no es necesario para operaciones que no soninsmov, como las actualizaciones de texto.[1] https://thymer.com
Por ejemplo, sería una forma de usar el orden del servidor en vez de marcas de tiempo de Lamport.
[1] https://inria.hal.science/inria-00555588/
Busqué Thymer en HN y apareció un Show HN[1] de 2009; parece que Thymer estuvo en beta privada durante los últimos 15 años.
0. https://news.ycombinator.com/item?id=40786425
Definitivamente tengo que leer este artículo. En un trabajo para un cliente freelance publiqué como open source React Table Library [0], y me enfoqué en operaciones de árbol.
Ellos manejan una estructura de árbol de carpetas/archivos de 100.000 nodos, con movimiento y duplicación de carpetas y archivos, carga diferida en el nivel superior y en niveles anidados, todo dentro de la misma estructura de tabla. Al terminar el proyecto entendí por qué Google Drive solo permite visualizar y editar dentro del mismo nivel jerárquico. Implementar esto en una vista anidada con muchos nodos implica demasiadas restricciones a considerar.
[0] https://react-table-library.com/
Quisiera pedir consejo. No es una app multijugador, pero en el frontend tenemos árboles desnormalizados grandes e interconectados que se usan como perfiles de usuario.
Imaginen algo como un layout de mosaicos, donde el usuario agrega/elimina/redimensiona tiles, añade varios componentes a cada slot de tile, y esos componentes también tienen sus propios perfiles. Puede haber varios layouts con distintas disposiciones de tiles, y también está la complejidad de que tiles individuales referencien o compartan otros fragmentos del estado global.
Es difícil actualizar esto de forma segura con REST común. Hay que garantizar que si el mismo usuario abre dos pestañas, actualiza en la pestaña 1 y luego vuelve a actualizar desde la pestaña 2, el perfil completo no termine en un estado inválido. En general, el orden también importa. En el cliente, si el servidor omite una actualización que sí se aplicó correctamente, todo puede romperse.
Como solución muy simple, usamos un enfoque de enviar los datos mínimos necesarios para sobrescribir por completo una parte específica del estado y ponerlos al final de una cola. Normalmente funciona bien, pero a veces es un desperdicio: el cambio real son apenas unos bytes y aun así se envían 50 KB.
No tenemos las razones típicas para necesitar CRDT, pero creo que incluso para un solo usuario podría hacer que la gestión del estado sea mucho más sencilla. Primero, permitiría sincronizar entre pestañas del navegador del usuario y, más importante aún, podría confiar en que si simplemente modifico el estado del frontend, el CRDT se coordinará adecuadamente con el servidor. Ya no tendría que manejarlo yo directamente. Me pregunto si esto tiene sentido, o si en una situación donde no se necesita multijugador ni local-first, el overhead de incorporar algo como Yjs no vale la pena.
Dicho eso, si la edición del perfil es exclusivamente para un solo usuario, introducir CRDT me parece excesivo. A primera vista, el escenario de tener dos pestañas abiertas parece ser la mayor fuente de bugs, así que podrían usar
BroadcastChannelpara notificar eventos de actualización a todas las demás pestañas.Mantener estado compartido mediante llamadas REST que sobrescriben parte del estado del servidor es, en la práctica, frágil, y solo resulta adecuado para sobrescribir campos de registros de datos planos. Además, siempre hay que pensar con cuidado en la coordinación del estado servidor-cliente, y en rutas que no son el flujo normal es fácil que se desincronicen.
Como dices, si creas un CRDT que especifique cómo se combinan las actualizaciones, la carga cognitiva se reducirá mucho.
En contenido de texto con formato, como Google Docs o Zoho Writer, operaciones como mover un elemento de lista hacia abajo o agregar una nueva columna, y las operaciones sobre tablas/listas, son esencialmente operaciones de manipulación de árboles.
Los conflictos simultáneos en estos casos son famosos por ser difíciles de hacer converger sin un manejo especial según el contexto [1]. Me pregunto si esta implementación ofrece una solución generalizada también para esos casos de uso.
Probablemente se podría usar un CRDT de lista o de cadena para los nodos hoja, es decir, los bloques de texto, y combinar este CRDT de árbol para los nodos estructurales, como listas y tablas. Pero entonces habría que agregar una dirección bidimensional
(parent-id, index_offset_into_that_parent)a todas las operaciones.[1] https://github.com/inkandswitch/peritext/issues/27
Un CRDT de texto es, en el fondo, solo un CRDT de lista que contiene datos de caracteres. Por lo tanto, un elemento embebido puede modelarse fácilmente como un elemento especial de tamaño 1 dentro de la cadena, es decir, como un nodo hijo embebido. Con el enfoque correcto, se pueden mezclar distintos CRDT dentro del árbol según haga falta. Por ejemplo, una tabla dentro de texto enriquecido, y una imagen en una de sus celdas.
Tener que agregar un campo
parent-crdt-ida todas las operaciones es una lástima, pero parece difícil de evitar. Por suerte, en la mayoría de los casos de uso reales, es muy probable que las operaciones consecutivas compartan el mismo CRDT padre, así que ese campo de ID debería comprimirse bien con codificación run-length.Sin embargo, como dijo Seph, las operaciones consecutivas bajo el mismo padre pueden comprimirse de forma efectiva, por lo que el overhead amortizado de esos ID de padre normalmente no es grande.
Me pregunto si ha habido CRDT prácticos para aplicaciones con alta densidad de datos, como los píxeles de una imagen o los modelos 3D.
Aunque la representación concreta del documento sea intensiva en datos, la forma de codificar las ediciones y operaciones individuales del usuario aún puede ser pequeña.
Supongamos que estás creando un editor de imágenes como Photoshop: una imagen sin comprimir de 102 megapíxeles con profundidad de color de 16 bits por canal, por ejemplo una foto de una Fujifilm GFX100, ocupa unos 610 MB como TIFF. Si cada píxel se representa como un registro independiente de último escritor gana, el overhead es grande, pero esa representación en realidad no encaja con la preservación de la intención del usuario. Las ediciones que haría el usuario son cosas como “aumentar el contraste de la imagen un 15%” o “pintar la spline [(0,0), (1500, 1500)] con el pincel Q y el color #000”. Si sincronizas cada píxel con timestamps de Lamport, el cambio de contraste del usuario 1 se aplicaría a todos los píxeles excepto a los que pintó el usuario 2, lo que podría hacer que los píxeles repintados se vieran raros.
En cambio, es mejor representar la intención del usuario como una lista de operaciones de edición. Eso es mucho más pequeño que toda la grilla de píxeles de 102 MB. Una estructura de datos CRDT es uno de los posibles mecanismos técnicos para sincronizar esa intención del usuario, pero la estructura debe elegirse según la semántica de la intención del usuario, no según la disposición concreta de los datos de salida.
Aun así, pueden aparecer operaciones de edición que incluyan grandes cantidades de datos, como
"add new layer namedbgbelow layerfgwith pixelsdata:(10mb of pixels)at (1500, 1500)". Pero el overhead de sincronización de un comando de edición así es muy bajo, y su tamaño es O(1), no O(pixels) proporcional a la cantidad de píxeles dentro del comando de edición.Los modelos 3D son otro problema, y no he visto herramientas colaborativas de modelado 3D en el mercado. Tampoco es que haya buscado activamente.
No lo he construido yo mismo y tampoco estoy seguro de que sea realmente práctico. Aun así, al menos podría preservar todo el historial del documento.
Representa los datos con Yjs, pero en lugar de guardar píxeles sin procesar, guarda el historial completo de transformaciones.
https://digest.browsertech.com/archive/browsertech-digest-ho...
Me pregunto si revisaron el texto con GPT. En el primer párrafo se siente muy fuerte el tono de ChatGPT.
This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.