Deshacer y rehacer: el orden total como fuente de verdad

De las tres familias, la segunda es la única que consigue que todas las réplicas descarten exactamente las mismas operaciones sin que nadie arbitre, y por eso merece una lección entera. Su formulación de referencia es el trabajo de Martin Kleppmann, Dominic Mulligan, Victor Gomes y Alastair Beresford sobre una operación de movimiento de alta disponibilidad para árboles replicados, publicado en 2021 y 2022, y su idea central se puede resumir en una frase engañosamente sencilla: el estado del árbol se define como el resultado de aplicar todas las operaciones de movimiento en orden total, saltándose las que en su turno cerrarían un ciclo. Lo engañoso está en en su turno, porque las operaciones no llegan en orden y la seguridad depende del estado. La consecuencia es un bucle de deshacer, aplicar y rehacer que el algoritmo ejecuta cada vez que aterriza algo con sello intermedio. Esta lección lo desmonta pieza a pieza, explica qué hay que guardar para poder deshacer y hace la cuenta honesta de lo que cuesta.

Una sola operación para todo el árbol

El primer movimiento del algoritmo es de modelado y ahorra la mitad de los casos difíciles. En lugar de tres operaciones, hay una: un movimiento descrito por cuatro componentes que el artículo escribe como Move t p m c, donde t es un sello temporal único y ordenable, p es el identificador del padre de destino, m son los metadatos asociados al nodo y c es el identificador del hijo que se mueve.

La componente de metadatos merece una nota, porque su presencia en la tupla no es decorativa: al viajar junto al movimiento permite que la creación de un nodo y la asignación de su contenido inicial sean el mismo evento, sin ventana entre ambos donde otra réplica pueda ver un nodo a medio construir. Es un detalle pequeño con consecuencias grandes en la interfaz, donde un nodo vacío parpadeando antes de recibir su nombre es exactamente el tipo de artefacto que hace parecer roto a un producto que funciona.

Con esa única forma se expresan las tres operaciones del árbol mediante una lectura contextual muy elegante. Si el nodo c no existe todavía en el árbol, el movimiento lo crea bajo p. Si existe, lo mueve desde su padre actual hasta p. Y el borrado se modela introduciendo un nodo especial de basura: mover algo bajo ese nodo equivale a borrarlo, y todo lo que cuelga de él se considera borrado. Los nodos borrados permanecen en memoria en vez de desaparecer, y eso no es un descuido: es lo que permite que una operación concurrente que mueva un descendiente de algo borrado se pueda aplicar y arbitrar como cualquier otra, en vez de convertirse en un caso especial sin respuesta.

El nodo de basura merece un momento de atención porque su función no es la que parece. No está ahí para ahorrar una operación sino para que los nodos borrados sigan existiendo como destinos válidos. Si el borrado eliminase el nodo del mapa, una operación concurrente que moviera un descendiente hacia fuera se encontraría con un padre inexistente y no habría forma de decidir qué hacer con ella sin inventar una regla nueva. Al conservarlo, esa operación se aplica como cualquier otra y el orden total decide: si el movimiento hacia fuera gana, el descendiente se salva; si pierde, se queda dentro de la basura. En ambos casos el resultado es el mismo en todas las réplicas y se obtiene con el mecanismo que ya existe.

Esta unificación tiene un efecto que conviene señalar porque resuelve gratis uno de los cuatro conflictos que el nivel identificó. Borrar y mover el mismo nodo a la vez deja de ser un choque entre operaciones de tipos distintos y pasa a ser un choque entre dos movimientos, que es un caso que el orden total ya sabe arbitrar. De los cuatro escenarios problemáticos, la unificación elimina uno y el orden total elimina otro, y solo queda el ciclo.

El orden total y lo que resuelve por sí solo

El segundo movimiento es imponer un orden total sobre las operaciones. Se usa un reloj lógico de Lamport: cada réplica lleva un contador que incrementa al producir un evento local y que, al recibir un mensaje, actualiza al máximo entre el suyo y el que llega. Para ordenar globalmente se comparan primero los contadores, y cuando coinciden se desempata con el identificador de réplica, que es único. El resultado es un orden total, sin empates posibles, y compatible con la causalidad.

La ganancia inmediata es que el segundo escenario problemático desaparece por construcción. Dos movimientos concurrentes del mismo nodo bajo padres distintos dejan de ser concurrentes desde el punto de vista del algoritmo: el orden total los pone uno detrás del otro, se aplican en secuencia y gana el segundo, con el resultado idéntico en todas las réplicas. No hay duplicados, no hay dos aristas de padre, no hay nada que decidir.

Conviene notar que ese orden total es compatible con la causalidad pero mucho más fuerte que ella. Contiene al orden parcial de precedencia y además ordena los pares que la causalidad dejaba incomparables, y lo hace mediante un criterio que no significa nada: el identificador de réplica. Esa arbitrariedad es deliberada y es el precio de la familia entera. Un desempate arbitrario pero acordado sirve para lo único que hace falta aquí, que es que todos calculen lo mismo, aunque no exprese ninguna verdad sobre lo que ocurrió.

Lo que el orden total no resuelve es el ciclo, y ahí está toda la dificultad restante. Aplicar en orden no impide que una operación, evaluada contra el estado que le corresponde, resulte insegura. Lo que sí garantiza es que la evaluación dé el mismo resultado en todas partes, siempre que todas las réplicas evalúen contra el mismo estado, es decir, siempre que todas apliquen en el orden acordado. Y esa condición es la que obliga a lo que viene ahora.

El bucle: deshacer, aplicar, rehacer

Cuando llega una operación con sello mayor que todos los aplicados, el caso es trivial: se comprueba su seguridad contra el estado actual y se aplica o se marca como sin efecto. Cuando llega con sello intermedio, hay que colocarla en su sitio, y como la seguridad depende del estado, no basta con insertarla en el registro. Se deshacen una a una las operaciones posteriores, se aplica la nueva y se rehacen las deshechas en orden, reevaluando la seguridad de cada una al rehacerla.

function aplicar(registro, estado, nueva) {
  const posteriores = [];
  // 1. Deshacer hacia atras hasta que la nueva sea la ultima.
  while (registro.length > 0 && mayor(registro.at(-1).t, nueva.t)) {
    const op = registro.pop();
    deshacer(estado, op);
    posteriores.push(op);
  }
  // 2. Aplicar la nueva en su sitio.
  hacer(estado, nueva);
  registro.push(nueva);
  // 3. Rehacer en orden, comprobando de nuevo cada una.
  while (posteriores.length > 0) {
    const op = posteriores.pop();
    hacer(estado, op); // puede pasar de efectiva a inefectiva y al reves
    registro.push(op);
  }
}

function hacer(estado, op) {
  if (!esSeguro(estado.padre, op.c, op.p)) {
    op.efectiva = false; // se registra igual, sin tocar el estado
    return;
  }
  op.padreViejo = estado.padre.get(op.c); // lo que hara falta para deshacer
  op.efectiva = true;
  estado.padre.set(op.c, op.p);
}

function deshacer(estado, op) {
  if (!op.efectiva) return; // no toco el estado, no hay nada que revertir
  if (op.padreViejo === undefined) estado.padre.delete(op.c);
  else estado.padre.set(op.c, op.padreViejo);
}

El detalle que más gente pasa por alto está en la tercera fase: al rehacer, una operación puede cambiar de veredicto. Una que era efectiva puede volverse insegura porque la operación recién insertada movió el árbol bajo sus pies, y una que estaba marcada como inefectiva puede volverse aplicable porque la nueva deshizo el lazo que la bloqueaba. Por eso hacer recalcula siempre y nunca confía en la marca anterior. Un algoritmo que cachee el veredicto converge a estados distintos según el orden de llegada, que es exactamente lo que se pretendía evitar.

sequenceDiagram
participant R as Registro ordenado
participant E as Estado del arbol
Note over R: llega una operacion con sello intermedio
R->>E: deshacer las posteriores una a una
R->>E: aplicar la nueva si es segura
R->>E: rehacer las deshechas en orden
Note over R,E: cada rehecho vuelve a comprobar la seguridad
Note over R,E: el veredicto puede cambiar en ambos sentidos

Observa también la simetría entre hacer y deshacer, porque es lo que hace correcto al conjunto. hacer decide si la operación es efectiva y, en caso afirmativo, guarda el padre anterior; deshacer lee esa marca y, si la operación no fue efectiva, no toca nada. Sin esa asimetría de tratamiento —revertir solo lo que se aplicó— una operación inefectiva reescribiría el padre del nodo al deshacerse y corrompería el estado silenciosamente. Es el tipo de error que no aparece en las pruebas simples porque exige que una operación insegura quede en medio de la secuencia y que después llegue otra más antigua.

Hay un requisito previo que el fragmento anterior da por hecho y que en un sistema real hay que implementar: una operación no se puede aplicar si depende de otras que aún no han llegado. Cuando eso ocurre se guarda en una zona de espera y se reintenta cuando el hueco causal se rellena, con la misma mecánica de entrega causal que ya conoces de los relojes vectoriales. Sin esa espera, el registro tendría agujeros y la reevaluación de seguridad se haría contra estados que nunca existieron.

Qué se guarda y qué cuesta

La factura de este algoritmo tiene tres partidas y conviene mirarlas por separado, porque no duelen en los mismos escenarios.

La partida que asusta sobre el papel es la última, porque en el peor caso una operación muy vieja obliga a deshacer y rehacer todo lo que hay detrás. Pero la distribución real de ese peor caso es benigna en la mayoría de los productos: los sellos que llegan muy retrasados son los de dispositivos que estuvieron mucho tiempo desconectados, y esos son minoría frente al flujo normal, donde casi todo llega con el sello mayor y entra por el camino trivial.

Conviene además notar que las tres primeras partidas se pagan una sola vez por operación y no crecen con el uso, mientras que la cuarta se paga en cada llegada desordenada. Esa distinción importa al medir: el tamaño del documento en disco depende de las tres primeras y crece de forma lineal y predecible con el número de movimientos históricos, mientras que la latencia percibida depende de la cuarta y es irregular. Confundirlas lleva a optimizar la partida equivocada, que suele ser la del tamaño cuando el problema estaba en las llegadas tardías.

Las cifras que Loro publicó al implementarlo dan una idea del orden de magnitud en un equipo de escritorio moderno: diez mil movimientos al azar sobre un árbol de mil nodos en veintiocho milisegundos; mil saltos entre versiones distintas en ciento cincuenta y tres milisegundos; y los mismos mil saltos sobre un árbol de trescientos niveles de profundidad en setecientos un milisegundos. La última cifra es la interesante, porque muestra dónde está la sensibilidad real: no en el número de nodos sino en la profundidad, que es lo que multiplica el coste de cada comprobación de seguridad.

De ahí sale un consejo de modelado con más recorrido del que parece: si tu jerarquía puede crecer en profundidad sin límite, ponle uno. Casi ningún dominio necesita de verdad doscientos niveles de anidamiento, y quien los alcanza suele estar usando el árbol para algo que no es una jerarquía, como codificar una secuencia larga colgando cada elemento del anterior. Un límite razonable convierte la comprobación de seguridad en una constante pequeña y elimina de golpe la única forma conocida de hacer lenta a esta familia.