G-Counter: un contador por réplica, el valor es la suma

El diagnóstico de la lección anterior señalaba un culpable concreto: sumar demasiado pronto. La reparación consiste, literalmente, en no sumar. En lugar de un número, cada réplica guarda un mapa que asigna a cada identificador de réplica el total de incrementos que esa réplica ha aportado; el valor observable se obtiene sumando el mapa entero en el momento de leer, y la fusión de dos mapas toma el máximo casilla por casilla. Con ese cambio, dos incrementos concurrentes dejan de competir porque ya no ocupan el mismo sitio, y el máximo —que en la lección anterior era el villano que descartaba trabajo— pasa a ser exactamente la operación correcta, porque ahora se aplica entre dos versiones de la misma casilla y no entre dos operaciones distintas. Esta lección construye la estructura completa, demuestra las tres propiedades una por una, y examina la invariante silenciosa de la que depende todo el edificio y que es lo primero que se rompe en producción.

De un número a un mapa: la información que faltaba

La estructura recibe el nombre de contador creciente, o G-Counter por grow-only, y su definición completa cabe en cuatro funciones. El estado es un mapa de identificador de réplica a número natural. Incrementar es sumar a la casilla propia y solo a la casilla propia. Leer es sumar todas las casillas. Fusionar es tomar el máximo entrada a entrada, tratando como cero las casillas que un lado desconoce.

// Estado: un mapa de identificador de replica a total aportado por ella
function crear() {
  return {};
}

function incrementar(g, replica, cantidad = 1) {
  if (!Number.isInteger(cantidad) || cantidad < 0) {
    throw new RangeError("un contador creciente solo admite incrementos no negativos");
  }
  return { ...g, [replica]: (g[replica] ?? 0) + cantidad };
}

function valor(g) {
  return Object.values(g).reduce((suma, n) => suma + n, 0);
}

function fusionar(a, b) {
  const salida = { ...a };
  for (const replica of Object.keys(b)) {
    salida[replica] = Math.max(salida[replica] ?? 0, b[replica]);
  }
  return salida;
}

Vuelve ahora al experimento que fracasaba. Ana y Ben parten del mismo mapa, cada uno incrementa el suyo sin conexión y cada uno acaba con un mapa distinto: Ana tiene su casilla a uno, Ben tiene la suya a uno. Cuando se fusionan, el máximo se aplica entre la casilla de Ana en un lado y su ausencia en el otro, y entre la casilla de Ben y su ausencia; ninguna comparación enfrenta a Ana contra Ben. El resultado contiene ambas casillas, la suma da dos y no se ha descartado nada. El conflicto no se ha resuelto: ha dejado de existir, porque las dos operaciones nunca escribieron en el mismo sitio.

flowchart TD
A[Ana tiene ana igual a 1] --> F[fusion casilla por casilla]
B[Ben tiene ben igual a 1] --> F
F --> M[mapa con ana igual a 1 y ben igual a 1]
M --> V[la lectura suma las casillas y devuelve 2]
F --> N[el maximo nunca compara a Ana contra Ben]
style M fill:#a6e3a1,color:#11111b
style V fill:#a6e3a1,color:#11111b
style N fill:#89b4fa,color:#11111b

Merece la pena mirar el tamaño real del cambio, porque es menor de lo que parece. No hemos inventado ninguna operación nueva ni hemos añadido relojes: hemos descompuesto una suma global en una familia de sumas locales, cada una de ellas con un único escritor. Y un dato con un único escritor no puede entrar en conflicto consigo mismo. Toda la maquinaria posterior de este track es, en el fondo, la búsqueda de descomposiciones de ese tipo para operaciones cada vez menos amables.

La fusión es el máximo, y tenía que serlo

La pregunta que casi todo el mundo hace al ver el código es por qué la fusión toma el máximo de cada casilla en vez de sumar las dos casillas, ya que sumar parece más acorde con la idea de un contador. La respuesta está en qué representa una casilla. g["ana"] no es lo que Ana aportó en esta sesión: es el total acumulado por Ana desde siempre, un número que solo crece y que ya incluye todo lo anterior. Dos copias de la casilla de Ana son dos fotografías del mismo acumulado tomadas en momentos distintos, y la fotografía correcta es siempre la más reciente, que por construcción es la mayor. Sumarlas contaría dos veces todo lo que ambas ya sabían.

Esa lectura convierte el máximo en algo más preciso que una heurística. El conjunto de mapas ordenado por ser menor o igual en todas las casillas forma un retículo, y el máximo elemento a elemento es la cota superior mínima de dos elementos: el estado más pequeño que contiene a los dos. La fusión no está eligiendo, está calculando el menor estado compatible con toda la información disponible, que es una operación sin ninguna arbitrariedad y que no depende del dominio.

// El orden parcial del reticulo: a es menor o igual que b si lo es casilla a casilla
function menorOIgual(a, b) {
  return Object.keys(a).every((r) => a[r] <= (b[r] ?? 0));
}

function comparar(a, b) {
  const ab = menorOIgual(a, b);
  const ba = menorOIgual(b, a);
  if (ab && ba) return "iguales";
  if (ab) return "a precede a b";
  if (ba) return "b precede a a";
  return "concurrentes";
}

Ese orden tiene una consecuencia práctica que se usa mucho y se explica poco: permite saber si hace falta enviar algo. Si menorOIgual(local, remoto) es cierto, la réplica local no tiene nada que aportar y puede callarse; si es cierto al revés, el otro extremo está desactualizado y basta con mandarle el estado. Solo cuando el resultado es concurrentes hay información en ambos sentidos. Es exactamente el mismo cálculo que hacía el vector de versiones del nivel anterior, y no es una coincidencia.

Las tres propiedades, comprobadas una a una

La convergencia de esta estructura no hay que creerla, se comprueba. Conmutatividad: el máximo de dos números no depende del orden, y como la fusión aplica el máximo casilla por casilla sobre la unión de claves, el mapa resultante asigna exactamente el mismo número a cada clave en los dos sentidos. Asociatividad: el máximo de tres números es independiente del agrupamiento, y de nuevo la propiedad se hereda casilla a casilla. Idempotencia: el máximo de un número consigo mismo es ese número, de modo que fusionar un estado con otro que ya se había incorporado no cambia nada y el transporte puede reenviar cuanto quiera.

// Convergencia: mismos estados, ordenes distintos, repeticiones arbitrarias
let a = incrementar(incrementar(crear(), "ana"), "ana"); // ana: 2
let b = incrementar(crear(), "ben");                     // ben: 1
let c = incrementar(crear(), "cen", 5);                  // cen: 5

const orden1 = fusionar(fusionar(a, b), c);
const orden2 = fusionar(c, fusionar(b, a));
const repetido = fusionar(fusionar(orden1, b), b);

valor(orden1);   // 8
valor(orden2);   // 8
valor(repetido); // 8

Falta una cuarta condición que no es una ley algebraica sino una exigencia sobre las operaciones locales, y que se olvida con frecuencia: cada escritura debe producir un estado mayor o igual que el anterior en el orden del retículo. Incrementar la cumple porque solo sube una casilla. Si alguna operación local pudiera bajar una casilla, la fusión con una copia antigua la restauraría al valor alto y la operación quedaría deshecha. Esa es, palabra por palabra, la razón por la que la lección siguiente necesita una estructura distinta para restar.

La invariante que sostiene el edificio

Todo lo anterior depende de una regla que el código no impone y que conviene enunciar en voz alta: una réplica solo escribe en su propia casilla. Si dos réplicas escriben en la misma clave, el máximo vuelve a enfrentar operaciones distintas y la pérdida de actualización reaparece intacta, solo que ahora escondida bajo una estructura que parece correcta. Y la invariante se rompe de tres maneras muy concretas, las tres vistas en sistemas reales.

La defensa práctica es barata y conviene ponerla desde el primer día: la función de incremento recibe el identificador propio de un único sitio del sistema, ninguna otra ruta del código puede escribir el mapa, y una comprobación en la fusión rechaza cualquier estado entrante en el que la casilla propia sea mayor que la local, porque eso solo puede significar que otra instancia está usando tu clave. Esa comprobación cuesta una línea, no se dispara nunca en un sistema sano, y cuando se dispara ha detectado un fallo que de otro modo aparecería meses después como un total que no cuadra.