CRDT de árboles movibles y la implementación de Loro

• Movable tree CRDTs and Loro's implementation

• Contexto

  • En sistemas distribuidos y software colaborativo, gestionar relaciones jerárquicas es complejo
  • Al modelar movimientos combinando eliminación e inserción en una estructura de datos, es difícil resolver conflictos y cumplir con las expectativas del usuario
  • Por ejemplo, si el mismo nodo se mueve simultáneamente a distintos padres, pueden generarse nodos duplicados con el mismo contenido

• Conflictos en árboles movibles

  • Operaciones principales de un árbol movible: crear, eliminar, mover
  • Conflictos que pueden surgir al sincronizar operaciones concurrentes:
    • El mismo nodo se elimina y se mueve
    • El mismo nodo se mueve debajo de otro nodo distinto
    • Se mueven otros nodos y se produce un ciclo
    • Un nodo descendiente se mueve mientras se elimina un nodo ancestro

• Eliminación y movimiento del mismo nodo

  • Relativamente fácil de resolver
  • Según los timestamps del sistema distribuido o los requisitos específicos de la aplicación, se aplica una operación y se ignora la otra

• Mover el mismo nodo debajo de padres distintos

  • Fusionar operaciones de movimiento concurrentes es más complejo
  • Dependiendo de la aplicación, pueden adoptarse varios enfoques:
    • Eliminar el nodo y crear una copia debajo de otro nodo padre
    • Permitir que el nodo quede conectado a dos padres (por lo general no se permite)
    • Ordenar todas las operaciones y aplicarlas secuencialmente

• Generación de ciclos por el movimiento de distintos nodos

  • Resolver ciclos causados por operaciones de movimiento concurrentes es complicado
  • Hay varias soluciones:
    • Generar un error
    • Renderizar los nodos cíclicos en un área especial de "timeout"
    • Procesar las operaciones de movimiento en el servidor
    • Usar ordenamiento topológico
    • Ocultar la arista que provoca el ciclo

• Eliminación de un nodo ancestro y movimiento de un nodo descendiente

  • El movimiento de un nodo descendiente durante la eliminación de un ancestro puede pasarse por alto fácilmente
  • Si se eliminan directamente todos los nodos descendientes, puede interpretarse como pérdida de datos

• Cómo manejan los conflictos las aplicaciones populares

  • Dropbox: trataba el movimiento de archivos como eliminación seguida de creación, pero había riesgo de pérdida de datos
  • Figma: un servidor central detecta ciclos y rechaza operaciones para mantener la consistencia

• CRDT de árboles movibles

  • Se usan CRDT en lugar de soluciones centralizadas
  • Los algoritmos iniciales basados en CRDT eran difíciles de implementar y tenían alto overhead de almacenamiento
  • Gracias a optimizaciones continuas, algunos algoritmos de sincronización de árboles basados en CRDT se volvieron aptos para entornos de producción

• Operaciones de movimiento de alta disponibilidad para árboles replicados

  • Las tres operaciones del árbol (crear, eliminar, mover) se integran en una sola operación de movimiento
  • La operación de movimiento se define como Move t p m c
  • La eliminación de nodos se maneja moviéndolos al nodo TRASH

• Timestamps lógicos ordenados globalmente

  • Se usan timestamps de Lamport para determinar el orden causal de eventos en sistemas distribuidos
  • Los números más pequeños indican eventos más tempranos

• Aplicación de operaciones remotas

  • La seguridad de una operación depende del estado del árbol al momento de aplicarla
  • Al procesar actualizaciones remotas, se revierten las operaciones más recientes, se inserta la nueva operación y luego se reaplican las operaciones revertidas

• CRDT: jerarquía de árbol mutable

  • Cada nodo rastrea todos sus padres históricos y les asigna contadores
  • Si aparece un ciclo durante la sincronización, se vuelve a conectar al nodo padre histórico más cercano

• Implementación de CRDT de árboles movibles en Loro

  • Implementa el algoritmo de Martin Kleppmann para ofrecer alto rendimiento
  • Integra el algoritmo Fractional Index para permitir el ordenamiento de nodos hijos

• Conflictos potenciales al ordenar nodos hijos

  • Al insertar varios nodos en la misma posición, puede asignarse el mismo Fractional Index
  • Se usa PeerID para determinar el orden relativo entre Fractional Index idénticos

• Implementación y tamaño de codificación

  • Fractional Index proporciona el orden de los nodos
  • En el peor caso, el tamaño de codificación requiere bytes adicionales, pero es una situación poco común

• Trabajo relacionado

  • Además de Fractional Index, existen CRDT de listas movibles
  • Fractional Index es simple de implementar y útil cuando solo se necesita orden relativo

• Benchmarks

  • Se realizaron benchmarks del rendimiento de la implementación de árboles movibles de Loro
  • Puede soportar colaboración en tiempo real y checkout fluido de versiones históricas

• Resumen

  • Se presentan las dificultades de implementar CRDT de árboles movibles y dos algoritmos innovadores
  • Loro integra el algoritmo de Martin Kleppmann y Fractional Index para cubrir diversos escenarios de aplicación

• Resumen de GN⁺

  • Los CRDT de árboles movibles cumplen un papel importante en la gestión de estructuras de datos jerárquicas en sistemas distribuidos
  • Loro ofrece alto rendimiento y resolución eficiente de conflictos, por lo que es adecuado para aplicaciones de colaboración en tiempo real
  • Usa Fractional Index para resolver el problema de ordenamiento de nodos hijos
  • Otros proyectos con funciones similares incluyen Figma y Dropbox

[GN⁺]

Comentarios de Hacker News

• Estoy desarrollando un nuevo editor multijugador

  • Soporta edición de texto y trabajo con esquemas
  • Los documentos se transforman en una gran estructura de árbol
  • Se sincroniza usando operaciones insmov (mover o insertar)
  • Cuando el servidor envía cambios, el cliente los vuelve a aplicar
  • En la mayoría de los casos no es necesario deshacer operaciones
  • Casi no surgen problemas durante las actualizaciones en tiempo real

• Ofrezco React Table Library como código abierto

  • Maneja estructuras de árbol de carpetas/archivos
  • Soporta mover y duplicar carpetas/archivos, carga diferida y más
  • Me hizo entender por qué Google Drive solo muestra y permite editar dentro del mismo nivel jerárquico

• Pido consejo

  • Estoy usando un gran árbol desnormalizado en el frontend
  • Administro perfiles de usuario con un diseño de mosaicos
  • Envío la mínima cantidad de datos para actualizaciones seguras
  • Parece que usar CRDT haría que la gestión del estado fuera mucho más sencilla
  • Permitirá sincronización entre pestañas del navegador

• Al trabajar con contenido de texto con formato como Google Docs/Zoho Writer, se necesita manipulación de árboles

  • Es difícil resolver problemas de conflictos simultáneos
  • Parece que se podrían combinar CRDT de listas y CRDT de árboles
  • Habría que añadir direcciones bidimensionales a todas las operaciones

• Me pregunto si existen CRDT prácticos para aplicaciones con datos densos, como imágenes (píxeles) y modelos 3D

• Creo que el primer párrafo suena a la voz de ChatGPT