Basados en estado: enviar el objeto entero y mezclarlo

De las dos maneras de construir un tipo de dato replicado que converge, la basada en estado es la que menos supone sobre el mundo. Una réplica no transmite lo que hizo: transmite lo que es. El receptor no reproduce ninguna acción, se limita a combinar el objeto recibido con el suyo mediante una función que debe cumplir tres leyes algebraicas y ninguna condición más. De esas tres leyes se deduce absolutamente todo lo demás: que da igual el orden de llegada, que da igual recibir catorce veces el mismo mensaje, que da igual perder la mitad de los envíos mientras alguno llegue alguna vez. Es el contrato de red más barato que se conoce en sistemas distribuidos, y esta lección trata de qué compra ese contrato y qué factura a cambio.

Tres leyes y un orden que aparece solo

Un tipo replicado basado en estado consta de tres piezas: un conjunto de estados posibles, una familia de actualizaciones locales que llevan un estado a otro, y una operación binaria de mezcla que combina dos estados cualesquiera en uno solo. La mezcla debe ser idempotente —mezclar un estado consigo mismo lo deja igual—, conmutativa —el orden de los argumentos no importa— y asociativa —el agrupamiento tampoco—. Con eso está dicho el contrato entero. No hay ninguna cláusula sobre identidades de réplica, ni sobre marcas de tiempo, ni sobre quién habló antes.

Lo notable es que esas tres leyes no son requisitos independientes que uno impone por comodidad: son exactamente la definición de un semirretículo de unión, y traen consigo una consecuencia que no se pidió. Si la mezcla las cumple, queda inducido un orden parcial sobre los estados definido por la propia mezcla: decimos que a precede a b cuando mezclar(a, b) es igual a b. Ese orden no se declara en ninguna parte del código, aparece como teorema, y la mezcla de dos estados resulta ser su mínima cota superior: el estado más pequeño que está por encima de ambos. Ni un bit de información de más, ni uno de menos.

El ejemplo canónico y más económico es el contador que solo crece. El estado no es un número sino un mapa de réplica a contribución, y la mezcla toma el máximo componente a componente porque el máximo es la unión del retículo de los naturales.

// Estado: un mapa de identificador de replica a su contribucion acumulada
function mezclar(a, b) {
  const salida = { ...a };
  for (const [replica, n] of Object.entries(b)) {
    salida[replica] = Math.max(salida[replica] ?? 0, n);
  }
  return salida;
}

function incrementar(estado, replica, n = 1) {
  return { ...estado, [replica]: (estado[replica] ?? 0) + n };
}

const valor = (estado) => Object.values(estado).reduce((s, n) => s + n, 0);

Fíjate en por qué el máximo es la elección correcta y la suma sería catastrófica. Cada entrada del mapa registra un hecho monótono —cuánto ha contribuido esa réplica hasta donde yo sé— y ese hecho no se acumula al recibirlo dos veces: se refina. Sumar convertiría cada retransmisión en un incremento fantasma, que es precisamente el fallo que la idempotencia existe para prohibir. La suma aparece una sola vez, al final, cuando se proyecta el estado a un valor observable, y esa proyección no forma parte del CRDT.

flowchart BT
V0[estado vacio] --> A[replica A vale 1]
V0 --> B[replica B vale 2]
A --> M[mezcla A vale 1 y B vale 2]
B --> M
M --> T[cualquier estado posterior]
style V0 fill:#89b4fa,color:#11111b
style M fill:#a6e3a1,color:#11111b

El diagrama tiene un elemento en la base que conviene nombrar porque hace falta más adelante: el estado neutro, el que no aporta información alguna y que mezclado con cualquier otro lo deja intacto. En el contador es el mapa vacío. Su existencia no es un detalle de implementación sino la que permite arrancar una réplica nueva sin coordinarse con nadie: se crea en el fondo del retículo y todo lo que reciba la hará subir. Un tipo cuyo estado inicial no sea neutro obliga a distinguir entre réplicas nuevas y antiguas, y esa distinción es una fuente inagotable de errores en el arranque en frío.

Conviene también fijar el vocabulario para no confundir dos cosas que se parecen. El orden inducido es parcial, no total: hay pares de estados en los que ninguno precede al otro, y ese caso es exactamente la concurrencia que el nivel anterior definió. La mezcla no lo resuelve eligiendo un ganador, lo resuelve subiendo a un tercer estado que está por encima de los dos y que es distinto de ambos. Esa es la diferencia estructural entre una función de mezcla y una política de resolución de conflictos, y explica por qué la primera no necesita conocer el dominio y la segunda sí.

La actualización es la que tiene que demostrar algo

Es fácil concentrar toda la atención en la mezcla y dar por hecho el resto, y ahí es donde se rompen la mayoría de las implementaciones caseras. La convergencia no se sigue solo de que la mezcla sea un semirretículo: exige además que toda actualización local sea monótona, es decir, que el estado resultante esté por encima del anterior en el orden inducido. Una actualización que baje en el retículo, aunque sea una sola vez y en un caso raro, destruye la garantía completa, porque el receptor puede haber mezclado ya un estado superior y la mezcla nunca desciende.

Esta obligación tiene consecuencias de diseño muy concretas y bastante incómodas. Borrar de verdad es no monótono, de ahí las lápidas. Reiniciar un contador a cero es no monótono, de ahí que un contador que sube y baja se modele como dos contadores que solo suben. Reasignar un valor por el simple hecho de ser el más reciente según el reloj local es no monótono si el reloj retrocede, de ahí que los registros de última escritura necesiten un desempate estable. La regla operativa es breve: una actualización solo puede añadir información, jamás retirarla, y el borrado se implementa siempre añadiendo la información de que algo fue borrado.

// Contador que sube y baja: dos mapas monotonos en lugar de uno mutable
const vacio = { mas: {}, menos: {} };

const mezclarPN = (a, b) => ({
  mas:   mezclar(a.mas,   b.mas),
  menos: mezclar(a.menos, b.menos),
});

const decrementar = (e, replica, n = 1) => ({
  ...e,
  menos: incrementar(e.menos, replica, n), // se anade al lado negativo
});

const valorPN = (e) => valor(e.mas) - valor(e.menos);

Lo que le pide al canal: prácticamente nada

Aquí está la razón de existir de la familia. Como la mezcla es idempotente, un mensaje duplicado no hace daño. Como es conmutativa y asociativa, un mensaje que llega desordenado no hace daño. Y como cada estado enviado contiene toda la información acumulada por su emisor, un mensaje perdido tampoco hace daño: el siguiente envío del mismo emisor incluirá lo que se perdió, porque el estado solo crece. El canal puede perder, duplicar y reordenar a voluntad, y la única condición que hay que garantizar es de una debilidad casi cómica: que cada par de réplicas se intercambie el estado infinitas veces, o dicho en términos de ingeniería, que sigan intentándolo.

Esa condición se llama anti-entropía y se implementa con un bucle periódico que elige un vecino y le manda todo. No necesita acuses de recibo, ni ventanas deslizantes, ni números de secuencia, ni reintentos selectivos, ni detección de huecos, ni entrega ordenada, ni sesiones. Se puede montar sobre un canal difusivo, sobre un fichero copiado a mano en una memoria USB, sobre un almacén de objetos donde cada réplica sube su estado y lee el de los demás, o sobre una red de rumores donde nadie conoce la topología completa.

// El protocolo entero: mandar todo a alguien, de vez en cuando
setInterval(async () => {
  const vecino = elegirAlAzar(vecinosConocidos);
  try {
    const suyo = await intercambiar(vecino, estado); // puede fallar sin consecuencias
    estado = mezclar(estado, suyo);
  } catch {
    // no hay nada que reintentar de forma especial: el siguiente ciclo lo cubre
  }
}, 5000);

Merece la pena detenerse en el bloque de captura vacío, porque en cualquier otro protocolo sería una negligencia y aquí es la respuesta correcta. Un fallo de envío no deja al sistema en un estado inconsistente ni pierde información: solo significa que la convergencia ocurrirá cinco segundos más tarde. No hace falta distinguir entre un error de red, un vecino caído y una respuesta corrupta, porque el tratamiento es idéntico en los tres casos y consiste en no hacer nada.

Merece la pena subrayar lo que esto significa en producto. Un sistema de esta familia sobrevive a un cliente que se queda tres meses sin conexión, a un servidor que se restaura desde una copia de seguridad de la semana pasada, a un despliegue que duplica mensajes durante veinte minutos y a una partición de red que aísla a la mitad de los nodos. Ninguno de esos escenarios requiere código especial, porque ninguno es un caso especial: todos son el caso normal con distintos retrasos.

El precio: el mensaje mide lo que mide el documento

La factura es exactamente el reverso de la moneda. Como el mensaje es el estado completo, su tamaño no guarda ninguna relación con el tamaño del cambio. Escribir un carácter en un documento de cuarenta megabytes produce una sincronización de cuarenta megabytes, y hacerlo cien veces produce cuatro gigabytes de tráfico para transportar cien caracteres. El coste de cómputo acompaña al de red, porque la mezcla recorre las dos estructuras enteras y no las regiones tocadas.

Hay paliativos y conviene conocer sus límites. La compresión ayuda cuando el estado es redundante y no cuando ya está codificado de forma densa. Comparar resúmenes criptográficos permite saltarse el envío si nada cambió, lo que resuelve el caso de la réplica ociosa pero no el de la que escribe una vez por minuto. Los protocolos de reconciliación por bloques al estilo rsync reducen el tráfico a costa de varias idas y vueltas y de suponer un canal con sesión, que era justo lo que no queríamos suponer. Y ninguno de los tres cambia el hecho estructural: el coste está atado al tamaño del objeto, no al de la edición.

Conviene además contar el segundo coste, que se olvida con frecuencia porque no aparece en las facturas de tráfico. El estado de un tipo replicado no es el contenido que el usuario ve: es el contenido más los metadatos que hacen posible la mezcla, y esos metadatos crecen con el número de réplicas que han escrito alguna vez y con el número de elementos que han existido alguna vez, incluidos los borrados. Un conjunto que ha visto pasar un millón de elementos y conserva mil arrastra las lápidas del resto, y esas lápidas viajan en cada sincronización junto con el contenido vivo. La poda de metadatos es un problema propio y difícil, porque retirar una lápida antes de que todos la hayan visto reintroduce el elemento borrado.