Deduplicazione vs. compressione: i due approcci per la minimizzazione dei dati

Secondo l’IDC, l’istituto internazionale delle indagini di mercato, ogni 24 mesi raddoppia la quantità di dati a livello mondiale. Già nel 2020 l’universo digitale comprenderà 44 zettabyte di dati e ciò significa che ci saranno 44 trilioni di gigabyte, prodotti in un anno o copiati dai file originali. Un’evoluzione simile incide soprattutto sulle tecniche di memorizzazione, le procedure di backup e i sistemi di ripristino (recovery systems), che devono essere in grado di gestire ed elaborare l’enorme carico di dati. I concetti alla base della realizzazione tecnica danno primaria importanza ai metodi che consentono la riduzione delle informazioni fisicamente salvate su un supporto e che fanno così abbassare notevolmente i costi della memorizzazione dei dati. Queste metodologie si basano essenzialmente su due approcci: la compressione dei dati e la deduplicazione. Per minimizzare i dati, una compressione senza perdita di informazioni utilizza le ridondanze all’interno di un file, mentre gli algoritmi di deduplicazione si occupano dei dati presenti sulle diverse piattaforme per evitare doppioni. La deduplicazione viene quindi usata principalmente per il backup dei dati.

Deduplicazione

Con deduplicazione si indica un processo per la riduzione dei dati, che consiste essenzialmente nell’evitare la ridondanza dei dati in un sistema di memoria. Per affrontare questo processo entra in azione un motore di deduplicazione, che si serve di specifici algoritmi per identificare e eliminare i file ridondanti o blocchi di dati. Si può integrare in un software per il backup o realizzare come un’appliance hardware.

L’obiettivo della deduplicazione nell’ambito della memorizzazione è quello di scrivere solamente le informazioni necessarie su un supporto dati non volatile per poter ricostruire senza perdite di informazioni un file. Più doppioni vengono eliminati, minore diventa la quantità di dati che devono essere salvati o trasferiti. L’identificazione dei doppioni può avvenire a livello dei file, com’è il caso di Git o Dropbox, ma sono senz’altro più efficienti gli algoritmi di deduplicazione, poiché agiscono a livello di sottofile. Successivamente i file vengono scomposti in blocchi di dati (chunks) e dotati di una somma di controllo (checksum) univoca, ovvero gli hash. Come istanza di controllo principale viene usato un tracking database, che comprende tutte le checksum.

Il metodo di deduplicazione basato sui blocchi si suddivide in due varianti:

  • La deduplicazione con una lunghezza dei blocchi predefinita: in una deduplicazione con una lunghezza dei blocchi predefinita l’algoritmo suddivide i file in segmenti della stessa lunghezza, orientandosi in genere alle dimensioni del cluster del file o del sistema RAID (tipicamente di 4KB), ma configurabile anche manualmente. In questo caso la lunghezza dei blocchi personalizzata diventa lo standard per tutti gli altri dati.
  • La deduplicazione con una lunghezza dei blocchi variabile: in una deduplicazione con la lunghezza dei blocchi variabile non viene stabilita alcuna lunghezza standard e quindi l’algoritmo divide i dati in blocchi diversi di lunghezza variabile a seconda dei dati da elaborare.

La variante scelta per la divisione in blocchi si ripercuote notevolmente sull’efficienza della deduplicazione dei dati, visibile soprattutto quando si modificano successivamente i file deduplicati. Se si amplia con informazioni aggiuntive un blocco con limiti fissi, di solito si sposta anche il contenuto di tutti i blocchi successivi correlati ai limiti predefiniti. Sebbene la modifica riguardi solo un blocco di dati, vengono classificati nuovamente anche tutti i segmenti successivi di un file per via dello spostamento dei limiti da parte dell’algoritmo di deduplicazione, a meno che i byte modificati non risultino esattamente un multiplo della lunghezza dei blocchi predefiniti. Visto che i blocchi modificati devono essere messi nuovamente in sicurezza, in caso di un backup, in una deduplicazione con una lunghezza fissa dei blocchi aumentano sia le prestazioni richieste al computer che l’utilizzo della banda larga.

Se invece un algoritmo utilizza dei limiti variabili per la lunghezza dei blocchi, le modifiche di un singolo blocco non incidono sui segmenti adiacenti. Al contrario, il blocco modificato viene solo ampliato di nuovi byte e salvato, alleggerendo la rete, dato che devono essere trasferiti meno dati nel backup. La flessibilità riguardo alle modifiche dei file richiede maggiori prestazioni, visto che l’algoritmo deve prima capire come sono divisi i chunks per poter avviare il processo.

L’identificazione di chunk ridondanti si basa sulla supposizione che i blocchi di dati con hash identici comprendono informazioni identiche. Per individuare i chunk ridondanti, l’algoritmo di deduplicazione necessita di nuovi hash da bilanciare con il tracking database. Se vengono riscontrate delle somme di controllo identiche, i chunk ridondanti vengono sostituiti da un puntatore (pointer), che rimanda al luogo di archiviazione dello stesso blocco. Lo spazio richiesto dal puntatore è minore rispetto a quello di un blocco di dati. Maggiore è il numero di chunk in un file che possono essere sostituiti da un segnaposto, meno spazio richiederanno. Non è però possibile prevedere l’efficienza della riduzione dei dati tramite gli algoritmi di deduplicazione, visto che il file in uscita e la sua struttura dipendono fortemente da questi. Inoltre, la deduplicazione è adatta solo per dati non cifrati. Infatti nei sistemi di crittografia le ridondanze vengono appositamente evitate, rendendo così impossibile riconoscere un particolare schema da seguire.

La deduplicazione si può realizzare nella destinazione di archiviazione o alla sorgente.

Deduplicazione alla sorgente

Se i dati ridondanti vengono eliminati già prima del trasferimento alla destinazione di memorizzazione, si parla di una deduplicazione alla sorgente. In questo caso il motore di deduplicazione è ad esempio integrato nel software di backup. Le informazioni ridondanti vengono eliminate direttamente nel file system della sorgente dati. Qui il software di backup scansiona i blocchi modificati a intervalli regolari e li compara con quelli che sono stati già salvati sul server di backup. Se si trova un blocco ridondante, verrà ignorato e non incluso nel prossimo backup. Se un file è stato rielaborato, il software di backup trasmette solo la nuova parte.

Il più grande vantaggio di questo metodo di deduplicazione è che nell’ambito delle copie di sicurezza vengono trasferite al server di backup solo le nuove informazioni, cosa che alleggerisce sia la banda larga sia la capacità della destinazione di archiviazione. A differenza della deduplicazione target (quella nella destinazione di archiviazione), il metodo alla sorgente richiede maggiori prestazioni per il software di backup e quindi non è adatto per tutti i tipi di utilizzo.

Deduplicazione target

Nella deduplicazione target, la riduzione dei dati avviene al di fuori della sorgente dati. Qui il motore di deduplicazione può essere integrato nell’array dell’hardware o attivato come appliance indipendente. In entrambi i casi la deduplicazione target riduce la capacità di memoria necessaria, ma diversamente dalla deduplicazione alla sorgente non ha alcun influsso sulla quantità di dati trasferiti durante il backup dalla sorgente alla destinazione di archiviazione tramite LAN o WAN. A seconda di quale struttura venga scelta per la deduplicazione target, si distingue tra deduplicazione post-processing e deduplicazione inline.

  • Deduplicazione post-processing: se il motore di deduplicazione è integrato nell’array, i dati del backup vengono prima immagazzinati non manipolati sul supporto di memoria e successivamente deduplicati. In questo caso si parla di deduplicazione post-processing. Questo tipo di deduplicazione offre il vantaggio che i dati possono essere trasmessi alla destinazione di archiviazione abbastanza velocemente, ma non saranno immediatamente disponibili dopo il trasferimento perché per poter eliminare le ridonanze, deve prima terminare il processo di backup. In questo modo i dati sul disco rigido vengono indirizzati 3 volte, prima che siano a disposizione per una duplicazione o per essere aperti, aumentando così lo sfruttamento del sistema di memoria. Inoltre il sistema di backup deve mettere a disposizione 2 zone separate di memoria: una per i dati in uscita e una per i dati deduplicati. Così è richiesto temporaneamente uno spazio fisico maggiore rispetto a quello di una deduplicazione inline. A differenza di quest’ultima, la deduplicazione post-processing consente una riduzione dei dati più efficiente sulla base di blocchi di dati variabili.
  • Deduplicazione inline: se il motore di deduplicazione è collocato prima del supporto di memoria, è possibile rimuovere i dati ridondanti direttamente durante il trasferimento, ancora prima che questi vengano scritti sul supporto di memoria. Ciò riduce il flusso di scrittura e limita la deduplicazione ai blocchi con una lunghezza fissa, ma riduce notevolmente la memoria fisica necessaria, che deve essere mantenuta sul sistema di destinazione, specialmente se paragonata alla deduplicazione post-processing. Inoltre i dati che sono stati deduplicati inline sono messi subito a disposizione per un ripristino dei dati o per la loro riproduzione.

Compressione dei dati

Nella compressione dei dati, i file vengono trasferiti in un modo alternativo più efficiente rispetto a quello originario. L’obiettivo di questa codifica è quello di ridurre lo spazio necessario, ma anche il tempo di trasferimento. Un adeguato tasso di compressione si può raggiungere tramite due diversi approcci:

  • Compressione delle ridondanze: in una compressione senza perdite (chiamata anche lossless) basata sulla riduzione delle ridondanze, i dati vengono decompressi senza alcuna alterazione di bit, anche dopo aver subito il processo di compressione, i file in entrata e quelli in uscita sono quindi identici. Una compressione simile è possibile sole se un file contiene delle informazioni ridondanti.
  • Compressione delle irrilevanze: nella compressione con perdita di dati (chiamata anche lossy) vengono eliminate le informazioni irrilevanti per comprimere un file, a scapito però dei dati. Infatti, dopo una compressione delle irrilevanze, i dati da ripristinare saranno molto simili a quelli originari, ma non più gli stessi. I criteri utilizzati per decidere quali dati siano irrilevanti sono variabili. Con una compressione audio MP3 vengono ad esempio rimosse alcune frequenze non percepibili dall’orecchio umano.

La compressione a livello dei sistemi di memoria avviene essenzialmente senza perdita di dati, mentre sono ormai accettate le perdite in altri settori per ottenere una riduzione delle dimensioni dei file, come nella riproduzione di immagini, video e audio.

Sia la codifica che la decodifica di un file richiedono prestazioni specifiche, variabili a seconda del metodo di compressione utilizzato. Alcune tecniche si basano su una presentazione il più possibile compatta dei dati in uscita, mentre in altre è fondamentale la riduzione del tempo necessario per l’elaborazione. La scelta del metodo di compressione dipende perciò sempre dal tipo di file e dall’uso che se ne vuole fare.

Nell’ambito di una trasmissione live, in cui viene registrato l’audio e il video, si consiglia ad esempio di scegliere un procedimento che consenta una compressione e un ripristino dei dati il più veloce possibile. Una minore compressione e delle possibili perdite di qualità sono in questo caso sostenibili. Diversa è la situazione nei file che sono messi a disposizione per un gran numero di utenti tramite un file server: qui si accetta un tempo maggiore per la compressione, utilizzando così un algoritmo di compressione più performante, che consenta una riduzione dei dati maggiore senza perdite di qualità.

Compressione dei dati senza perdite

Mentre un algoritmo di deduplicazione cerca gli stessi segmenti di dati in file diversi e sostituisce quelli ridondanti tramite segnaposti che rimandano a questi, i procedimenti di compressione dei dati senza perdite si servono delle cosiddette rappresentanze. In questo caso i segmenti che si ripetono più volte in un file vengono sostituiti da una rappresentazione molto più ridotta, visualizzabile come nell’esempio seguente:

Testo in uscita: ABCDEABCEEABCEE

Codifica: ABC = 1; EE = 2

Testo compresso: 1DE1212

Il testo in uscita con una lunghezza originaria di 15 caratteri si può ridurre a 7; il tasso di compressione ammonta così a più del 50%. Per attuare una compressione simile, la codifica alla base del sistema di codifica e quello di decodifica è la stessa.

La maggior parte dei processi senza perdita di informazioni utilizza la ripetizione dei caratteri o di una combinazione di caratteri all’interno di uno stesso file. Tra i procedimenti di compressione più conosciuti, basati sulla ripetizione, rientrano la codifica delle informazioni e il procedimento Lempel-Ziv (LZ77).

  • Codifica delle informazioni: i procedimenti di compressione basati sulla codifica delle informazioni sono particolarmente indicati per i file testuali. Il principio alla base è la sostituzione di parole tramite rappresentanze più brevi. A questo scopo viene creata per prima cosa una lista e assegnato un valore ad ogni parola nel file. Così si calcolano i codici numerici nei testi.

Testo in uscita:              essere o non essere

Codifica:                          essere=1, o= 2, non=3

Testo compresso:          1231

La codifica delle informazioni è particolarmente efficace nei testi più lunghi con molte ripetizioni, perché utilizzando questo procedimento di compressione, oltre ai dati, viene anche salvata la lista delle parole.

  • Procedimento Lempel-Ziv: anche il procedimento Lempel-Ziv è un metodo basato su dizionario, che consente di comprimere le sequenze di caratteri sulla base di ridondanze. Così l’algoritmo di compressione utilizza il contenuto letto fino ad ora come dizionario, senza che debba essere fornito in modo aggiuntivo. Il rinvio ad una sequenza di caratteri identica nel flusso di dati letto finora avviene tramite una tripla, che codifica la posizione e la lunghezza della parte da copiare così come il primo carattere non corrispondente. Il bilanciamento avviene tramite un’iterazione e un buffer. Se per un carattere non si trova nessuna corrispondenza, la tripla sarà (0, 0, x), dove “x” rappresenta il carattere corrispondente. Il seguente esempio mostra una codifica LZ77 della parola tedesca BANANE (banana):

La sequenza di caratteri nel buffer viene paragonato con i caratteri già letti nell’iterazione. Se si riscontrano delle equivalenze, i caratteri corrispondenti nell’iterazione vengono sostituiti da una tripla che rimanda a questi. Nella riga 4 viene sostituito la sequenza ANE con la tripla (2,2,E), che si legge nel modo seguente:

2 = Sostituisce la sequenza attuale tramite una sequenza di caratteri già letta, che inizia alla posizione 2 dell’iterazione (A).

2 = La sostituzione comprende due caratteri (A e N).

E = Il primo carattere dopo la sostituzione è la E.

È possibile comprimere efficacemente la maggior parte dei dati tramite LZ77, cosa che rende questo e i successivi algoritmi, come LZSS, ancora largamente diffusi e utilizzati soprattutto per i formati ZIP, immagini in PNG o file PDF.

Oltre ai procedimenti basati sulla ripetizione, nella compressione senza perdita di informazioni sono utilizzati anche i metodi basati sulla frequenza come il run-length encoding o la codifica di Huffman.

  • Run-length encoding: nella run-length encoding (RLE) vengono analizzate le ridondanze generate da un susseguirsi in sequenza di caratteri uguali. Questo processo si può chiarire meglio con una rappresentazione schematica di una riga di immagine di un elemento grafico in bianco e nero.

Dati in uscita: WWWWWSSSSWWSSWWWWWWSSSSSSWWW

Si ottiene una riduzione più chiara dei dati da salvare, sostituendo il carattere che si ripete con una coppia di valori, composta dal carattere e dal numero di ripetizioni.

File compresso: 5W4S2W2S6W6S3W

L’algoritmo di RLE è utilizzato nella compressione delle immagini, ma diventa meno efficiente, se devono essere codificati più colori diversi. Mentre gli schizzi in bianco e in nero si possono stampare solo utilizzando due tonalità, per le immagini con gradazioni di grigio a 8 bit sono richieste invece 256 tonalità di grigio. La possibilità che più di due pixel successivi presentino lo stesso colore, diminuisce nel caso di immagini complesse con diverse tonalità di colori. Considerando che la codifica nell’esempio si basa su coppie di valori a due cifre, si ottiene una maggiore compressione solo se si susseguono almeno 3 caratteri uguali. Una forma modificata del run-length encoding fa parte del conosciuto procedimento di compressione delle immagini JPEG.

  • Codifica di Huffman: nella compressione dei dati di Huffman viene individuata la frequenza di tutti i caratteri presenti in un file. Nel passaggio successivo i caratteri vengono convertiti in una sequenza di bit, dove si orienta la lunghezza della rappresentanza in base alla frequenza. La rappresentazione grafica della codifica di Huffman consiste in un albero binario collegato ai simboli da codificare (visti come foglie). Utilizziamo la frase di esempio “this is an example of a huffman tree“ per chiarire meglio questo metodo.

Caratteri

Spazi vuoti

a

e

f

h

i

m

n

s

t

l

o

p

r

u

x

Frequenza

7

4

4

3

2

2

2

2

2

2

1

1

1

1

1

1

Il rispettivo codice binario di un carattere risulta dal percorso effettuato dalle radici per raggiungere le foglie. Qui le diramazioni a sinistra vengono codificate con uno 0 e quelle a destra con un 1.

Dai caratteri della frase di esempio risulta quindi il seguente codice:

Spazi vuoti

a

e

f

h

i

m

n

111

010

000

1101

1010

1000

0111

0010

s

t

l

o

p

r

u

x

1011

0110

11001

00110

10011

11000

00111

10010

In questo esempio, i caratteri che compaiono spesso, come lo spazio vuoto, la a e la e, sono codificati solo con 3 bit, mentre i caratteri più rari come r, u o x richiedono una codifica a 5 bit. Da tenere presente che ad esempio il codice ASCII utilizza 7 bit per carattere. Nelle codifiche di caratteri compatibili con ASCII, come UTF-8 o ISO 8859-1 (Latin-1), viene di norma aggiunto un ottavo bit, visto che i computer attuali lavorano a 8,16,32 o a 64 Bit. Nella codifica di Huffman si può così salvare il testo in modo più compatto.

La seguente serie di caratteri mostra la frase di esempio “this is an example of a huffman tree“, ricorrendo al codice binario di Huffman:

0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000

Un confronto con la sequenza di bit dello stesso contenuto in base alla codifica ASCII con un ottavo bit aggiunto (rispettivamente il primo 0):

01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 01100001 01101110 00100000 01110100 01110010 01100101 01100101

A seconda della distribuzione della frequenza dei caratteri, con la codifica di Huffman si possono ridurre i dati ad 1/3 delle dimensioni originali. Ma è da notare che deve essere memorizzato anche l’albero binario per permettere una successiva decodifica.

La codifica di Huffman non è solo usata nella compressione di file testuali. Il metodo trova anche applicazione come passaggio del procedimento di compressione delle immagini JPEG e nel formato ZIP, che si presenta come una combinazione tra l’algoritmo LZSS e la codifica di Huffman.

Compressione con perdita

Mentre la compressione dei dati senza perdita è possibile solo se si riscontrano ridondanze all’interno di un file, la compressione con perdita di informazioni è principalmente sempre possibile sulla base della riduzione delle irrilevanze, a patto che si presuppongano delle perdite di dati. Essenzialmente nella compressione con perdita di informazioni si decide quale parte dei dati originali non sia necessaria. Un limite teorico per una compressione massima si può indagare con la teoria rate distortion, che indica il rapporto tra compressione e qualità del segnale.

I procedimenti di compressione con perdita di informazioni si orientano in genere sulla percezione umana. Così nella compressione di audio dati in MP3, AAC o WMA vengono ad esempio eliminate le frequenze, che non sono percepibili dall’orecchio umano. Un esempio comune per la riduzione delle irrilevanze riguarda le immagini salvate in formato JPEG, dove sono combinati i metodi di compressione senza e con perdite di informazioni. Tra questi ultimi rientrano ad esempio la conversione dei colori dal sistema RGB al modello YCbCr, la trasformata discreta del coseno (DCT) e la quantizzazione.

La deduplicazione e la compressione dei dati a confronto

Per realizzare delle procedure di backup o per ottimizzare lo spazio nei file system standard, le aziende ricorrono solitamente alla deduplicazione, visto l’estrema efficienza di questi sistemi nel caso in cui debbano essere memorizzati dei file identici.

I processi di compressione dei dati prevedono solitamente un maggiore utilizzo delle risorse e necessitano perciò di piattaforme più complesse. I sistemi di memorizzazione si possono utilizzare nella maniera più efficace con una combinazione di entrambi i metodi di riduzione dei dati. Così le ridondanze nei file da salvare vengono rimosse tramite deduplicazione e i dati rimasti vengono successivamente compressi.


Abbiamo una proposta per te:
Web hosting a partire da 1 €/mese!

Dominio gratis
Certificato SSL Wildcard incluso
Assistenza clienti 24/7
A partire da 1 €/mese IVA escl. per un anno,
poi 8 €/ mese IVA escl.