CRDTs: convergencia sin coordinación

Hay una asimetría instructiva entre las dos grandes familias de la colaboración. La transformación operacional acepta que las operaciones hablan en coordenadas relativas y monta toda su maquinaria para traducirlas, lo que la obliga a conocer la historia completa de lo que ocurrió mientras el mensaje viajaba. Los CRDT hacen la pregunta anterior: por qué usamos coordenadas relativas. Un carácter no tiene por qué ser el quinto de la línea; puede ser simplemente él mismo, con un identificador único que le asignó su autor en el momento de escribirlo y que no cambiará jamás, ni cuando alguien inserte diez párrafos por encima, ni cuando alguien borre la mitad de la frase. Con identidades estables, una operación de borrado no dice borra el tercero sino borra este, y esa frase significa lo mismo en todas las réplicas del mundo y en cualquier momento. Al desaparecer la ambigüedad desaparece la traducción, y con la traducción desaparecen el historial, el vector de versiones que había que consultar y la propiedad TP2 que costó veinte años de literatura. Lo que queda es una operación de fusión que solo mira dos estados y produce un tercero, sin preguntarle nada a nadie. Esta lección explica por qué eso funciona, qué exige exactamente a la estructura de datos y cuánto cuesta, porque cuesta.

De la coordenada a la identidad

La diferencia entre las dos familias se ve mejor en el dato que en el algoritmo. Un editor basado en índices guarda una cadena y describe los cambios con números que se refieren a esa cadena en un instante concreto. Un editor basado en CRDT guarda una colección de átomos, cada uno con un identificador que lo distingue de todos los demás para siempre, y describe los cambios refiriéndose a esos identificadores. El texto visible ya no es el dato: es una vista que se obtiene ordenando los átomos vivos por su identificador y concatenando sus caracteres.

// El caracter deja de ser una posicion y pasa a ser una identidad
type Atomo = {
  id: string        // unico y permanente, por ejemplo sitio + contador
  ch: string
  despuesDe: string // identidad del vecino izquierdo en el momento de insertar
  vivo: boolean     // borrar no elimina: marca
}

// Borrar deja de ser ambiguo: no dice el tercero, dice este
function borrar(doc: Map<string, Atomo>, id: string) {
  const a = doc.get(id)
  if (a) a.vivo = false   // idempotente: repetirlo no cambia nada
}

Fíjate en lo que se ha ganado y en lo que se ha pagado, porque el intercambio es la lección entera. Se ha ganado que la operación borrar sea absolutamente inequívoca y, además, idempotente: recibirla dos veces produce el mismo resultado que recibirla una, de modo que la red puede duplicar mensajes sin consecuencias. Se ha pagado que el documento ya no es una cadena de mil caracteres sino un grafo de mil átomos con identificadores, punteros a vecinos y una bandera de vida, y que los caracteres borrados siguen ahí ocupando memoria, convertidos en lápidas. Ese es el impuesto estructural del enfoque y volveremos sobre él al final.

La fusión conmutativa: por qué el orden deja de importar

Con identidades estables, fusionar dos réplicas consiste en tomar la unión de sus átomos y la unión de sus marcas de borrado. Nada más. Pero para que esa operación garantice convergencia hace falta que cumpla tres propiedades algebraicas, y merece la pena verlas emparejadas con el problema concreto de red que resuelve cada una, porque así dejan de parecer requisitos matemáticos abstractos y se revelan como respuestas de ingeniería.

// La fusion solo mira dos estados. No consulta historia ni pide permiso.
function merge(a: Doc, b: Doc): Doc {
  const r = new Map(a)
  for (const [id, at] of b) {
    const mio = r.get(id)
    // union de atomos y disyuncion de borrados: max en un semirreticulo
    if (!mio) r.set(id, { ...at })
    else mio.vivo = mio.vivo && at.vivo
  }
  return r
}

Ese merge es el corazón del asunto y conviene leerlo con el ojo puesto en lo que no hace. No consulta un historial de operaciones concurrentes. No necesita saber qué vio el emisor antes de escribir. No requiere que el mensaje llegue una única vez ni en orden. Es una función pura de dos estados a un estado, y por eso una réplica desconectada durante seis meses puede reaparecer y fundirse sin ceremonia alguna. La consecuencia práctica es la que da nombre a la propiedad más citada del campo, la consistencia eventual fuerte: dos réplicas que han visto el mismo conjunto de cambios tienen exactamente el mismo estado, sin importar cómo lo vieron. La coordinación no se ha eliminado del sistema; se ha trasladado del tiempo de ejecución al tiempo de diseño, y se pagó una sola vez, cuando alguien diseñó la estructura de datos.

flowchart TD
I[documento inicial replicado] --> A[replica A inserta atomo con id A1]
I --> B[replica B inserta atomo con id B1]
I --> C[replica C borra atomo existente]
A --> M1[A funde con B]
B --> M1
C --> M2[C funde con B primero]
B --> M2
M1 --> F[mismo estado final]
M2 --> F
style F fill:#a6e3a1,color:#11111b

El caso difícil: ordenar texto sin coordenadas

Un conjunto de átomos no es un documento; falta decir en qué orden se leen. Aquí es donde los CRDT de secuencia hacen su trabajo, y donde reside casi toda la investigación seria del campo. La idea general consiste en dotar a los identificadores de un orden total denso: entre dos identificadores cualesquiera siempre debe existir espacio para crear otro intermedio, porque insertar entre dos caracteres es precisamente lo que hace un editor de texto todo el rato. Una familia lo resuelve con fracciones o listas de dígitos que se refinan indefinidamente, al estilo de Logoot, y otra con enlaces al vecino izquierdo más una regla determinista de desempate entre inserciones concurrentes en el mismo hueco, al estilo de RGA y YATA.

// Identificadores densos: entre dos posiciones siempre cabe otra.
// Se comparan lexicograficamente y se desempata por identificador de sitio.
type Pos = { digitos: number[]; sitio: string }

function entre(a: Pos, b: Pos, sitio: string): Pos {
  const d: number[] = []
  for (let i = 0; ; i++) {
    const x = a.digitos[i] ?? 0
    const y = b.digitos[i] ?? 256
    if (y - x > 1) { d.push(x + 1 + Math.floor(Math.random() * (y - x - 1))); break }
    d.push(x)             // no cabe en este nivel: se anade profundidad
  }
  return { digitos: d, sitio }
}

Este diseño tiene una consecuencia que sorprende la primera vez: los identificadores crecen. Cada vez que no cabe un valor intermedio en el nivel actual se añade un dígito más, de modo que escribir repetidamente en el mismo punto —justo lo que hace una persona tecleando una palabra— alarga los identificadores de los caracteres nuevos. Las implementaciones serias lo mitigan agrupando ejecuciones de caracteres consecutivos del mismo autor en bloques, que es lo que hace Yjs y por lo que su rendimiento con texto real es mucho mejor de lo que sugiere el modelo teórico átomo a átomo.

Rendimiento real: por qué la teoría exagera el coste

Si te quedas con el modelo mental de un objeto por carácter, con su identificador, su puntero al vecino y su bandera, concluirás que un CRDT es inviable para documentos grandes. La conclusión sería correcta para la formulación teórica e incorrecta para las implementaciones serias, y la diferencia está en tres optimizaciones que conviene conocer porque cambian el orden de magnitud del coste.

Con esas tres técnicas, un documento de texto de tamaño realista se sostiene sin problemas en un navegador, y los experimentos públicos con trazas de edición reales —el conjunto clásico es la traza de escritura de un artículo académico completo, con más de doscientas mil operaciones— se cargan y funden en tiempos que se miden en decenas de milisegundos. Lo que no desaparece con ninguna optimización es la naturaleza del coste: sigue siendo lineal en el número de ediciones jamás realizadas, no en el tamaño del texto visible. Un documento pequeño con un año de historia intensa pesa más que un documento grande recién escrito, y esa es una intuición que conviene tener incorporada antes de diseñar límites de producto.