El problema: descubrir la diferencia sin transmitir el estado

Todo lo construido en los niveles anteriores da por hecho un paso que casi nunca se enuncia: que las réplicas se han intercambiado lo que les faltaba. Los CRDT garantizan que si dos réplicas reciben las mismas operaciones convergen, pero no dicen ni una palabra sobre cómo averiguar qué operaciones le faltan a la otra. El almacén direccionado por contenido garantiza que un bloque con el mismo nombre es el mismo bloque, pero no dice qué nombres tiene el vecino. Esa laguna es precisamente el problema de la reconciliación, y resolverlo mandando el estado entero es tan correcto como inviable: un cuaderno con diez años de notas son cientos de megabytes, la sincronización ocurre cada pocos segundos y la divergencia típica son tres operaciones. Pagar cientos de megabytes para descubrir que faltaban tres operaciones no es una ineficiencia menor, es un error de categoría. Esta lección enuncia el problema con la precisión suficiente para poder medirlo, demuestra por qué las respuestas obvias fracasan por el mismo motivo, establece cuál es el coste mínimo teórico de la pregunta y presenta las tres familias de mecanismos que el resto del nivel desarrolla, cada una pagando ese mínimo en una moneda distinta.

Enunciar el problema con precisión

Conviene fijar el vocabulario antes de discutir mecanismos, porque casi todos los errores de diseño de esta capa vienen de haber mezclado preguntas que tienen respuestas de coste muy distinto. La primera pregunta es de detección: difieren estas dos réplicas. La segunda es de localización: en qué difieren exactamente. La tercera, que suele darse por supuesta, es de obtención: cómo consigo los bytes que me faltan una vez sé sus nombres. Un protocolo puede resolver la primera en un mensaje y seguir siendo pésimo en la segunda, y puede resolver las dos primeras a la perfección y quedarse colgado en la tercera porque quien tiene los datos está desconectado.

Formalmente, cada réplica guarda un conjunto de elementos identificables de forma estable: operaciones con su identificador, bloques con su hash, claves con su versión. Llamemos n al número de elementos que guarda cada una y d al tamaño de la diferencia simétrica, es decir, al número de elementos que uno tiene y el otro no, contando los dos sentidos. La reconciliación termina cuando ambos extremos poseen la unión. Lo que se mide no es si termina, sino cuánto ha costado, y el coste tiene cuatro dimensiones que compiten entre sí y que hay que apuntar por separado porque optimizar una empeora otra.

Las cuatro dimensiones del coste de una sincronizacion

  bytes transmitidos ..... lo unico que casi todos miden
  rondas de red .......... multiplican por la latencia y no por el ancho de banda
  computo local .......... hashes, indices, arboles que hay que mantener o construir
  metadatos guardados .... lo que hay que conservar entre sincronizaciones para que funcione

La cuarta dimensión es la que se olvida y la que más caro sale. Un mecanismo que transmite pocos bytes porque mantiene una tabla auxiliar en cada réplica ha trasladado el coste del enlace al disco, y esa tabla habrá que actualizarla en cada escritura, conservarla íntegra durante meses y decidir qué hacer cuando alguien la borre. La comparación honesta entre dos mecanismos de reconciliación solo se puede hacer si se cuentan las cuatro columnas a la vez, y la mayoría de las comparaciones publicadas solo cuentan la primera.

Lo que cuestan las respuestas ingenuas

La respuesta más simple es mandar el estado entero y dejar que el receptor mezcle. Es correcta sin matices, no necesita metadatos, funciona con cualquier transporte y sigue siendo la mejor opción cuando el estado es pequeño o cuando la divergencia es tan grande que cualquier otra cosa terminaría transmitiendo casi lo mismo tras muchas rondas. Su problema es que su coste es n y no depende de d, de modo que sincronizar dos veces por minuto un estado de cien megabytes que ha cambiado en tres bytes cuesta lo mismo que la primera sincronización de la historia.

El primer refinamiento evidente es no mandar los datos sino sus nombres, y que el otro pida lo que no reconozca. Es una mejora real, porque cambia el tamaño medio de un elemento por el tamaño de un identificador, y en muchos dominios eso es un factor de cien o de mil. Pero no cambia la naturaleza del coste: sigue siendo proporcional a n. Con diez millones de elementos e identificadores de treinta y dos bytes, el catálogo pesa trescientos veinte megabytes, y hay que enviarlo entero cada vez para descubrir que sobraban tres.

// Tres respuestas ingenuas, con su coste dominante
async function estadoEntero(remoto) {
  await remoto.recibir(await leerTodo());        // n bytes, una ronda
}

async function catalogoDeNombres(remoto) {
  const mios = await listarIdentificadores();    // n hashes, una ronda
  const faltan = await remoto.cualesNoTienes(mios);
  await remoto.recibir(await leer(faltan));      // luego d elementos
}

async function porFecha(remoto, desde) {
  const cambiados = await leerModificadosDesde(desde);
  await remoto.recibir(cambiados);               // barato y silenciosamente incorrecto
}

La tercera función merece un comentario aparte porque es, con diferencia, la más usada y la más rota. Preguntar qué ha cambiado desde una fecha traslada la corrección del protocolo a la sincronía de los relojes, que el nivel de relojes lógicos ya desmontó: basta con que una réplica tenga el reloj atrasado para que sus escrituras caigan por debajo del corte y no se envíen nunca. El fallo no produce un error visible sino una ausencia, y las ausencias no se detectan hasta que alguien echa de menos un dato meses después.

Cuánto hay que decirse como mínimo

La teoría de la complejidad de la comunicación da una respuesta incómoda a la pregunta más simple. Decidir con certeza y de forma determinista si dos estados de n bits son iguales exige, en el peor caso, intercambiar del orden de n bits: no hay resumen determinista que valga, porque para cualquier resumen más corto existen dos estados distintos que lo comparten y un adversario puede elegirlos. La única salida es renunciar a la certeza absoluta y aceptar aleatoriedad, y entonces bastan unas decenas de bits. Eso es exactamente lo que hace comparar dos raíces de Merkle: un protocolo aleatorizado de coste constante cuya probabilidad de error es la probabilidad de una colisión.

Para la segunda pregunta, la de localizar, el límite es de otro tipo y es más útil todavía. Si la diferencia consta de d elementos tomados de un universo de identificadores de treinta y dos bytes, nombrar esos elementos requiere al menos d por treinta y dos bytes, porque hay que decir cuáles son. Ese es el suelo. Lo importante es que en ese suelo no aparece n por ningún lado: existe, en principio, un protocolo cuyo coste depende solo de lo que difiere y es indiferente al tamaño de lo que se guarda. Todo el nivel consiste en aproximarse a ese suelo por caminos distintos.

Diez millones de elementos, tres de diferencia, identificadores de 32 bytes

  estado entero .............. cientos de megabytes    1 ronda
  catalogo de nombres ........ 320 MB                   2 rondas
  suelo teorico .............. 96 bytes                 desconocido
  arbol de hashes ............ unos pocos KB            log n rondas
  filtro invertible .......... unos pocos KB            1 o 2 rondas

El hueco entre la tercera fila y las dos últimas es donde vive la ingeniería de este nivel. Nadie alcanza el suelo, porque el suelo supone conocer d de antemano y conocer d es ya casi resolver el problema, pero se puede quedar cerca pagando en una de dos monedas: rondas de red, que es lo que hace el descenso por un árbol de hashes, o probabilidad de error, que es lo que hacen los filtros. Y conviene tener presente que las rondas no son gratis: en un enlace intercontinental con ciento cincuenta milisegundos de ida y vuelta, veinte rondas son tres segundos de espera pura, con independencia de que los mensajes pesen doce bytes.

flowchart TB
P1[detectar si hay diferencia] --> R1[coste constante con un resumen]
P1 --> P2[localizar en que difieren]
P2 --> R2[coste segun el tamano de la diferencia]
P2 --> P3[obtener los bytes que faltan]
P3 --> R3[problema de la capa de red y de disponibilidad]
style R1 fill:#a6e3a1,color:#11111b
style R2 fill:#f9e2af,color:#11111b
style R3 fill:#f38ba8,color:#11111b

Las tres familias y las tres monedas

Las tres familias resuelven el mismo problema y se diferencian en qué recurso están dispuestas a gastar. La contabilidad compra exactitud y una sola ronda a cambio de memoria: metadatos que crecen con el número de réplicas y un registro que no se puede podar por debajo de lo que le falta al más rezagado. El resumen recursivo compra independencia de metadatos a cambio de latencia: no necesita recordar nada sobre el interlocutor, pero paga una ronda por nivel del árbol. El boceto probabilístico compra tamaño de mensaje a cambio de certeza: cabe en un paquete y a veces se equivoca, de modo que necesita una segunda pasada o un mecanismo de reparación.

Esa manera de mirarlo también explica por qué ningún sistema serio elige uno solo. Cada mecanismo tiene un régimen en el que degenera —el vector cuando las réplicas se multiplican, el árbol cuando la divergencia es masiva, el filtro cuando la diferencia es mayor de lo previsto— y el diseño maduro consiste en tener un mecanismo barato para el caso frecuente y una vía de escape para el caso raro. La última lección del nivel se dedica precisamente a esa composición, pero conviene sospechar desde ya de cualquier respuesta que empiece por el nombre de un algoritmo en lugar de por una medida del estado.