Las estrategias: rechazar, reordenar o rescatar

La lección anterior terminó con un resultado negativo: las dos operaciones que forman el ciclo son imágenes especulares la una de la otra, así que ninguna regla que las mire por separado puede preferir una. Romper esa simetría exige información que no está en las operaciones, y eso deja exactamente tres sitios de donde sacarla. Puedes negarte a aplicar la que cerraría el ciclo, y entonces la información que importas es cuál llegó cuando según algún criterio impuesto desde fuera. Puedes imponer un orden total sobre todas las operaciones y reconstruir el estado según ese orden, deshaciendo lo que haga falta, y entonces la información que importas es un orden global que ninguna réplica podía conocer al emitir. O puedes aceptar las dos y reubicar el nodo que sobra en un lugar visible, y entonces la información que importas es la de un humano que decidirá después. Esta lección recorre las tres familias, muestra sus variantes conocidas y hace explícito el precio de cada una, porque ninguna es gratis y elegir bien consiste en saber qué estás dispuesto a perder.

La comprobación que las tres comparten

Conviene empezar señalando lo que las tres familias tienen en común, porque es más de lo que sus nombres sugieren. Las tres detectan el ciclo con el mismo predicado y las tres actúan después de saber que existe. Ninguna lo previene, y no por falta de ingenio: prevenirlo exigiría que la réplica emisora supiera lo que la otra iba a hacer, que es información que no existe en el momento de emitir. Toda esta lección trata, por tanto, de reacciones, y elegir entre ellas es elegir qué clase de daño prefieres.

Antes de las estrategias hace falta el predicado, porque las tres lo usan. Un movimiento de c bajo p es inseguro exactamente cuando p es descendiente de c en el estado actual, incluido el caso degenerado de que p sea el propio c. La razón es directa: mover un nodo dentro de su propio subárbol convierte la cadena de padres de esa región en un lazo cerrado que ya no sale hacia la raíz.

// Es p descendiente de c, o el propio c. Si lo es, mover c bajo p cierra un ciclo.
function esDescendiente(padre, p, c) {
  let actual = p;
  const vistos = new Set();
  while (actual !== undefined) {
    if (actual === c) return true;
    if (vistos.has(actual)) return true; // el estado ya venia roto
    vistos.add(actual);
    actual = padre.get(actual);
  }
  return false;
}

const esSeguro = (padre, c, p) => !esDescendiente(padre, p, c);

Dos observaciones sobre esta función, ambas con consecuencias. La primera es su coste: recorre hacia arriba hasta la raíz, de modo que cuesta proporcional a la profundidad del árbol, no a su tamaño. En jerarquías reales la profundidad rara vez pasa de unas decenas, y por eso el guardián de invariante resulta viable en la práctica pese a ser una comprobación global.

La segunda es más sutil y determina el diseño de todo lo que sigue: la respuesta depende del estado en el que se evalúe. La misma operación es segura contra un estado e insegura contra otro. Y como el estado depende de qué operaciones se hayan aplicado antes, la seguridad de una operación no es una propiedad de la operación: es una propiedad del par formado por la operación y el punto de la historia donde se la evalúa. Nada de lo que sigue tiene sentido sin haber aceptado ese hecho.

Conviene además fijarse en el caso degenerado que la función cubre sin decirlo: mover un nodo bajo sí mismo. Parece un absurdo que ninguna interfaz permitiría, y sin embargo aparece en cuanto hay concurrencia, porque el destino que el usuario eligió puede haberse convertido en descendiente del nodo movido antes de que la operación llegue a otra réplica. El ciclo de longitud uno y el de longitud cinco son el mismo fenómeno y merecen el mismo tratamiento, así que no hace falta un caso especial para el primero.

La otra cara de esa observación es que el árbol tiene que estar sano cuando se hace la comprobación. Si el estado sobre el que evalúas ya contiene un ciclo, el recorrido hacia arriba no termina nunca, y por eso la implementación de arriba lleva un conjunto de nodos vistos que la protege de un bucle infinito. En un sistema bien construido esa guarda no debería dispararse jamás, lo cual la convierte en el mejor sitio donde poner una traza: si salta, tienes un fallo en la disciplina de aplicación de operaciones y lo tienes localizado.

flowchart TD
O[llega un movimiento] --> C[comprobar si p desciende de c]
C --> R1[rechazar: la operacion no surte efecto]
C --> R2[reordenar: deshacer aplicar y rehacer]
C --> R3[rescatar: reubicar el nodo en un sitio visible]
R1 --> P1[paga la intencion de quien movio]
R2 --> P2[paga historia y trabajo en cada llegada tardia]
R3 --> P3[paga la atencion de una persona]
style R1 fill:#f9e2af,color:#11111b
style R2 fill:#89b4fa,color:#11111b
style R3 fill:#a6e3a1,color:#11111b

Rechazar: la operación insegura no surte efecto

La familia más simple consiste en aplicar la comprobación antes de cada movimiento y, si sale insegura, no hacer nada. La operación se recibe, se registra y se ignora en cuanto a su efecto sobre el estado. Es determinista, es barata y converge, siempre que todas las réplicas evalúen la comprobación en el mismo punto de la historia, que es exactamente la condición que la hace difícil.

Antes de las variantes conviene precisar en qué sentido converge, porque la letra pequeña es todo. Rechazar converge si y solo si todas las réplicas evalúan la misma operación contra el mismo estado. Eso no ocurre por casualidad: hay que construirlo, y solo hay dos formas conocidas de construirlo, que son tener un observador privilegiado o tener un orden acordado. Las variantes de esta familia se distinguen exactamente por cuál de las dos eligen, y la que no elige ninguna es la que falla.

Su variante más antigua es la que Kleppmann y sus coautores documentan en aplicaciones de sincronización de escritorio: el sistema devuelve un error y le pide al usuario que resuelva. Su variante centralizada es la de Figma, donde el servidor es quien evalúa: si una operación crearía un ciclo en el estado del servidor, la rechaza y los clientes hacen lo propio. Como los clientes aplican de forma optimista mientras esperan respuesta, pueden aparecer ciclos temporales, y para esos Figma recurre a una técnica de la tercera familia, ocultar los elementos implicados hasta que llegue el veredicto.

El coste de esta familia se enuncia sin rodeos: se pierde una intención de usuario, en silencio y sin aviso. Alguien decidió que X iba dentro de Y, el sistema lo aceptó en local, la persona vio el resultado en pantalla y más tarde el movimiento se deshizo sin que nadie se lo dijera. Si tu producto puede permitirse notificar ese rechazo, el problema se vuelve tolerable. Si no puede, has construido un sistema que deshace trabajo del usuario a sus espaldas.

Hay una versión de esta familia que parece la más simple de todas y que no funciona, así que conviene descartarla explícitamente: rechazar según el orden de llegada, es decir, aceptar la primera operación que aterrice y rechazar la que después resulte insegura. Es tentadora porque no exige ni servidor ni historia, y falla por la razón más elemental: el orden de llegada es distinto en cada réplica. La que recibió primero el movimiento de X rechaza el de Y, la que recibió primero el de Y rechaza el de X, y ambas se quedan con un árbol perfectamente válido y distinto del de la otra. Has cambiado un fallo de invariante por un fallo de convergencia, que es peor, porque el primero al menos se ve.

Ese contraejemplo aclara qué es lo que de verdad aporta el servidor en la variante centralizada, y no es capacidad de cómputo. El servidor no comprueba nada que un cliente no pueda comprobar; lo que aporta es que todos miran el mismo orden de llegada, porque solo hay uno. Rechazar es una estrategia correcta exactamente cuando existe un punto de vista privilegiado, y por eso los productos que la eligen tienen todos un servidor en el camino y ninguno funciona entre pares.

Reordenar: deshacer, aplicar y rehacer

La segunda familia empieza por una decisión distinta: en vez de resolver el empate operación a operación, se impone un orden total sobre todas las operaciones —típicamente un reloj lógico con la identidad de la réplica como desempate— y se define que el estado correcto es el que resulta de aplicarlas en ese orden, comprobando la seguridad de cada una en su turno.

Fíjate en el desplazamiento que esa definición introduce y que la lección siguiente explota a fondo: el estado deja de ser algo que se modifica y pasa a ser algo que se calcula. Ya no dices el árbol es esto y las operaciones lo van cambiando; dices el árbol es la función que resulta de aplicar el registro en orden, y lo que guardas en memoria es una caché de esa función. Todo el comportamiento raro de esta familia —deshacer, rehacer, cambiar de opinión sobre operaciones antiguas— es consecuencia directa de haber aceptado esa definición y de nada más.

La dificultad práctica es que las operaciones no llegan en ese orden. Una operación puede aterrizar con un sello que la coloca en mitad de la secuencia ya aplicada, y como la seguridad depende del estado, no basta con insertarla al final. Hay que deshacer las posteriores, aplicar la nueva y rehacer las deshechas comprobando de nuevo cada una. Ese bucle es el núcleo del algoritmo que la lección siguiente desarrolla entero, así que aquí basta con retener su forma y su factura: exige conservar historia y trabajar en cada llegada tardía.

A cambio ofrece algo que la primera familia no da: un criterio de rechazo que no depende del orden de llegada de nadie. Dos réplicas que hayan visto las mismas operaciones descartan exactamente las mismas, con independencia de por qué camino llegaron. Es la única de las tres familias que consigue eso sin un servidor, y ese es todo el motivo por el que existe.

Nótese que reordenar sigue descartando operaciones, igual que rechazar, así que no evita la pérdida de intención. Lo que cambia es quién queda descartado y con qué criterio: en vez de perder la que llegó tarde a un observador concreto, se pierde la que ocupa la posición perdedora en un orden que todos calculan igual. Desde el punto de vista del usuario cuyo movimiento se evapora la diferencia es nula; desde el punto de vista del sistema es la diferencia entre converger y no converger, que es la única que un algoritmo puede prometer.

Rescatar, y el criterio para elegir entre las tres

La tercera familia acepta las dos operaciones y arregla el resultado moviendo alguno de los nodos implicados a un destino que rompa el lazo. Matthew Weidner, en su repaso de la materia, enumera varias formas de hacerlo, y conviene verlas juntas porque cubren un abanico amplio de compromisos.

La última tarjeta describe el algoritmo de Evan Wallace, que merece un párrafo propio porque ataca el problema desde un ángulo distinto a todo lo anterior. Cada nodo lleva la lista de sus padres históricos, cada uno con un contador que es uno más que el de todos los anteriores, y el padre vigente es el de contador más alto. Esa información viaja en la sincronización. Cuando aparece un ciclo, el algoritmo reengancha los nodos implicados al padre histórico más cercano que no cierre el lazo y que esté conectado a la raíz, y repite hasta que todo cuelga del árbol. Su gran ventaja es que evita por completo el bucle de deshacer y rehacer; su coste, como el propio autor señala, es que cada movimiento remoto obliga a comprobar la conectividad de todos los nodos, y eso escala mal cuando el árbol es grande.

La comparación entre ese algoritmo y el de la lección siguiente es un buen ejemplo de cómo se negocian los costes en esta materia, porque los dos pagan lo mismo en distinta moneda. Uno guarda historia de operaciones y paga trabajo cuando llega algo desordenado; el otro guarda historia de padres por nodo y paga trabajo en cada llegada, ordenada o no. Los dos conservan el pasado, porque los dos necesitan poder deshacer decisiones, y esa necesidad no es negociable: viene de que la validez es global. Lo único que cambia es la forma del pasado que cada uno decide conservar.

Puestas las tres sobre la mesa, el criterio de elección no es cuál algoritmo es mejor, porque ninguno domina a los demás, sino qué recurso te sobra en tu dominio. Si tienes un servidor en el camino y te lo puedes permitir, rechazar en el servidor es la respuesta más simple que funciona, y es la que usa el producto colaborativo de árboles más conocido que existe. Si no tienes servidor y necesitas que todas las réplicas coincidan sin negociar, reordenar es la única familia que lo consigue, y pagarás en historia. Si tu dominio no tolera que el sistema deshaga trabajo en silencio, rescatar es la única honesta, y pagarás en atención humana.

Hay un criterio adicional que suele decidir el empate cuando los anteriores no lo hacen, y es la frecuencia esperada. Si en tu producto el ciclo ocurre una vez cada muchos meses, casi cualquier estrategia sirve y conviene elegir la más simple de mantener, que probablemente sea rescatar con una zona visible, porque no exige historia ni infraestructura y su coste solo se paga cuando el caso aparece. Si ocurre a diario porque tu dominio invita a reorganizar en equipo, la solución tiene que ser automática y determinista, y entonces reordenar es la única que aguanta el volumen sin fatigar a nadie. Medir esa frecuencia antes de elegir es más útil que cualquier razonamiento sobre elegancia.

Hay un cuarto escenario que las tres familias tratan de forma distinta y que conviene puntuar aparte porque es el que más se olvida: el borrado de un ancestro mientras alguien mueve un descendiente hacia fuera. Si el borrado arrastra a todos los descendientes sin más, el archivo que la otra persona acababa de rescatar se va con la carpeta y la sensación es de pérdida de datos, aunque técnicamente el sistema haya hecho lo que decía su especificación. Rechazar y reordenar lo resuelven bien si el borrado se modela como un movimiento a un nodo de basura, porque entonces el conflicto se reduce a dos movimientos ordinarios sobre nodos distintos. Rescatar lo resuelve por otra vía, sacando el descendiente a una zona visible. Lo que ninguna resuelve es no haberlo pensado.

Hay además una combinación que aparece una y otra vez en los productos que funcionan, y no es un compromiso tibio sino la respuesta correcta a que el problema tenga dos escalas de tiempo. En el instante, mientras el estado remoto aún no ha llegado, se rescata: se oculta o se recoloca lo que forma el ciclo para que la interfaz siga siendo dibujable. A medio plazo, cuando la información completa está disponible, se aplica el criterio determinista, rechazando o reordenando. Figma hace exactamente eso, y el motivo de fondo es que la primera escala necesita una respuesta ahora y la segunda necesita una respuesta igual en todas partes, que son requisitos distintos.

Ese desdoblamiento tiene una lectura arquitectónica que vale para mucho más que los árboles. Toda aplicación optimista vive con dos estados a la vez, el que ya está acordado y el que aún es una apuesta local, y normalmente la diferencia entre ambos es invisible porque la apuesta casi siempre se confirma. El ciclo es uno de los pocos casos donde la apuesta puede resultar estructuralmente imposible, no simplemente perdedora, y por eso obliga a hacer explícito un mecanismo que en el resto del producto está implícito. Si tu interfaz no sabe dibujar el estado intermedio, la única alternativa es dejar de ser optimista para los movimientos, es decir, esperar confirmación antes de mover en pantalla, y eso se nota tanto que casi nadie lo elige.