CRDT: la apuesta contraria

La lección anterior cerró la primera vía de escape a la dificultad de OT: comprar linealización, con la factura denominada en autonomía. Queda la segunda, y su formulación es tan simple que cuesta creer que baste. Si el problema es que una operación lleva un parámetro que caduca al viajar, no reparemos el parámetro: eliminémoslo. Una inserción que no dice en la posición 7 sino inmediatamente después del elemento con este identificador único e inmutable no necesita transformarse contra nada, porque su significado no depende de qué haya pasado mientras viajaba. Sobre esa idea, y sobre el aparato algebraico que la generaliza a cualquier tipo de dato, se construyó una familia entera de estructuras que convergen sin árbitro, sin funciones de transformación y sin propiedades incómodas que demostrar caso por caso. El trabajo de Shapiro, Preguiça, Baquero y Zawirski de 2011 es el que unificó esas construcciones dispersas, les dio un marco común y les puso el nombre por el que hoy las conocemos.

Identidad en lugar de posición

Vuelve al ejemplo con el que empezó el nivel. El documento abc y una inserción de X en la posición 1: el número 1 es una coordenada relativa a un estado, y por eso caduca. Ahora supón que cada carácter, al nacer, recibe un identificador único que nunca cambia y que ningún otro elemento tendrá jamás —típicamente el par formado por el identificador de la réplica y un contador local—. La inserción deja de decir en la posición 1 y pasa a decir entre el elemento r1.4 y el elemento r1.5. Esa formulación sigue siendo verdadera después de cualquier cantidad de cambios concurrentes, porque los identificadores a los que se refiere no se mueven: si alguien insertó algo entremedias, la operación sigue apuntando a los mismos vecinos; si alguien borró uno de ellos, el elemento se marca como muerto pero su identidad permanece disponible como punto de anclaje.

// La operacion no lleva indice sino identidad de los vecinos
const insercion = {
  id: "r2.17",          // quien lo creo y su contador local
  valor: "X",
  izquierda: "r1.4",    // ancla estable, no una posicion
  derecha: "r1.5",
};

// Borrar no elimina: marca. La identidad sigue siendo un ancla valida
const borrado = { tipo: "marcarMuerto", id: "r1.4" };

Conviene detenerse un segundo en lo que acaba de hacerse, porque es un movimiento reutilizable mucho más allá de este contexto. Un índice es una referencia por descripción: designa a su objeto por la propiedad de ocupar cierto lugar, y esa propiedad puede dejar de cumplirse. Un identificador es una referencia por nombre propio: designa a su objeto directamente, y por tanto no puede fallar mientras el objeto exista. Toda la diferencia entre las dos escuelas de este nivel cabe en esa distinción, y la misma distinción explica por qué las claves subrogadas sobreviven a las reorganizaciones de una base de datos y por qué los enlaces por posición se rompen y los enlaces por identificador no.

Ahí está la inversión completa y conviene enunciarla sin adornos. OT conserva un parámetro frágil y construye maquinaria para repararlo en el destino; los CRDT construyen un parámetro que no puede romperse y se ahorran la maquinaria entera. Lo que desaparece del sistema no es una función auxiliar: desaparece la matriz cuadrática, desaparece la obligación de demostrar propiedades sobre la clausura de las transformaciones, desaparece la necesidad de saber contra qué sufijo exacto del historial transformar, y desaparece con ello la razón que empujaba hacia el servidor central. Lo que aparece a cambio son dos cosas nuevas que la lección siguiente cuantifica: identificadores que pesan y elementos muertos que no se pueden tirar mientras alguna réplica pueda referirse a ellos.

Merece la pena observar que la misma inversión resuelve de paso el problema del contexto, que en OT era la mitad del código. Una operación anclada a identidades no necesita saber qué ha visto el receptor, porque su significado no depende de ello; puede llegar por cualquier camino, repetida, fuera de orden o meses después, y seguirá diciendo lo mismo. Desaparecen con ello el registro de historia que había que consultar para calcular el sufijo, el vector que había que transmitir con cada mensaje y la obligación de que el emisor y el receptor compartan una noción de revisión. Lo único que queda del transporte es una exigencia mucho más débil: que todo llegue eventualmente a todas partes.

Queda una decisión que la identidad no resuelve sola. Si dos réplicas insertan concurrentemente entre los mismos vecinos, ambas operaciones son válidas y hay que ordenarlas de alguna manera; el algoritmo lo hace comparando los identificadores con un criterio total y determinista, idéntico en todas las réplicas. Fíjate en que es la misma decisión que en OT resolvía el desempate por identificador de sitio dentro de la función de transformación. No ha desaparecido —las políticas nunca desaparecen, solo cambian de sitio—, pero ahora vive en la definición del tipo de dato en lugar de en una celda de una matriz, y eso significa que se declara una vez y se demuestra una vez.

Dos formulaciones y un mismo teorema

El marco general reconoce dos maneras de replicar y ambas están desarrolladas en el trabajo de 2011. La formulación basada en estado propaga estados completos y los combina con una operación de fusión que debe ser conmutativa, asociativa e idempotente; formalmente, los estados forman una retícula de unión y la fusión es el supremo, mientras que cada actualización local solo puede mover el estado hacia arriba en ese orden. La consecuencia práctica es notable: si la fusión tiene esas tres propiedades, el transporte puede ser arbitrariamente malo —mensajes duplicados, desordenados, retransmitidos mil veces— y la convergencia sigue garantizada con tal de que cada estado llegue eventualmente a todas partes.

// Basada en estado: la fusion es el supremo de la reticula
function fusionarContador(a, b) {
  const claves = new Set([...Object.keys(a), ...Object.keys(b)]);
  const salida = {};
  for (const k of claves) salida[k] = Math.max(a[k] ?? 0, b[k] ?? 0);
  return salida; // conmutativa, asociativa e idempotente por construccion
}

// Basada en operaciones: se difunde el efecto y debe conmutar
function aplicarIncremento(estado, op) {
  return { ...estado, [op.replica]: (estado[op.replica] ?? 0) + op.cantidad };
}

La formulación basada en operaciones propaga los efectos en vez de los estados y exige menos ancho de banda a cambio de exigir más al transporte: necesita entrega fiable, exactamente una vez y respetando el orden causal, y bajo esas condiciones basta con que las operaciones concurrentes conmuten entre sí. El trabajo de 2011 demuestra además que las dos formulaciones son mutuamente emulables, de modo que la elección entre ellas es de ingeniería y no de expresividad: se decide según cuánto cuesta el estado completo, cuánto cuesta garantizar la entrega causal y qué se puede exigir de la red disponible.

Entre ambas hay un punto medio que la práctica ha ido imponiendo y que conviene conocer antes de elegir: propagar deltas de estado, es decir, fragmentos de la retícula que representan solo lo que ha cambiado, y fusionarlos con la misma operación de unión que se usaría con estados completos. Se conserva la tolerancia a duplicados y desórdenes de la formulación basada en estado, porque la unión sigue siendo idempotente, y se recupera casi todo el ahorro de ancho de banda de la basada en operaciones. Es la forma en que están construidas la mayoría de las bibliotecas serias de hoy, y explica por qué la vieja dicotomía entre las dos formulaciones aparece cada vez menos en las discusiones de ingeniería.

La garantía que ambas formulaciones ofrecen tiene nombre propio y conviene enunciarla con cuidado porque se cita mal a menudo. Se llama consistencia eventual fuerte, y añade a la consistencia eventual clásica una condición decisiva: dos réplicas que hayan recibido el mismo conjunto de actualizaciones tienen estados equivalentes, sin necesidad de ningún protocolo de reconciliación ni de resolver nada. La consistencia eventual corriente promete que las réplicas acabarán coincidiendo si dejan de llegar escrituras, y no dice nada sobre cómo; la fuerte convierte la coincidencia en una consecuencia inmediata de haber visto lo mismo. Lo que no promete, y aquí es donde se equivoca mucha gente, es que el estado al que se converge sea el que un humano habría elegido: la convergencia es una propiedad matemática y la corrección semántica sigue siendo un problema de diseño, exactamente como el nivel anterior estableció al hablar de las políticas de fusión.

El artículo de 2011 y su linaje

La familia recibió su nombre y su marco unificado en 2011, en el trabajo de Marc Shapiro, Nuno Preguiça, Carlos Baquero y Marek Zawirski. Ese año aparecen dos piezas complementarias del mismo grupo: un informe de investigación extenso titulado A comprehensive study of Convergent and Commutative Replicated Data Types, que desarrolla el marco formal y un catálogo amplio de tipos, y el artículo Conflict-free replicated data types, presentado en el simposio SSS de 2011, que consolida la denominación por la que la familia se conoce. La aportación decisiva no fue inventar una estructura concreta sino establecer las condiciones suficientes —retícula de unión y actualizaciones monótonas por un lado, conmutatividad de las operaciones concurrentes bajo entrega causal por otro— y demostrar que cualquier tipo que las cumpla obtiene consistencia eventual fuerte gratis, sin coordinación de ninguna clase.

flowchart TD
P[operaciones concurrentes sin coordinacion] --> A[la estructura las hace conmutar]
A --> B[condicion de reticula o condicion de conmutatividad]
B --> C[consistencia eventual fuerte demostrada una vez por tipo]
C --> D[cualquier topologia sirve incluido entre iguales]
C --> E[no hace falta transformar ni linealizar]
D --> F[precio identidad persistente y marcas de borrado]
E --> F
style C fill:#a6e3a1,color:#11111b
style F fill:#f9e2af,color:#11111b

El catálogo que ese marco ordena es más amplio de lo que las discusiones sobre texto colaborativo dejan ver, y conviene tenerlo presente porque la mayoría de los datos de una aplicación no son documentos: contadores que solo crecen y contadores con incremento y decremento, conjuntos que solo admiten altas, conjuntos con borrado observado que resuelven el caso de la baja concurrente mediante etiquetas únicas, registros de último escritor, registros multivalor que conservan todas las escrituras incomparables, mapas cuyos valores son a su vez tipos convergentes, grafos, y varias familias de secuencias con criterios de orden distintos. Buena parte del trabajo real de diseñar un sistema local-first consiste en asignar el tipo correcto a cada campo, que es exactamente el ejercicio con el que terminaba el nivel anterior, ahora con un catálogo respaldado por demostraciones.

Conviene ser honesto con el linaje, porque presentar 2011 como un año cero es históricamente falso y además hace perder de vista lo interesante. La regla de que gana la escritura con la marca de tiempo mayor está documentada desde los años setenta en el trabajo sobre mantenimiento de bases de datos duplicadas de Johnson y Thomas, y el propio artículo de Wuu y Bernstein de 1984 sobre soluciones eficientes a los problemas del registro y el diccionario replicados ya contiene estructuras que hoy llamaríamos convergentes. En el terreno de las secuencias, la tradición que abandona la transformación es anterior a 2011 y bien documentada: WOOT, presentado por Oster, Urso, Molli e Imine en la conferencia CSCW de 2006 bajo el título Data consistency for P2P collaborative editing, nace explícitamente de los resultados de imposibilidad sobre la segunda propiedad de transformación que la lección dos citó; y en 2009 aparecen Treedoc, de Preguiça, Marquès, Shapiro y Letia, y Logoot, de Weiss, Urso y Molli, ambos en la conferencia ICDCS. El trabajo de 2011 recoge esa dispersión y le da un techo común.

Conviene fijarse en qué tipo de aportación es esa, porque marca la diferencia con el modo de progresar de la escuela rival. En OT, avanzar significaba proponer un algoritmo nuevo y argumentar que cumplía las propiedades; cada propuesta era un artefacto que había que verificar entero. Aquí, avanzar significa exhibir una estructura y comprobar que satisface unas condiciones fijadas de antemano, con lo que la carga de la demostración se estandariza: quien inventa un tipo nuevo no tiene que razonar sobre convergencia, tiene que comprobar tres propiedades algebraicas y heredar el teorema. Ese cambio de régimen es la razón por la que el catálogo de tipos creció con rapidez después de 2011 y por la que resulta razonable escribir tipos convergentes a medida para un dominio concreto, algo impensable con una matriz de transformación.

Lo que vino después consolidó la familia como infraestructura. El tipo JSON convergente descrito por Kleppmann y Beresford en la revista IEEE Transactions on Parallel and Distributed Systems en 2017 extendió el enfoque a documentos anidados con mapas y listas arbitrarias, que es la forma en que las aplicaciones reales modelan sus datos. Y en 2017 también, Gomes, Kleppmann, Mulligan y Beresford publicaron en OOPSLA Verifying strong eventual consistency in distributed systems, un marco de verificación mecanizada con demostraciones comprobadas por máquina de la consistencia eventual fuerte para varios tipos concretos. Ese trabajo cierra el círculo abierto en la lección dos: donde OT acumulaba contraejemplos a propiedades que se creían demostradas, aquí hay demostraciones que una máquina ha verificado.

El precio: la identidad que no se puede tirar

Conviene cerrar la lección con la factura enunciada sin suavizantes, porque es lo que el nivel siguiente y buena parte del track van a administrar. Todo lo que esta familia consigue descansa en que los identificadores sean estables y universalmente interpretables, y esa exigencia tiene una consecuencia que no admite atajos: un identificador no se puede reutilizar nunca, y la marca que registra la muerte de un elemento no se puede borrar mientras alguna réplica pueda todavía enviar una operación que se refiera a él. El resultado es que la estructura crece con el número de operaciones realizadas, no con el tamaño de lo que muestra, y un documento del que se ha borrado el noventa por ciento sigue arrastrando el noventa por ciento en marcas.

// La pregunta dificil no es como borrar, sino cuando es seguro hacerlo
function sePuedeRecolectar(marca, resumenesCausalesConocidos) {
  // solo si TODAS las replicas que existen han visto ya el borrado
  return resumenesCausalesConocidos.every((vv) => yaVisto(vv, marca.id));
  // y "todas las replicas que existen" es una afirmacion sobre el futuro:
  // no hay forma local de saber que no aparecera una manana con datos viejos
}

Fíjate en la forma de la dificultad, porque es la misma que el nivel anterior encontró al hablar de podar vectores de versiones. Saber cuándo un elemento muerto puede desaparecer de verdad requiere saber que ninguna réplica del mundo volverá a mencionarlo, y eso es una afirmación sobre el futuro que ningún nodo puede establecer por su cuenta. Las salidas conocidas son todas parciales y todas tienen un coste: exigir un resumen causal de todos los participantes, que reintroduce coordinación; declarar caducadas las réplicas que llevan demasiado tiempo calladas, que reintroduce pérdida de datos; o comprimir en vez de borrar, que retrasa el problema sin resolverlo. Existe además una línea de trabajo que ataca el otro extremo del coste, el de la transmisión: los tipos convergentes por deltas descritos por Almeida, Shoker y Baquero, que evitan enviar el estado completo transmitiendo solo los fragmentos de retícula que han cambiado, y que fueron desarrollados en un artículo publicado en la revista Journal of Parallel and Distributed Computing en 2018. Nada de eso hace desaparecer la factura de la identidad; la reparte mejor.