Más allá de la convergencia: calidad, rendimiento y sus límites

El nivel treinta y tres dejó una frase que ahora se vuelve operativa: la convergencia es necesaria y no es suficiente. Un sistema puede pasar diez mil historias generadas, coincidir siempre y producir documentos que ninguna persona escribió. La buena noticia es que el simulador, el generador y el reductor ya construidos no sirven solo para la propiedad de convergencia: son infraestructura reutilizable, y añadir una propiedad de calidad cuesta escribir un predicado nuevo y nada más. La no intercalación maximal del nivel treinta y cuatro se convierte en seis líneas de código; la preservación de la intención, en una familia de aserciones sobre lo que puede y no puede aparecer en el resultado; incluso el rendimiento admite formularse como propiedad si se enuncia sobre la forma asintótica y no sobre milisegundos. Y luego está la parte que cierra el nivel y que conviene decir sin adornos: hay tres clases de garantía que este método no puede dar, y confundirlas con las que sí da es el error que deja sistemas rotos con la suite en verde.

La no intercalación como aserción ejecutable

La propiedad se enuncia en el nivel treinta y cuatro en términos de orígenes izquierdo y derecho, pero su consecuencia observable es mucho más simple de comprobar: cada aportación concurrente debe seguir siendo una subsecuencia contigua del resultado. Si una réplica insertó tres caracteres seguidos y en el documento final esos tres caracteres no aparecen juntos, algo se ha intercalado. Basta con que el generador etiquete cada elemento con la réplica y el instante que lo produjo para que la aserción sea directa.

// resultado: lista ordenada de identificadores vivos en el documento final.
// aportacion: identificadores que una replica inserto consecutivamente.
function esContigua(resultado, aportacion) {
  const pos = aportacion.map((id) => resultado.indexOf(id));
  if (pos.some((p) => p < 0)) return false;
  return pos.every((p, i) => i === 0 || p === pos[i - 1] + 1);
}

const bien = ['a1', 'a2', 'a3', 'b1', 'b2'];
const mal  = ['a1', 'b1', 'a2', 'b2', 'a3'];
console.log(esContigua(bien, ['a1', 'a2', 'a3']));  // true
console.log(esContigua(mal,  ['a1', 'a2', 'a3']));  // false

Dos observaciones sobre lo que esta aserción hace y lo que deja libre, porque ilustran la diferencia entre prohibir y prescribir. Prohíbe el troceado, que es lo que ninguna persona tolera, y no dice absolutamente nada sobre cuál de las dos aportaciones va primero, porque cualquiera de los dos órdenes es defendible y elegirlo es una decisión legítima del algoritmo. Un predicado bien calibrado deja más de un resultado admisible y menos de todos; este deja exactamente dos por cada par de aportaciones concurrentes.

La parte delicada no está en el predicado sino en el generador, que ahora debe producir la situación que la propiedad vigila. Historias donde dos réplicas insertan ráfagas de varios caracteres en la misma posición, partiendo del mismo estado y sin haberse visto. Un generador de operaciones sueltas en posiciones aleatorias casi nunca produce esa configuración, y la propiedad pasaría siempre sin haber mirado nunca donde importa.

Preservación de la intención y otras propiedades de calidad

La contigüidad es un caso particular de una familia más amplia, la de las aserciones que relacionan el estado final con las operaciones que lo produjeron en lugar de relacionar réplicas entre sí. Todas comparten una forma: nada aparece que nadie escribiera, nada desaparece que nadie borrara.

function sinInvenciones(resultado, insertados, borrados) {
  const vivos = insertados.filter((id) => !borrados.has(id));
  return resultado.length === vivos.length
      && resultado.every((id) => insertados.includes(id));
}

La cuarta tarjeta introduce una diferencia técnica que conviene marcar. Las tres primeras son propiedades del estado de reposo y se comprueban una vez al terminar la historia; la monotonía de lecturas es una invariante intermedia y se comprueba en cada paso del simulador. Instrumentar el bucle para evaluar invariantes tras cada evento multiplica el coste de cada historia pero detecta el fallo en el instante en que ocurre, no al final, lo que hace la reducción mucho más eficaz porque el guion culpable es más corto por construcción.

Las cuatro aserciones comparten un requisito que obliga a tocar el simulador y que suele descubrirse tarde: necesitan procedencia. Para afirmar que nada se inventó hay que saber qué operaciones existieron, quién las emitió y en qué instante, de modo que el simulador debe llevar un registro paralelo de todo lo aplicado además del estado de cada réplica. Ese registro no forma parte del sistema bajo prueba y no debe influir en él; es el modelo de referencia contra el que se juzga el resultado, y mantenerlo estrictamente separado del estado replicado es lo que impide el error clásico de comparar el sistema consigo mismo.

El rendimiento como propiedad

El instinto dice que el rendimiento se mide con bancos de pruebas y no con propiedades, y es correcto para las cifras absolutas. Pero hay una clase de afirmación sobre rendimiento que sí es una propiedad y que es la que de verdad importa en un CRDT: la forma del coste. Que la memoria en reposo no dependa de la longitud de la historia sino del texto visible; que la fusión no crezca cuadráticamente con la longitud de las ramas divergentes; que abrir un documento no dependa del número de operaciones que alguna vez existieron.

Esas afirmaciones se comprueban midiendo a varios tamaños y estimando el exponente empírico, no comparando contra un umbral en milisegundos que dependerá de la máquina y volverá la prueba inestable.

// Pendiente de la recta en escala logaritmica: el exponente del coste.
function exponente(medidas) {
  const n = medidas.length;
  const lx = medidas.map(([x]) => Math.log(x));
  const ly = medidas.map(([, y]) => Math.log(y));
  const mx = lx.reduce((a, v) => a + v, 0) / n;
  const my = ly.reduce((a, v) => a + v, 0) / n;
  let num = 0, den = 0;
  for (let i = 0; i < n; i += 1) {
    num += (lx[i] - mx) * (ly[i] - my);
    den += (lx[i] - mx) ** 2;
  }
  return num / den;
}

console.log(exponente([[100, 100], [200, 200], [400, 400], [800, 800]]));   // 1
console.log(exponente([[100, 1e4], [200, 4e4], [400, 16e4], [800, 64e4]])); // 2

Con esa función la propiedad se enuncia como una cota sobre el exponente: al medir el coste de fusión para ramas de cien, doscientas, cuatrocientas y ochocientas operaciones, el exponente estimado debe quedar por debajo de uno coma cinco. Es una aserción estable frente al hardware, frente al ruido del recolector de basura y frente a la máquina de integración continua, porque la pendiente en escala logarítmica es invariante ante factores multiplicativos constantes. Un servidor tres veces más lento desplaza la recta y no cambia su pendiente.

Que se puede afirmar sobre rendimiento y como

  cifra absoluta ........ banco de pruebas, entorno fijo, alta varianza
  regresion relativa .... comparar contra la version anterior, util y fragil
  forma asintotica ...... exponente en escala logaritmica, estable y barato
  cota de memoria ....... memoria residente frente a texto visible, no a historia

Qué no se puede probar así

Queda la parte que cierra el nivel y que hay que decir con precisión, porque el entusiasmo con esta técnica produce una confianza que no le corresponde. Hay tres clases de garantía que el muestreo no da, y ninguna de las tres se arregla con más casos.

La primera es la ausencia de errores. Una propiedad que pasa diez mil veces afirma que no se encontró contraejemplo en diez mil puntos de un espacio de veintidós dígitos, y no afirma nada más. Para pasar de ahí a una garantía universal hace falta cambiar de método: verificación de modelos, que recorre exhaustivamente un espacio acotado, o demostración mecanizada, que razona sobre el espacio entero. Los dos existen, los dos se han aplicado a esta clase de algoritmos y los dos son órdenes de magnitud más caros.

La segunda es toda propiedad que hable de un tiempo no acotado. Convergencia eventual significa que si el flujo de operaciones cesa y la red se recupera, las réplicas acabarán coincidiendo; la palabra clave es acabarán, y ninguna ejecución finita puede refutar una promesa sobre un futuro sin plazo. Lo que el simulador comprueba en realidad es una versión más fuerte y más modesta a la vez: que en el estado de reposo que él define, las réplicas coinciden. Que ese reposo se alcance en la vida real es una hipótesis sobre el transporte, no un resultado de la prueba.

La tercera es la aceptabilidad misma. Que el resultado de fusionar sea algo que una persona reconocería como su trabajo no es un teorema sino una definición, y alguien tiene que escribirla para cada tipo de dato del dominio. El generador no la descubre y el predicado no la deduce: el predicado es esa definición, y su calidad es exactamente la calidad del juicio de quien lo redactó. El nivel treinta y cuatro pudo formalizar la no intercalación porque alguien dedicó un artículo entero a definirla; para el modelo de datos concreto de tu aplicación no existe ese artículo.

Que compra cada metodo y que deja fuera

  ejemplo ............ memoria de un comportamiento observado
  propiedad .......... exploracion dirigida dentro del alcance del generador
  verificacion ....... exhaustividad dentro de cotas pequenas del modelo
  demostracion ....... universalidad sobre el modelo formalizado
  ninguno ............ que el enunciado sea el correcto para tu dominio

La última fila no es una broma retórica: es la casilla donde vive la mayoría de los fallos que llegan al usuario, y la única cuyo trabajo no se puede comprar ni automatizar.