MicroPatcher un formato para la diferenciación binaria de información


Introducción
Los algoritmos de diferenciación de información tienen por objeto producir un fichero parche capaz de reconstruir una versión de una información a partir de otra versión, su versión anterior. Históricamente, para observar los cambios en información textual apareció la utilidad diff en 1970 dentro del sistema operativo Unix liberado por AT&T BELL Labs, su versión final de 1974fue escrita por Douglas McIlory [1] para ficheros de texto y en los años 80 sus salidas fueron rediseñadas para soportar ficheros binarios. El programa diff implementa un algoritmo de diferenciación basado en la comparación de las 'líneas' de cada fichero resultando muy útil en procesos de asistencia humana al control de versiones (SCCS) pero resulta poco útil cuando el objetivo que planteamos esobtener un parche mínimo.

En este sentido tenemos los algoritmos de “codificación Delta” (compresión delta o compresión diferencial) El algoritmo Delta encoding tiene como objetivo obtener solamente los bytes que han sido modificados desde la última versión del archivo, permitiendo reducir considerablemente el tamaño de éste y logrando así una optimización del uso de la red en el momento derealizar un respaldo de información.

Como algoritmos codificadores de compresión Delta tenemos los relatados en las RFC 3229 [2] (Delta Encoding in HTTP) y RFC 3284 [3] (The VCDIFF Generic Differencing and Compression Data Format).

Diferenciación binaria

La diferenciación binaria de información es pues el proceso de codificar las variaciones de dos ficheros de forma compacta, tal que podamosreconstruir el fichero objetivo dada la codificación obtenida y el fichero fuente. El algoritmo VCDIFF considera que la compresión de información es un concepto muy similar al de la diferenciación, pero sin dato fuente. Los creadores de VCDIFF observaron esto en la técnica Vdelta de D.G. Korn and K.P. Vo [4] para los que la compresión puede asimilarse perfectamente a una diferenciación inicial odiferenciación en la que la información anterior no existe. De esta manera una cadena de versiones puede codificarse como la compresión de la primera versión y la diferenciación binaria de todas las siguientes respecto a la anterior. La idea básica que surge de este concepto es unificar el esquema de procesamiento de strings de Lempel Ziv'77 (LZ'77) [5] y la técnica de movimiento de bloques deTichy [6].

En este trabajo vamos a estudiar el formato de datos binario diferenciales de Yildun Internet Backup, una propuesta original y diferente inspirada en el algoritmo rsync [7], que utiliza la diferenciación binaria de información para reconstruir la información en un remoto. Vamos a ver primeramente las consideraciones especiales que deben de tenerse en cuenta en el diseño de una estructurade datos cuando van orientados al backup o a la reconstrucción remota (sincronización remota), para después exponer detalladamente los elementos de estructura de los archivos diferenciales de Yildun. En sucesivos trabajos desarrollaremos “Un algoritmo de doble ventana para la diferenciación binaria de información” donde podremos apreciar el compromiso entre tiempo de cómputo y el grado final decompresión.

La estructura que aquí exponemos ha sido sometida a test reales de detección, rearme y autocura en sistemas con fallos (sin ventiladores y calentamiento forzado de cpu) capaces de provocar errores por calentamiento en una compresion bzip2 y no en una compresión zlib [8], resultando un procesamiento seguro y libre de errores finales: la estructura permite el rearme y el reenvío conautocura de los segmentos dañados.
La diferenciación binaria en Yildun Internet Backup
El archivo diferencial de Yildun es un archivo autocomprimido con bzip2 o zlib y contiene una colección de directorios y ficheros cualesquiera, diferenciados dos a dos, que permiten la comunicación de variaciones de información a un remoto, el cual, disponiendo de la versión anterior de información,...