algorithm - Algoritmo para la difusión eficiente de grandes archivos.

diff rcs (5)

Tengo que almacenar dos archivos A y B que son muy grandes (como 100 GB). Sin embargo, es probable que B sea similar en partes grandes a A, por lo que podría almacenar A y diff (A, B). Hay dos aspectos interesantes de este problema:

Los archivos son demasiado grandes para ser analizados por cualquier biblioteca de datos que conozco porque están en la memoria
En realidad, no necesito una diferencia. Una diferencia típicamente tiene inserciones, ediciones y eliminaciones porque está pensada para que la lean los humanos. Puedo obtener menos información: solo necesito "nuevo rango de bytes" y "copiar bytes de un archivo antiguo de un desplazamiento arbitrario".

Actualmente no entiendo cómo calcular el delta de A a B en estas condiciones. ¿Alguien sabe de un algoritmo para esto?

Nuevamente, el problema es simple: escriba un algoritmo que pueda almacenar los archivos A y B con la menor cantidad de bytes posible, dado que ambos son bastante similares.

Información adicional: aunque las partes grandes pueden ser idénticas, es probable que tengan diferentes compensaciones y estén fuera de servicio. El último hecho es por qué un diferencial convencional puede no ahorrar mucho.

Dependiendo de sus requisitos de rendimiento, podría obtener muestras de los trozos de huellas dactilares y aumentarlos cuando coincidan. De esa manera, no tiene que ejecutar una suma de comprobación en todo su archivo grande.

Si necesita alineaciones de bytes arbitrarias y realmente le importa el rendimiento, observe el algorithm simhash y utilícelo para encontrar bloques similares pero no alineados.

Eche un vistazo al algoritmo RSYNC, ya que está diseñado para hacer exactamente esto para que pueda copiar deltas de manera eficiente. Y el algoritmo está bastante bien documentado, como recuerdo.

Ese es exactamente el problema conocido como "deduplicación de datos" . El enfoque más utilizado es:

Leer sobre los archivos en bloques:
- Dividir los datos de los llamados "trozos". El enfoque más utilizado se denomina "Separación de contenido definido utilizando el método de huellas dactilares de Rabins" ( Code ). El uso de ese enfoque de fragmentación conduce a una mejor deduplicación en la mayoría de los conjuntos de datos que luego utiliza fragmentos de tamaño estático (por ejemplo, se muestra here ).
- Haga una huella digital de los fragmentos utilizando un método criptográfico de huellas digitales, por ejemplo, SHA-256.
- Almacene las huellas digitales en un índice y busque cada fragmento si ya se conoce la huella digital. Si se conoce la huella dactilar, no es necesario almacenar el fragmento por segunda vez. Solo cuando no se conoce la huella dactilar, los datos deben almacenarse.

Tal algoritmo de deduplicación de datos no es tan exacto como, por ejemplo, xdelta , pero es más rápido y más escalable para grandes conjuntos de datos. La fragmentación y la toma de huellas dactilares se realizan con aproximadamente 50 MB / s por núcleo (Java). El tamaño del índice depende de las redundancias, el tamaño del fragmento y el tamaño de los datos. Para 200 GB, debe caber en la memoria para tamaños de trozos de, por ejemplo, 16 KB.

El enfoque de compresión de Bentleys y Mciloys es muy similar (utilizado, por ejemplo, por Googles BigTable), sin embargo, no tengo conocimiento de ninguna herramienta de línea de comandos lista para usar que utilice la técnica de compresión.

El proyecto de código abierto "fs-c" contiene la mayoría del código que es necesario. Sin embargo, fs-c solo intenta medir las redundancias y los archivos analzye en memoria o mediante un clúster de Hadoop .

una pregunta es cuál es el tamaño de registro en sus archivos, es decir, ¿pueden las compensaciones cambiar byte a byte o hacer que los archivos consistan, por ejemplo, en bloques 1024B? Suponiendo que los datos estén orientados a bytes, podría hacer lo siguiente:

Cree una matriz de sufijos para el archivo A. Esta matriz es una permutación de todos los valores de índice al archivo A. Si A tiene 2 ^ 37 bytes, entonces la matriz de índice se representa más fácilmente mediante números enteros de 64 bits, por lo que cada byte (desplazamiento del archivo) corresponde a 8 bytes en la matriz de índice, por lo que la matriz de índice tendrá una longitud de 2 ^ 40 bytes. Por ejemplo, 800 GB, digamos. También puede indexar cada ubicación 1024, por ejemplo, para reducir el tamaño de la matriz de índice. Esto, a su vez, perjudica la calidad del embalaje en función de la duración media de las copias de los fragmentos copiables.
Ahora, para empacar con avidez el archivo B, comience desde su inicio en offset o = 0 y luego use la matriz de índice para encontrar la coincidencia más larga en A que coincida con los datos que comienzan en ''o''. Se imprime el par en el archivo empaquetado. Esto toma en su caso sin ningún tipo de codificación de 16 bytes, por lo que si la ejecución es <16 bytes, realmente pierde espacio. Esto puede remediarse fácilmente utilizando la codificación de nivel de bits y luego un marcador de bits para marcar si codifica un byte aislado (marcador + 8 bits = 9 bits) o un par de desplazamiento / longitud (marcador + 40 bits + 40 bits = 81 bits), digamos. Después de empaquetar el fragmento más largo en o, aumente o al siguiente byte después del fragmento y repita hasta el final del archivo.

La construcción y el uso de una matriz de sufijos es fácil y debería encontrar referencias fácilmente. En las aplicaciones de alta velocidad, las personas usan árboles de sufijos o intentos de sufijos, que son más complejos de manipular pero proporcionan una búsqueda más rápida. En su caso, tendrá la matriz en el almacenamiento secundario y si la velocidad de ejecución de la fase de empaque no es un problema, una matriz de sufijos debería ser suficiente.

Puedes usar rdiff , que funciona muy bien con archivos grandes. Aquí creo un diff de dos archivos grandes A y B :

Crear una firma de un archivo, con por ejemplo
rdiff signature A sig.txt
utilizando el archivo de firma generado sig.txt y el otro archivo grande, cree el delta:
rdiff delta sig.txt B delta
ahora delta contiene toda la información que necesita para recrear el archivo B cuando tiene tanto A como delta . Para recrear B, ejecute
rdiff patch A delta B

En Ubuntu, simplemente ejecute sudo apt-get install rdiff para instalarlo. Es bastante rápido, obtengo unos 40 MB por segundo en mi PC. Acabo de probarlo en un archivo de 8 GB y la memoria utilizada por rsync era de aproximadamente 1 MB.