Questo articolo è già il secondo sull'argomento della compressione dei dati ad alta velocità. Il primo articolo descriveva un compressore funzionante ad una velocità di 10 GB/sec. per core del processore (compressione minima, RTT-Min).
Questo compressore è già stato implementato nelle apparecchiature dei duplicatori forensi per la compressione ad alta velocità dei dump dei supporti di memorizzazione e per migliorare la forza della crittografia; può anche essere utilizzato per comprimere immagini di macchine virtuali e file di scambio RAM quando vengono salvati su dispositivi ad alta velocità Unità SSD.
Il primo articolo annunciava anche lo sviluppo di un algoritmo di compressione per la compressione di copie di backup di unità disco HDD e SSD (compressione media, RTT-Mid) con parametri di compressione dei dati notevolmente migliorati. Ormai questo compressore è completamente pronto e questo articolo ne parla.
Un compressore che implementa l'algoritmo RTT-Mid fornisce un rapporto di compressione paragonabile agli archiviatori standard come WinRar, 7-Zip, che funzionano in modalità ad alta velocità. Allo stesso tempo, la sua velocità operativa è almeno un ordine di grandezza superiore.
La velocità di compressione/decompressione dei dati è un parametro critico che determina l'ambito di applicazione delle tecnologie di compressione. È improbabile che qualcuno possa pensare di comprimere un terabyte di dati ad una velocità di 10-15 MegaByte al secondo (questa è esattamente la velocità degli archiviatori in modalità di compressione standard), perché ci vorrebbero quasi venti ore con un carico completo del processore.. .
D'altronde lo stesso terabyte può essere copiato a velocità dell'ordine di 2-3Gigabyte al secondo in una decina di minuti.
Pertanto, la compressione di grandi volumi di informazioni è importante se eseguita a una velocità non inferiore alla velocità dell'input/output reale. Per i sistemi moderni questo è almeno 100 Megabyte al secondo.
I compressori moderni possono produrre tali velocità solo in modalità “veloce”. È in questa modalità attuale che confronteremo l'algoritmo RTT-Mid con i compressori tradizionali.
Test comparativo di un nuovo algoritmo di compressione
Il compressore RTT-Mid ha funzionato come parte del programma di test. In una vera applicazione “funzionante” funziona molto più velocemente, utilizza saggiamente il multithreading e utilizza un compilatore “normale”, non C#.
Poiché i compressori utilizzati nel test comparativo sono costruiti su principi diversi e diversi tipi di dati vengono compressi in modo diverso, per l'obiettività del test è stato utilizzato il metodo di misurazione della "temperatura media in ospedale"...
È stato creato un file dump settore per settore di un disco logico con il sistema operativo Windows 10; questa è la miscela più naturale di varie strutture dati effettivamente disponibili su ogni computer. La compressione di questo file ti consentirà di confrontare la velocità e il grado di compressione del nuovo algoritmo con i compressori più avanzati utilizzati nei moderni archiviatori.
Ecco il file di dump:
Il file dump è stato compresso utilizzando i compressori PTT-Mid, 7-zip e WinRar. Il compressore WinRar e 7-zip erano impostati alla massima velocità.
Compressore in funzione 7-zip:
Carica il processore al 100%, mentre la velocità media di lettura del dump originale è di circa 60 MegaByte/sec.
Compressore in funzione WinRAR:
La situazione è simile, il carico del processore è quasi al 100%, la velocità media di lettura del dump è di circa 125 Megabyte/sec.
Come nel caso precedente, la velocità dell'archiviatore è limitata dalle capacità del processore.
Il programma di test del compressore è ora in esecuzione RTT-Medio:
Lo screenshot mostra che il processore è caricato al 50% ed è inattivo per il resto del tempo, perché non c'è nessun posto dove caricare i dati compressi. Il disco di caricamento dati (Disco 0) è quasi completamente caricato. La velocità di lettura dei dati (Disco 1) varia notevolmente, ma in media è superiore a 200 MegaByte/sec.
La velocità del compressore in questo caso è limitata dalla capacità di scrivere dati compressi sul Disco 0.
Ora il rapporto di compressione degli archivi risultanti:
Si può vedere che il compressore RTT-Mid ha fatto il miglior lavoro di compressione; l'archivio che ha creato era 1,3 GigaByte più piccolo dell'archivio WinRar e 2,1 GigaByte più piccolo dell'archivio 7z.
Tempo impiegato per creare l'archivio:
- 7 zip – 26 minuti e 10 secondi;
- WinRar – 17 minuti e 40 secondi;
- RTT-Medio – 7 minuti e 30 secondi.
Pertanto, anche un programma di prova non ottimizzato, utilizzando l'algoritmo RTT-Mid, è stato in grado di creare un archivio più di due volte e mezzo più velocemente, mentre l'archivio si è rivelato significativamente più piccolo di quello dei suoi concorrenti...
Coloro che non credono agli screenshot possono verificarne personalmente l'autenticità. Il programma del test è disponibile su , scarica e controlla.
Ma solo sui processori con supporto AVX-2, senza supporto per queste istruzioni il compressore non funziona, e non testare l'algoritmo sui processori AMD più vecchi, sono lenti in termini di esecuzione delle istruzioni AVX...
Metodo di compressione utilizzato
L'algoritmo utilizza un metodo per indicizzare frammenti di testo ripetuti con granularità in byte. Questo metodo di compressione è noto da molto tempo, ma non è stato utilizzato perché l'operazione di abbinamento era molto costosa in termini di risorse necessarie e richiedeva molto più tempo rispetto alla costruzione di un dizionario. Quindi l’algoritmo RTT-Mid è un classico esempio di “ritorno al futuro”...
Il compressore PTT utilizza un esclusivo scanner di ricerca delle corrispondenze ad alta velocità, che ci consente di accelerare il processo di compressione. Uno scanner autocostruito, questo è “il mio fascino...”, “è piuttosto costoso, perché è completamente fatto a mano” (scritto in assembler).
Lo scanner di ricerca delle partite è realizzato secondo uno schema probabilistico a due livelli: in primo luogo, viene scansionata la presenza di un "segno" di una corrispondenza, e solo dopo aver identificato il "segno" in questo luogo, viene avviata la procedura per rilevare una corrispondenza reale è iniziato.
La finestra di ricerca delle corrispondenze ha una dimensione imprevedibile, a seconda del grado di entropia nel blocco dati elaborato. Per i dati completamente casuali (incomprimibili) ha una dimensione di megabyte, per i dati con ripetizioni è sempre più grande di un megabyte.
Ma molti formati di dati moderni sono incomprimibili e l'esecuzione di uno scanner ad alta intensità di risorse attraverso di essi è inutile e dispendioso, quindi lo scanner utilizza due modalità operative. Per prima cosa vengono ricercati i tratti del testo sorgente con possibili ripetizioni; anche questa operazione viene effettuata con metodo probabilistico e viene eseguita in tempi molto rapidi (ad una velocità di 4-6 GigaBytes/sec). Le aree con possibili corrispondenze vengono poi elaborate dallo scanner principale.
La compressione dell'indice non è molto efficiente, è necessario sostituire i frammenti duplicati con gli indici e l'array dell'indice riduce significativamente il rapporto di compressione.
Per aumentare il rapporto di compressione, vengono indicizzate non solo le corrispondenze complete delle stringhe di byte, ma anche quelle parziali, quando la stringa contiene byte corrispondenti e non corrispondenti. Per fare ciò, il formato dell'indice include un campo maschera di corrispondenza che indica i byte corrispondenti di due blocchi. Per una compressione ancora maggiore, l'indicizzazione viene utilizzata per sovrapporre diversi blocchi parzialmente corrispondenti al blocco corrente.
Tutto ciò ha permesso di ottenere nel compressore PTT-Mid un rapporto di compressione paragonabile ai compressori realizzati con il metodo del dizionario, ma lavorando molto più velocemente.
Velocità del nuovo algoritmo di compressione
Se il compressore funziona utilizzando esclusivamente la memoria cache (sono necessari 4 Megabyte per thread), la velocità operativa varia da 700 a 2000 Megabyte/sec. per core del processore, a seconda del tipo di dati da comprimere e dipende poco dalla frequenza operativa del processore.
Con un'implementazione multi-thread del compressore, la scalabilità effettiva è determinata dalla dimensione della cache di terzo livello. Ad esempio, avendo 9 MegaByte di memoria cache “a bordo”, non ha senso avviare più di due thread di compressione; la velocità non aumenterà da questo. Ma con una cache di 20 Megabyte puoi già eseguire cinque thread di compressione.
Inoltre, la latenza della RAM diventa un parametro importante che determina la velocità del compressore. L'algoritmo utilizza l'accesso casuale all'OP, una parte del quale non entra nella memoria cache (circa il 10%) e deve restare inattivo, in attesa dei dati dall'OP, il che riduce la velocità di funzionamento.
Influisce in modo significativo sulla velocità del compressore e sul funzionamento del sistema di input/output dei dati. Le richieste all'OP dalla periferia bloccano le richieste di dati dalla CPU, il che riduce anche la velocità di compressione. Questo problema è significativo per laptop e desktop; per i server è meno significativo a causa di un'unità di controllo dell'accesso al bus di sistema più avanzata e di una RAM multicanale.
In tutto il testo dell’articolo si parla di compressione; la decompressione resta fuori dall’ambito di questo articolo poiché “è tutto ricoperto di cioccolato”. La decompressione è molto più veloce ed è limitata dalla velocità I/O. Un core fisico in un thread fornisce facilmente velocità di decompressione di 3-4 GB/sec.
Ciò è dovuto all'assenza di un'operazione di ricerca delle corrispondenze durante il processo di decompressione, che “consuma” le principali risorse del processore e della memoria cache durante la compressione.
Affidabilità dell'archiviazione dei dati compressi
Come suggerisce il nome dell'intera classe di software che utilizza la compressione dei dati (archiviatori), sono progettati per l'archiviazione di informazioni a lungo termine, non per anni, ma per secoli e millenni...
Durante la memorizzazione i supporti di memorizzazione perdono alcuni dati, ecco un esempio:
Questo supporto informativo “analogico” ha mille anni, alcuni frammenti sono andati perduti, ma in generale l'informazione è “leggibile”...
Nessuno dei produttori responsabili dei moderni sistemi di archiviazione dei dati digitali e dei supporti digitali fornisce garanzie sulla completa sicurezza dei dati da più di 75 anni.
E questo è un problema, ma un problema rinviato, i nostri discendenti lo risolveranno...
I sistemi di archiviazione digitale dei dati possono perdere i dati non solo dopo 75 anni, gli errori nei dati possono comparire in qualsiasi momento, anche durante la loro registrazione, si cerca di minimizzare queste distorsioni utilizzando la ridondanza e correggendole con sistemi di correzione degli errori. I sistemi di ridondanza e correzione non sempre riescono a ripristinare le informazioni perse e, se lo fanno, non vi è alcuna garanzia che l'operazione di ripristino sia stata completata correttamente.
E anche questo è un grosso problema, ma non differito, ma attuale.
I moderni compressori utilizzati per l'archiviazione dei dati digitali si basano su varie modifiche del metodo del dizionario e per tali archivi la perdita di un'informazione sarà un evento fatale; esiste persino un termine stabilito per tale situazione: un archivio "rotto" ...
La scarsa affidabilità della memorizzazione delle informazioni negli archivi con compressione del dizionario è associata alla struttura dei dati compressi. Le informazioni in un tale archivio non contengono il testo di partenza, i numeri delle voci nel dizionario sono memorizzati lì e il dizionario stesso viene modificato dinamicamente dal testo compresso corrente. Se un frammento di archivio viene perso o danneggiato, tutte le voci di archivio successive non possono essere identificate né dal contenuto né dalla lunghezza della voce nel dizionario, poiché non è chiaro a cosa corrisponda il numero della voce del dizionario.
È impossibile ripristinare le informazioni da un archivio così "rotto".
L'algoritmo RTT si basa su un metodo più affidabile per archiviare i dati compressi. Utilizza il metodo dell'indice per tenere conto dei frammenti ripetuti. Questo approccio alla compressione consente di ridurre al minimo le conseguenze della distorsione delle informazioni sul supporto di memorizzazione e in molti casi di correggere automaticamente le distorsioni che si sono verificate durante la memorizzazione delle informazioni.
Ciò è dovuto al fatto che il file di archivio in caso di compressione dell'indice contiene due campi:
- un campo di testo di origine da cui sono state rimosse le sezioni ripetute;
- campo indice.
Il campo indice, fondamentale per il recupero delle informazioni, non è di grandi dimensioni e può essere duplicato per un'archiviazione affidabile dei dati. Pertanto, anche se si perde un frammento del testo sorgente o dell'array dell'indice, tutte le altre informazioni verranno ripristinate senza problemi, come nell'immagine con un supporto di memorizzazione “analogico”.
Svantaggi dell'algoritmo
Non esistono vantaggi senza svantaggi. Il metodo di compressione dell'indice non comprime brevi sequenze ripetute. Ciò è dovuto alle limitazioni del metodo dell'indice. Gli indici hanno una dimensione minima di 3 byte e possono avere una dimensione massima di 12 byte. Se viene rilevata una ripetizione di dimensioni inferiori rispetto all'indice che la descrive, non viene presa in considerazione, indipendentemente dalla frequenza con cui tali ripetizioni vengono rilevate nel file compresso.
Il tradizionale metodo di compressione del dizionario comprime efficacemente più ripetizioni di breve durata e pertanto raggiunge un rapporto di compressione più elevato rispetto alla compressione dell'indice. È vero, ciò è ottenuto a causa dell'elevato carico sul processore centrale; affinché il metodo del dizionario possa iniziare a comprimere i dati in modo più efficiente rispetto al metodo dell'indice, deve ridurre la velocità di elaborazione dei dati a 10-20 megabyte al secondo in termini reali installazioni informatiche con un carico completo della CPU.
Velocità così basse sono inaccettabili per i moderni sistemi di archiviazione dati e rivestono un interesse più “accademico” che pratico.
Con la prossima modifica dell'algoritmo RTT (RTT-Max), già in fase di sviluppo, il grado di compressione delle informazioni verrà notevolmente aumentato.
Quindi, come sempre, continua...
Fonte: habr.com