RGA: la lista como árbol de inserciones

Entre nombrar a los dos vecinos, como hacía WOOT, y no nombrar a ninguno, como hacen Logoot y LSEQ, queda una tercera vía que resulta ser la buena: nombrar solo al de la izquierda. Un elemento se define por su valor y por la identidad de aquel tras el cual se insertó, y nada más. Esa asimetría deliberada convierte el documento en un bosque de inserciones colgando de una raíz virtual, donde cada elemento es hijo de su predecesor y el texto se obtiene recorriendo el árbol en profundidad. RGA —Replicated Growable Array, formalizado por Roh, Jeon, Kim y Lee en un trabajo de 2011 sobre tipos de datos abstractos replicados— añade a esa estructura una regla de desempate entre hermanos concurrentes que cabe en una línea y que basta para que todas las réplicas produzcan la misma secuencia. El resultado tiene identificadores de tamaño fijo, integración esencialmente constante y una linealización que es un simple paseo, y esa combinación explica por qué es el punto de partida de prácticamente todo lo que hoy se usa en producción.

Cada elemento cuelga de su predecesor

La operación de inserción de RGA no dice ponme en la posición tres ni ponme entre X e Y, sino simplemente ponme justo después de X. El elemento resultante guarda tres cosas: su propio sello, la identidad del predecesor al que se enganchó y su valor. El sello es un identificador con orden total —en la práctica un contador lógico de tipo Lamport acompañado del identificador de réplica como desempate— y su tamaño es constante, no depende de cuánto se haya escrito antes ni de dónde.

// Un nodo de RGA: sello propio, enganche al predecesor y valor
const nodo = {
  sello: { contador: 87, replica: "r3" },   // orden total, tamano fijo
  padre: { contador: 42, replica: "r1" },   // identidad del elemento anterior
  valor: "a",
  borrado: false
};

Cuando varias réplicas insertan concurrentemente justo después del mismo elemento, todos esos nodos declaran el mismo padre y se convierten en hermanos. El documento deja así de ser una lista y pasa a ser un árbol: la raíz es un centinela que existe en todas las réplicas desde el arranque, los hijos de un nodo son las inserciones que lo eligieron como predecesor, y la secuencia visible es el recorrido en profundidad y por orden, visitando cada nodo y a continuación sus hijos.

flowchart TD
R[raiz virtual] --> A[a con sello 10 de r1]
A --> B[b con sello 25 de r2]
A --> C[c con sello 18 de r3]
B --> D[d con sello 31 de r2]
C --> E[e con sello 22 de r1]
style B fill:#a6e3a1,color:#11111b
style C fill:#f9e2af,color:#11111b

En el diagrama, b y c son hermanos porque ambos se insertaron justo después de a. El recorrido produce primero a, después la rama de b completa y después la rama de c, es decir la cadena a b d c e. Si el orden entre hermanos fuera el contrario, la secuencia sería a c e b d. Ninguna de las dos es más correcta que la otra desde el punto de vista del usuario; lo único que importa es que todas las réplicas elijan la misma, y de eso se ocupa la regla de la sección siguiente.

La regla: entre hermanos, gana el sello mayor

El orden entre hermanos es descendente por sello: el hermano con el sello más grande se visita primero. Enunciada así suena arbitraria, y su justificación es sutil. Consideremos una réplica que ya tiene un hijo colgando de a y recibe una inserción nueva que también declara a a como padre. Si el sello del recién llegado es menor que el del hijo existente, significa que quien lo emitió no había visto ese hijo o lo vio y aun así fue posterior en el orden lógico; en cualquier caso, colocarlo detrás preserva la intención de quien escribió después. La implementación es un desplazamiento a la derecha mientras se encuentren sellos mayores.

// Integracion: desde el padre, avanzar mientras el sello del vecino sea mayor
function integrar(lista, nodo) {
  let i = indiceDe(lista, nodo.padre) + 1;      // busqueda directa por tabla asociativa
  while (i < lista.length && esDescendienteDe(lista[i], nodo.padre)
         && mayor(lista[i].sello, nodo.sello)) {
    i += 1;                                      // saltar hermanos con sello mayor y su subarbol
  }
  lista.splice(i, 0, nodo);
  return lista;
}

function mayor(a, b) {
  return a.contador !== b.contador ? a.contador > b.contador : a.replica > b.replica;
}

Dos observaciones sobre este fragmento, que es la pieza central de todo el nivel. La primera es que el salto no es hermano a hermano sino subárbol a subárbol: al descartar un hermano con sello mayor hay que saltar también a todos sus descendientes, porque van pegados a él en la linealización. La segunda es que la operación es conmutativa en el sentido que hace falta: el resultado depende del conjunto de nodos presentes y de sus sellos, nunca del orden en que llegaron, y por eso dos réplicas con el mismo conjunto de operaciones producen literalmente el mismo recorrido.

Las lápidas y el índice: dónde está el coste

En RGA borrar no puede borrar. La razón es la misma que en WOOT y ahora se ve mejor: si un nodo desaparece, cualquier inserción concurrente que lo declarase como padre se queda huérfana y la réplica no sabe dónde colocarla. El nodo borrado se marca y se queda, invisible para el usuario y presente para el algoritmo. Ese es el residuo permanente de la familia, y su tamaño es proporcional a todo lo que se escribió y se borró en la vida del documento.

La cuarta tarjeta señala el coste que suele olvidarse en las descripciones teóricas. El algoritmo trabaja con identidades, pero la interfaz de usuario trabaja con posiciones: cuando alguien teclea en la columna cuatro mil, la aplicación necesita traducir ese número a un nodo concreto. Recorrer la lista para encontrarlo es lineal, y como hay que hacerlo en cada pulsación, en documentos grandes se nota. Las implementaciones serias mantienen por eso una estructura auxiliar —un árbol equilibrado o una lista con saltos que guarda en cada nodo el número de elementos visibles bajo él— que hace logarítmica esa traducción. Esa estructura no forma parte del modelo de datos replicado: es índice local, se reconstruye y no se transmite, y confundirla con el estado del CRDT es una fuente habitual de malentendidos.

// El nodo real de una implementacion seria: un tramo, no un caracter
const tramo = {
  sello: { contador: 87, replica: "r3" },   // sello del primer elemento del tramo
  longitud: 14,                              // los siguientes son 88, 89, 90 ...
  padre: { contador: 42, replica: "r1" },
  valor: "hola que tal am",
  borrados: [[3, 5]]                         // rangos relativos, no marcas por elemento
};

// Insertar dentro de un tramo lo parte en dos y engancha el nuevo al primero
function partir(tramo, desplazamiento) {
  const cola = {
    sello: { contador: tramo.sello.contador + desplazamiento, replica: tramo.sello.replica },
    longitud: tramo.longitud - desplazamiento,
    padre: { contador: tramo.sello.contador + desplazamiento - 1, replica: tramo.sello.replica },
    valor: tramo.valor.slice(desplazamiento)
  };
  tramo.longitud = desplazamiento;
  tramo.valor = tramo.valor.slice(0, desplazamiento);
  return [tramo, cola];
}

Este fragmento es el que separa las descripciones de artículo de las implementaciones que aguantan un documento real, y merece leerse con atención porque contiene tres decisiones. La primera es que el sello de un elemento interior del tramo no se guarda: se calcula sumando su desplazamiento al sello inicial, lo que reduce la memoria por carácter a prácticamente el carácter. La segunda es que el enganche al padre tampoco se guarda para los interiores, porque por construcción cada uno cuelga del anterior. Y la tercera es que los borrados se representan como rangos dentro del tramo en vez de como una marca por elemento, que es exactamente el punto donde 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 es varios órdenes de magnitud menor.

Por qué es la base de casi todo lo que se usa

Cuatro propiedades explican el dominio de esta familia. El identificador es de tamaño constante, así que ningún patrón de escritura lo degrada. La integración es esencialmente local: se localiza el padre por tabla asociativa y se avanza sobre un puñado de hermanos concurrentes, que en una sesión real son muy pocos. La linealización es un recorrido, no una ordenación, de modo que leer el documento cuesta lo que cuesta leerlo. Y la estructura resultante se comprime bien, porque la escritura humana produce tandas contiguas de la misma réplica y las lápidas se acumulan en rangos.

Hay una quinta propiedad, menos citada y decisiva para quien vaya a mantener el código: la estructura es incrementalmente verificable. Como el orden depende solo del conjunto de nodos y de la regla de desempate, dos réplicas pueden comprobar que coinciden comparando resúmenes de sus conjuntos de sellos, sin recorrer el documento ni acordar nada previamente; y si difieren, la diferencia se localiza en los sellos que a una le faltan, que es precisamente lo que hace falta pedir. En las familias posicionales esa comprobación es mucho más incómoda, porque un mismo contenido puede estar representado por identificadores generados de formas distintas y comparar conjuntos de nombres no dice directamente qué operaciones faltan.

El linaje es fácil de trazar. Yjs, la biblioteca de Kevin Jahns, implementa YATA, una variante presentada hacia 2016 que engancha cada elemento por su izquierda y por su derecha y resuelve los empates con una regla propia, muy cercana en espíritu a RGA y con las mismas propiedades operativas. Automerge, en el linaje de Martin Kleppmann, partió de RGA para sus listas y su texto y dedicó su reescritura posterior a la representación compacta más que al algoritmo. Las propuestas más recientes sobre entrelazado, alrededor de 2023, son también variantes de este mismo esqueleto con reglas de desempate más finas. Ninguna biblioteca de uso general de la última década partió de Logoot ni de Treedoc, y esa unanimidad no es moda: es el reconocimiento de que un nombre corto que puede repetirse en tandas vence a un nombre autosuficiente que no puede compartirse con nadie.