El orden es el problema

Hasta aquí hemos delimitado el terreno: la partición es el régimen normal, bajo partición hay que elegir, y la elección local-first consiste en seguir aceptando escrituras a cambio de renunciar a la linealizabilidad. Esta lección responde a la pregunta que queda pendiente y que resulta ser la más importante de las cinco: ¿por qué exactamente es difícil volver a juntar lo que divergió? La respuesta no está en la red, ni en el formato de los mensajes, ni en la calidad de la implementación. Está en una propiedad algebraica de las operaciones que tu aplicación ofrece. Dos réplicas que reciben el mismo conjunto de cambios en distinto orden acaban en el mismo estado si y solo si esos cambios se comportan bien frente al reordenamiento, y casi ninguna operación escrita con naturalidad se comporta bien. Ese es el problema entero, y todo lo que este track construye a partir de aquí son maneras de rodearlo.

El mismo orden o nada

El resultado fundacional de la replicación es tan simple que casi decepciona. Si varias réplicas parten del mismo estado inicial, ejecutan una máquina de estados determinista y aplican la misma secuencia de comandos en el mismo orden, terminan en el mismo estado. Es una inducción de dos líneas sobre la longitud de la secuencia. Y de ella se sigue que todo el problema de mantener réplicas idénticas se reduce a un único subproblema: ponerse de acuerdo en el orden.

Conviene ver el ejemplo mínimo, porque desactiva cualquier tentación de pensar que esto es un caso rebuscado. Dos usuarios editan el título de un documento. Uno ejecuta asignar(titulo, "Informe") y el otro, sin haber visto al primero, ejecuta asignar(titulo, "Borrador"). Una réplica que las aplique en un orden acaba con un valor; la otra, con el contrario. No hay pérdida de mensajes, no hay error de programación y ninguna de las dos réplicas ha hecho nada incorrecto. Simplemente el resultado de la asignación depende del orden, y el orden no está determinado.

flowchart TD
E[mismo estado inicial en ambas replicas] --> A[replica A aplica op1 y despues op2]
E --> B[replica B aplica op2 y despues op1]
A --> X[estado final X]
B --> Y[estado final Y]
X --> Q[X coincide con Y solo si las operaciones conmutan]
Y --> Q
Q --> R[imponer un orden comun que cuesta consenso]
Q --> S[disenar operaciones que conmuten]
style Q fill:#f38ba8,color:#11111b
style R fill:#fab387,color:#11111b
style S fill:#a6e3a1,color:#11111b

Conviene subrayar la palabra determinista del enunciado, porque es una condición y no un adorno, y se incumple con una facilidad asombrosa. Una operación que consulta la hora del dispositivo no es determinista. Una que genera un identificador al azar tampoco. Una que recorre una tabla asociativa cuyo orden de iteración depende de la historia de inserciones tampoco lo es en la práctica. Cualquiera de esas tres basta para que dos réplicas que apliquen exactamente la misma secuencia en el mismo orden acaben distintas, y el fallo resultante es especialmente desagradable porque contradice la intuición de todo el mundo sobre lo que debería ocurrir. Antes de preocuparse por el orden hay que asegurar el determinismo, o el orden no servirá de nada.

Ahora la parte que casi nunca se dice y que cambia la conversación: acordar un orden total entre nodos distribuidos no es parecido al consenso, es el consenso. El problema de entregar mensajes a todos los participantes en el mismo orden, conocido como difusión atómica o difusión con orden total, se ha demostrado equivalente al consenso: cualquier solución de uno resuelve el otro. Y eso arrastra consigo todo lo que el consenso trae: un viaje de ida y vuelta a un quórum antes de que una operación sea un hecho, indisponibilidad para la minoría aislada, y el resultado de imposibilidad que muestra que en un sistema puramente asíncrono ningún algoritmo determinista garantiza terminar aun con un solo fallo por caída. Cuando alguien propone simplemente ordenamos los cambios, está proponiendo consenso sin llamarlo por su nombre.

El orden que sale gratis es parcial

Antes de dar por perdida la partida conviene preguntarse si de verdad hace falta un orden total, porque la respuesta es que no siempre, y ahí está la rendija por la que pasa todo lo demás.

Existe, sin embargo, un orden que no hay que fabricar porque la propia circulación de mensajes lo produce. Es la relación sucede antes de Lamport, y se define con tres cláusulas: dos eventos del mismo proceso están ordenados por su orden de ejecución; el envío de un mensaje precede a su recepción; y la relación es transitiva. Cuando dos eventos no están relacionados en ninguna dirección, se dicen concurrentes.

Lo esencial es que esa relación es un orden parcial, y que su parcialidad no es un defecto de la definición sino un reflejo fiel de lo que ocurrió. Si dos personas escribieron sin haberse visto, no existe ningún hecho del mundo que diga cuál fue primero para el sistema; puede haber un antes y un después en el tiempo físico, pero ninguna cadena causal los conecta, y por tanto ninguna réplica puede deducirlo de la información que recibe. La concurrencia no es ignorancia sobre el orden: es la ausencia de orden.

Merece la pena insistir en el matiz de potencial, porque la relación no captura la causalidad real sino la posibilidad de influencia. Si dos personas hablan por teléfono y una edita justo después de que la otra le cuente qué escribió, hubo influencia real y el sistema no la ve, porque el canal por el que viajó no era el suyo. La relación de Lamport es una cota superior de lo que el sistema puede saber, no una descripción de lo que pasó en el mundo. Reconocer ese límite evita expectativas imposibles: ningún protocolo va a ordenar correctamente dos cambios que se coordinaron fuera de él.

De ahí sale el principio que gobierna todo el diseño posterior. La causalidad se obtiene gratis, adjuntando a cada mensaje lo que su emisor había visto; el orden total hay que comprarlo con coordinación. Los relojes lógicos que verás en el nivel siguiente son precisamente el mecanismo para transportar ese orden parcial de forma barata: los escalares al estilo Lamport lo respetan pero no permiten distinguir la concurrencia, y los vectoriales sí la detectan con exactitud, a cambio de metadatos que crecen con el número de participantes.

Las tres propiedades que hacen irrelevante el orden

Tenemos entonces dos hechos enfrentados: el orden total es caro y el orden parcial es gratis pero insuficiente para determinar un estado. La salida no puede consistir en conseguir más orden del que hay, así que tiene que consistir en necesitar menos.

Si imponer un orden común cuesta consenso, la salida es dejar de necesitarlo. Y la condición para no necesitarlo se enuncia con precisión: las réplicas convergen sea cual sea el orden de entrega si y solo si las operaciones concurrentes conmutan entre sí. Con eso basta para el enfoque basado en operaciones. Cuando en lugar de propagar operaciones se propagan estados que hay que fusionar, la exigencia se descompone en tres propiedades de la función de fusión, y cada una responde a un accidente distinto de la red.

Fíjate en que cada una de las tres corresponde a una imperfección concreta de la red y no a un capricho matemático. Si los mensajes llegaran siempre en orden, bastaría con menos; si nunca se duplicaran, la idempotencia sobraría. Las propiedades no son fuertes por gusto: son exactamente tan fuertes como desordenada es la realidad que deben tolerar.

Las tres primeras propiedades no son una lista de deseos: son exactamente los axiomas de un semirretículo de unión. Cualquier operación binaria conmutativa, asociativa e idempotente induce un orden parcial sobre su dominio —se define que x precede a y cuando fusionar ambos da y— y en ese orden la operación resulta ser el supremo, es decir, el elemento más pequeño que está por encima de los dos. Ese hecho algebraico es el que convierte la convergencia en un teorema: si los estados forman un semirretículo, la fusión es el supremo y cada cambio local solo puede subir en el orden, entonces el estado de cualquier réplica es el supremo de todo lo que ha visto, y un supremo no depende del orden en que se calcule.

// Maximo sobre enteros y union de conjuntos son semirreticulos.
const fusionarMax = (a, b) => Math.max(a, b);
const fusionarUnion = (a, b) => new Set([...a, ...b]);

// Conmutativa, asociativa e idempotente: el orden de llegada deja de importar.
fusionarMax(fusionarMax(3, 7), 5) === fusionarMax(3, fusionarMax(7, 5)); // true
fusionarUnion(a, a); // igual a a

// La asignacion no lo es, y por eso diverge:
const asignar = (a, b) => b; // no conmutativa: asignar(x,y) distinto de asignar(y,x)

Merece la pena señalar un caso que suele desconcertar. La regla de gana la última escritura, con un desempate determinista, sí cumple los tres axiomas y por tanto converge de verdad: todas las réplicas acaban con el mismo valor. Lo que ocurre es que ese valor descarta trabajo que alguien hizo. La lección que hay que extraer es incómoda y hay que retenerla: convergencia no significa corrección. Converger es que todos acaben igual; preservar la intención es otra cosa, mucho más cara, y es la que separa un contador que funciona de un editor de texto que no destroza párrafos ajenos.

Dicho de otro modo: la convergencia deja de ser algo que se comprueba a posteriori y pasa a ser algo que se deduce de la estructura. Esa diferencia es la que separa una sincronización que funciona de una que parece funcionar.

La cuarta propiedad, la monotonía, es la que explica por qué el borrado será un tema recurrente durante los próximos veinte niveles. Quitar un elemento de un conjunto hace que el estado baje en el orden, y un estado que baja puede ser reintroducido por la siguiente fusión con una réplica que aún no se enteró. Por eso los diseños que convergen no borran: marcan. Las lápidas, los contadores por réplica y los identificadores únicos por elemento que aparecerán más adelante son todos el mismo remedio para la misma enfermedad: convertir una operación que resta en una que suma.

Del álgebra al modelo de datos

Todo lo anterior se traduce en un puñado de movimientos concretos de diseño, y merece la pena verlos porque son los mismos que reaparecerán, con más sofisticación, durante el resto del track. Cada uno consiste en sustituir una operación cuyo resultado depende del orden por otra cuyo resultado no depende de él, aun a costa de guardar más cosas.

Los tres comparten una forma reconocible: sustituyen una operación que pisa por una que añade, porque pisar depende de quién llegue el último y añadir no depende de nada.

El primero es cambiar asignación por acumulación. En lugar de fijar el valor de un contador, registra el incremento que cada réplica ha aportado y define el valor como la suma de las aportaciones; los incrementos conmutan y las asignaciones no. El segundo es cambiar borrado por marca, porque quitar hace bajar el estado en el orden del semirretículo y marcar lo hace subir; el precio son las lápidas, que hay que acabar podando. El tercero es cambiar posición por identidad: si una operación dice inserta en el índice cuarto, su significado depende de cuántas inserciones ajenas hayan llegado antes, mientras que si dice inserta después del elemento con este identificador, su significado es estable frente a cualquier reordenamiento. Ese tercer movimiento es, en germen, toda la teoría de las secuencias replicadas.

// No conmuta: el resultado depende de quien llegue el ultimo.
estado.contador = nuevoValor;

// Conmuta: cada replica solo toca su propia casilla y el valor es la suma.
estado.aportaciones[miReplica] += delta;
const valor = Object.values(estado.aportaciones).reduce((a, b) => a + b, 0);

// Fusion como supremo casilla a casilla, con maximo en cada una.
function fusionar(a, b) {
  const claves = new Set([...Object.keys(a), ...Object.keys(b)]);
  return Object.fromEntries(
    [...claves].map((k) => [k, Math.max(a[k] ?? 0, b[k] ?? 0)])
  );
}

Fíjate en lo que tienen en común los tres movimientos: ninguno es un truco de implementación, todos cambian qué se guarda y por tanto qué se puede preguntar. Ese es el sentido exacto en el que el modelo de datos decide si habrá conflictos, y también el motivo por el que estas decisiones son tan caras de tomar tarde: cuando ya hay usuarios con historia guardada, cambiar de asignación a acumulación no es una refactorización sino una migración de esquema en un sistema donde no todos los participantes se actualizan a la vez.