El compromiso que define la familia: dígitos que crecen o árboles que engordan

El nivel se cierra con la pieza que convierte cinco lecciones en un mapa. Sabemos que la posición debe representarse, que el identificador debe ser inmutable y denso, y que la densidad ilimitada obliga a que crezca algo sin cota. Falta la pregunta que ninguna de las lecciones anteriores ha contestado: qué crece exactamente. Y resulta que solo hay dos respuestas posibles, cada una con su factura y su patología. Se puede dejar que crezcan los propios identificadores, alargándolos un nivel cada vez que el hueco aprieta, o se puede fijar el identificador y dejar que crezca la estructura que lo interpreta, acumulando nodos y metadatos alrededor de un texto que quizá ya no existe. Todos los algoritmos que verás en el nivel siguiente son un punto concreto de ese eje, y quien entienda el eje encontrará el catálogo casi obvio.

Los dos polos

El primer polo es el de los identificadores densos explícitos. Cada elemento lleva una secuencia de dígitos que codifica su posición absoluta dentro de un orden lexicográfico, y esa secuencia se alarga cuando el hueco donde hay que insertar ya no admite un dígito más. La estructura que lo sostiene es un simple conjunto ordenado por comparación: no guarda relaciones entre elementos porque toda la información de orden está dentro de cada identificador. Logoot y Treedoc son los representantes históricos de este polo.

El segundo es el de los identificadores relativos con estructura. Cada elemento se identifica por un par de réplica y contador, que es corto y de tamaño fijo, y su posición se expresa diciendo junto a qué otro elemento se insertó. El orden ya no vive en el identificador sino en el grafo de relaciones entre elementos, de modo que la estructura tiene que conservar todos los nodos que alguna vez sirvieron de referencia, incluidos los borrados. RGA y la familia de WOOT viven aquí, y Yjs es su descendiente más usado.

flowchart LR
P[la densidad exige que algo crezca sin cota] --> A[polo de identificadores densos]
P --> B[polo de identificadores relativos]
A --> A1[el orden vive dentro del identificador]
A1 --> A2[crece la longitud de cada identificador]
B --> B1[el orden vive en las relaciones entre nodos]
B1 --> B2[crece el numero de nodos y lapidas conservados]
style A2 fill:#f9e2af,color:#11111b
style B2 fill:#89b4fa,color:#11111b

Antes de comparar conviene fijar en qué son idénticos, porque lo son en casi todo. Los dos polos satisfacen las cuatro exigencias de la lección tercera, los dos convergen por unión, los dos usan el nombre de la réplica para desempatar y los dos dejan rastro de lo borrado. La diferencia no está en la teoría sino en dónde se deposita la información de orden, y esa única decisión de colocación determina después todo el perfil de coste del algoritmo: cuánto ocupa en disco, cuánta memoria pide al abrir, qué operaciones son baratas y qué carga de trabajo lo degrada.

Hay una asimetría que merece señalarse porque no es evidente y explica bastantes decisiones de las librerías reales. En el polo denso, la información de orden es local a cada elemento: puedes coger un elemento suelto, compararlo con otro suelto y saber cuál va antes sin tener el resto del documento cargado. En el polo relativo eso es imposible, porque el orden entre dos elementos cualesquiera solo se conoce recorriendo la cadena de anclas que los conecta, y esa cadena puede pasar por elementos borrados hace años. Esa diferencia es la que decide si puedes cargar un documento parcialmente, si puedes indexarlo en una base de datos externa y si puedes sincronizar solo un fragmento.

Cómo se paga en cada polo

Vale la pena ver los dos crecimientos como funciones de magnitudes distintas, porque de ahí sale todo lo demás. El coste del polo denso depende de cómo se ha escrito: es una función de la profundidad de subdivisión, que a su vez depende de cuántas veces se ha insertado en el mismo punto. El coste del polo relativo depende de cuánto se ha escrito: es una función del número total de operaciones vividas, mires donde mires del documento. Dos documentos del mismo tamaño final pueden tener costes opuestos según cuál de las dos magnitudes sea grande en cada uno.

// Dos funciones de coste sobre magnitudes distintas
const costeDenso    = (profundidadMedia, elementos) => profundidadMedia * elementos;
const costeRelativo = (operacionesTotales) => operacionesTotales;

// Texto escrito de un tiron y apenas editado
costeDenso(2, 50000);        // 100000 unidades: la profundidad se mantiene baja
costeRelativo(52000);        // 52000 unidades: casi no hay historia

// Texto editado durante dos anos en los mismos parrafos
costeDenso(9, 50000);        // 450000 unidades: la subdivision se acumula
costeRelativo(1_800_000);    // 1800000 unidades: la historia domina

La patología del primer polo tiene nombre: el identificador puede acabar pesando más que el contenido que localiza. En un documento de texto con muchas ediciones concentradas, no es raro que la posición de un carácter ocupe decenas de bytes, y como esos bytes viajan en cada sincronización y se comparan en cada inserción, el coste no es solo de almacenamiento. Los esquemas de asignación adaptativa —elegir el hueco con un sesgo que dependa de la dirección de escritura y de la profundidad— existen precisamente para que el caso común escape de esa patología, y funcionan bien, pero no cambian el hecho de que el peor caso sigue siendo ilimitado.

La patología del segundo polo es distinta y más insidiosa, porque no depende de cómo escribas sino de cuánto tiempo lleve vivo el documento. Como cada elemento se define por referencia a otro, ninguno puede desaparecer del todo: borrar un carácter deja un nodo con su contenido vaciado pero con su identidad intacta, porque una inserción que llegue desde una réplica dormida puede necesitarlo como ancla. Un documento con años de historia acumula un número de nodos proporcional a todas las pulsaciones que alguna vez recibió, y ese es el motivo de que un editor colaborativo pueda tardar segundos en abrir un archivo cuyo texto visible cabe en una pantalla.

Las dos patologías se distinguen además por cuándo se manifiestan, y eso importa para detectarlas a tiempo. La del polo denso se nota mientras escribes, porque cada inserción produce un identificador un poco más largo y el efecto es continuo y proporcional al trabajo del momento. La del polo relativo se nota al abrir, porque el coste está en reconstruir una estructura que creció durante meses y que no tiene nada que ver con lo que vas a hacer hoy. Un equipo que solo mide latencia de tecleo no verá nunca el segundo problema, y un equipo que solo mide tiempo de arranque no verá nunca el primero.

// Dos maneras de decir lo mismo, con dos perfiles de coste opuestos
const denso = { pos: [12, 200, 7, 141, 88, 3], valor: "a" };
// posicion absoluta: se compara sola, pero la longitud crece al subdividir

const relativo = { id: ["r7", 4213], tras: ["r2", 118], valor: "a" };
// identificador fijo y corto: pero el ancla ["r2", 118] no se puede borrar jamas

El eje como mapa del nivel siguiente

Con el eje en la mano, el catálogo del nivel siguiente deja de ser una lista de nombres que memorizar y pasa a ser una secuencia de decisiones comprensibles. Logoot se sitúa en el extremo denso puro y paga con identificadores largos a cambio de una estructura trivial. Treedoc se mueve un paso hacia el centro representando la posición como el camino dentro de un árbol binario, lo cual es otra forma de identificador denso que además admite reequilibrado, aunque el reequilibrado exija una coordinación que en local-first cuesta cara. LSEQ se queda en el mismo polo pero ataca la constante con asignación adaptativa por nivel, alternando la estrategia de reparto según la profundidad.

RGA cruza al otro polo y expresa cada inserción como detrás de este elemento, con esta marca lógica, resolviendo los empates concurrentes con el reloj de Lamport. Su identificador es diminuto y su preservación de la intención es superior, y su precio es la conservación indefinida de nodos. Yjs es un RGA con una ingeniería considerable encima —fusión de series de caracteres consecutivos en bloques, borrado de contenido conservando la identidad, formatos binarios compactos— y esa ingeniería es la que le permite dominar el mercado sin haber cambiado de polo.

Automerge merece mención aparte porque ilustra que el eje no agota las decisiones. Vive también en el polo relativo, pero añade un compromiso propio: conservar la historia completa de operaciones para poder ofrecer viaje en el tiempo y atribución de cambios, lo cual es una funcionalidad de producto y no una necesidad del algoritmo. Su formato de almacenamiento por columnas existe para que esa historia completa quepa en un tamaño razonable, y es un buen ejemplo de cómo una decisión de producto puede recolocar por completo el perfil de coste de una implementación sin cambiar el algoritmo de secuencia que lleva dentro.

Y luego están los intentos de salirse del eje, que son la parte viva del campo. Fugue mantiene el enfoque relativo y redefine el criterio de colocación para garantizar la no intercalación maximal, mejorando la preservación de la intención sin cambiar el perfil de coste. Eg-walker hace algo más radical: guarda las operaciones originales al estilo de la transformación operacional y reconstruye los identificadores solo cuando hace falta, lo que traslada el gasto de espacio permanente a tiempo de cómputo puntual. Ninguno de los dos deroga el resultado de la lección anterior; ambos cambian la moneda en que se paga.

Falta mencionar una técnica transversal que se aplica en los dos polos y que en la práctica desplaza los números más que la elección de polo: la agrupación en bloques. En vez de un identificador por carácter, se guarda uno por tramo de caracteres consecutivos insertados por la misma réplica de forma contigua, y el tramo se parte solo cuando alguien inserta o borra en su interior. Como escribir palabras seguidas es abrumadoramente el caso común, la reducción es enorme y hace viables documentos que sin ella no lo serían. Conviene tenerla presente al leer comparativas, porque dos implementaciones del mismo algoritmo con y sin agrupación difieren en un orden de magnitud, y esa diferencia se atribuye a veces al algoritmo cuando es de la ingeniería.

Cómo usar el eje para decidir

El eje solo vale si se convierte en una decisión, y la conversión pasa por medir dos magnitudes de tu propia aplicación en lugar de razonar en abstracto. La primera es la forma de las inserciones: qué proporción cae al final de la lista, cuál en medio y cuál al principio. La segunda es la razón entre operaciones acumuladas y contenido vivo a lo largo de la vida de un documento típico, que es lo que predice el tamaño de la metadata en el polo relativo.

// Dos metricas que colocan tu aplicacion en el eje mejor que cualquier intuicion
function perfil(operaciones, longitudFinal) {
  const alFinal = operaciones.filter((op) => op.tipo === "ins" && op.alFinal).length;
  const inserciones = operaciones.filter((op) => op.tipo === "ins").length;

  return {
    proporcionAlFinal: alFinal / inserciones,      // alto favorece al polo denso
    operacionesPorCaracter: operaciones.length / longitudFinal, // alto castiga al relativo
  };
}

La lectura de esas dos cifras es directa. Una proporción alta de inserciones al final significa que el polo denso apenas alargará identificadores, porque la asignación adaptativa está diseñada justo para ese caso. Un número alto de operaciones por carácter vivo significa que el documento se ha editado mucho más de lo que mide su longitud, y ahí el polo relativo acumula anclas que ya no sostienen nada visible. Cuando ambas cifras son altas a la vez, el candidato natural es el enfoque que guarda operaciones y reconstruye, porque es el único que no paga permanentemente por ninguna de las dos.

Hay una tercera pregunta que no es de coste sino de forma del producto y que a veces decide antes que las cifras: si necesitas el historial. Si tu aplicación quiere mostrar quién escribió qué, volver a un estado anterior o auditar cambios, entonces conservar operaciones deja de ser un coste y pasa a ser un requisito, y la comparación cambia por completo porque una de las facturas ya la ibas a pagar de todos modos. Conviene hacerse esa pregunta antes que las otras dos, porque su respuesta puede eliminar la mitad de los candidatos sin necesidad de medir nada.

Y queda una advertencia sobre el orden de las decisiones. Elegir el algoritmo de secuencia es, en casi todos los proyectos, una consecuencia de haber elegido la librería, y elegir la librería depende de cosas que este nivel no trata: qué editor de texto enriquecido soporta, qué transportes trae, qué madurez tiene su ecosistema, si hay implementación en el lenguaje de tu servidor. Lo que este nivel te da no es el criterio principal de esa elección sino el criterio para entender la factura que vendrá después, y para saber qué medir cuando algo vaya mal.