Logoot y LSEQ: el identificador como camino en un árbol de dígitos

Si el problema es nombrar posiciones, hay una respuesta que un matemático daría antes que un ingeniero: usa un conjunto denso. Entre dos números racionales cualesquiera siempre cabe otro, y esa propiedad, trasladada a un espacio de identificadores, elimina de raíz la necesidad de referirse a los vecinos. Logoot, propuesto por Weiss, Urso y Molli en 2009, construye exactamente eso: cada carácter recibe como nombre una secuencia de dígitos que se lee como un camino descendente en un árbol de aridad grande, y el orden del documento es el orden lexicográfico de esos caminos. La consecuencia inmediata es espectacular y explica el interés que despertó: como la posición de un carácter no depende de ningún otro, borrar puede borrar de verdad, sin lápidas y sin dejar residuo. La consecuencia diferida es la que decidió su suerte: el camino se alarga cada vez que hay que meter algo donde ya no cabe, y hay patrones de escritura completamente normales que lo alargan sin techo. LSEQ, de 2013, es la respuesta más elaborada a ese segundo problema, y estudiar por qué lo mitiga sin resolverlo enseña más que cualquiera de las dos propuestas por separado.

El nombre es un camino, no un número

Un identificador de Logoot es una lista de componentes, y cada componente lleva un dígito acompañado del identificador de la réplica que lo generó y de su contador local. El dígito es lo que ordena; la réplica y el contador están ahí para desempatar cuando dos sitios eligen el mismo dígito de forma concurrente, y de paso garantizan que el identificador sea único en todo el sistema. La comparación entre dos identificadores es lexicográfica componente a componente, y dentro de cada componente se compara primero el dígito y después la réplica.

// Un identificador de Logoot: camino de componentes, cada uno con su desempate
const idA = [{ d: 4, sitio: 2, reloj: 11 }];
const idB = [{ d: 4, sitio: 2, reloj: 11 }, { d: 7, sitio: 5, reloj: 3 }];

function comparar(a, b) {
  for (let i = 0; i < Math.min(a.length, b.length); i += 1) {
    if (a[i].d !== b[i].d) return a[i].d - b[i].d;
    if (a[i].sitio !== b[i].sitio) return a[i].sitio - b[i].sitio;
  }
  return a.length - b.length;   // el prefijo precede a su extension
}

La última línea es la que hace denso el espacio. Un identificador que es prefijo de otro va siempre antes que él, de modo que descender un nivel siempre crea sitio: por muy pegados que estén dos caminos, añadir un componente al menor produce un nombre que cae estrictamente entre ambos. No hay ningún par de posiciones entre las que no quepa una tercera, y por tanto ninguna inserción puede fallar por falta de espacio. Esa garantía es la que permite prescindir de las lápidas: como el nombre de un carácter no menciona a sus vecinos, borrar un carácter no invalida ninguna referencia y el objeto puede desaparecer sin dejar rastro.

flowchart TD
R[raiz del espacio de nombres] --> A[digito 4]
R --> B[digito 5]
A --> A1[4 luego 2]
A --> A2[4 luego 7]
A2 --> A21[4 luego 7 luego 1]
B --> B1[5 luego 3]
style A2 fill:#89b4fa,color:#11111b
style A21 fill:#cba6f7,color:#11111b

El documento se guarda como una lista ordenada por identificador, con las dos posiciones extremas reservadas como cotas. Localizar dónde va un carácter que llega de la red es una búsqueda binaria sobre esa lista, con coste logarítmico en el número de caracteres vivos —vivos, no históricos, porque aquí no hay lápidas— multiplicado por el coste de comparar dos identificadores, que es proporcional a la longitud del camino. Esa segunda parte del producto es la que hay que vigilar, y es el tema de las dos secciones siguientes.

Generar una posición entre otras dos

La operación central es una función que recibe los identificadores de los vecinos izquierdo y derecho y devuelve uno estrictamente intermedio. El caso cómodo es que en el primer componente donde ambos difieren quede al menos un dígito libre: se elige uno de ellos y el identificador tiene la misma longitud que sus vecinos. El caso incómodo es que no quede hueco, y entonces hay que descender: se copia el prefijo del vecino izquierdo, se añade un componente nuevo y se elige el dígito dentro del rango completo del nivel inferior.

// Esbozo del esquema de asignacion, sin la aritmetica exacta de ninguna variante
function generarEntre(izq, der, nivel, sitio, reloj) {
  const base = baseDelNivel(nivel);              // en Logoot fija, en LSEQ creciente
  const a = digitoEn(izq, nivel, 0);
  const b = digitoEn(der, nivel, base);

  if (b - a > 1) {
    const d = elegirDigito(a, b, nivel);         // aqui vive toda la politica
    return [...prefijo(izq, nivel), { d, sitio, reloj }];
  }
  // No cabe nada en este nivel: se desciende y se reintenta con mas espacio
  return generarEntre(izq, der, nivel + 1, sitio, reloj);
}

El componente de réplica que acompaña a cada dígito cumple aquí una función que es fácil pasar por alto. Dos réplicas que generan concurrentemente una posición entre los mismos vecinos pueden elegir por azar el mismo dígito, y si el identificador fuese solo el dígito tendríamos dos caracteres distintos con el mismo nombre, que es la única situación que este diseño no puede tolerar. Al incluir la réplica en la comparación, el empate se rompe siempre y de la misma manera en todas partes, sin comunicación alguna. Es el mismo papel que juega el identificador de réplica en los relojes de Lamport del nivel 21, y no es casualidad: en ambos casos se trata de convertir un orden parcial en uno total por el procedimiento más barato posible.

Toda la diferencia entre las variantes de esta familia está en elegirDigito y en baseDelNivel, y conviene ver por qué. Elegir el dígito al azar en todo el intervalo reparte bien el espacio cuando las inserciones son dispersas, pero desperdicia el rango cuando son consecutivas: si cada carácter se coloca en el centro del hueco disponible, el hueco se divide a la mitad en cada pulsación y se agota tras unas pocas decenas de teclas. Elegir el dígito a poca distancia de uno de los extremos —la estrategia que se conoce como asignación con frontera— consume el espacio de forma lineal en lugar de exponencial, y por eso es la que adoptaron las implementaciones serias. Pero una frontera fija tiene un sesgo: favorece a quien escribe hacia un lado y castiga a quien escribe hacia el otro.

Cuando alguien escribe siempre en el mismo sitio

El patrón que rompe a Logoot no es exótico: es escribir. Alguien que teclea un párrafo de principio a fin inserta cada carácter inmediatamente a la derecha del anterior, siempre en el mismo hueco, y cada inserción consume una porción del rango disponible en ese nivel. Con una base fija y una estrategia de frontera, ese rango se agota tras un número de pulsaciones proporcional a la base, y a partir de ahí cada carácter nuevo obliga a descender un nivel más. El identificador deja de ser un componente y pasa a ser dos, tres, diez; en el peor caso su longitud crece de forma lineal con el número de caracteres escritos en ese punto.

Las consecuencias son de tres tipos y todas se agravan a la vez. La memoria, porque el nombre de un carácter puede llegar a pesar mucho más que el carácter, y en un documento de texto plano eso significa que los metadatos dominan el contenido en uno o dos órdenes de magnitud. El coste de comparar, porque la búsqueda binaria sigue siendo logarítmica en el número de elementos pero cada comparación recorre caminos cada vez más largos. Y el tráfico, porque cada operación transporta su identificador completo y la red acaba moviendo mucho más nombre que texto.

La última tarjeta apunta a la respuesta más pragmática que dio esta familia. En lugar de un identificador por carácter, se asigna uno por bloque de caracteres contiguos escritos por la misma réplica, y el bloque se parte en dos cuando alguien inserta en su interior. La propuesta se formalizó hacia 2013 bajo el nombre de LogootSplit y reduce drásticamente el número de identificadores en el caso normal, que es precisamente el de escribir tramos seguidos. No cambia el comportamiento asintótico de los caminos, pero cambia el número de caminos, y en la práctica esa es la mitad de la batalla. La idea de agrupar en tramos volverá en la última lección, porque es la que salvó también a la familia rival.

Lo que LSEQ arregla y lo que no

LSEQ, presentado por Nédelec, Molli, Mostéfaoui y Desmontils en 2013, ataca el crecimiento con dos ideas combinadas. La primera es una base que crece al descender: cada nivel dispone de un espacio de dígitos mayor que el anterior, de modo que la profundidad se paga con anchura y cada nivel nuevo tarda mucho más que el previo en agotarse. La segunda es alternar la dirección de la asignación: para cada nivel se decide, de forma aleatoria pero estable, si el dígito se elige cerca del extremo izquierdo o cerca del derecho. Así ningún patrón de escritura queda sistemáticamente castigado, porque el patrón que agota rápido un nivel se encuentra en el siguiente con una política que le es favorable. Con esa combinación, los autores mostraron un crecimiento del identificador muy por debajo del lineal bajo los patrones de edición que midieron.

// Las dos piezas de LSEQ: base que crece al descender y direccion estable por nivel
const politicaDeNivel = new Map();   // se decide una vez por nivel y no cambia jamas

function baseDelNivel(nivel) {
  return 2 ** (nivelBase + nivel);   // el espacio disponible se duplica al bajar
}

function elegirDigito(a, b, nivel) {
  if (!politicaDeNivel.has(nivel)) politicaDeNivel.set(nivel, Math.random() < 0.5);
  const desdeIzquierda = politicaDeNivel.get(nivel);
  const hueco = Math.min(b - a - 1, ventana);
  return desdeIzquierda
    ? a + 1 + Math.floor(Math.random() * hueco)   // cerca del vecino izquierdo
    : b - 1 - Math.floor(Math.random() * hueco);  // cerca del vecino derecho
}

La decisión de política tiene que ser estable por nivel y no por inserción, porque si cambiase de una llamada a otra dos réplicas podrían generar identificadores incoherentes con lo que la otra espera; que se derive de una fuente pseudoaleatoria sembrada de forma idéntica en todas las réplicas, o simplemente del número de nivel, es un detalle de implementación que cada variante resuelve a su manera. Lo esencial del esquema es que la profundidad deja de ser un castigo puro: cada nivel nuevo trae más espacio que el anterior y llega con una dirección de asignación que, con probabilidad un medio, favorece precisamente al patrón que agotó el nivel de arriba.

Hay un tercer efecto de LSEQ que sus autores no destacan y que en la práctica pesa tanto como los otros dos: al repartir la presión entre niveles con políticas distintas, el esquema desacopla la longitud del identificador del comportamiento de una sola réplica. En Logoot con frontera fija, una única sesión de escritura monótona degrada el espacio de nombres para todos los que vengan después a esa zona del documento; con la alternancia, esa degradación se reparte y ningún autor puede envenenar un punto por sí solo. Es un cambio de la propiedad que se garantiza, de una cota sobre el caso medio a una cierta robustez frente al caso adversario, y en sistemas abiertos donde no controlas quién escribe esa diferencia importa más que cualquier constante.