Trocear ficheros grandes: bloques, cortes y deduplicación

Las dos lecciones anteriores trabajaron con grafos cuyos nodos ya venían dados: un directorio con sus entradas, un documento con sus campos. Falta la capa de abajo, la que fabrica nodos donde no había ninguno, porque el dato original es una tira continua de bytes sin estructura interna. Un vídeo de cuatro gigabytes, una imagen de disco, un volcado de base de datos: nada de eso cabe en un bloque, y todo eso necesita convertirse en un DAG para participar del esquema. La operación se llama trocear, y su parte interesante no es partir —eso lo hace cualquiera— sino decidir dónde se corta. Esa decisión, que parece un parámetro de implementación sin importancia, determina si la deduplicación funciona o si es puramente decorativa, y la diferencia entre las dos opciones evidentes es tan grande que conviene entenderla antes de escribir una línea de código.

Por qué un fichero se convierte en un grafo

Hay una razón obvia y cuatro que importan más. La obvia es el tamaño: los transportes, los almacenes y las memorias trabajan con unidades acotadas, y un bloque de cuatro gigabytes no se mueve, no se cachea y no se verifica sin materializarlo entero. Las otras cuatro justifican el troceado incluso cuando el tamaño no aprieta. Primera, la granularidad de la verificación: con un solo hash sobre el fichero entero no puedes comprobar nada hasta tener el último byte, mientras que con bloques verificas cada uno al llegar y detectas la corrupción en el acto. Segunda, la descarga paralela desde varias fuentes, que solo tiene sentido si cada trozo se autentica por separado. Tercera, la lectura parcial: si quieres el minuto cuarenta de un vídeo no deberías descargar los treinta y nueve anteriores. Cuarta, la reutilización entre versiones, que es el asunto central de esta lección.

La forma habitual del resultado es un grafo de dos clases de nodos. Las hojas contienen bytes de datos y nada más. Los nodos intermedios no contienen datos: contienen una lista ordenada de identificadores de hijos, cada uno acompañado del número de bytes que cuelgan por debajo de él. Esa segunda columna es lo que permite responder a la pregunta qué bloque contiene el byte número doscientos millones descendiendo por el grafo y sumando tamaños, sin leer un solo byte de datos.

Un fichero como DAG, con tamanos acumulados en los enlaces

  raiz del fichero
    enlace 0 -> nodo intermedio A   ...  1 048 576 bytes
    enlace 1 -> nodo intermedio B   ...  1 048 576 bytes
    enlace 2 -> nodo intermedio C   ...    262 144 bytes

  nodo intermedio A
    enlace 0 -> hoja h1  ... 262 144 bytes
    enlace 1 -> hoja h2  ... 262 144 bytes
    ...

  buscar el byte 1 300 000 es descender sumando, no leer datos

El troceado de tamaño fijo y su fragilidad

La forma inmediata de partir es cortar cada N bytes. Es trivial de implementar, produce bloques uniformes, permite calcular la posición de cualquier byte con una división y funciona perfectamente mientras el fichero no cambie nunca. En cuanto cambia, revela un defecto que lo invalida para casi todo uso interesante.

El defecto es el desplazamiento de fronteras. Inserta un byte al principio de un fichero de un gigabyte troceado en bloques de doscientos cincuenta y seis kilobytes. El primer bloque cambia, evidentemente. Pero también cambia el segundo, porque su primer byte es ahora el que antes era el último del primero, y así todos: cada frontera se ha corrido un byte y por tanto cada bloque tiene un contenido distinto y un identificador distinto. Una inserción de un byte ha invalidado cuatro mil bloques y la deduplicación entre las dos versiones es exactamente cero.

// Troceado de tamano fijo: correcto, simple y catastrofico ante inserciones
function trocearFijo(bytes, tam = 262144) {
  const trozos = [];
  for (let i = 0; i < bytes.length; i += tam) trozos.push(bytes.slice(i, i + tam));
  return trozos;   // insertar un byte al principio cambia todos los trozos
}

Merece la pena notar que el troceado de tamaño fijo no es inútil: sigue siendo la elección correcta cuando los datos son inmutables por naturaleza y solo se busca granularidad de verificación y descarga paralela, como en la distribución de artefactos que nunca se editan. El error consiste en aplicarlo a datos que evolucionan y esperar de él una deduplicación que estructuralmente no puede dar. Elegir el método de corte es, por tanto, una decisión sobre el ciclo de vida de los datos y no sobre su tamaño.

Conviene ver por qué esto no es un caso rebuscado. Editar un documento, añadir una fila al principio de un registro, cambiar una cabecera, recomprimir con otra versión de la herramienta: todas esas operaciones desplazan contenido. El troceado de tamaño fijo solo deduplica bien cuando los cambios son sustituciones que respetan la longitud, que es el caso menos frecuente en datos reales. Y la raíz del problema se puede nombrar con precisión: la frontera depende de la posición absoluta, que es justamente la magnitud que cualquier inserción o borrado altera.

El troceado definido por el contenido

La solución invierte la dependencia. En lugar de cortar donde lo dice el contador, se corta donde lo dice el contenido. Se recorre el fichero con una ventana deslizante de unas pocas decenas de bytes y se calcula sobre ella una huella barata de actualizar —una huella que se puede recalcular al avanzar un byte quitando el que sale y añadiendo el que entra, sin rehacer la ventana entera—. Cuando esa huella cumple un predicado, por ejemplo que sus últimos bits sean todos cero, se declara una frontera ahí mismo.

// Troceado por contenido: la frontera la decide la ventana, no el indice
function trocearPorContenido(bytes, { min = 65536, medio = 262144, max = 1048576 }) {
  const mascara = medio - 1;          // longitud media esperada de 2 elevado a k
  const trozos = [];
  let huella = 0, inicio = 0;
  for (let i = 0; i < bytes.length; i++) {
    huella = rodar(huella, bytes[i], bytes[i - 48]);   // ventana de 48 bytes
    const largo = i - inicio + 1;
    if (largo < min) continue;                          // suelo para no fragmentar
    if ((huella & mascara) === 0 || largo >= max) {     // frontera o techo
      trozos.push(bytes.slice(inicio, i + 1));
      inicio = i + 1;
      huella = 0;
    }
  }
  if (inicio < bytes.length) trozos.push(bytes.slice(inicio));
  return trozos;
}

La propiedad que se obtiene a cambio es la resincronización local. Si insertas un byte en medio del fichero, la ventana deslizante cambia solo mientras el byte insertado está dentro de ella, es decir, durante unas decenas de posiciones. Las fronteras anteriores no se enteran porque dependen de bytes que no se han tocado, y las posteriores tampoco, porque en cuanto la ventana deja atrás la zona alterada vuelve a ver exactamente la misma secuencia que antes. El daño queda confinado al bloque que contiene la inserción y, como mucho, al siguiente.

flowchart LR
V1[version original] --> C1[bloque a] --> C2[bloque b] --> C3[bloque c] --> C4[bloque d]
V2[version con insercion en b] --> D1[bloque a] --> D2[bloque b prima] --> D3[bloque c] --> D4[bloque d]
style C1 fill:#a6e3a1,color:#11111b
style D1 fill:#a6e3a1,color:#11111b
style C3 fill:#a6e3a1,color:#11111b
style D3 fill:#a6e3a1,color:#11111b
style D2 fill:#f38ba8,color:#11111b

Los tres parámetros del código merecen comentario porque su elección tiene consecuencias medibles. La máscara fija la longitud media esperada, que sigue una distribución geométrica: la mayoría de los bloques rondan la media, pero la cola es larga. El mínimo evita que una racha desafortunada produzca bloques diminutos que disparen los metadatos, y el máximo evita el caso contrario, un tramo de datos muy uniformes —una región de ceros, por ejemplo— donde la huella nunca cumple el predicado y el bloque crecería sin freno. Sin esos dos topes el algoritmo funciona igual pero su varianza lo hace inservible en producción.

Hay un matiz sobre el troceado por contenido que suele omitirse y que cambia las expectativas. El corte estable protege ante inserciones y borrados, pero no protege ante transformaciones que reescriben todo el flujo de bytes. Comprimir un fichero, cifrarlo con un modo que encadena bloques o volver a codificarlo produce una secuencia completamente distinta desde el primer byte, y la deduplicación cae a cero por muy bueno que sea el algoritmo de corte. De ahí una regla práctica que ahorra decepciones: si quieres deduplicar, trocea antes de comprimir y antes de cifrar, y comprime o cifra cada bloque por separado, aceptando la peor ratio de compresión que eso implica.

Lo que gana la deduplicación y lo que cuesta

Y hay un efecto colateral del troceado por contenido que rara vez se enuncia y que conviene aprovechar: como el corte es determinista y depende solo de los bytes, dos personas que troceen el mismo fichero con los mismos parámetros obtienen exactamente los mismos bloques sin haberse coordinado. El troceado deja de ser una decisión privada de cada almacén y pasa a ser una función pública del contenido, y por eso los parámetros —ventana, máscara, mínimo y máximo— forman parte del contrato del sistema tanto como el formato de los nodos. Cambiarlos en una versión nueva rompe la deduplicación con todo lo troceado antes.

Con fronteras estables ante desplazamientos, la deduplicación pasa de anecdótica a estructural, y actúa en cuatro planos distintos que conviene no mezclar. Dentro de un mismo fichero, cuando hay contenido repetido. Entre versiones sucesivas del mismo fichero, que es el caso que motiva todo. Entre ficheros distintos que comparten regiones, como dos imágenes de máquina virtual con el mismo sistema base. Y entre usuarios distintos de un almacén compartido, donde el ahorro se multiplica por el número de participantes sin que ninguno haga nada.

La tercera tarjeta es el compromiso central y conviene ponerle números aproximados. Con hojas de un kilobyte, un fichero de un gigabyte genera un millón de bloques, un millón de identificadores en nodos internos y un millón de entradas en el índice que traduce identificador a ubicación; el ahorro por deduplicación se lo come la contabilidad. Con hojas de un megabyte, la contabilidad es despreciable pero cualquier cambio invalida un megabyte entero y el ahorro se desploma. El punto razonable está en el medio y depende del perfil de los datos, no de una constante universal.

Conviene añadir que el índice de identificador a ubicación es la pieza que más se subestima al planificar. No es un fichero de configuración: es una tabla con una entrada por bloque distinto del almacén, que debe consultarse en cada escritura para saber si el bloque ya estaba, y que por tanto quiere vivir en memoria o en una estructura muy rápida. Cuando el almacén crece hasta cientos de millones de bloques, ese índice se convierte en el recurso limitante del sistema entero, y la decisión de tamaño de bloque acaba tomándose en función de él y no del ahorro en datos.

La cuarta tarjeta señala un riesgo que se olvida con frecuencia porque no es de rendimiento. Si un almacén compartido deduplica entre usuarios, alguien que sospeche qué fichero tienes puede trocearlo él mismo, calcular los identificadores y preguntar si existen; una respuesta afirmativa confirma la sospecha sin haber accedido a nada. La deduplicación entre usuarios y la confidencialidad frente al operador del almacén son objetivos en tensión, y resolverlo exige o bien renunciar a la deduplicación cruzada, o bien derivar las claves del propio contenido, con las implicaciones que eso tiene y que el track retomará al hablar de cifrado.