El ciclo: dos movimientos legales, un resultado imposible

Este es uno de los pocos problemas de sistemas distribuidos que se puede enunciar entero en una frase y aun así resiste veinte años de literatura. Dos personas reorganizan la misma jerarquía sin estar conectadas. La primera decide que la carpeta X pertenece dentro de Y. La segunda, con la misma legitimidad y sobre un estado igual de válido, decide que Y pertenece dentro de X. Ninguna de las dos ha hecho nada raro, ninguna ha visto a la otra, ninguna podría haber sabido de la otra, y las dos operaciones son individualmente correctas contra el árbol que cada una tenía delante. Cuando los dispositivos se encuentran, la fusión aplica ambas y el resultado no es un árbol con un problema: es un objeto que no pertenece a la categoría. X cuelga de Y, Y cuelga de X, y ninguno de los dos —ni nada de lo que contenían— alcanza ya la raíz. Esta lección disecciona ese escenario hasta el fondo, porque de entenderlo bien depende que las estrategias de la lección siguiente parezcan razonables en vez de arbitrarias.

El escenario mínimo

Basta con tres nodos y dos operaciones, y conviene apreciar esa economía antes de entrar en detalles. Los contraejemplos mínimos son la herramienta más valiosa que tiene esta disciplina, porque cierran discusiones: mientras el fallo se describe con palabras siempre queda margen para pensar que con un poco más de cuidado se evitaría, y en cuanto cabe en cinco líneas de código deja de haber margen. Este es de los más pequeños que existen para un problema de esta importancia.

Parte de un árbol donde X e Y son hermanos colgando de la raíz, cada uno con contenido dentro. La réplica A decide que el proyecto X es en realidad una parte del proyecto Y y lo mueve dentro. La réplica B, ese mismo día y sin conexión, llega a la conclusión contraria y mueve Y dentro de X. Cada una comprueba su invariante antes de escribir, y cada una la pasa sin objeciones: en el árbol de A, Y no es descendiente de X; en el árbol de B, X no es descendiente de Y.

// El estado de partida, identico en las dos replicas.
const inicial = { X: "raiz", Y: "raiz" };

// A comprueba y escribe. Contra SU estado la comprobacion pasa.
const enA = { ...inicial, X: "Y" }; // valido: Y no desciende de X

// B comprueba y escribe. Contra SU estado la comprobacion tambien pasa.
const enB = { ...inicial, Y: "X" }; // valido: X no desciende de Y

// La fusion clave a clave: ninguna clave esta en disputa.
const fusion = { X: "Y", Y: "X" };
// alcanzaLaRaiz(fusion, "X") -> false
// alcanzaLaRaiz(fusion, "Y") -> false

Antes de mirar la fusión conviene subrayar algo del guion: las dos decisiones son razonables, no caprichosas. Que dos personas discrepen sobre si un proyecto contiene al otro o al revés es una discrepancia de criterio perfectamente ordinaria en cualquier organización, y no señala ningún fallo de comunicación. En un sistema con servidor esa discrepancia se resolvería sola porque la segunda persona vería el resultado de la primera y reaccionaría. Sin conexión no hay tal cosa: las dos ven un árbol donde su decisión tiene todo el sentido del mundo.

Presta atención a la línea que fusiona, porque contiene la parte contraintuitiva del asunto. Aquí no hay conflicto en ninguna clave. La clave X solo la tocó A y la clave Y solo la tocó B. No hace falta desempatar nada, no hay política que aplicar, no hay ganador que elegir. Cualquier algoritmo de fusión concebible produce este mapa, porque cada entrada tiene un único candidato. El estado inválido no es el resultado de haber elegido mal: es el resultado de no haber tenido que elegir.

sequenceDiagram
participant A as Replica A
participant B as Replica B
Note over A: comprueba y mueve X dentro de Y
Note over B: comprueba y mueve Y dentro de X
A->>B: operacion mover X con padre Y
B->>A: operacion mover Y con padre X
Note over A,B: padre de X es Y y padre de Y es X
Note over A,B: la cadena de padres ya no llega a la raiz

Conviene ver el desastre con números, porque la aritmética del árbol lo hace muy visible. Un árbol con n nodos tiene exactamente n menos uno aristas y una única componente conexa que cuelga de la raíz. El mapa fusionado sigue teniendo el mismo número de aristas —no se ha creado ni destruido ninguna— y sin embargo ahora tiene dos componentes: la que cuelga de la raíz y el lazo formado por X e Y con todos sus descendientes. Nada se ha perdido en el sentido contable del término. Lo que se ha perdido es la conexión, y con ella todo lo que dependía de poder llegar.

// El mismo estado, dos preguntas distintas, dos respuestas contradictorias.
const nodos = ["X", "Y", "informe.pdf", "logo.svg"];
const fusion = { X: "Y", Y: "X", "informe.pdf": "X", "logo.svg": "Y" };

nodos.every((n) => fusion[n] !== undefined); // true: todos tienen padre
nodos.every((n) => alcanzaLaRaiz(fusion, n)); // false: ninguno llega a la raiz

Ese par de líneas es la firma del fallo y conviene tenerla presente porque explica su longevidad en producción. La primera comprobación es la que casi todo el mundo escribe, porque es local, barata y suena a integridad referencial. La segunda es la única que detecta el problema, y no la escribe nadie salvo que sepa exactamente qué está buscando.

Este es también el motivo por el que la granularidad, que en otros niveles fue una palanca útil, aquí no ofrece nada. Ya estás en la unidad más fina posible: una clave por arista. No hay forma de trocear más el estado, porque la arista es atómica. El problema no está dentro de ninguna unidad, está entre unidades, y esa región del espacio de diseño no la cubre ninguna técnica de las que has visto.

Nadie tiene la culpa

Merece la pena insistir en la ausencia de culpable porque casi todas las respuestas malas a este problema nacen de suponer que existe uno. La tentación habitual es decidir que la operación equivocada es la segunda que llega, o la que tiene la marca de tiempo mayor, o la del dispositivo menos fiable. Ninguna de esas etiquetas se sostiene: las dos operaciones fueron emitidas contra estados válidos, comprobadas contra esos estados y aceptadas legítimamente en local. La que llega segunda solo llegó segunda desde el punto de vista de un observador concreto; desde el otro extremo del enlace, la que llegó segunda fue la otra.

Hay además un argumento más fuerte contra la idea de culpa, y es que ninguna de las dos réplicas podía haber hecho nada distinto. Para que A supiera que su movimiento iba a chocar tendría que conocer una operación que en ese instante no existía en ningún sitio al que A tuviera acceso, y exigirle eso equivale a exigirle que consulte antes de escribir, que es precisamente la coordinación que el trabajo sin conexión descarta por definición. No estamos ante una comprobación que se olvidó implementar: estamos ante una comprobación que no se puede implementar sin renunciar a la premisa del track.

Conviene también resistir una tentación intermedia que parece razonable y no lo es: hacer la comprobación al recibir, y descartar la operación remota que resultaría insegura contra el estado local. Eso convierte el problema en algo peor, porque cada réplica descarta una operación distinta —cada una descarta la del otro— y acabas con dos árboles válidos y diferentes, es decir, con una divergencia permanente disfrazada de corrección. Volveremos sobre este falso remedio en la lección siguiente, porque es el error de diseño más habitual de toda la materia.

Lo que sí se puede decir es algo más incómodo. El estado inválido no lo escribió nadie. No existe ninguna réplica que en ningún momento haya tenido delante un árbol con un ciclo y haya decidido que estaba bien. El ciclo lo fabricó el algoritmo de fusión al combinar dos decisiones que nunca se destinaron a coexistir. Esa frase merece leerse dos veces porque invierte la intuición habitual sobre los fallos de software. Normalmente un estado inválido aparece porque alguien escribió algo que no debía, y el arreglo consiste en impedir esa escritura. Aquí no hay ninguna escritura que impedir: todas fueron correctas y todas se aceptaron correctamente. El defecto está en la combinación, que es una operación que ningún autor ejecutó y que sin embargo el sistema realiza en su nombre cada vez que dos dispositivos se encuentran.

Es la misma firma del conflicto semántico del nivel 23, con un agravante: allí el estado inventado era indeseable pero representable —un intervalo con el fin antes del inicio se puede almacenar y mostrar—, mientras que aquí es directamente inexpresable en el modelo, y ninguna vista de árbol sabe pintarlo.

La variante que produce duplicados

Hay una versión de este problema que aparece antes en la vida de casi todos los productos, porque nace de la decisión más natural del mundo: no tener operación de movimiento y expresar el movimiento como un borrado seguido de una inserción. Es lo que hace cualquier API que solo ofrece insertar y eliminar, y es lo que hizo Dropbox en su día, con el detalle poco tranquilizador de que un corte de corriente entre los dos pasos podía dejar el archivo en ninguna parte.

Vale la pena entender por qué esa descomposición es tan atractiva, porque no se elige por ignorancia. Es la única forma de expresar un movimiento cuando la librería que usas no tiene otra cosa, y la mayoría no la tiene. Es además lo que hacen casi todas las interfaces de programación de colecciones que has usado en tu vida, donde reordenar un array es exactamente eliminar en una posición e insertar en otra. La descomposición no es un atajo perezoso: es el camino por defecto que el ecosistema te ofrece, y hace falta saber lo que se está buscando para no tomarlo.

Cuando el movimiento se descompone así, el escenario concurrente ya no produce un ciclo. Produce copias. Si dos réplicas mueven el mismo nodo a padres distintos, cada una borra el original y crea uno nuevo bajo su destino; la fusión aplica los dos borrados y las dos creaciones, y el usuario acaba con dos nodos de contenido idéntico colgando de sitios distintos. El artículo de referencia sobre movimiento en CRDT de JSON menciona precisamente ese par de patologías —duplicados y ciclos— como los resultados inesperados que un algoritmo ingenuo de fusión introduce.

Merece la pena señalar por qué el duplicado se percibe como un fallo menos grave que el ciclo y por qué esa percepción es engañosa. El duplicado es visible: el usuario ve dos carpetas iguales, entiende lo que ha pasado y borra una. El ciclo es invisible: el usuario ve que le falta media jerarquía y no tiene ninguna hipótesis. Pero el duplicado destruye información que el ciclo conserva —al borrar una copia se pierde la mitad de la historia que estaba en ella— mientras que el ciclo es completamente reversible en cuanto alguien mueve uno de los dos nodos a la raíz. El fallo que se ve peor es el más recuperable de los dos.

La conclusión de este cuadro es que el ciclo no es el precio de haber elegido la representación con puntero al padre. Es el precio de querer un árbol. Las representaciones alternativas no eliminan la dificultad, la cambian de forma: por duplicados, por desapariciones o por la renuncia a que la estructura sea un árbol. De las cuatro, el ciclo es la que menos daño hace, porque al menos conserva la identidad de cada nodo y todo su contenido, que es justo lo que las otras pierden.

Lo que ve el usuario

El daño de este fallo tiene una característica que lo hace especialmente caro de diagnosticar: es indistinguible de una pérdida de datos aunque no se haya perdido absolutamente nada. Los nodos siguen ahí, con su contenido intacto y sus identificadores válidos, y todas las consultas por identificador los devuelven. Lo único que ocurre es que ninguna ruta desde la raíz llega hasta ellos, y como la interfaz dibuja el árbol recorriendo desde la raíz, para el usuario han desaparecido. Ha desaparecido X, ha desaparecido Y y ha desaparecido todo lo que colgaba de los dos, que en un sistema de archivos pueden ser miles de documentos.

Ese detalle es el que convierte el incidente en algo caro de atender. Cuando un usuario informa de una pérdida de datos, lo primero que hace cualquier equipo es comprobar si los datos están, y aquí están: íntegros, con su contenido, con sus fechas, con sus permisos. La conclusión natural del soporte es que el usuario se confunde, y la conclusión natural del usuario es que el producto le ha borrado el trabajo. Las dos partes tienen razón desde su punto de vista y ninguna de las dos dispone de la pregunta que resolvería la discusión, que es si esos nodos alcanzan la raíz.

Ese es también el motivo por el que el fallo se detecta tarde. Una copia de seguridad que exporte el estado por identificador lo exporta completo. Una comprobación de integridad referencial pasa sin quejas, porque todos los punteros apuntan a nodos existentes. Los tamaños cuadran, los contadores cuadran y el usuario está seguro de que le falta media unidad de disco. Solo una verificación explícita de alcanzabilidad desde la raíz encuentra el problema, y esa verificación no está en ningún sitio salvo que alguien la haya escrito a propósito.

Hay un agravante final que conviene anticipar porque decide cuánta urgencia le pones al asunto. El estado con ciclo no es estable: es fértil. Una vez que existe, las operaciones siguientes se emiten contra él. Alguien mueve otra carpeta dentro de X sin saber que X está desconectada y esa carpeta también desaparece. Un proceso de limpieza que borre lo inalcanzable —y hay muchos sistemas que tienen uno— convierte el fallo recuperable en pérdida definitiva. Y una sincronización con un dispositivo nuevo propaga el estado roto a un sitio más. El tiempo que el ciclo pasa sin detectarse no es tiempo neutro, es tiempo durante el cual el daño crece.

Los productos con árbol replicado que hoy funcionan en producción se enfrentaron a esto de forma explícita, y sus respuestas son un mapa razonable de lo que hay disponible. Dropbox detecta el conflicto y guarda una versión con nombre de copia en conflicto, dejando la decisión a la persona. Figma coloca un servidor central en el camino de las operaciones de movimiento: si una crearía un ciclo en el estado del servidor, el servidor la rechaza, y como los clientes aplican de forma optimista mientras tanto, puede haber ciclos temporales que Figma resuelve ocultando los elementos implicados hasta que la respuesta llega. Ambas soluciones son buenas y ambas se apoyan en algo que este track lleva veinte niveles retirando: un punto único que arbitra.

Esa observación fija el listón de lo que viene. No se trata de encontrar una respuesta cualquiera al ciclo, porque respuestas hay varias y llevan años en producción. Se trata de encontrar una que no necesite un árbitro, porque un árbol que solo se puede reorganizar con el servidor delante deja de ser una estructura local-first en el momento en que el usuario se queda sin cobertura, que es justo el momento para el que se construyó todo lo demás. Ese es el problema concreto que la siguiente lección aborda enumerando lo que hay, y que la cuarta desarrolla eligiendo una respuesta y pagándola.