Facebook: un algoritmo di compressione moderno

Zstandard è un algoritmo di compressione sviluppato da Facebook che sembra offrire migliori prestazioni rispetto agli attuali standard (Deflate)

 

Facebook ha reso ufficialmente disponibile su GitHub il codice sorgente di Zstandard, un algoritmo di compressione sviluppato internamente. Secondo quanto affermato da Yann Collet e Chip Turner (ingegneri d’alto profilo dell’azienda, il primo è l’ideatore originario del progetto), Zstandard ha tutte le carte in regola per rimpiazzare Deflate, l’algoritmo alla base di noti formati come Zip e Zlib ed a tutti gli effetti l’attuale standard del settore.

Zstandard, ha dichiarato la compagnia, è in utilizzo nei data center proprietari da circa sei mesi – ha permesso di ridurre del 6% il quantitativo di storage richiesto dai dati in archivio/da archiviare e la capacità computazionale da destinare alle operazioni di compressione (-19%) e decompressione (-40%). Queste ultime, raffrontate con soluzioni alternative, sono risultate più rapide restituendo file di dimensioni contenute.

Il seguente benchmark mostra i risultati ottenuti da Zstandard e Zlib con il cosidetto metodo di compressione loseless Silesia corpus:

Zstandard e Zlib a confronto - fonte Facebook

Zstandard e Zlib a confronto – fonte Facebook

Zstandard è stato in grado di superare agevolmente Zlib in ogni test, indipendentemente dal livello di compressione scelto e dalla banda disponibile. In generale si  osserva che:

  • a parità di compression rate, Zstandard si è dimostrato da 3 a 5 volte più veloce;
  • a parità di compression speed, i file prodotti sono risultati dal 10 al 15% più piccoli;
  • indipendentemente dalla compression ratio, le operazioni di decompressione sono state eseguite nella metà del tempo;
  • Zstandard è stato in grado di scalare fino ad un compression ratio più elevato (4x invece di 3.15)

Un algoritmo di compressione moderno

L’algoritmo Deflate, osservano gli ingegneri, è ormai sulla scena da diversi decenni (fu ideato negli degli anni ’90) e risente inevitabilmente dei limiti tecnologici dell’epoca. I processori erano ad esempio stati pensati per eseguire una sola operazione alla volta e non diverse task in parallelo, come al giorno d’oggi – caratteristica indicata dal termine parallel execution. Zstandard è inoltre in grado di utilizzare un quantitativo di memoria superiore ( in teoria illimitato ma si consiglia di impostare la soglia massima ad 8MB) rispetto a Deflate, limitato a soli 32KB.

Zstandard è stato inoltre progettato per sfruttare al meglio il design branchless. “Le CPU moderne [giocano d’azzardo]” si legge nel post degli ingegneri Collett e Turner. In sintesi, il modus operandi previsto dal design branchless prevede che la CPU, di fronte all’esecuzione di una task dipendente dal risultato di un’altra task, cerchi di dedurre autonomamente tale risultato, al fine di eseguire in anticipo l’operazione principale.La CPU non è tuttavia in grado di indovinare sempre il risultato incorrendo nelle pipeline flush, situazioni che obbligano la CPU a ricominciare il lavoro da capo e ad impegnare un quantitativo maggiore di capacità computazionale. L’algoritmo cerca allora di avvantaggiarsi del design branchless riducendo al minimo gli eventuali disagi causati dalle deduzioni errate.

In base a quanto visto, le potenzialità di Zstandard sembrano elevate. E per il futuro gli ingegneri Facebook promettono l’arrivo di altre novità, come il supporto multi-thread e livelli di compressione più efficienti.

 

 

Facci sapere cosa ne pensi!

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *