Dónde duele: lápidas, metadatos y lo que hacen las bibliotecas

El RGA de las cuatro lecciones anteriores converge, y eso ya es más de lo que consigue la mayoría de los primeros intentos. Lo que no hace es aguantar. Tiene tres puntos que se degradan de forma predecible y que aparecerán en cuanto alguien escriba durante meses en el mismo documento: el recorrido de una lista donde casi todo son lápidas, la multiplicación de identificadores hasta que los metadatos pesan más que el contenido, y la traducción entre posiciones de la interfaz y sellos de la estructura, que ocurre en cada pulsación de teclado y es lineal. Esta lección los mide sobre el código que ya tienes, con números reales de una ejecución concreta, y enseña las dos técnicas con las que las bibliotecas de producción los convierten en un problema resuelto. Ninguna de las dos cambia el algoritmo: ambas cambian la representación, y esa distinción es la conclusión del nivel.

El recorrido: el coste lo fija lo borrado, no lo visible

La medida más reveladora se obtiene manteniendo constante lo que el usuario ve y variando solo lo que el usuario ya no ve. Diez mil caracteres visibles en todos los casos, y cada vez más lápidas alrededor.

nodos=  10000 visibles=10000 lapidas=  0.0%  texto()=0.057ms  anclaEn(5000)=0.010ms
nodos= 100000 visibles=10000 lapidas= 90.0%  texto()=0.152ms  anclaEn(5000)=0.040ms
nodos= 500000 visibles=10000 lapidas= 98.0%  texto()=0.817ms  anclaEn(5000)=0.269ms
nodos=1000000 visibles=10000 lapidas= 99.0%  texto()=1.201ms  anclaEn(5000)=0.498ms

El documento que se ve en pantalla es exactamente el mismo en las cuatro filas. Lo único que cambia es cuánto se escribió y se borró antes, y anclaEn pasa de diez microsegundos a casi medio milisegundo: cincuenta veces más lento para mostrar lo mismo. Y anclaEn no se llama una vez al abrir el documento, se llama en cada pulsación de teclado. Medio milisegundo por tecla suena a poco hasta que se recuerda que hay que compartir el hilo con el renderizado, con el resaltado de sintaxis y con la serialización del estado.

Merece la pena insistir en qué se está midiendo, porque la intuición engaña. No es que el documento sea grande: el documento es idéntico en las cuatro filas y cabe en una pantalla larga. Lo que ha crecido es su pasado, y en esta estructura el pasado no es un registro que se pueda consultar aparte, es parte del estado activo que hay que atravesar para responder a cualquier pregunta. Un editor que va lento porque el documento es enorme se entiende y se explica al usuario; uno que va lento porque hace seis meses se escribieron y se borraron cien mil caracteres es incomprensible desde fuera, y esa incomprensión es la que convierte el problema en una queja difícil de diagnosticar.

Hay un segundo coste, más silencioso, en la inserción misma. Nuestro integrar localiza el padre con indexOf sobre el array, que es lineal, y el resultado es que teclear al final se encarece con el tamaño del documento aunque el punto de inserción no se mueva.

--- teclear 1000 caracteres al final de un documento de N nodos ---
N=  1000   1.7 ms  (0.0017 ms por pulsacion)
N= 10000   4.4 ms  (0.0044 ms por pulsacion)
N=100000  19.9 ms  (0.0199 ms por pulsacion)
N=500000  77.8 ms  (0.0778 ms por pulsacion)

Los identificadores no se alargan, pero se multiplican

El nivel 31 dejó claro que el mal de las familias posicionales era el crecimiento del nombre: cada inserción en un hueco lleno alargaba el identificador, y ciertos patrones de escritura lo hacían crecer sin techo. RGA resolvió ese problema de raíz con un sello de tamaño fijo. Lo que no resolvió, y conviene no confundir, es la proliferación: hay un sello por cada carácter que alguna vez existió, y cada uno arrastra además el sello de su padre.

texto plano ............ 20005 bytes
un nodo por caracter ... 20005 objetos, 603479 bytes (30.2x)

Treinta veces el contenido para un documento de veinte mil caracteres escrito por tres réplicas con ediciones dispersas. Y esa cifra es solo la serialización; en memoria, veinte mil objetos de JavaScript con dos objetos anidados cada uno cuestan bastante más que los seiscientos kilobytes del JSON. El contador, además, crece monótonamente con cada edición del sistema entero, así que su representación decimal se va alargando: no es el crecimiento sin techo de Logoot, pero tampoco es constante para siempre.

Las cuatro tarjetas describen lo mismo desde ángulos distintos: la estructura está llena de información predecible. Y la información predecible es, por definición, información comprimible. Ahí está la salida, y no en ninguna modificación del algoritmo.

Antes de seguir conviene desactivar una esperanza recurrente. Casi todo el mundo, al ver estos números, propone lo mismo: recolectar las lápidas cuando ya no hagan falta. La idea es correcta y el problema es saber cuándo es ya no hacen falta. Un nodo solo se puede retirar si ninguna réplica del sistema podrá emitir jamás una operación que lo cite como padre, y establecer eso exige un acuerdo global sobre lo que todo el mundo ha visto: un vector de versiones de todos los participantes, o un corte causal acordado, o un servidor que dictamine. Cualquiera de esas tres opciones reintroduce exactamente la coordinación que la arquitectura entera existe para no necesitar. Por eso la compactación real no se hace cuando conviene sino en momentos excepcionales y negociados —cerrar un documento, archivar una versión, consolidar una instantánea— y no es una optimización que se pueda añadir a este código con un if.

Agrupar caracteres consecutivos en tramos

La técnica es la que anticipó el nivel 32 y ahora se puede medir. Una ráfaga de escritura produce nodos cuyos contadores son consecutivos, cuya réplica es la misma y cada uno de los cuales cuelga del anterior. Toda esa información se deduce del primero: basta con guardar el sello inicial, el padre inicial y la cadena completa.

// Reagrupar un array de nodos en tramos: misma replica, contadores consecutivos,
// y cada nodo colgando del inmediatamente anterior
const tramos = [];
for (const n of nodos) {
  const u = tramos[tramos.length - 1];
  const continua = u
    && u.replica === n.id.replica
    && u.contador + u.valor.length === n.id.contador
    && n.padre.replica === u.replica
    && n.padre.contador === n.id.contador - 1;
  if (continua) u.valor += n.valor;
  else tramos.push({ contador: n.id.contador, replica: n.id.replica, padre: n.padre, valor: n.valor });
}

un nodo por caracter ... 20005 objetos, 603479 bytes (30.2x)
agrupado en tramos ..... 987 objetos, 48067 bytes ( 2.4x)
reduccion de objetos ... 20.3x   longitud media de tramo 20.3

De treinta veces el contenido a dos veces y media, y de veinte mil objetos a novecientos ochenta y siete. Nada de eso cambia el modelo replicado: los sellos individuales siguen existiendo conceptualmente, simplemente se calculan en vez de almacenarse. El sello del carácter que ocupa el desplazamiento siete de un tramo es el contador inicial más siete, con la misma réplica, y su padre es el anterior de ese mismo tramo.

flowchart TD
A[rafaga de veinte caracteres de una replica] --> B[veinte nodos con contadores consecutivos]
B --> C[un tramo con sello inicial mas longitud]
C --> D[insertar en medio parte el tramo en dos]
D --> E[el nuevo cuelga de la mitad izquierda]
C --> F[borrar marca un rango dentro del tramo]
style C fill:#a6e3a1,color:#11111b
style D fill:#f9e2af,color:#11111b
style F fill:#89b4fa,color:#11111b

La longitud media de tramo que sale de esa ejecución, veinte caracteres, no es un número mágico ni depende del algoritmo: es una medida de cómo escribe la gente. Cada tramo se corta cuando cambia el autor o cuando alguien salta a otro punto del documento, de modo que la longitud media es aproximadamente la longitud de una ráfaga ininterrumpida de tecleo. En un documento escrito por una sola persona de principio a fin, los tramos son enormes y la reducción es de varios órdenes de magnitud. En uno con tres autores editando a la vez en sitios dispersos —que es el caso que hemos medido— la reducción sigue siendo de veinte veces. El caso peor sería una alternancia carácter a carácter entre autores, que no ocurre porque nadie escribe así.

El precio del agrupamiento es que insertar en mitad de un tramo obliga a partirlo, y borrar dentro de él obliga a representar los borrados como rangos en vez de como una marca por nodo. Las dos operaciones son aritmética sencilla, y a cambio el coste de las lápidas deja de ser proporcional al número de caracteres borrados y pasa a serlo al número de operaciones de borrado, que en un documento real es varios órdenes de magnitud menor: borrar un párrafo entero de mil caracteres deja un rango, no mil marcas.

Índices auxiliares y lo que hacen las bibliotecas reales

Conviene además notar que el agrupamiento y las lápidas se ayudan mutuamente. Al representar los borrados como rangos dentro del tramo, un párrafo eliminado deja de ser mil nodos marcados y pasa a ser una pareja de números, de modo que el recorrido que producía la tabla de la primera sección atraviesa el hueco de un salto en vez de mil comprobaciones. Es la razón de que las cifras que hemos medido con un nodo por carácter sean el peor caso posible y no una predicción de lo que verás en una biblioteca seria.

Queda el coste que el agrupamiento alivia pero no elimina: traducir una posición visible a un nodo. La solución universal es un índice de orden estadístico: una estructura equilibrada —un árbol de búsqueda, un árbol B o una lista con saltos— donde cada nodo interno guarda cuántos elementos visibles cuelga por debajo. Con eso, encontrar la posición cuarenta y dos mil es descender comparando acumulados, y el coste pasa de lineal a logarítmico.

Lo decisivo de esa estructura es que no forma parte del estado replicado. No se transmite, no participa en la convergencia y se puede reconstruir entera recorriendo el documento al arrancar. Confundirla con el modelo de datos es uno de los malentendidos más frecuentes al leer código de estas bibliotecas: hay dos representaciones del mismo documento conviviendo, una que define la corrección y otra que solo existe para que la interfaz responda.

Puestas juntas, las decisiones que toman las implementaciones serias se ordenan en tres capas bien separadas y conviene tenerlas presentes al leer su código, porque casi nunca están documentadas como tales. En la capa de disco y red se usa codificación columnar: los contadores de todos los nodos van juntos y se guardan como diferencias respecto del anterior, los identificadores de réplica se sustituyen por índices en una tabla, y las repeticiones se codifican por longitud de tirada. Es el formato al que apuntó la reescritura de Automerge, y funciona porque un documento con muchas ráfagas de un mismo autor produce columnas casi constantes. En la capa de memoria se usan tramos con partido bajo demanda, que es lo que hace Yjs con sus elementos y su tabla de estructuras por cliente. Y en la capa de acceso, la que sirve al cursor, se usan índices de orden estadístico o marcadores de búsqueda según lo exigente que sea el caso de uso.

La consecuencia práctica de esa separación es que cada capa se puede cambiar sola. Puedes adoptar la codificación columnar sin tocar la memoria, añadir un índice sin tocar el formato de disco, o pasar de marcadores a árbol equilibrado cuando midas que hace falta. Y la prueba de convergencia de la lección anterior sigue siendo válida después de cada uno de esos cambios, porque ninguno de ellos altera qué nodos existen ni cómo se ordenan: ese es el mejor argumento posible para tenerla escrita antes de empezar a optimizar.