Treedoc y los árboles binarios: el reequilibrado exige coordinación

Treedoc, presentado por Preguiça, Marquès, Shapiro y Letia en 2009, es la formulación más limpia y más geométrica de la idea de nombrar posiciones: el identificador de un carácter es el camino que lleva hasta él desde la raíz de un árbol binario, escrito como una tira de bits donde cero significa izquierda y uno significa derecha, y el orden del documento es el recorrido en orden simétrico de ese árbol. Entre dos posiciones cualesquiera siempre cabe otra, porque siempre se puede descender; la comparación de dos identificadores es una comparación de tiras de bits; y un árbol equilibrado sobre un millón de caracteres tiene caminos de veinte bits, es decir, nombres más pequeños que el propio carácter en cualquier codificación seria. Sobre el papel es la mejor propuesta del nivel. Su defecto no está en la estructura sino en lo que le ocurre con el tiempo: el árbol se desequilibra, los caminos se alargan y la única cura conocida —reequilibrar— consiste en renombrarlo todo, que es precisamente la operación que un sistema sin coordinación no puede permitirse. Esta lección trata de ese callejón, porque entenderlo es entender el límite de toda la vía posicional.

La posición como camino de bits

Un documento Treedoc es un árbol binario cuyos nodos contienen los caracteres. El identificador de un carácter es la secuencia de decisiones tomadas para llegar hasta él desde la raíz, y el orden entre dos identificadores es el que produce el recorrido en orden simétrico: primero todo el subárbol izquierdo, después el nodo, después todo el subárbol derecho. Comparar dos caminos consiste en avanzar bit a bit hasta la primera diferencia, con la convención de que un camino que es prefijo de otro se sitúa según el bit siguiente del más largo.

// Un camino de Treedoc: bits de decision desde la raiz
const idIzquierdo = [0, 1];       // izquierda y luego derecha
const idDerecho   = [1];          // derecha desde la raiz

function comparar(a, b) {
  for (let i = 0; i < Math.min(a.length, b.length); i += 1) {
    if (a[i] !== b[i]) return a[i] - b[i];
  }
  if (a.length === b.length) return 0;
  // El mas largo continua descendiendo: su primer bit extra decide el lado
  return a.length > b.length ? (a[b.length] === 0 ? -1 : 1)
                             : (b[a.length] === 0 ? 1 : -1);
}

Insertar entre dos caracteres es descender: se busca un camino libre que caiga estrictamente entre ambos, y siempre existe, porque bajo cualquier nodo hay un subárbol vacío disponible. La densidad no es una propiedad que haya que construir con cuidado, como en la aritmética de dígitos de Logoot, sino una consecuencia inmediata de la forma del árbol. Esa elegancia es real y explica por qué la idea reaparece cada pocos años bajo otros nombres.

Comparada con la lección anterior, la relación es de caso particular: Treedoc es Logoot con base dos y sin dígitos intermedios que elegir. Esa reducción tiene una ventaja y un inconveniente que conviene tener claros antes de seguir. La ventaja es que no hay política de asignación, porque con dos opciones por nivel no queda nada que decidir: desaparecen las heurísticas de frontera, la base variable y toda la familia de ajustes que la lección 2 dedicaba a repartir el espacio. El inconveniente es la otra cara de lo mismo: al no haber espacio que repartir en cada nivel, cada inserción entre dos vecinos consecutivos añade profundidad sin excepción, mientras que en una base grande cabían muchas inserciones antes de tener que descender. Treedoc paga en profundidad lo que Logoot pagaba en anchura, y como la profundidad es lo que se transmite, el intercambio no le sale bien.

Desambiguadores: dos réplicas, el mismo hueco

Un camino de bits, por sí solo, no basta. Si dos réplicas insertan concurrentemente en el mismo hueco, ambas eligen el mismo camino y producen dos caracteres distintos con el mismo nombre, que es exactamente lo que un identificador no puede permitir. Treedoc resuelve el choque permitiendo que una posición del árbol aloje varios caracteres, cada uno etiquetado con un desambiguador único formado por el identificador de réplica y su contador; dentro de esa posición, el orden entre los caracteres es el orden de sus desambiguadores.

// Identificador completo: camino de bits mas desambiguadores en los nodos compartidos
const id = [
  { bit: 1, dis: null },                        // nodo sin colision, no necesita etiqueta
  { bit: 0, dis: { replica: "r4", n: 12 } }     // nodo compartido por insercion concurrente
];

Merece la pena ver por qué hace falta esta pieza aquí y no hacía falta en Logoot, porque la diferencia ilumina el diseño. En Logoot, cada componente del camino llevaba ya la réplica y el contador incorporados, de modo que la colisión era imposible por construcción a costa de engordar todos los componentes. Treedoc elige lo contrario: componentes mínimos de un bit y una etiqueta añadida solo cuando la colisión ocurre de verdad. Es una optimización por el caso frecuente, y es correcta, pero introduce un identificador de estructura irregular —una lista de bits con etiquetas ocasionales— que complica la comparación, la serialización y cualquier intento posterior de comprimir en columnas.

El detalle importante es que el desambiguador solo aparece donde hubo colisión, de modo que en un uso normal la mayoría de los componentes del camino son un bit pelado y el identificador se mantiene compacto. El detalle incómodo es que ese nodo compartido queda para siempre en la estructura: aunque después se borren todos los caracteres que alberga, si alguno tiene descendientes el nodo no puede desaparecer sin dejar huérfano al subárbol que cuelga de él. Aquí también hay lápidas, aunque de otra naturaleza que en RGA: no se conserva el contenido borrado, se conserva el esqueleto que sostiene a los caminos vivos.

El árbol se degenera

La cuarta tarjeta dice con el árbol equilibrado, y ahí está todo el problema. El equilibrio de un árbol binario de búsqueda depende del orden en que llegan las claves, y en un editor las claves no llegan al azar: llegan en el orden en que una persona escribe. Alguien que redacta un texto de principio a fin inserta siempre a la derecha del último carácter, y cada inserción de ese tipo añade un nivel a una rama que solo crece hacia un lado. El árbol se convierte en una lista enlazada disfrazada, con caminos de longitud proporcional al número de caracteres en vez de a su logaritmo.

flowchart TD
R[raiz] --> L[subarbol izquierdo vacio]
R --> D1[bit 1]
D1 --> D2[bits 1 1]
D2 --> D3[bits 1 1 1]
D3 --> D4[bits 1 1 1 1]
D4 --> D5[el camino crece con cada pulsacion]
style R fill:#a6e3a1,color:#11111b
style D5 fill:#f38ba8,color:#11111b

Conviene detenerse en el mecanismo exacto, porque es más específico de lo que parece. Un árbol binario de búsqueda se equilibra bien cuando las claves llegan desordenadas respecto del orden final, y se degenera cuando llegan ya ordenadas. En un editor, la clave de un carácter es su posición, y su posición es aproximadamente el momento en que se escribió: teclear un párrafo genera claves estrictamente crecientes, que es la entrada exactamente peor para la estructura. Dicho de otro modo, la correlación entre el orden temporal de las inserciones y el orden espacial del resultado —que en un texto es casi perfecta— es justo la patología que el árbol binario no tolera.

Las consecuencias son las mismas tres que en Logoot y por la misma razón de fondo: identificadores que pesan más que el contenido, comparaciones cada vez más largas y operaciones de red cada vez más gordas. Pero aquí hay un agravante estructural. En Logoot, la longitud del identificador dependía del número de inserciones en ese punto concreto; en Treedoc depende de la profundidad de la rama, y una rama profunda penaliza a todo lo que cuelgue de ella, incluidas las inserciones futuras de otras réplicas que no tuvieron nada que ver con el patrón que la degeneró. La degeneración es contagiosa hacia abajo.

Reequilibrar exige consenso

La cura evidente para un árbol degenerado es reequilibrarlo, y aquí es donde toda la elegancia se rompe. Reequilibrar significa reconstruir el árbol de forma que la secuencia visible sea la misma pero los caminos sean cortos, y como el camino es el identificador, reequilibrar significa cambiarle el nombre a todos los caracteres del documento. Cualquier operación que estuviera viajando por la red en ese momento —emitida por una réplica que aún no sabe nada del reequilibrado— cita nombres que han dejado de existir, y no hay forma local de traducirla, porque su posición relativa depende de un árbol que ya no está.

// El contraejemplo minimo: las dos ordenaciones no producen el mismo documento
const doc = ["", "1", "11"];                 // arbol degenerado hacia la derecha

const insercion = { camino: [1, 1, 1], valor: "d" };   // emitida por una replica remota
const reequilibrado = (arbol) => reconstruirEquilibrado(arbol);  // renombra todos los caminos

// Camino A: primero la insercion, despues el reequilibrado
const a = reequilibrado(aplicar(doc, insercion));       // "d" existe y recibe un nombre nuevo

// Camino B: primero el reequilibrado, despues la insercion
const b = aplicar(reequilibrado(doc), insercion);       // el camino 1,1,1 ya no designa nada

El comentario de la última línea es todo el problema. Tras el reequilibrado, el camino que la operación cita puede no existir, o peor, puede existir y designar otro carácter completamente distinto, en cuyo caso la inserción se aplica en silencio en un lugar equivocado y las réplicas divergen sin ningún error visible. No es un caso raro que se pueda tratar como excepción: es el comportamiento normal de cualquier operación emitida antes del reequilibrado y recibida después, y en un sistema donde las réplicas pueden estar desconectadas durante días, esa ventana no tiene cota superior.

Dicho con precisión: el reequilibrado no conmuta con la inserción. Aplicar primero una inserción y después el reequilibrado no da el mismo resultado que aplicar primero el reequilibrado y después esa misma inserción, y una operación cuya aplicación depende del orden es exactamente lo que un tipo de dato replicado convergente no puede tener. Es la única operación de todo este nivel que rompe la propiedad fundacional.

Hay tres salidas posibles y las tres son insatisfactorias por razones distintas, así que conviene enunciarlas para cerrar el análisis. La primera es no reequilibrar nunca, que es lo que eligió Logoot y lo que convierte el problema de coordinación en un problema de crecimiento sin techo. La segunda es reequilibrar con acuerdo global, que es la vía de Treedoc y la que introduce en el sistema un punto de sincronía. La tercera, la que usan en la práctica las aplicaciones con índice fraccionario, es reequilibrar contra una autoridad: un servidor renumera en una transacción, publica el resultado y los clientes lo adoptan como cualquier otro cambio de estado. Esta última funciona muy bien y es perfectamente respetable, con una condición que hay que decir en voz alta: deja de ser una arquitectura sin coordinación, y por tanto no sirve para el escenario en que dos réplicas deben poder editar durante días sin verse.

Treedoc afrontó el problema con un protocolo de compromiso: separar la parte de la historia sobre la que todas las réplicas ya están de acuerdo de la parte reciente aún en circulación, reequilibrar solo la primera y hacerlo en un instante que todas las réplicas reconozcan como el mismo, lo que exige que todas hayan confirmado su participación. Las réplicas que estaban desconectadas durante el reequilibrado tienen que ponerse al día traduciendo sus operaciones pendientes antes de poder participar de nuevo. Funciona, y es una pieza de ingeniería respetable, pero la conclusión es inapelable: hay un punto del sistema donde hace falta acuerdo entre todos, y ese punto es un servidor de coordinación con otro nombre, con su disponibilidad, sus tiempos de espera y su comportamiento bajo partición.