Mover como operación de primera clase

Queda la pregunta que un ingeniero pragmático lleva cuatro lecciones aguantando: si mover es tan caro, ¿por qué no expresarlo con las operaciones que ya tengo? Borrar el nodo de donde estaba, insertarlo donde debe ir, y a otra cosa. La respuesta es que esa descomposición no es una implementación del movimiento sino una operación distinta que casualmente produce el mismo resultado cuando no hay concurrencia, y que produce resultados muy diferentes en cuanto la hay. Lo que se pierde por el camino no es rendimiento: es la identidad del nodo, las ediciones que otras personas le hicieron mientras se movía y la propia intención de quien lo movió, que era conservar la cosa y cambiarle el sitio, no destruirla y fabricar otra parecida. Esta lección explica con precisión qué se rompe, por qué ninguna capa superior puede reconstruirlo después y qué librerías ofrecen hoy el movimiento como primitiva real, con nombres, algoritmos y limitaciones concretas.

Lo que la descomposición destruye

Empieza por el caso sin concurrencia, donde todo parece funcionar. Una persona arrastra un nodo de un padre a otro, el código emite un borrado y una inserción, y el resultado en pantalla es indistinguible del que daría un movimiento nativo. Esa indistinguibilidad es la trampa: garantiza que el error pasará todas las pruebas escritas por un desarrollador trabajando solo.

Conviene además reconocer la fuerza del argumento contrario, porque tiene una parte razonable. En un sistema con un único escritor, borrar más insertar es una implementación correcta del movimiento, y millones de líneas de código en producción lo demuestran cada día. El error no consiste en creer que funciona, porque funciona; consiste en trasladar esa creencia a un contexto donde la premisa que la sostenía —que nadie más toca el dato entre las dos operaciones— ha dejado de ser cierta sin que nadie lo anunciara.

Vale la pena nombrar ese fenómeno porque se repite en todo el diseño de sistemas replicados: dos codificaciones distintas de la misma intención coinciden en el caso secuencial y divergen bajo concurrencia. El caso secuencial es el que se prueba, el que se demuestra en la reunión de producto y el que el desarrollador experimenta a diario, así que el error tiene todas las condiciones para instalarse y ninguna para salir a la luz hasta que hay usuarios de verdad trabajando a la vez.

Ahora añade una segunda réplica y mira las tres cosas que se rompen. La primera es la identidad. El nodo insertado es un nodo nuevo, con un identificador nuevo, y todo lo que apuntaba al viejo apunta ahora a algo borrado: los comentarios asociados, los permisos, los enlaces desde otros documentos, el historial, las suscripciones, el marcador que alguien había guardado. Nada de eso es recuperable, porque desde el punto de vista de la capa de fusión el nodo original dejó de existir.

La magnitud de esa primera pérdida depende de cuánto haya construido tu producto sobre el identificador, y suele ser mucho más de lo que el equipo recuerda. Basta con enumerar: las menciones desde otros documentos, las notificaciones pendientes, los permisos concedidos por nodo, las suscripciones a cambios, las entradas del historial, las referencias guardadas por el propio usuario en marcadores o en enlaces que ha compartido con otras personas. Ninguna de esas cosas está en el árbol y todas apuntan a él, así que todas se rompen a la vez y en sitios distintos del código.

La segunda es la edición concurrente. Mientras la primera persona movía el nodo, la segunda estaba escribiendo dentro de él. Esas escrituras se aplicaron sobre el nodo original, que ahora está borrado, y la fusión decide con toda coherencia que las escrituras a un nodo borrado no van a ninguna parte. La copia insertada lleva el contenido que tenía en el instante en que se copió, y el trabajo de la otra persona se evapora sin ninguna señal, que es la peor forma en la que puede evaporarse.

// Dos codificaciones del mismo gesto. Sin concurrencia dan lo mismo.
function moverDescompuesto(doc, nodo, nuevoPadre) {
  const copia = structuredClone(doc.nodos[nodo]); // instantanea, ya obsoleta
  delete doc.nodos[nodo];                          // el original deja de existir
  const nuevoId = crypto.randomUUID();             // identidad distinta
  doc.nodos[nuevoId] = { ...copia, padre: nuevoPadre };
  return nuevoId;
}

function moverNativo(doc, nodo, nuevoPadre) {
  doc.padre[nodo] = nuevoPadre; // una escritura, misma identidad, mismo contenido vivo
  return nodo;
}

La línea que más daño hace es la primera del bloque descompuesto. Ese clon congela el contenido en el instante del arrastre, y a partir de ahí cualquier escritura que llegue dirigida al nodo original se aplica sobre algo que ya no está en el documento. El movimiento nativo no clona nada porque no lo necesita: el nodo sigue siendo el mismo objeto y las escrituras concurrentes lo alcanzan igual que antes, con independencia de dónde haya acabado colgado.

La tercera es la que ya viste en la segunda lección: el duplicado. Si dos réplicas mueven el mismo nodo a padres distintos, cada una borra el original y crea el suyo, la fusión aplica los dos borrados y las dos creaciones, y el usuario acaba con dos copias del mismo contenido colgando de sitios distintos. Ninguna de las dos es la original, ninguna tiene la historia completa y no hay forma automática de decidir cuál conservar.

Nótese que este tercer fallo no requiere que los dos destinos sean incompatibles ni que haya nada parecido a un ciclo. Dos personas que muevan la misma carpeta a dos sitios perfectamente razonables y sin ninguna relación entre sí producen el duplicado igual, porque el problema no está en los destinos sino en que el borrado se aplica dos veces sobre un nodo que solo existía una. Es, en ese sentido, un fallo más fácil de provocar que el ciclo.

flowchart LR
A[borrar mas insertar] --> A1[identidad nueva: se rompen enlaces y permisos]
A --> A2[ediciones concurrentes aplicadas a un nodo borrado]
A --> A3[dos copias si dos personas mueven a la vez]
M[mover de primera clase] --> M1[identidad estable]
M --> M2[ediciones concurrentes conservadas]
M --> M3[un solo nodo con un padre decidido]
style A fill:#f38ba8,color:#11111b
style M fill:#a6e3a1,color:#11111b

Hay una cuarta pérdida, menos evidente y bastante cara, que solo se nota cuando alguien pide el historial. Un nodo que se mueve mediante borrado e inserción rompe su propia línea temporal en dos: la historia anterior pertenece a un identificador que ya no existe y la posterior empieza de cero en uno nuevo. Preguntas perfectamente razonables —quién movió esto, dónde estaba antes, cómo era hace un mes— dejan de tener respuesta calculable, no porque falten los datos sino porque falta el hilo que los une. En un sistema donde toda la propuesta de valor es que el usuario posee su historia, romper esa continuidad es más grave de lo que parece.

Hay además una versión no distribuida del mismo problema que conviene mencionar porque es históricamente anterior y todavía muerde. Si el borrado y la inserción son dos escrituras separadas, un fallo entre ambas deja el nodo en ninguna parte. Dropbox trató durante un tiempo el movimiento de archivos como esa secuencia de dos pasos y el riesgo era exactamente ese: un corte de corriente o una caída del sistema entre el borrado y la creación se llevaba el archivo por delante.

Por qué no se arregla desde arriba

La reacción natural es intentar recomponer lo perdido en una capa superior: guardar un identificador estable en los datos del nodo, mantener una tabla que relacione el identificador viejo con el nuevo, o detectar por contenido que la inserción y el borrado son en realidad el mismo nodo. Ninguna de las tres funciona, y entender por qué cierra el asunto.

El identificador estable en los datos no ayuda porque el problema no es cómo llamas al nodo sino qué hace la función de fusión con él. La fusión no lee tus datos de aplicación: ve un borrado y una inserción, y hace lo que corresponde a un borrado y una inserción. Dos réplicas que inserten nodos distintos con el mismo identificador de aplicación producen dos nodos, y ahora además con la identidad duplicada.

La tabla de correspondencias tampoco, porque tendría que ser ella misma un dato replicado y sujeto a los mismos conflictos, con el agravante de que su corrección depende de un emparejamiento que solo existió en la cabeza del código que emitió las dos operaciones. Y la detección por contenido es peor todavía: cuando dos nodos tienen el mismo contenido no puedes saber si es un movimiento o una copia legítima, que es una distinción que el usuario sí tiene clara y el heurístico nunca.

Hay un intento más sofisticado que también conviene descartar, porque a mucha gente se le ocurre y consume semanas: emitir el borrado y la inserción dentro de una transacción atómica, de modo que la fusión no pueda aceptar una mitad sin la otra. La atomicidad resuelve el problema del corte de corriente, que es real, y no resuelve absolutamente nada de lo demás. Dos réplicas pueden ejecutar sus dos transacciones enteras sin verse, y entonces tienes dos borrados atómicos y dos inserciones atómicas, con el mismo duplicado que antes. La atomicidad ordena lo que pasa dentro de una réplica; el problema está entre réplicas, y ahí no llega.

El patrón que subyace a los cuatro intentos fallidos es el mismo y es útil reconocerlo: todos tratan de recuperar información después del punto en el que se descartó. La traducción del gesto a operaciones es un embudo, y lo que no pasa por él no está en ninguna parte del sistema, ni en los datos, ni en los metadatos, ni en el registro. Es exactamente la misma razón por la que un texto plano no permite reconstruir el formato que tenía el documento del que salió, y por la que ningún esfuerzo posterior lo consigue.

Quién lo implementa de verdad

El panorama actual es más estrecho de lo que la abundancia de librerías sugiere, y conviene conocerlo con nombres concretos.

Antes del detalle conviene leer bien ese cuadro, porque su distribución no es casual. El movimiento nativo aparece en las librerías que se propusieron el árbol como objetivo explícito y falta en las que crecieron desde el texto colaborativo hacia arriba, que son la mayoría y también las más maduras. No es un descuido de sus autores: es que añadir movimiento a una librería consolidada obliga a tocar el formato de operaciones, la lógica de fusión y el formato de almacenamiento a la vez, y eso es una migración, no una función nueva. Por eso el estado del arte avanza aquí más despacio de lo que la calidad general del ecosistema sugeriría.

Loro merece el detalle porque es hoy la implementación más completa y sus decisiones de diseño son instructivas. Sobre el algoritmo de movimiento de árbol añade un segundo mecanismo para un problema que el árbol puro no resuelve: el orden entre hermanos. Un esquema de notas o un panel de capas necesitan que los hijos de un nodo tengan una secuencia, y la relación de padre no dice nada sobre eso. Loro lo cubre con índices fraccionarios, tomados de la implementación de Drifting in Space y extendidos, de modo que cada nodo recibe un valor ordenable y una inserción entre dos vecinos obtiene un valor intermedio.

Que el orden entre hermanos haga falta un mecanismo aparte no es un capricho de implementación, y conviene entender por qué. La relación de padre es una función: cada nodo tiene uno y con eso queda dicho todo lo que el árbol afirma. El orden entre hermanos es información adicional que el árbol no contiene y que hay que añadir por fuera, y como es una secuencia, arrastra consigo todos los problemas del nivel anterior: identificadores de posición, densidad, entrelazado. Un árbol ordenado es en realidad dos estructuras convergentes superpuestas, y sus costes se suman.

Ese añadido trae sus propios conflictos y su tratamiento es un buen ejemplo de honestidad de diseño. Dos réplicas que inserten en la misma posición generan el mismo índice fraccionario, y Loro conserva ambos y desempata con el identificador de réplica. Como después no se puede generar un valor intermedio entre dos iguales, se recurre a dos remedios: añadir una perturbación aleatoria a cada valor generado, cuyo tamaño se configura y cuesta bytes, y reasignar valores cuando la colisión ya se ha producido. La documentación publica incluso la relación entre el tamaño de la perturbación y el número de ediciones concurrentes que soporta con un noventa y nueve por ciento de probabilidad de no colisionar, y reconoce que los índices fraccionarios sufren entrelazado, algo que consideran aceptable para árboles aunque no lo sería para texto.

En Loro, además, cada nodo del árbol lleva asociado un mapa como contenedor de datos, accesible desde el propio nodo, dentro del cual se pueden anidar los demás tipos de la librería. Ese detalle de diseño es el que hace que el árbol sea utilizable para algo más que dibujar carpetas: el nodo no es una etiqueta con un padre, es un contenedor con contenido convergente propio, y por tanto mover el nodo y editar su contenido son operaciones sobre planos distintos que no se estorban. La interfaz completa incluye también consultar el índice del nodo entre sus hermanos y su valor fraccionario, que es lo que permite reconstruir una vista ordenada sin recorrer nada.

El artículo de 2023 de Liangrun Da y Martin Kleppmann, presentado en el taller sobre principios y práctica de la consistencia para datos distribuidos de 2024, aborda una pieza que el algoritmo del árbol no cubría: la interacción entre las operaciones de movimiento y las operaciones que no son de movimiento dentro de un documento JSON, además de optimizaciones de rendimiento. Ese matiz importa para tu diseño porque un árbol en la vida real nunca es solo un árbol: sus nodos llevan texto, mapas y listas, y mover un subárbol mientras alguien edita el texto de dentro es el caso corriente, no el raro.

El mismo artículo señala, en la descripción de su propio problema, las dos patologías que un algoritmo de fusión ingenuo produce al mover subárboles o reordenar elementos dentro de un documento JSON: duplicados y ciclos. Es la confirmación, desde la literatura y no desde la anécdota, de que las dos formas de fallo que este nivel ha ido desmenuzando son las dos caras de la misma carencia, y que la carencia es la ausencia de una operación de movimiento con estatuto propio.

Qué preguntar antes de elegir

Conviene recordar, antes del cuestionario, por qué esta evaluación no se puede delegar en la reputación del proyecto. Las librerías que has visto son todas excelentes y están todas bien construidas; la diferencia entre ellas no es de calidad sino de alcance declarado, y una librería que no promete árboles movibles no está incumpliendo nada al no tenerlos. El error no está en elegir la que no lo ofrece, está en elegirla creyendo que sí, y eso solo se evita preguntando de forma explícita.

Con todo lo anterior en la mano, la evaluación de una librería para una jerarquía editable se reduce a media docena de preguntas concretas, y ninguna se contesta leyendo la portada del repositorio. ¿Existe una operación de movimiento en la interfaz pública, o se espera que la compongas? ¿Qué hace exactamente ante dos movimientos concurrentes que cerrarían un ciclo: rechaza, reordena o rescata? ¿Sobreviven las ediciones concurrentes al contenido del nodo movido? ¿Hay orden entre hermanos y con qué mecanismo? ¿Qué se guarda para poder deshacer y se puede podar? Y la más reveladora de todas: ¿está documentado el comportamiento ante el ciclo, o hay que descubrirlo escribiendo la prueba?

Y hay una respuesta que conviene aceptar sin dramatismo cuando toque: para una parte de los productos, la conclusión correcta es que la jerarquía no necesita ser editable. Si el usuario nunca reorganiza, o si reorganiza tan poco que un bloqueo momentáneo resulta aceptable, puedes evitar todo este nivel eligiendo no ofrecer el movimiento como operación sincronizada. Es una decisión legítima y bastante más barata que cualquiera de las tres estrategias, siempre que se tome a conciencia y no por descuido. Lo que no es legítimo es ofrecer el gesto de arrastrar y soltar sin haber contestado a ninguna de las preguntas anteriores.

Esa última pregunta funciona como filtro porque el comportamiento ante el ciclo es la parte del contrato que más cuesta implementar y la primera que se omite en la documentación de quien no lo ha resuelto. Un proyecto que explica su respuesta al ciclo, con nombre de algoritmo y limitaciones reconocidas, te está diciendo que ha llegado hasta el fondo del problema. Uno que solo enseña la llamada de mover en el ejemplo de inicio rápido te está diciendo lo contrario, aunque no fuera su intención.