Algoritmo per la differenziazione efficiente di file di grandi dimensioni

Question

Devo archiviare due file A e B che sono entrambi molto grandi (come 100 GB).Tuttavia è probabile che B sia simile in grandi parti ad A, quindi potrei memorizzare A e diff (A, B).Ci sono due aspetti interessanti in questo problema:

1. I file sono troppo grandi per essere analizzati da qualsiasi libreria diff che conosco perché sono in memoria
2. In realtà non ho bisogno di un diff: un diff in genere ha inserimenti, modifiche ed eliminazioni perché è pensato per essere letto dagli esseri umani.Posso farla franca con meno informazioni:Ho solo bisogno di "nuovo intervallo di byte" e "copia byte dal vecchio file da offset arbitrario".

Attualmente non so come calcolare il delta da A a B in queste condizioni.Qualcuno conosce un algoritmo per questo?

Anche in questo caso il problema è semplice:Scrivi un algoritmo in grado di memorizzare i file A e B con il minor numero di byte possibile dato che entrambi sono abbastanza simili.

Informazioni addizionali:Sebbene le parti grandi possano essere identiche, è probabile che abbiano offset diversi e siano fuori servizio.L'ultimo fatto è il motivo per cui un differenziale convenzionale potrebbe non far risparmiare molto.

Answer 1

Date un'occhiata a algoritmo di rsyncs, come è stato progettato più o meno a fare esattamente questo in modo che possa efficacemente copiare delta. E l'algoritmo è abbastanza ben documentato, se ben ricordo.

Answer 2

È possibile utilizzare rdiff, che funziona molto bene con i file di grandi dimensioni. Qui crea un diff di due file di grandi dimensioni e A B:

1. Creare una firma di un file, con per esempio.

   rdiff signature A sig.txt
   

2. utilizzando il file di firma sig.txt generato e l'altro file grande, creare il delta:

   rdiff delta sig.txt B delta
   

3. ora delta contiene tutte le informazioni necessarie per ricreare il file B quando si dispone di entrambi A e delta. Per ricreare B, eseguire

   rdiff patch A delta B
   

In Ubuntu, basta eseguire sudo apt-get install rdiff per installarlo. E 'abbastanza veloce, ottengo circa 40 MB al secondo sul mio PC. Ho appena provato su un file da 8 GB e la memoria utilizzata da rsync era di circa 1 MB.

Answer 3

Questo è esattamente il problema noto come "deduplicazione dei dati" . L'approccio più comunemente usata è:

• Leggi sopra i file in blocchi:
  • suddividere i dati dei cosiddetti "blocchi". L'approccio più utilizzato è chiamato "contenuto definito Chunking usando il metodo Rabins Fingerprinting" ( Codice ). Utilizzando tale chunking approccio porta a una deduplicazione meglio sulla maggior parte di set di dati poi usando blocchi statici dimensioni (ad esempio mostrato qui ).
  • Fingerprint i pezzi utilizzando un metodo di fingerprinting di crittografia, ad esempio, SHA-256.
  • Conservare le impronte digitali di un indice e di ricerca per ogni blocco, se l'impronta è già noto. Se l'impronta digitale è noto, non v'è alcuna necessità di memorizzare il pezzo una seconda volta. Solo quando l'impronta digitale non è noto, i dati devono essere memorizzati.

Un tale algoritmo di deduplicazione dei dati non è esatto come ad esempio xdelta , ma è più veloce e più scalabile per grandi insiemi di dati. Il chunking e fingerprinting viene eseguita con circa 50 MB / s per core (Java). La dimensione dell'indice dipende dalle ridondanze, la dimensione del blocco e la dimensione dei dati. Per 200 GB, dovrebbe rientrare nella memoria per dimensione del chunk esempio 16KB.

Bentley e Mciloys approccio compressione è molto simile (usato ad esempio Googles BigTable), ma io non sono a conoscenza di strumenti a linea di out-of-box del comando utilizzando la tecnica di compressione.

Il "fs-c" progetto open source contiene la maggior parte del codice che è necessario. Tuttavia, FS-c si cerca solo di misurare i licenziamenti ei file analzye in memoria o utilizzando un grappolo Hadoop .

Answer 4

una domanda è: qual è la dimensione del record nei tuoi file, ad es.gli offset possono cambiare byte per byte o i file sono costituiti, ad esempio, da blocchi 1024B.Supponendo che i dati siano orientati ai byte, potresti fare quanto segue:

1. Crea un array di suffissi per il file A.Questo array è una permutazione di tutti i valori dell'indice nel file A.Se A ha 2 ^ 37 byte, allora l'array dell'indice è rappresentato più facilmente da numeri interi a 64 bit, quindi ogni byte (offset al file) corrisponde a 8 byte nell'array dell'indice, quindi l'array dell'indice sarà lungo 2 ^ 40 byte .Per esempio.800 GB, diciamo.Puoi anche indicizzare solo ogni 1024a posizione, ad esempio, per ridurre la dimensione dell'array dell'indice.Ciò quindi peggiora la qualità dell'imballaggio a seconda della lunghezza delle tirature medie dei frammenti copiabili.

2. Ora quindi per comprimere avidamente il file B si inizia dal suo inizio all'offset o=0 e quindi si utilizza l'array di indici per trovare la corrispondenza più lunga in A che corrisponde ai dati che iniziano da "o".Emetti la coppia nel file compresso.Nel tuo caso questo richiede senza alcuna codifica 16 byte, quindi se la corsa è <16 byte in realtà perdi spazio.Questo può essere facilmente risolto utilizzando la codifica a livello di bit e utilizzando un marcatore di bit per contrassegnare se si codifica un byte isolato (marcatore + 8 bit = 9 bit) o ​​una coppia offset/lunghezza (marcatore + 40 bit + 40 bit = 81 bit), diciamo.Dopo aver compresso il frammento più lungo in o, aumentare o al byte successivo al frammento e ripetere fino alla fine del file.

La costruzione e l'uso di un array di suffissi è semplice e dovresti trovare facilmente i riferimenti.Nelle applicazioni ad alta velocità le persone utilizzano invece alberi di suffisso o tentativi di suffisso, che sono più complessi da manipolare ma forniscono una ricerca più rapida.Nel tuo caso avrai l'array sulla memoria secondaria e se la velocità di esecuzione della fase di imballaggio non è un problema, un array di suffissi dovrebbe essere sufficiente.

Answer 5

A seconda dei requisiti di prestazioni, si potrebbe ottenere via con il campionamento dei pezzi si impronte digitali, e farle crescere quando corrispondono. In questo modo non c'è bisogno di eseguire un checksum sul vostro intero file di grandi dimensioni.

Se avete bisogno di allineamenti di byte arbitrari e davvero a cuore le prestazioni, guardare il simhash < a href = "http://svcs.cs.pdx.edu/gitweb/simhash.git" rel = "nofollow noreferrer"> algoritmo , e usarlo per trovare i blocchi simili, ma non allineati.