CRDTs: fundir sin árbitro

La lección anterior dejó una promesa pendiente: para que local-first funcione, dos copias del mismo dato editadas a la vez en dos dispositivos deben poder fundirse en un resultado único sin que un servidor decida quién gana. Suena imposible, porque nuestra intuición sobre datos concurrentes está entrenada por el conflicto: dos personas editan la misma celda, alguien tiene que perder. Los CRDTs —tipos de datos replicados sin conflictos— disuelven esa intuición cambiando la pregunta. No se preguntan quién gana cuando hay conflicto, sino cómo diseñar el dato para que el conflicto no exista, para que cualquier par de réplicas que hayan visto los mismos cambios acaben, por construcción matemática, en el mismo estado. La palabra clave es converger: no reconciliar a posteriori, no votar, no consultar un reloj central, sino garantizar de antemano que la fusión es determinista y que da igual el orden en que lleguen las piezas. Esta lección abre la caja negra. Verás que detrás de la magia hay un teorema modesto y hermoso —el de los semirretículos— y tres propiedades algebraicas que, una vez las reconoces, hacen que la convergencia deje de parecer un truco y se vuelva obvia. Entender esto es entender el ladrillo con el que están hechos Yjs, Automerge y todos los motores que veremos después.

Convergencia sin árbitro: la consistencia eventual fuerte

Un sistema distribuido clásico persigue la consistencia fuerte: todas las réplicas ven el mismo valor en todo momento, lo que exige coordinación —bloqueos, consenso, un líder— antes de cada escritura. Esa coordinación es cara y, sobre todo, requiere red: sin poder hablar con las demás réplicas, una réplica no puede escribir. Local-first no puede pagar ese precio, porque su ideal tres es que la red sea opcional. Los CRDTs renuncian a la consistencia fuerte y abrazan una variante disciplinada de la consistencia eventual: la consistencia eventual fuerte, o SEC por sus siglas en inglés. Su garantía es precisa y más potente de lo que suena: dos réplicas que han recibido el mismo conjunto de actualizaciones —sin importar el orden— tienen exactamente el mismo estado. No hay ventana de divergencia que reconciliar después, ni posibilidad de que dos réplicas con la misma información discrepen. La convergencia no es probable ni eventual en el sentido flojo: es una certeza matemática que se cumple en cuanto la información ha circulado.

Lo notable es lo que esa garantía compra: cada réplica escribe cuando quiere, sin preguntar a nadie, incluso completamente desconectada, y aun así el sistema no puede divergir permanentemente. La coordinación desaparece del camino de la escritura y se traslada al diseño del propio tipo de dato. Ahí está el truco, y no es magia: es álgebra. Y esa reubicación de la coordinación no es casual, sino forzada por un teorema famoso —el teorema CAP—, que demuestra que ante una partición de red un sistema solo puede elegir entre seguir disponible o seguir consistente. Los CRDTs eligen sin titubear la disponibilidad, y recuperan una forma fuerte de consistencia por la puerta de atrás: no impidiendo la divergencia, sino garantizando que toda divergencia es temporal y se resuelve sola.

flowchart TD
I[estado inicial compartido] --> A1[replica A inserta X]
I --> B1[replica B inserta Y]
A1 -->|sin red, en paralelo| A2[A tiene X]
B1 -->|sin red, en paralelo| B2[B tiene Y]
A2 --> M[merge al reconectar]
B2 --> M
M --> F[ambas convergen al mismo estado con X e Y]
style M fill:#cba6f7,color:#11111b
style F fill:#a6e3a1,color:#11111b

Las tres propiedades de la fusión

La pieza central de todo CRDT es su operación de fusión, el merge que combina dos réplicas en una. Para que la convergencia sea inevitable, esa fusión debe cumplir tres propiedades. Son las mismas que caracterizan a un semirretículo de unión, y por eso los CRDTs también se llaman, con más precisión, tipos de datos convergentes basados en semirretículos.

• Conmutatividad. Fundir A con B da lo mismo que fundir B con A. El orden en que dos réplicas se encuentran no altera el resultado.
• Asociatividad. Al fundir tres o más réplicas, da igual cómo las agrupes. La topología de propagación —quién habla con quién y en qué orden— es irrelevante.
• Idempotencia. Fundir una réplica consigo misma, o volver a aplicar un cambio ya visto, no cambia nada. Recibir el mismo mensaje dos veces es inofensivo.

Junta las tres y obtienes un resultado poderoso: el estado final no depende ni del orden, ni de la agrupación, ni de la repetición de los mensajes. Y esas son exactamente las tres patologías de una red real —mensajes desordenados, caminos distintos, entregas duplicadas—. Un CRDT es, en el fondo, una estructura de datos inmune a las tres. El ejemplo canónico es el contador que solo crece, el G-Counter: cada réplica lleva su propia cuenta en un mapa indexado por identificador de réplica, y la fusión toma el máximo elemento a elemento.

type GCounter = Record<string, number> // idReplica -> conteo local

function incrementar(c: GCounter, id: string): GCounter {
  return { ...c, [id]: (c[id] ?? 0) + 1 }
}

// merge = maximo elemento a elemento: conmutativo, asociativo, idempotente
function merge(a: GCounter, b: GCounter): GCounter {
  const r: GCounter = { ...a }
  for (const id in b) r[id] = Math.max(a[id] ?? 0, b[id] ?? 0)
  return r
}

const valor = (c: GCounter) => Object.values(c).reduce((s, n) => s + n, 0)

El máximo es la clave. Como Math.max es conmutativo, asociativo e idempotente, el merge hereda las tres propiedades gratis, y el contador converge pase lo que pase con la red. Cada réplica solo toca su propia casilla, así que nunca sobrescribe el trabajo de otra; la fusión reconstruye el total tomando lo más alto que cada réplica haya visto de cada una. Esa es la intuición del merge en su forma más pura: no elegir un ganador, sino combinar de un modo que respeta lo que todos aportaron. Compáralo con la alternativa ingenua —guardar un único número y que la última escritura lo pise—: esa sí pierde incrementos concurrentes, porque la asignación directa no es conmutativa. El diseño del CRDT consiste, precisamente, en encontrar la representación cuyo merge sí lo sea.

Dos familias y un catálogo

Los CRDTs se presentan en dos familias, según qué viaje por la red. Son teóricamente equivalentes —cada una puede emular a la otra— pero imponen exigencias muy distintas al transporte.

El catálogo de CRDTs conocidos cubre casi cualquier estructura, y conviene tener un mapa de sus familias porque casi todo lo que construyas se apoya en una de ellas.

Un LWW-Register merece un vistazo al código porque muestra el otro extremo del espectro frente al G-Counter: donde el contador nunca pierde datos, el registro elige un ganador por reloj y descarta al perdedor. Ambos convergen, pero encarnan filosofías opuestas sobre qué hacer con lo concurrente.

type LWW<T> = { valor: T; ts: number; id: string } // ts = marca de tiempo

// merge: gana el ts mayor; empate resuelto por id, para que sea determinista
function merge<T>(a: LWW<T>, b: LWW<T>): LWW<T> {
  if (a.ts !== b.ts) return a.ts > b.ts ? a : b
  return a.id > b.id ? a : b
}