il modo più veloce per creare checksum per file di grandi dimensioni in python

Question

Ho bisogno di trasferire file di grandi dimensioni attraverso la rete e ho bisogno di creare il checksum per loro su base oraria. quindi la velocità per generare il checksum è fondamentale per me.

in qualche modo non riesco a far funzionare zlib.crc32 e zlib.adler32 con file più grandi di 4 GB su Windows XP Pro a 64 bit. sospetto di aver raggiunto il limite di 32 bit qui? usando hashlib.md5 potrei ottenere un risultato ma il problema è la velocità. ci vogliono circa 5 minuti per generare un file md5 per 4,8 GB. il task manager mostra che il processo utilizza solo un core.

le mie domande sono:

1. c'è un modo per fare opere CRC file di grandi dimensioni? preferisco usare crc rispetto a md5
2. se non c'è un modo per velocizzare md5.hexdigest()/md5.digest? o in questo caso un hashlib hexdigest/digest? magari dividerlo in un processo multi-thread? Come lo faccio?

PS: sto lavorando a qualcosa di simile a un sistema di "Gestione risorse", un po 'come svn ma la risorsa è costituita da file di immagine compressi di grandi dimensioni. i file hanno piccole modifiche incrementali. l'hashing/checksum è necessario per rilevare le modifiche e il rilevamento degli errori.

Answer 1

Non è possibile utilizzare più di un core per calcolare l'hash MD5 di un file di grandi dimensioni a causa della natura stessa di MD5: prevede che un messaggio venga suddiviso in blocchi e immesso nella funzione di hashing in sequenza rigorosa. Tuttavia, è possibile utilizzare un thread per leggere un file nella coda interna e quindi calcolare l'hash in un thread separato in modo che. Non penso però che questo ti darà un significativo incremento delle prestazioni.

Il fatto che ci vuole così tanto tempo per elaborare un file di grandi dimensioni potrebbe essere dovuto alle letture "senza buffer". Prova a leggere, diciamo, 16 Kb alla volta e poi invia il contenuto in blocchi alla funzione di hashing.

Answer 2

md5 non può essere eseguito in parallelo. Comunque puoi md5 il file in sezioni (in parallelo) e prendi un md5 della lista di hash.

Tuttavia, questo presuppone che l'hashing non sia limitato all'IO, cosa che sospetto sia. Come suggerisce Anton Gogolev, assicurati di leggere il file in modo efficiente (in grossi blocchi di potenza di 2). Una volta fatto, assicurati che il file non sia frammentato.

Anche un hash come sha256 deve essere selezionato anziché md5 per i nuovi progetti.

I checksum zlib sono molto più veloci di md5 per i file 4Gb?

Answer 3

Hai provato il modulo crc-generator?

Answer 4

È un problema di selezione dell'algoritmo, piuttosto che un problema di selezione di libreria/lingua!

Sembra che ci sia due punti da considerare in primo luogo:

• quanto sarebbe il disco I/O influenzare le prestazioni complessive?
• Qual è l'affidabilità prevista della funzione di rilevamento errori?

A quanto pare, la risposta alla seconda domanda è qualcosa di simile a 'alcuni falsi negativi ammessi' dal momento che l'affidabilità dei eventuali 32 bit hash, relativa a un messaggio 4Gb, anche in un canale moderatamente rumorosa, è non sarà praticamente assoluto.

Supponendo che l'I/O possa essere migliorato tramite il multithreading, possiamo scegliere un hash che non richiede una scansione sequenziale del messaggio completo. Possiamo invece lavorare il file in parallelo, triturando le singole sezioni e combinando i valori hash o aggiungendoli, per formare un dispositivo di rilevamento degli errori più lungo e più affidabile.

Il passaggio successivo potrebbe essere quello di formalizzare questa gestione dei file come sezioni ordinate e di trasmetterli come tali (da ri-incollare insieme alla fine del destinatario). Questo approccio, insieme a ulteriori informazioni sul modo in cui i file vengono prodotti (ad esempio possono essere modificati esclusivamente da append, come i file di log), può anche consentire di limitare la quantità di calcolo hash richiesta. La complessità aggiuntiva di questo approccio deve essere appesantita dal desiderio di avere un calcolo CRC veloce e veloce.

Nota a margine: Alder32 è non limitato alle dimensioni dei messaggi inferiori a una soglia specifica. Potrebbe essere solo un limite dell'API zlib. (A proposito, il riferimento che ho trovato su zlib.adler32 ha usato un buffer, e beh ... questo approccio deve essere evitato nel contesto dei nostri enormi messaggi, a favore dei processi in streaming: leggi un po 'dal file, calcola, ripeti. .)

Answer 5

In primo luogo, non c'è nulla di intrinseco in nessuno degli algoritmi CRC che impedirebbe loro di lavorare su una lunghezza arbitraria di dati (tuttavia, un'implementazione particolare potrebbe ben imporre un limite).

Tuttavia, in un'applicazione di sincronizzazione di file, che probabilmente non ha importanza, dato che non si può desiderare di eseguire l'hashing dell'intero file quando diventa grande, è sufficiente solo blocchi. Se si hash l'intero file e gli hash a ciascuna estremità differiscono, è necessario copiare l'intero file. Se hai hash pezzi di dimensioni fisse, devi solo copiare i blocchi il cui hash è cambiato. Se la maggior parte delle modifiche ai file sono localizzate (ad es. Database), è probabile che ciò richieda una copia molto minore (ed è più facile da diffondere per calcoli a blocchi su più core).

Come per l'algoritmo hash, il compromesso di base è la velocità rispetto alla mancanza di collisioni (due blocchi di dati diversi che producono lo stesso hash). CRC-32 è veloce, ma con solo 2^32 valori unici, si possono vedere collisioni. MD5 è molto più lento, ma ha 2^128 valori unici, quindi le collisioni non saranno quasi mai viste (ma sono ancora teoricamente possibili). Gli hash più grandi (SHA1, SHA256, ...) hanno valori ancora più unici, ma sono ancora più lenti: dubito che ne hai bisogno: sei preoccupato per le collisioni accidentali, a differenza delle applicazioni di firma digitale, in cui sei preoccupato deliberatamente (malicatamente) collisioni ingegnerizzate.

Sembra che tu stia cercando di fare qualcosa di molto simile a ciò che fa l'utilità rsync. Puoi usare rsync?

Answer 6

È possibile che si stia raggiungendo un limite di dimensioni per i file in XP. Il 64-bit ti offre più spazio per l'indirizzamento (rimuovendo lo spazio di indirizzamento da 2 GB (o così) per applicazione), ma probabilmente non fa nulla per il problema delle dimensioni del file.