Las tres consecuencias: inmutabilidad, deduplicación y verificación

La lección anterior estableció el giro conceptual; esta se ocupa de cobrarlo. De la decisión de calcular el nombre a partir de los bytes se siguen inmediatamente tres propiedades que en un sistema por ubicación son características costosas que hay que construir, defender y mantener: la inmutabilidad de todo lo almacenado, la fusión automática de contenidos idénticos y la posibilidad de verificar cualquier respuesta sin consultar a nadie. Lo notable no es que se obtengan, sino que se obtengan sin código: no hay un módulo de inmutabilidad, ni un proceso de deduplicación, ni un servicio de verificación. Son consecuencias aritméticas de la definición del nombre, y por tanto no se pueden desactivar por descuido, ni se degradan bajo carga, ni tienen fallos de configuración. Esta lección desmonta cada una, señala el precio escondido de cada una y muestra al final que las tres son la misma observación mirada desde tres sitios distintos.

Inmutabilidad: cambiar el contenido es cambiar de nombre

En un almacén por ubicación, modificar un fichero es una operación natural: se abre la ruta, se escriben bytes nuevos y el nombre sigue siendo el mismo. En un almacén por contenido esa operación sencillamente no está disponible, y no porque alguien la haya prohibido, sino porque no significa nada. Si los bytes cambian, el resumen cambia, y por tanto lo que se ha creado es otra entrada con otro nombre. El bloque anterior sigue exactamente donde estaba, con su nombre intacto, y nadie lo ha tocado.

Conviene subrayar la diferencia con la inmutabilidad que ofrecen otros sistemas, porque es de otra naturaleza. Un almacén de objetos puede ofrecer un modo de solo escritura, y una base de datos puede ofrecer tablas de solo añadir; en ambos casos la inmutabilidad es una regla que el sistema aplica y que alguien con privilegios suficientes puede levantar. Aquí no hay regla que levantar: la única forma de que un nombre devuelva bytes distintos sería encontrar una colisión de la función resumen, que es precisamente el problema que se supone computacionalmente inabordable.

// Actualizar no existe: lo que hay es crear una version nueva
const v1 = await guardar(almacen, texto('borrador inicial'));
const v2 = await guardar(almacen, texto('borrador revisado'));

// v1 sigue disponible, intacto y con su nombre original
console.log(v1 !== v2);              // true, siempre
console.log(await leer(almacen, v1)); // borrador inicial, para siempre

Esa propiedad tiene un efecto en cascada sobre la concurrencia que es fácil pasar por alto y que es enorme. Dos procesos escribiendo a la vez el mismo contenido no compiten por nada: ambos calculan el mismo nombre y ambos escriben los mismos bytes en el mismo sitio, de modo que la operación de escritura es idempotente y no necesita bloqueo. Dos procesos escribiendo contenidos distintos tampoco compiten, porque van a nombres distintos. La escritura, que en cualquier otro almacén es el punto donde vive toda la coordinación, aquí deja de necesitarla por completo.

El precio de todo esto es el crecimiento, y conviene mirarlo de frente antes de celebrar nada. Si cada versión de cada cosa permanece disponible para siempre, el almacén solo crece, y la pregunta de qué se puede tirar se convierte en un problema de alcanzabilidad idéntico al de un recolector de basura: un bloque se puede borrar cuando nadie lo referencia, y averiguar quién referencia a quién exige recorrer el grafo desde las raíces vivas. Es un problema conocido y con soluciones conocidas, pero es trabajo nuevo que en un almacén mutable no existía, porque allí sobrescribir liberaba el espacio automáticamente.

Deduplicación: lo idéntico se fusiona sin que nadie lo pida

La segunda consecuencia es que dos ficheros con el mismo contenido tienen el mismo nombre y por tanto ocupan una sola entrada. No hay un proceso que los detecte, ni una ventana de tiempo en la que todavía estén duplicados, ni una tarea nocturna que los consolide: es que nunca llegaron a ser dos cosas. Un mil usuarios que suben el mismo adjunto producen un almacenamiento igual al de uno solo, y lo hacen sin coordinarse entre sí y sin que el sistema lo advierta.

flowchart TB
A[usuario A sube un fichero] --> H[funcion resumen]
B[usuario B sube el mismo fichero] --> H
C[copia de seguridad del ano pasado] --> H
H --> N[un unico nombre]
N --> S[una unica copia almacenada]
style H fill:#cba6f7,color:#11111b
style S fill:#a6e3a1,color:#11111b

La pregunta interesante no es si hay deduplicación, sino a qué granularidad ocurre, porque de ahí sale toda su eficacia real. Si el nombre se calcula sobre el fichero entero, dos ficheros que difieren en un byte no comparten nada. Si el fichero se trocea en bloques y cada bloque se nombra por su contenido, dos versiones parecidas comparten todos los bloques que no cambiaron. Y si el troceo se hace en fronteras fijas, insertar un byte al principio desplaza todo lo demás y arruina la coincidencia, motivo por el cual los sistemas serios usan troceo definido por el propio contenido, donde las fronteras se deciden con una función deslizante sobre los bytes y sobreviven a las inserciones.

// Frontera decidida por el contenido: una ventana deslizante sobre los bytes
function trocear(bytes, mascara = 0x1fff) {
  const bloques = []; let inicio = 0, huella = 0;
  for (let i = 0; i < bytes.length; i++) {
    huella = ((huella << 1) + bytes[i]) >>> 0;      // huella deslizante
    if ((huella & mascara) === 0 || i - inicio > 65536) {
      bloques.push(bytes.subarray(inicio, i + 1));  // aqui corta el dato
      inicio = i + 1;
    }
  }
  if (inicio < bytes.length) bloques.push(bytes.subarray(inicio));
  return bloques;   // insertar un byte al inicio solo altera el primer bloque
}

# Las herramientas de copia de seguridad serias usan esta tecnica
restic backup /datos          # deduplica entre instantaneas y entre maquinas
borg create repo::hoy /datos  # mismo principio, distinta implementacion

Merece la pena nombrar el coste, porque existe y suele omitirse. La deduplicación acopla la vida de los datos: un bloque compartido por diez ficheros no se puede borrar al borrar uno de ellos, lo que obliga a llevar una cuenta de referencias o a hacer recorridos de alcanzabilidad, exactamente igual que un recolector de basura. Y acopla también su seguridad: en un servicio multiusuario, que la subida de un fichero sea instantánea revela que ese fichero ya estaba, lo que permite a un atacante confirmar la presencia de un contenido que sospecha. Los sistemas que se toman esto en serio deduplican dentro de un ámbito de confianza y no entre ámbitos distintos.

Verificación: comprobar es recalcular

La tercera consecuencia es que quien recibe unos bytes puede decidir por su cuenta si son los que pidió, sin preguntar a nadie y sin confiar en nadie. Recalcula el resumen y lo compara con el nombre que tenía. Si coincide, la respuesta es correcta con la misma certeza con la que la función resumen es resistente; si no coincide, la respuesta se descarta y se pide a otro. Es la operación más barata de todo el sistema y la que soporta más peso.

Conviene delimitar con precisión qué cubre y qué no, porque aquí se acumulan la mayoría de los malentendidos. La verificación establece que los bytes recibidos son los bytes nombrados. No establece que esos bytes sean recientes, ni que quien los envió tenga derecho a tenerlos, ni que el nombre que tú tienes sea el nombre que deberías tener. Esas tres preguntas se responden en otras capas, y confundirlas con la integridad es la forma más común de construir un sistema que parece verificado y no lo está.

Hay un detalle de implementación que decide si la verificación es utilizable en la práctica y que en el papel nunca aparece: el momento en que se puede comprobar. Si el nombre cubre un fichero de dos gigabytes, hay que recibirlo entero antes de saber si sirve, lo que obliga a almacenar en un lugar provisional una carga potencialmente hostil. Si el fichero está representado como un árbol de bloques pequeños, cada bloque se verifica al llegar y se puede empezar a entregar el resultado en cuanto llega el primero. Esa es la razón real por la que estos sistemas trocean, y no el ahorro de espacio.

// Verificacion incremental: nada sin comprobar llega al consumidor
async function* entregar(nombreRaiz, fuente) {
  const nodo = await pedirYVerificar(nombreRaiz, fuente);
  for (const hijo of nodo.hijos) {
    if (hijo.esHoja) yield await pedirYVerificar(hijo.nombre, fuente);
    else yield* entregar(hijo.nombre, fuente);   // se valida en cada nivel
  }
}

Conviene además ser explícito sobre una asimetría en el coste del fallo. Verificar y aceptar cuesta un recorrido de los bytes; verificar y rechazar cuesta lo mismo más el ancho de banda desperdiciado. Eso significa que un adversario que solo pueda enviar basura consigue, como mucho, hacernos gastar tráfico, y que la defensa contra él no es criptográfica sino económica: penalizar a la fuente que falla y no volver a preguntarle. Con troceo fino, además, ese desperdicio queda acotado al tamaño de un bloque en lugar de al del fichero entero, lo que convierte un ataque de agotamiento en una molestia.

Las tres son la misma propiedad vista desde tres sitios

Vale la pena cerrar señalando que no se trata de tres características, sino de una sola observación formulada de tres maneras. La función resumen define una correspondencia inyectiva entre secuencias de bytes y nombres: cada contenido tiene un nombre y, en la práctica, cada nombre tiene un único contenido. La inmutabilidad es esa inyectividad leída de izquierda a derecha: si el contenido cambia, el nombre tiene que cambiar. La deduplicación es la misma leída al revés: si el nombre coincide, el contenido es el mismo, luego no hace falta guardarlo dos veces. Y la verificación es la comprobación de que la correspondencia se cumple en un caso concreto.

El matiz de en la práctica que aparece en esa frase no es un descuido y conviene desarrollarlo, porque marca el único punto donde el edificio se apoya en una hipótesis y no en un teorema. Hay infinitas secuencias de bytes y un número finito de nombres, de modo que las colisiones existen necesariamente; lo que no existe es un método conocido para encontrarlas. Con una salida de doscientos cincuenta y seis bits, la probabilidad de tropezar con una por azar es tan pequeña que resulta irrelevante frente a la de que falle el hardware que ejecuta la comparación. La inyectividad, por tanto, no es matemática sino computacional, y su validez está atada a que la función elegida siga sin estar rota. Esa es exactamente la razón por la que los nombres deben declarar qué función los produjo.

// Las tres propiedades salen de la misma comprobacion, escrita una vez
const n1 = await guardar(almacen, bytesA);
const n2 = await guardar(almacen, bytesA);   // dedup: mismo nombre, una copia
const n3 = await guardar(almacen, bytesB);   // inmutabilidad: otro nombre
await leer(almacen, n1);                     // verificacion: recalcular y comparar
console.log(n1 === n2, n1 !== n3);           // true true