Árboles con movimiento: el problema del nivel 36 como característica

El nivel 36 dejó planteado el problema del movimiento en jerarquías replicadas y por qué modelarlo como un borrado seguido de una creación produce desastres: nodos duplicados, subárboles perdidos y, en el peor caso, ciclos que dejan de ser un árbol. Loro no lo deja como ejercicio para el programador ni lo delega en un servidor árbitro: lo implementa como contenedor de primera clase, con la operación de movimiento incorporada al modelo de datos y con orden entre hermanos incluido. Esta lección desmonta las dos mitades de esa implementación —el algoritmo de movimiento propiamente dicho y el mecanismo de ordenación de los hijos— y termina en la pregunta que decide si esto te importa o no: qué clase de aplicación deja de ser viable sin ello y cuál puede vivir perfectamente sin enterarse.

Unificarlo todo en una sola operación

La documentación de Loro es explícita sobre su procedencia: el contenedor de árbol implementa el algoritmo publicado por Kleppmann y otros bajo el título de una operación de movimiento de alta disponibilidad para árboles replicados. El primer movimiento de ese trabajo es de simplificación radical, y conviene apreciarlo antes de mirar ningún mecanismo.

Las tres operaciones que uno esperaría —crear, borrar y mover— se colapsan en una sola. Un movimiento es una tupla con cuatro componentes: una marca de tiempo única y ordenable, el identificador del nodo padre, los metadatos asociados y el identificador del nodo hijo. Si el hijo no existe todavía en el árbol, la operación crea; si ya existe, la operación mueve. Y el borrado se modela introduciendo un nodo especial de papelera: mover un nodo allí equivale a borrarlo, y todo lo que cuelga de la papelera se considera borrado.

Los cuatro conflictos posibles y su dificultad

  mismo nodo borrado y movido ......... trivial tras la unificacion
  mismo nodo movido a dos padres ...... trivial con orden total
  ancestro borrado, descendiente movido  resuelto por el nodo papelera
  dos movimientos que forman un ciclo .. el unico problema de verdad

El detalle de la papelera merece un segundo de atención porque es más astuto de lo que parece. Los nodos borrados no se destruyen: siguen en memoria colgando del nodo especial. La razón no es la nostalgia sino la corrección, y se ve en el cuarto conflicto de la lista. Si una réplica borra una carpeta mientras otra saca un documento de dentro de ella, la operación de sacarlo llegará referida a un nodo que localmente ya está en la papelera; si ese nodo hubiera desaparecido de verdad, la operación no tendría dónde aplicarse y el documento se perdería sin que nadie lo hubiera pedido.

Esa unificación no es cosmética: elimina tres de los cuatro conflictos posibles. Borrar y mover el mismo nodo pasa a ser dos movimientos del mismo nodo, no un choque entre categorías distintas. Mover el mismo nodo a dos padres distintos se resuelve ordenando linealmente todas las operaciones por marca de tiempo de Lamport, con el identificador del participante como desempate, de modo que dejan de ser concurrentes y pasan a ser sucesivas. Y el caso perverso de borrar un ancestro mientras otro mueve un descendiente queda cubierto porque los nodos de la papelera siguen en memoria, precisamente para poder sacarlos de allí si una operación concurrente lo pide.

Deshacer, aplicar, rehacer

De la ordenación total surge el problema de ingeniería. Si todas las operaciones deben aplicarse en orden de marca de tiempo, y llega una operación remota cuya marca cae en medio de la secuencia ya aplicada, no basta con añadirla al final: hay que reconstruir la historia como si siempre hubiera estado allí.

flowchart TB
R[llega operacion remota con marca intermedia] --> U[deshacer las operaciones posteriores]
U --> A[aplicar la operacion nueva]
A --> C[comprobar si formaria un ciclo]
C --> S[segura: cambia el estado]
C --> I[insegura: se registra pero no surte efecto]
S --> D[rehacer las deshechas en orden]
I --> D
style C fill:#f9e2af,color:#11111b
style D fill:#a6e3a1,color:#11111b

El procedimiento tiene tres tiempos. Se deshacen una a una las operaciones cuya marca es mayor que la recién llegada; se aplica la nueva, comprobando antes si crearía un ciclo; y se rehacen en orden las que se habían deshecho. Deshacer un movimiento es barato porque el algoritmo cachea, antes de aplicar cada operación, cuál era el padre anterior del nodo afectado, de modo que revertir consiste en devolverlo a ese padre.

// Integrar una operacion remota que no es la mas reciente
function aplicar(nueva, registro) {
  if (registro.esPosteriorATodo(nueva)) {
    registro.aplicar(nueva);
    return;
  }
  const deshechas = registro.deshacerHastaPoderAplicar(nueva);
  registro.aplicar(nueva);
  registro.rehacer(deshechas);
}

Hay un caso previo que el procedimiento no puede resolver y que conviene nombrar: si la operación recién llegada depende causalmente de otra que todavía no conocemos, no hay nada que reconstruir todavía. Falta un tramo de historia intermedia, y lo correcto es guardarla en espera hasta que llegue lo que falta. Es la misma disciplina de las operaciones pendientes que aparece en toda la biblioteca, y confundirla con el caso de la marca intermedia lleva a aplicar operaciones sobre un árbol que aún no tiene los nodos que ellas mencionan.

Aquí aparece el punto más sutil del algoritmo y el que conviene retener. Una operación que se declaró insegura y no surtió efecto no se descarta: se registra marcada como inefectiva. El motivo es que la seguridad es dinámica. Si más tarde llega una operación con marca anterior que borra uno de los nodos implicados, el ciclo desaparece y aquella operación pasa a ser segura en la siguiente reconstrucción. Además, la caché del padre anterior debe apuntar al último movimiento efectivo, no simplemente al anterior en el registro, y esa distinción es la que hace correcto todo el mecanismo de deshacer.

Ordenar hermanos: el índice fraccional

Resuelta la jerarquía, queda un problema distinto que la jerarquía no cubre: el orden entre los hijos de un mismo padre. Un esquema de subrayado de notas, un panel de capas de una herramienta de diseño o una lista de subtareas necesitan que arrastrar un elemento por encima de otro sea una operación sincronizable, y eso no es un cambio de padre.

Loro incorpora para ello un índice fraccional, tomado de la implementación de Drifting in Space y extendido. La idea es la de siempre: a cada hijo se le asigna un valor ordenable, y para insertar entre dos se genera un valor intermedio. La implementación es en base doscientos cincuenta y seis sobre un vector de bytes, lo que hace que el tamaño solo crezca cuando se insertan muchas veces seguidas en el mismo punto.

// El orden entre hermanos es una operacion de primera clase
const arbol = doc.getTree("arbol");
const raiz = arbol.createNode();
const a = raiz.createNode();
const b = raiz.createNode(0);   // posicion explicita entre hermanos
a.moveBefore(b);                // reordenar sin cambiar de padre
a.move(b, 0);                   // cambiar de padre y de posicion
a.data.set("titulo", "Nodo A"); // cada nodo lleva su mapa de datos

Dos ordenes que no se estorban

  orden jerarquico ...... quien cuelga de quien
    lo resuelve el algoritmo de movimiento
    su conflicto propio es el ciclo

  orden entre hermanos .. quien va antes que quien bajo el mismo padre
    lo resuelve el indice fraccional
    su conflicto propio es el valor repetido

  una aplicacion de esquemas necesita los dos a la vez

El punto interesante es el conflicto propio de este mecanismo. Si dos participantes insertan a la vez en la misma posición, generan el mismo índice fraccional. Loro conserva ambos y desempata por identificador de participante, lo que resuelve el orden pero rompe la generación futura, porque no se puede fabricar un valor intermedio entre dos valores iguales. Las dos salidas que ofrece son añadir una pequeña perturbación aleatoria a cada valor generado, configurable, y reasignar índices cuando la colisión ya se ha producido. La documentación advierte con honestidad de que el índice fraccional sufre entrelazado, y sostiene que es aceptable en árboles porque ahí se pide orden relativo y no semántica secuencial estricta.

Para qué aplicaciones esto decide la arquitectura

El contraste con lo que no lo necesita aclara el criterio. Un documento de texto plano, un formulario, un tablero de valores clave o cualquier estructura donde la jerarquía sea fija y solo cambien las hojas no gana nada con esto. La pregunta discriminante no es si tu modelo tiene forma de árbol, sino si los usuarios reorganizan ese árbol y si dos de ellos pueden reorganizarlo a la vez.

Hay un tercer grupo que conviene nombrar aparte: las aplicaciones cuya jerarquía la reorganiza el sistema y no el usuario, como un índice recalculado o un agrupamiento automático. Ahí el movimiento tampoco necesita ser una operación replicada, porque el resultado es derivable del contenido y se puede recomputar en cada réplica sin sincronizar nada. Confundir ese caso con el anterior lleva a sincronizar un estado que era una función pura de otro estado, que es el error de diseño más caro que se puede cometer en un sistema replicado.