Questo articolo è il secondo della serie sulla compressione veloce dei dati. Nel primo articolo è stato descritto un compressore che lavora a una velocità di 10 Gbyte/sec. per ogni core della CPU (compressione minima, RTT-Min).
Questo compressore è già stato integrato nell'hardware dei duplicatori forensi per la compressione rapida dei dump dei supporti informatici e per potenziare la resistenza della crittografia; può anche essere utilizzato per comprimere immagini di macchine virtuali e file di swap della memoria RAM quando vengono salvati su unità SSD ad alte prestazioni.
Nel primo articolo è stata anche annunciata la progettazione di un algoritmo di compressione per comprimere i backup di unità HDD e SSD (compressione media, RTT-Mid) con parametri di compressione dei dati notevolmente migliorati. Al momento attuale, questo compressore è completamente pronto e questo articolo è specificamente su di esso.
Il compressore che implementa l'algoritmo RTT-Mid garantisce un tasso di compressione paragonabile a quello degli archivi tradizionali come WinRar e 7-Zip operanti in modalità veloce. Tuttavia, la sua velocità di esecuzione è almeno dieci volte superiore.
La velocità di imballaggio/scomprimente dei dati è un parametro cruciale che determina il campo di applicazione delle tecnologie di compressione. È difficile immaginare di comprimere un terabyte di dati a una velocità di 10-15 MegaByte al secondo (questa è la velocità degli archivi in modalità di compressione standard), poiché ciò richiederebbe quasi venti ore a pieno carico della CPU…
D'altra parte, lo stesso terabyte può essere copiato a velocità di circa 2-3 GigaByte al secondo in circa dieci minuti.
Pertanto, la compressione di informazioni di grande volume è pertinente solo se viene eseguita a una velocità non inferiore a quella di ingresso/uscita reale. Per i sistemi moderni, questo è di almeno 100 MegaByte al secondo.
Queste velocità possono essere raggiunte dai moderni compressori solo in modalità "fast". In questa modalità attuale, confronteremo l'algoritmo RTT-Mid con i tradizionali compressori.
Test comparativo del nuovo algoritmo di compressione
Il compressore RTT-Mid ha funzionato all'interno di un programma di test. In un'applicazione "reale" lavora significativamente più veloce, utilizzando correttamente il multithreading e un compilatore "normale", non C#.
Poiché i compressori utilizzati nel test comparativo sono basati su principi diversi e comprimono vari tipi di dati in modo diverso, per garantire l'oggettività del test è stato impiegato il metodo della "temperatura media in ospedale"...
È stato creato un file di dump settoriale del disco logico con il sistema operativo Windows 10, che rappresenta la combinazione più naturale di diverse strutture di dati realmente presenti su ogni computer. La compressione di questo file permetterà un confronto in termini di velocità e grado di compressione del nuovo algoritmo con i compressori più avanzati utilizzati negli attuali archivi.
Ecco questo file di dump:
Il file di dump è stato compresso dai compressori RTT-Mid, 7-zip, WinRar. I compressori WinRar e 7-zip sono stati impostati sulla massima velocità di lavoro.
Funziona il compressore 7-zip:
Utilizza il 100% della CPU, mentre la velocità media di lettura del dump originale è di circa 60 MegaByte/sec.
Funziona il compressore WinRar:
Situazione simile, il carico della CPU è praticamente al 100%, la velocità media di lettura del dump è di circa 125 MegaByte/sec.
Come nel caso precedente, la velocità di funzionamento dell'archiviatore è limitata dalle capacità della CPU.
Ora è in esecuzione il programma di prova del compressore RTT-Mid:
Lo screenshot mostra che la CPU è caricata al 50% e inattiva il resto del tempo, poiché non ci sono destinazioni per scaricare i dati compressi. L'unità di scarico dati (Disco 0) è quasi completamente carica. La velocità di lettura dei dati (Disco 1) oscilla notevolmente, ma in media supera i 200 MegaByte/sec.
La velocità di lavoro del compressore è limitata in questo caso dalla capacità di scrittura dei dati compressi su Disco 0.
Ora il grado di compressione degli archivi ottenuti:
È evidente che il compressore RTT-Mid ha ottenuto i migliori risultati in termini di compressione, l'archivio creato da lui è di 1,3 GigaByte più piccolo dell'archivio WinRar e di 2,1 GigaByte più piccolo dell'archivio 7z.
Tempo impiegato per creare l'archivio:
- 7-zip – 26 minuti 10 secondi;
- WinRar – 17 minuti 40 secondi;
- RTT-Mid – 7 minuti 30 secondi.
Pertanto, anche un programma di prova non ottimizzato, utilizzando l'algoritmo RTT-Mid, è riuscito a creare un archivio più di due volte e mezzo più velocemente, e l'archivio è risultato significativamente più piccolo rispetto ai concorrenti...
Coloro che non credono agli screenshot possono verificarne l'autenticità personalmente. Il programma di prova è disponibile su , scaricatelo e verificate.
Ma solo su processori con supporto AVX-2, senza supporto per queste istruzioni il compressore non funziona, e non testate l'algoritmo su processori AMD obsoleti, sono lenti nell'esecuzione dei comandi AVX…
Metodo di compressione utilizzato
L'algoritmo utilizza un metodo di indicizzazione dei frammenti di testo ripetuti in granuli di byte. Questo metodo di compressione è noto da tempo, ma non è stato utilizzato poiché l'operazione di ricerca delle corrispondenze era molto costosa in termini di risorse richieste e richiedeva molto più tempo rispetto alla costruzione di un dizionario. Quindi, l'algoritmo RTT-Mid è un classico esempio di un passo indietro verso il futuro…
Nel compressore RTT si utilizza uno scanner di ricerca delle corrispondenze unico e veloce, proprio lui ha permesso di velocizzare il processo di compressione. Lo scanner è di fabbricazione propria, è "la mia preziosità...", "il costo è notevole, poiché è completamente fatto a mano" (scritto in assembly).
Lo scanner di ricerca delle corrispondenze è realizzato secondo uno schema probabilistico a due livelli, prima viene scansionata la presenza di un "segno" di corrispondenza, e solo dopo aver individuato il "segno" in quel punto viene avviata la procedura per scoprire la corrispondenza reale.
La finestra di ricerca delle corrispondenze ha una dimensione imprevedibile, che dipende dal grado di entropia nel blocco di dati elaborato. Per i dati completamente casuali (non comprimibili) ha una dimensione di megabyte, mentre per i dati con ripetizioni ha sempre una dimensione superiore al megabyte.
Tuttavia, molti formati di dati moderni non sono comprimibili e "far girare" su di essi uno scanner impegnativo in termini di risorse è inutile e sprecherebbe tempo, quindi nello scanner vengono utilizzati due modi di funzionamento. Inizialmente si cercano sezioni del testo sorgente con possibili ripetizioni; questa operazione viene eseguita anch'essa tramite un metodo probabilistico e viene completata molto rapidamente (alla velocità di 4-6 Gigabyte/sec). Successivamente, le sezioni con possibili corrispondenze vengono elaborate dallo scanner principale.
La compressione indicizzata non è molto efficiente, si deve sostituire i frammenti ripetuti con gli indici, e l'array degli indici riduce significativamente il coefficiente di compressione.
Per aumentare il grado di compressione, vengono indicizzati non solo i corrispondenze complete delle stringhe di byte, ma anche quelle parziali, quando nella stringa sono presenti byte corrispondenti e non corrispondenti. A questo scopo, nel formato dell'indice è incluso un campo di maschera di corrispondenza che indica i byte corrispondenti di due blocchi. Per una compressione ancora maggiore, si utilizza l'indicizzazione sovrapponendo più blocchi parzialmente corrispondenti al blocco attuale.
Tutto questo ha permesso di ottenere nel compressore RTT-Mid un grado di compressione comparabile con i compressori realizzati con il metodo basato su dizionario, ma funzionante con molta più rapidità.
La velocità di funzionamento del nuovo algoritmo di compressione
Se il compressore funziona con utilizzo monopolistico della cache della memoria (per un thread sono richiesti 4 MegaByte), la velocità di funzionamento oscilla tra 700 e 2000 MegaByte/sec. per ogni core della CPU a seconda del tipo di dati compressi e dipende poco dalla frequenza di lavoro del processore.
Nella realizzazione multithreading del compressore, l'efficacia della scalabilità è determinata dal volume della cache di terzo livello. Ad esempio, avendo "a bordo" 9 MegaByte di cache, non ha senso avviare più di due thread di compressione, la velocità non aumenterà per questo. Ma con 20 MegaByte di cache, è possibile avviare fino a cinque thread di compressione.
Un altro parametro significativo che determina la velocità di funzionamento del compressore è la latenza della memoria operativa. L'algoritmo utilizza accessi casuali alla memoria temporanea, parte dei quali non va nella cache (circa il 10%) e deve attendere i dati dalla memoria operativa, il che riduce la velocità di funzionamento.
Influisce significativamente sulla velocità del compressore anche il funzionamento del sistema di input/output dei dati. Le richieste alla memoria operativa da input/output bloccano gli accessi ai dati da parte della CPU, il che riduce anche la velocità di compressione. Questo problema è significativo per i laptop e i desktop, per server è meno significativo grazie a un modulo di gestione dell'accesso al bus di sistema più avanzato e alla memoria operativa multicanale.
Ovunque nel testo dell'articolo si parla di compressione, la decompressione rimane al di fuori di questo articolo poiché lì «è tutto a posto». La decompressione avviene molto più velocemente ed è limitata dalla velocità di input/output. Un singolo core fisico in un unico thread fornisce tranquillamente velocità di estrazione nell'ordine di 3-4 Gigabyte al secondo.
Ciò è dovuto all'assenza, nel processo di estrazione, di operazioni di ricerca delle corrispondenze, che «consumano» le risorse principali della CPU e della cache durante la compressione.
Affidabilità della conservazione dei dati compressi
Come suggerisce il nome dell'intera classe di strumenti software che utilizzano la compressione dei dati (archivatori), sono destinati a una conservazione a lungo termine delle informazioni, non per anni, ma per secoli e millenni...
Nel corso della conservazione, i supporti di informazione perdono parte dei dati, ecco un esempio:
Questo supporto di informazione «analogico» ha mille anni, alcuni frammenti sono andati perduti, ma in generale l'informazione è «leggibile»...
Nessuno dei produttori responsabili dei moderni sistemi di archiviazione dati digitali e dei supporti digitali ad essi associati offre garanzie di completa integrità dei dati per più di 75 anni.
E questo è un problema, ma un problema rimandato, da risolvere saranno i nostri discendenti...
I sistemi di archiviazione di dati digitali possono perdere dati non solo dopo 75 anni, ma anche durante la registrazione, possono presentarsi errori in qualsiasi momento; queste distorsioni cercano di essere minime attraverso l'uso di ridondanza e sistemi di correzione degli errori. La ridondanza e i sistemi di correzione non possono sempre ripristinare le informazioni perse e, anche se lo fanno, non ci sono garanzie che l'operazione di ripristino sia avvenuta correttamente.
E questo è anche un grande problema, ma non rinviato, bensì attuale.
I moderni compressori utilizzati per l'archiviazione di dati digitali si basano su diverse modifiche del metodo del dizionario e per tali archivi la perdita di un frammento di informazione sarebbe un evento fatale; esiste anche un termine consolidato per tale situazione - «archivio danneggiato»...
La bassa affidabilità nel salvataggio delle informazioni in archivi con compressione lessicale è legata alla struttura dei dati compressi. Le informazioni in tale archivio non contengono il testo originale, ma conservano i numeri di registro nel dizionario, il quale viene dinamicamente modificato dal testo attualmente compresso. In caso di perdita o distorsione di un frammento dell'archivio, tutte le registrazioni successive dell'archivio non possono essere identificate né in base al contenuto né in base alla lunghezza della registrazione nel dizionario, poiché non è chiaro a cosa corrisponde il numero della registrazione dizionario.
Ripristinare informazioni da un tale archivio "incrinato" è impossibile.
L'algoritmo RTT si basa su un metodo di archiviazione dei dati compressi più affidabile. Utilizza un metodo indicizzato per tenere conto dei frammenti ripetuti. Questo approccio alla compressione consente di minimizzare le conseguenze della distorsione delle informazioni sul supporto, e in molti casi di correggere automaticamente le distorsioni verificatesi durante il salvataggio delle informazioni.
Ciò è dovuto al fatto che il file di archivio, nel caso di compressione indicizzata, contiene due campi:
- il campo del testo originale con le sezioni di ripetizione rimosse;
- il campo degli indici.
Il campo degli indici, critico per il ripristino delle informazioni, non è di grande dimensione e può essere duplicato per garantire l'affidabilità del salvataggio dei dati. Pertanto, anche se si perde un frammento del testo originale o dell'array degli indici, tutte le altre informazioni possono essere recuperate senza problemi, come nell'immagine di un supporto informativo "analogico".
Svantaggi dell'algoritmo
Non ci sono vantaggi senza svantaggi. Il metodo di compressione indicizzato non comprime le sequenze ripetute di lunghezza ridotta. Ciò è legato ai limiti del metodo indicizzato. Gli indici hanno una dimensione minima di 3 byte e possono avere una dimensione fino a 12 byte. Se viene trovata una ripetizione di dimensioni inferiori rispetto all'indice che la descrive, non viene conteggiata, indipendentemente da quanto spesso tali ripetizioni vengano rinvenute nel file compresso.
Il metodo di compressione tradizionale basato su dizionario comprime efficacemente numerosi ripetizioni di breve durata e pertanto raggiunge un coefficiente di compressione maggiore rispetto alla compressione basata su indice. Tuttavia, ciò viene ottenuto a scapito di un alto carico sulla CPU centrale, il che significa che, affinché il metodo basato su dizionario inizi a comprimere i dati più efficacemente rispetto al metodo basato su indice, è costretto a ridurre la velocità di elaborazione dei dati a 10-20 megabyte al secondo su installazioni computazionali reali a pieno carico della CPU.
Tali velocità elevate sono inaccettabili per i moderni sistemi di archiviazione dati e rappresentano più un interesse «accademico» che pratico.
Il grado di compressione delle informazioni sarà notevolmente aumentato nella prossima modifica dell'algoritmo RTT (RTT-Max), attualmente in fase di sviluppo.
Quindi, come sempre, seguiteci…
Fonte: habr.com
