Aggiornamento: L’algoritmo è ora sotto licenza WTFPLv2. Codici sorgente disponibili a https://github.com/schizofreny/middle-out.
La compressione middle-out non è più un’invenzione fittizia dello show Silicon Valley della HBO. Ispirati sia dallo show televisivo che dai nuovi set di istruzioni vettoriali, abbiamo sviluppato un nuovo algoritmo di compressione senza perdita di dati per le serie temporali. La compressione è sempre un compromesso tra velocità e rapporto e non è mai facile bilanciare questi compromessi, ma l’intero concetto di middle-out ci permette di spingere il punteggio di Weissman ancora oltre.
Si rompe semplicemente la dipendenza dai dati. Se abbiamo bisogno di un valore precedente per calcolarne uno attuale, abbiamo bisogno di tutti i valori antecedenti. Ma se iniziamo l’elaborazione da più posizioni del chunk, dipendiamo solo dai valori antecedenti all’interno di questo frammento. Questo ci permette, per esempio, di usare efficacemente le istruzioni SIMD.
Come funziona?
In linea di principio, l’algoritmo calcola lo XOR di un nuovo valore e quello precedente. In questo modo otteniamo una sorta di differenza tra i valori e possiamo memorizzare solo questa differenza. Negli insiemi di dati di serie temporali questa differenza ha tipicamente un numero di zeri iniziali e/o finali. Quindi l’informazione che dobbiamo memorizzare è di solito significativamente più piccola, ma abbiamo anche bisogno di memorizzare il conteggio degli zeri iniziali e la lunghezza del frammento XOR non nullo.
Questi concetti sono generalmente utilizzati negli algoritmi di compressione attuali, ad esempio il Gorilla di Facebook. Per l’efficienza della compressione, Gorilla opera a livello di bit, ma queste operazioni sono abbastanza espansive. Abbiamo progettato la nostra compressione per essere il più veloce possibile, quindi siamo passati dalla granularità bit a quella byte. Di conseguenza, ci si aspetterebbe un rapporto di compressione peggiore, ma non è sempre così.
Per quanto riguarda il middle-out, la compressione opera su blocchi di dati, ma questo non è un problema perché i database di serie temporali utilizzano comunque dei blocchi.
Che dire del rapporto di compressione?
Esaminiamo il rapporto di compressione in due diversi scenari. Il primo scenario – prendiamo una serie di doppie (cioè 0,1, 0,2, 0,3, …) e misuriamo il rapporto di compressione a seconda della porzione di punti ripetuti. Per il confronto usiamo la compressione Gorilla di Facebook. Per impostazione predefinita Gorilla comprime sia i valori che i timestamp dei dati delle serie temporali. Per i nostri scopi di test, la compressione dei timestamp è disabilitata.
Non è sorprendente scoprire che Gorilla ha un rapporto di compressione leggermente migliore per questi tipi di dati. Possiamo vedere la stessa tendenza con le sequenze intere lunghe.
Secondo scenario – set di dati. I set di dati A e B condividono gli stessi dati di stock di minuti. Nel caso del set di dati A, i punti di prezzo sono compressi come numeri in virgola mobile. Nel set di dati B questi numeri sono prima moltiplicati per spostare la virgola e quindi possiamo rappresentare questi numeri come lunghi senza perdere precisione.
I set di dati C e D sono generati utilizzando uno strumento di benchmarking di InfluxData: rappresentano le scritture su disco e l’utilizzo della memoria redis. Nel caso del set di dati A, Gorilla comprime i dati leggermente meglio del nostro algoritmo – con un rapporto di 1,45 contro 1,3. Altri set di dati che utilizzano numeri interi sono meglio compressi con il nostro nuovo algoritmo. La più grande differenza può essere vista nel set di dati D dove il rapporto di compressione Middle-out è 3.3, mentre Gorilla può comprimere questi dati solo con un rapporto di 1.84. Il rapporto di compressione dipende sostanzialmente dall’input dei dati e ci sono ovviamente set di dati in cui un algoritmo comprime meglio di un altro. Ma se la performance è la tua preoccupazione – continua a leggere.
Prestazioni di compressione
Al momento abbiamo due implementazioni compatibili dell’algoritmo. Una utilizza un nuovo set di istruzioni AVX-512 disponibile sulle CPU Skylake-X. La seconda implementazione si rivolge a computer senza il supporto di questo set di istruzioni.
Il throughput è misurato su un singolo core di Skylake-X in esecuzione a 2,0 GHz.
I seguenti grafici mostrano la velocità di compressione e decompressione di entrambe le implementazioni rispetto a Gorilla di Facebook.
Questo grafico mostra il throughput di compressione come misurato sui quattro set di dati discussi sopra, più il throughput di una serie con la rispettiva percentuale di valori ripetuti.
Il throughput della compressione Gorilla varia da 120-440 MB/s con una velocità media di 185 MB/s. Il throughput più basso della nostra implementazione scalare comprime circa 670 MB/s per il 50% dei valori ripetuti. Questo è dovuto ad un alto rapporto di misprediction del ramo. La velocità media di compressione è di 1,27 GB/s. Un algoritmo che usa istruzioni vettoriali non soffre di branch misprediction e comprime i dati da 2,33 GB/s a 2,59 GB/s, con una velocità media di 2,48 GB/s. Non male per un singolo core di chip da 2 GHz.
Gorilla può decomprimere questi dati a velocità che vanno da 100 MB/s a 430 MB/s . Ma come potete vedere, la nostra decompressione degli stessi dati è ancora più veloce di una compressione. La decompressione non vettorizzata opera a una velocità minima di 2,36 GB/s e 2,7 GB/s in media. I codici vettorizzati decomprimono i dati da 3,4 GB/s, toccando i 4,86 GB/s per il set di dati D. In media è in grado di decomprimere i dati a 4,0 GB/s.
La velocità media complessiva per la compressione è 6,8x (implementazione scalare) e 13,4x (implementazione vettorizzata). L’accelerazione media per la decompressione è 16,1x e 22,5x rispettivamente.
Chi siamo
Noi di Schizofreny ci dedichiamo alle prestazioni e crediamo che i limiti possano sempre essere superati. Amiamo le sfide e siamo qui per aiutarvi con i vostri problemi HPC.
Parte II
www.vldb.org/pvldb/vol8/p1816-teller.pdf
https://github.com/influxdata/influxdb-comparisons/