Questo articolo è il secondo su un tema riguardante la compressione rapida dei dati. Nel primo articolo è stato descritto un compressore che funziona a 10 GB/s per core di CPU (compressione minima, RTT-Min).
Questo compressore è già stato integrato nell'attrezzatura degli duplicatori forensi per la compressione rapida dei dump dei supporti informatici e per migliorare la robustezza della crittografia; può anche essere utilizzato per comprimere le immagini delle macchine virtuali e i file di swap della memoria mentre sono salvati su SSD ad alte prestazioni.
Nel primo articolo è stata anche annunciata lo sviluppo di un algoritmo di compressione per comprimere i backup di dischi rigidi e SSD (compressione media, RTT-Mid) con parametri di compressione dei dati notevolmente migliorati. Attualmente, questo compressore è completamente pronto e questo articolo è dedicato proprio a lui.
Il compressore che implementa l'algoritmo RTT-Mid offre un tasso di compressione comparabile a quello di archiviatori standard come WinRar e 7-Zip, operanti in modalità rapida. La sua velocità di lavoro è almeno un ordine di grandezza superiore.
La velocità di imballaggio/estrazione dei dati è un parametro critico 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 archiviatori in modalità di compressione standard), poiché ciò richiederebbe quasi venti ore con la CPU completamente carica...
D'altro canto, lo stesso terabyte può essere copiato a velocità di 2-3 Gigabyte al secondo in circa dieci minuti.
Pertanto, la compressione di grandi volumi di informazioni è pertinente se può essere eseguita a una velocità non inferiore alla velocità reale di input/output. Per i sistemi moderni, ciò equivale ad almeno 100 Megabyte al secondo.
Solo in questo modo le moderne compressori possono raggiungere tali velocità, esclusivamente in modalità 'fast'. E in questa modalità attuale confronteremo l'algoritmo RTT-Mid con compressori tradizionali.
Test comparativo del nuovo algoritmo di compressione
Il compressore RTT-Mid ha funzionato come parte di un programma di test. In un'applicazione 'reale', funziona notevolmente più velocemente, poiché sfrutta in modo efficiente la multithreading e utilizza un compilatore 'normale', non C#.
Poiché i compressori utilizzati nel test comparativo sono basati su principi diversi e comprimono diversi tipi di dati in modo differente, per ovviare la soggettività del test è stato utilizzato il metodo della 'media della temperatura in ospedale'...
È stato creato un file di dump settoriale del disco logico con il sistema operativo Windows 10; questo rappresenta la miscela più naturale di diverse strutture dati normalmente presenti su ogni computer. La compressione di questo file permetterà di confrontare la velocità e il grado di compressione del nuovo algoritmo con i compressori più avanzati utilizzati nei moderni archiviatori.
Ecco questo file dump:
Il file dump è stato compresso dai compressori RTT-Mid, 7-Zip e WinRar. I compressori WinRar e 7-Zip sono stati impostati sulla massima velocità di lavoro.
Funziona il compressore 7-zip:
Carica la CPU al 100%, mentre la velocità media di lettura del dump originale è di circa 60 Megabyte/sec.
Funziona il compressore WinRar:
Situazione simile, il caricamento della CPU è praticamente al 100%, con una velocità media di lettura del dump di circa 125 Megabyte/sec.
Come nel caso precedente, la velocità di lavoro dell'archiviatore è limitata dalle capacità del processore.
Ora funziona il programma di test del compressore RTT-Mid:
Lo screenshot mostra che la CPU è caricata al 50% e il resto del tempo rimane inattivo, poiché non ci sono dove scaricare i dati compressi. Il disco di scarico dei dati (Disco 0) è quasi completamente carico. La velocità di lettura dei dati (Disco 1) tende a oscillare, ma in media supera i 200 Megabyte/sec.
La velocità di funzionamento del compressore è limitata in questo caso dalla capacità di scrittura dei dati compressi sul Disco 0.
Ora, il grado di compressione degli archivi risultanti:
È evidente che il compressore RTT-Mid ha ottenuto i risultati migliori in termini di compressione, l'archivio da lui creato è di 1,3 Gigabyte più piccolo dell'archivio WinRar e di 2,1 Gigabyte più piccolo dell'archivio 7z.
Il tempo impiegato per creare l'archivio:
- 7-Zip – 26 minuti e 10 secondi;
- WinRar – 17 minuti e 40 secondi;
- RTT-Mid – 7 minuti e 30 secondi.
Pertanto, anche un programma di test non ottimizzato, utilizzando l'algoritmo RTT-Mid, è riuscito a creare un archivio più di due volte e mezzo più velocemente, risultando anche notevolmente più piccolo rispetto ai concorrenti...
Coloro che non credono agli screenshot possono verificarne l'autenticità autonomamente. Il programma di test è disponibile su , scaricate e verificate.
Ma solo su processori con supporto AVX-2; senza il supporto di queste istruzioni il compressore non funziona, e non testate l'algoritmo su vecchi processori AMD, poiché sono lenti nell'esecuzione dei comandi AVX…
Metodo di compressione utilizzato
L'algoritmo utilizza un metodo di indicizzazione dei frammenti di testo ripetuti a granularità byte. Questo metodo di compressione è conosciuto da tempo, ma non è stato utilizzato in precedenza, poiché l'operazione di ricerca delle corrispondenze richiedeva molte risorse e richiedeva molto più tempo rispetto alla costruzione di un dizionario. Pertanto, l'algoritmo RTT-Mid è un classico esempio di un ritorno al futuro…
Nel compressore RTT viene utilizzato uno scanner di ricerca delle corrispondenze unico e veloce, che ha reso possibile accelerare il processo di compressione. Lo scanner è di produzione propria, il che lo rende costoso, poiché è interamente fatto a mano (scritto in assembly).
Lo scanner di ricerca delle corrispondenze è realizzato secondo uno schema probabilistico a due livelli: inizialmente viene esaminata la presenza di un 'segnale' di corrispondenza, e solo dopo aver rilevato il 'segnale' in quel punto viene avviata la procedura per rilevare 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 dimensioni in megabyte, mentre per i dati con ripetizioni ha sempre dimensioni superiori a un megabyte.
Tuttavia, molti formati dati moderni non sono comprimibili e 'far girare' su di essi uno scanner ad alta intensità di risorse è inutile e dispendioso; pertanto, lo scanner utilizza due modalità operative. Inizialmente vengono cercate sezioni del testo originale con possibili ripetizioni; questa operazione viene eseguita anch'essa con un metodo probabilistico e avviene molto rapidamente (a una velocità di 4-6 Gigabyte/sec). Successivamente, le sezioni con possibili corrispondenze vengono elaborate dallo scanner principale.
La compressione per indicizzazione non è molto efficace, poiché è necessario 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 le corrispondenze complete delle stringhe byte, ma anche quelle parziali, quando nella stringa ci sono byte corrispondenti e non corrispondenti. A tal fine, il formato dell'indice include un campo di maschera di corrispondenza che indica i byte corrispondenti tra i due blocchi. Per una compressione ancora maggiore, viene utilizzata l'indicizzazione sovrapposta di più blocchi parzialmente corrispondenti sul blocco attuale.
Tutto ciò ha permesso al compressore RTT-Mid di raggiungere un grado di compressione paragonabile a quello dei compressori basati su metodi di dizionario, ma con una velocità di funzionamento significativamente superiore.
Velocità di funzionamento del nuovo algoritmo di compressione
Se il compressore opera con un utilizzo monopolistico della cache di memoria (richiesta di 4 Megabyte per un thread), la velocità di funzionamento oscilla tra 700 e 2000 Megabyte/sec. per ciascun core del processore, a seconda del tipo di dati compressi e dipende poco dalla frequenza di lavoro del processore.
Nell'implementazione multithreading del compressore, la scalabilità effettiva è determinata dalla dimensione della cache di terzo livello. Ad esempio, con 9 Megabyte di cache, non ha senso avviare più di due thread di compressione, poiché la velocità non aumenterà. Tuttavia, con una cache di 20 Megabyte, è possibile avviare già cinque thread di compressione.
Un altro parametro significativo che determina la velocità di funzionamento del compressore è la latenza della memoria RAM. L'algoritmo utilizza accessi casuali alla RAM, una parte dei quali non rientra nella cache (circa il 10%) e ciò lo costringe ad attendere i dati dalla RAM, il che riduce la velocità di funzionamento.
Influisce notevolmente sulla velocità del compressore anche il funzionamento del sistema di input/output dei dati. Le richieste di RAM dall'input/output bloccano gli accessi ai dati da parte della CPU, il che riduce anche la velocità di compressione. Questo problema è significativo per laptop e desktop, mentre server è meno rilevante grazie a un più avanzato blocco di gestione dell'accesso al bus di sistema e alla memoria RAM multicanale.
In tutto il testo dell'articolo si parla di compressione; la decompressione resta al di fuori dell'ambito di questo articolo, poiché lì 'tutto va bene'. La decompressione avviene in modo significativamente più veloce ed è limitata dalla velocità di input/output. Un singolo core fisico in un singolo thread riesce a garantire velocità di decompressione di 3-4 Gigabyte/sec.
Ciò è dovuto all'assenza, durante il processo di decompressione, dell'operazione di ricerca delle corrispondenze, che 'consuma' le principali risorse della CPU e della cache durante la compressione.
Affidabilità della conservazione dei dati compressi
Come suggerisce il nome dell'intera classe di software che utilizza la compressione dei dati (archiviatore), è destinata alla conservazione a lungo termine delle informazioni, non per anni, ma per secoli e millenni…
Nel tempo di archiviazione, 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 nel complesso l'informazione è 'leggibile'…
Nessuno dei produttori responsabili dei moderni sistemi di archiviazione digitale e dei supporti digitali fornisce 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 dei dati digitali possono perdere dati non solo dopo 75 anni; gli errori nei dati possono apparire in qualsiasi momento, anche durante la registrazione. Queste distorsioni vengono cercate di essere minimizzate utilizzando ridondanza e sistemi di correzione degli errori. La ridondanza e i sistemi di correzione possono recuperare informazioni perse, ma non sempre; e se lo fanno, non c'è garanzia che l'operazione di recupero sia avvenuta correttamente.
E anche questo è un grande problema, ma non rimandato, bensì attuale.
I moderni compressori usati per l'archiviazione dei dati digitali sono basati su diverse varianti del metodo lessicale, e per tali archivi, la perdita di un frammento di informazione è un evento fatale; esiste persino un termine consolidato per tale situazione: 'archivio danneggiato'…
La bassa affidabilità nella conservazione delle informazioni negli archivi con compressione lessicale è legata alla struttura dei dati compressi. Le informazioni in un tale archivio non contengono il testo originale; ci sono numeri di registrazione nel lessico, e il lessico viene modificato dinamicamente dal testo attuale in fase di compressione. In caso di perdita o distorsione di un frammento dell'archivio, tutte le registrazioni successive dell'archivio non possono essere identificate né per contenuto né per lunghezza della registrazione nel lessico, poiché non è chiaro a cosa corrisponda il numero della registrazione lessicale.
Recuperare informazioni da un tale 'archivio danneggiato' è impossibile.
L'algoritmo RTT si basa su un metodo di archiviazione dei dati compressi più affidabile. Utilizza un metodo indicizzato per tenere traccia di frammenti ripetuti. Questo approccio alla compressione permette di minimizzare le conseguenze delle distorsioni delle informazioni su un supporto, e in molti casi corregge automaticamente le distorsioni avvenute durante la conservazione delle informazioni.
Questo è dovuto al fatto che il file di archivio nel caso della compressione indicizzata contiene due campi:
- campo del testo originale con le porzioni di ripetizione rimosse;
- campo degli indici.
Il campo degli indici, critico per il recupero delle informazioni, non è grande e può essere duplicato per garantire l'affidabilità della conservazione dei dati. Pertanto, anche se un frammento del testo originale o dell'array degli indici viene perso, tutte le altre informazioni possono essere recuperate senza problemi, proprio come nell'immagine con il supporto di informazione 'analogico'.
Svantaggi dell'algoritmo
Non ci sono vantaggi senza svantaggi. Il metodo di compressione indicizzato non comprime le sequenze ripetute di piccole dimensioni. Ciò è dovuto ai limiti del metodo indicizzato. Gli indici hanno una dimensione di almeno 3 byte e possono arrivare fino a 12 byte. Se si verifica una ripetizione di dimensione inferiore a quella descritta dal suo indice, non viene presa in considerazione, indipendentemente da quanto spesso tali ripetizioni vengano riscontrate nel file compresso.
Il tradizionale metodo lessicale di compressione comprime efficacemente le molteplici ripetizioni di piccole dimensioni e perciò ottiene un rapporto di compressione maggiore rispetto alla compressione indicizzata. Tuttavia, questo è raggiunto a scapito di un elevato carico sulla CPU centrale; affinché il metodo lessicale inizi a comprimere i dati in modo più efficiente rispetto al metodo indicizzato, deve ridurre la velocità di elaborazione dei dati a 10-20 megabyte al secondo su sistemi di calcolo reali con CPU completamente caricata.
Tali basse velocità sono inaccettabili per i moderni sistemi di archiviazione dei dati e rappresentano più un interesse 'accademico' che pratico.
Il grado di compressione delle informazioni sarà sostanzialmente aumentato nella prossima modifica dell'algoritmo RTT (RTT-Max), che è già in fase di sviluppo.
Quindi, come sempre, continuera...
Fonte: habr.com
