El cuadro comparativo: qué eligió cada biblioteca y por qué

Puestos los cuatro algoritmos uno junto a otro, la tentación es buscar un ganador y anotarlo. La tabla que sigue lo da, y de hecho la industria lo dio hace años con una unanimidad poco frecuente, pero el valor de este ejercicio no está en el veredicto sino en entender qué columna lo produjo. Los tres primeros ejes —tamaño del nombre, coste de insertar, coste de recorrer— son los que aparecen en todos los artículos y los que se miden en los bancos de pruebas, y son también los que menos decidieron: en los tres hay empates, compensaciones y regímenes donde cada familia gana. El cuarto eje, los metadatos que quedan cuando el usuario ya ha terminado, es el que no admite compensación, porque es el único cuyo coste no se paga una vez sino todos los días durante toda la vida del documento. Esta lección monta el cuadro completo, lo lee columna a columna y después mira lo que efectivamente escogieron Yjs, Automerge y sus contemporáneas, que es la única evidencia empírica disponible sobre qué importa de verdad.

Los cuatro ejes y sus trampas

El tamaño del identificador admite una lectura engañosa. WOOT y RGA lo tienen de tamaño fijo —una réplica y un contador—, y Logoot, LSEQ y Treedoc lo tienen variable, pero la comparación honesta no es por elemento sino por documento, y ahí entra el agrupamiento en tramos: si una tanda de cien caracteres seguidos comparte un solo identificador con una longitud, el coste efectivo por carácter se desploma. Ese truco funciona en las dos familias, pero funciona mucho mejor donde los identificadores de una tanda son consecutivos y predecibles.

El coste de inserción hay que descomponerlo en dos partes que suelen mezclarse. Una es localizar el punto de anclaje a partir de lo que la operación cita, y es donde las familias se diferencian de verdad. La otra es traducir la posición visible que da la interfaz a un elemento concreto de la estructura, y esa parte es la misma para todo el mundo: exige un índice local con tamaños de subárbol y cuesta del orden del logaritmo del documento, gane quien gane el resto de la comparación.

Conviene además separar el coste de una inserción local, la que produce el usuario al teclear, del coste de una inserción remota, la que llega por la red. La local es siempre barata porque ya sabes dónde estás: tienes el cursor, tienes el nodo y no hay nada que buscar. La remota es la que hay que medir, y es la que sufre cuando el documento es grande, cuando hay muchas operaciones concurrentes acumuladas o cuando una réplica vuelve tras días desconectada y descarga miles de operaciones de golpe. Casi todas las comparaciones publicadas miden lo segundo, y casi todas las quejas de los usuarios vienen de lo segundo, pero muchas evaluaciones caseras miden lo primero y concluyen que todo va bien.

El coste de recorrido parece trivial y esconde el efecto más importante del cuadro. Recorrer es lineal en todas las familias, pero lineal en qué: en Logoot es lineal en los caracteres vivos, mientras que en WOOT y RGA es lineal en los caracteres que han existido alguna vez. En un documento con una historia larga de ediciones, esa diferencia puede ser de un orden de magnitud, y es la principal razón por la que las implementaciones de la familia RGA acaban manteniendo un índice que salta los tramos borrados de una vez.

Los metadatos residuales son lo que queda cuando nadie está escribiendo, y la pregunta útil no es cuánto ocupan sino si se pueden reducir sin coordinación. Las lápidas de RGA son un conjunto de rangos de sellos consecutivos y se comprimen a casi nada; los identificadores largos de Logoot son información incompresible; y el desequilibrio de Treedoc no es que ocupe mucho, es que solo se repara con un acuerdo global.

// La medida que ordena el campo, y que casi nadie hace: metadatos antes y despues de comprimir
async function perfil(estructura, texto) {
  const crudo = serializar(estructura);
  const comprimido = await comprimir(crudo);       // compresion de proposito general
  return {
    porCaracterCrudo: crudo.byteLength / texto.length,
    porCaracterComprimido: comprimido.byteLength / texto.length,
    factor: crudo.byteLength / comprimido.byteLength   // aqui esta el veredicto
  };
}

El campo factor es el número que resume estas cinco lecciones. Una estructura cuyos metadatos son redundantes tiene un factor alto, y eso significa que su coste nominal es una ilusión contable: desaparece al escribir en disco y al mandar por la red, que son las dos operaciones que de verdad ocurren. Una estructura cuyos metadatos son entropía tiene un factor cercano a uno, y entonces el coste que mediste en memoria es el coste que vas a pagar en todas partes y para siempre. Dos implementaciones pueden empatar en la primera línea del resultado y diferir en un orden de magnitud en la segunda, y es la segunda la que decide si tu documento de un millón de caracteres cabe en el presupuesto.

El cuadro

Hay una fila que no está en el cuadro porque no admite una casilla y sin embargo condiciona todas las demás: quién paga el coste y cuándo. En las familias de identificador fijo, el precio se paga en espacio, se acumula de forma predecible y se puede diferir con compresión y poda, es decir, se parece a una deuda con intereses bajos. En las familias posicionales, el precio se paga en el tamaño de cada operación que se emite, de modo que llega antes, se paga en la red y no se puede aplazar. Y en Treedoc hay además un pago extraordinario e impredecible, el reequilibrado, que exige que todo el sistema esté disponible a la vez. Tres perfiles de coste muy distintos que el análisis asintótico presenta como si fueran comparables.

Léelo por filas y verás compensaciones; léelo por la última fila y verás el veredicto. Las tres primeras familias empatan en lo asintótico dentro de un factor pequeño, y las diferencias entre ellas se mueven según el patrón de escritura que uses para medir. Pero solo una tiene un formato que se deja comprimir en la dirección en que la escritura humana genera redundancia, y esa es la que ganó.

Qué eligió cada biblioteca

flowchart TD
W[WOOT en 2006 identidad por caracter] --> L[Logoot en 2009 camino de digitos]
W --> T[Treedoc en 2009 camino de bits]
W --> R[RGA en 2011 enganche al predecesor]
L --> LS[LSEQ en 2013 base creciente]
R --> Y[YATA hacia 2016 base de Yjs]
R --> A[Automerge listas y texto]
R --> F[Fugue hacia 2023 sin entrelazado]
F --> C[bibliotecas recientes de listas]
style R fill:#a6e3a1,color:#11111b
style T fill:#f38ba8,color:#11111b
style LS fill:#f9e2af,color:#11111b

Antes de repasar las bibliotecas conviene fijar una advertencia sobre el diagrama que sigue. Las flechas indican influencia conceptual, no derivación directa de código, y las fechas son las de la primera publicación de la idea, no las de su adopción: entre que un algoritmo aparece en un artículo y que alguien lo lleva a una biblioteca que aguanta un documento grande suelen pasar varios años, y en esos años casi todo el trabajo es de representación. Léelo como un mapa de qué respuesta dio cada grupo a la pregunta de cómo nombrar una posición, y observa que después de 2011 todas las ramas vivas salen del mismo tronco.

Yjs implementa YATA, la variante presentada hacia 2016 que engancha cada elemento por ambos lados y resuelve los empates con una regla propia; operativamente es la misma familia que RGA. Su aportación decisiva no está en el algoritmo sino en la representación: los caracteres escritos seguidos por una réplica se guardan como un único bloque con longitud, los borrados se registran como conjuntos de rangos y la estructura admite recolección de lo que ya nadie puede citar. Es el ejemplo más claro de que la victoria se jugó en el formato.

Automerge partió de RGA para sus listas y su texto, y dedicó su reescritura posterior a un formato binario por columnas donde cada campo de los sellos se codifica por separado y se comprime con la técnica que le conviene. Es exactamente la maniobra que la lección 3 describía como imposible en las familias posicionales: cambiar la representación de arriba abajo sin tocar el modelo replicado ni la corrección.

Las propuestas más recientes se mueven dentro de la misma rama. Fugue, hacia 2023, es una variante con garantías más fuertes contra el entrelazado de tramos concurrentes, y sobre ella se apoyan varias bibliotecas de listas de los últimos años. Otra línea, la de los recorridos sobre el grafo de eventos, guarda la historia de operaciones y reconstruye el estado al vuelo en lugar de mantener metadatos persistentes por elemento, lo que ataca el cuarto eje desde un ángulo distinto sin abandonar el modelo del enganche al predecesor.

Merece la pena señalar qué añadieron todas ellas por encima del algoritmo, porque es donde está el trabajo de la última década y no aparece en ningún artículo fundacional. Las cuatro piezas se repiten con nombres distintos: el agrupamiento en tramos para que una tanda de escritura sea un objeto y no cien; el formato binario compacto, casi siempre orientado a columnas, que codifica por separado cada componente del sello y aprovecha que unos avanzan de uno en uno y otros se repiten; el índice local con tamaños de subárbol para traducir posiciones en tiempo logarítmico sin tocar el modelo replicado; y algún mecanismo de poda de lo que ya nadie puede citar, que es la única forma de que las lápidas no crezcan indefinidamente. Ninguna de las cuatro es parte del CRDT; las cuatro son imprescindibles para que el CRDT sea usable.

Del otro lado, la evidencia es igual de nítida por ausencia. Ninguna biblioteca de uso general de la última década partió de Logoot, de LSEQ o de Treedoc. Se usaron en editores de investigación y demostraron sus propiedades, pero cuando llegó el momento de sostener un documento grande durante meses, el coste incompresible del nombre y la necesidad de reequilibrar los dejaron fuera.

Esa unanimidad es un dato inusual en ingeniería y merece interpretarse con cuidado, porque puede leerse de dos maneras. La lectura perezosa dice que la comunidad convergió por imitación y por disponibilidad de código, que es un fenómeno real y que sin duda influyó. La lectura que sostienen las mediciones dice otra cosa: los grupos que eligieron la rama de RGA lo hicieron en momentos distintos, con lenguajes distintos y con objetivos distintos, y varios de ellos publicaron comparaciones propias antes de decidir. Cuando equipos independientes llegan al mismo sitio por caminos separados, lo prudente es asumir que hay una razón estructural, y en esta lección ya está identificada: es la cuarta columna.

El criterio para tu caso

La última tarjeta merece una lectura desapasionada, porque el índice fraccionario sigue siendo la elección correcta en muchos productos y esta lección no pretende desaconsejarlo. Ordenar treinta tareas en un tablero no es ordenar un millón de caracteres en un documento: el número de inserciones en un mismo punto es pequeño, el crecimiento del nombre nunca llega a doler y, si algún día duele, hay un servidor que puede renumerar en una transacción y nadie se entera. Aplicar una secuencia convergente completa a ese problema es cargar con lápidas, sellos y un índice auxiliar para resolver algo que una clave ordenada resuelve en veinte líneas.

El criterio que separa ambos mundos tiene tres preguntas y ninguna es sobre rendimiento. ¿Puede el número de inserciones entre dos elementos fijos crecer sin límite, como ocurre al escribir texto, o está acotado por el uso, como ocurre al reordenar una lista? ¿Existe algún momento en que un componente con autoridad pueda renumerar sin romper a nadie, o el sistema debe funcionar con réplicas desconectadas durante días? ¿Importa que dos ediciones concurrentes del mismo punto queden agrupadas en bloques, o basta con que el resultado sea determinista? Tres síes de la segunda columna llevan al índice fraccionario y tres de la primera llevan a la rama de RGA, y casi nunca hay dudas.

El caso genuinamente incómodo es el intermedio, y conviene reconocerlo antes de tropezar con él: listas largas de elementos estructurados que además se reordenan, como los bloques de un documento por secciones o las filas de una hoja de cálculo. Ahí el número de inserciones en un punto puede crecer bastante, no hay servidor que arbitre y, sobre todo, aparece una operación que ninguno de los cuatro algoritmos de este nivel sabe hacer: mover un elemento sin borrarlo y recrearlo. Un movimiento expresado como borrado más inserción se duplica cuando dos réplicas mueven el mismo elemento a sitios distintos, y ese es un problema propio que exige estructuras específicas y que el track aborda más adelante.

Queda un consejo final que no se deduce de la tabla y sí de la historia que la tabla resume. Estos cinco algoritmos tardaron quince años en converger a una respuesta, y el trabajo que separa una descripción correcta de una implementación que aguanta un documento real es mucho mayor que el que separa dos algoritmos entre sí. Implementa uno para entenderlo, y hazlo con la traza de tu dominio delante; después usa una biblioteca que alguien mantenga. Lo que has aprendido en estas cinco lecciones no sirve para escribir tu propio motor de secuencias, sirve para leer el que elijas, entender qué te está costando y saber, cuando algo vaya mal, en qué columna del cuadro está el problema.