UPDATE: Algoritmul este acum licențiat sub WTFPLv2. Codurile sursă sunt disponibile la https://github.com/schizofreny/middle-out.

Compresia middle-out nu mai este o invenție fictivă din serialul Silicon Valley de la HBO. Inspirați atât de emisiunea TV, cât și de noile seturi de instrucțiuni vectoriale, am venit cu un nou algoritm de compresie fără pierderi pentru datele din seriile de timp. Compresia este întotdeauna un compromis între viteză și raport și Nu este niciodată ușor să echilibrezi aceste compromisuri, dar întregul concept middle-out ne permite să împingem scorul Weissman și mai departe.

Simplu, rupe dependența datelor. Dacă avem nevoie de o valoare anterioară pentru a calcula o valoare curentă, avem nevoie de toate valorile antecedente. Dar dacă începem procesarea din mai multe poziții ale fragmentului, depindem doar de valorile antecedente din cadrul acestui fragment. Acest lucru ne permite, de exemplu, să folosim eficient instrucțiunile SIMD.

Cum funcționează?

În principiu, algoritmul calculează XOR-ul dintre o valoare nouă și cea anterioară. În acest fel, obținem un fel de diferență între valori și putem stoca doar această diferență. În seturile de date din seriile de timp, acest dif are, de obicei, un număr de zerouri anterioare și/sau posterioare. Prin urmare, informațiile pe care trebuie să le stocăm sunt, de obicei, semnificativ mai mici, dar trebuie, de asemenea, să stocăm numărul de zerouri de frunte și lungimea fragmentului XOR care nu este egal cu zero.

Aceste concepte sunt, în general, utilizate în algoritmii de compresie actuali, de exemplu, Gorilla de la Facebook . De dragul eficienței compresiei, Gorilla operează la nivel de biți, dar aceste operații sunt destul de extinse. Noi am proiectat compresia noastră pentru a fi cât mai rapidă posibil, așa că am trecut de la granularitatea de bit la cea de octet. În consecință, ne-am aștepta la un raport de compresie mai prost, dar nu este întotdeauna cazul.

În ceea ce privește middle-out, compresia operează pe blocuri de date, dar aceasta nu este o problemă deoarece bazele de date cu serii de timp utilizează oricum blocuri.

Cum rămâne cu raportul de compresie?

Să examinăm raportul de compresie în două scenarii diferite. Primul scenariu – luăm o serie de duble (adică 0,1, 0,2, 0,3, …) și măsurăm raportul de compresie în funcție de porțiunea de puncte care se repetă. Pentru comparație, folosim compresia Gorilla de la Facebook. În mod implicit, Gorilla comprimă atât valorile, cât și marcajele temporale ale datelor din seriile de timp. În scopul testului nostru, compresia timestamp-urilor este dezactivată.

Nu este surprinzător să constatăm că Gorilla are un raport de compresie ușor mai bun pentru aceste tipuri de date. Putem observa aceeași tendință în cazul secvențelor cu numere întregi lungi.

Secundul scenariu – seturi de date. Seturile de date A și B împart aceleași date de stocuri de minute. În cazul setului de date A, punctele de preț sunt comprimate ca numere cu virgulă mobilă. În setul de date B, aceste numere sunt mai întâi înmulțite pentru a deplasa virgula zecimală și, prin urmare, putem reprezenta aceste numere ca numere lungi fără a pierde din precizie.

Seturile de date C și D sunt generate cu ajutorul unui instrument de analiză comparativă de la InfluxData : reprezentând scrieri pe disc și utilizarea memoriei redis. În cazul setului de date A, Gorilla comprimă datele puțin mai bine decât algoritmul nostru – cu un raport de 1,45 față de 1,3. Alte seturi de date care utilizează numere întregi sunt mai bine comprimate cu noul nostru algoritm. Cea mai mare diferență poate fi observată în cazul setului de date D, unde raportul de compresie Middle-out este de 3,3, în timp ce Gorilla poate comprima aceste date doar cu un raport de 1,84. Raportul de compresie depinde în mare măsură de datele de intrare și, în mod evident, există seturi de date în care un algoritm comprimă mai bine decât altul. Dar dacă performanța este preocuparea dumneavoastră – continuați să citiți.

Performanța comprimării

În prezent avem două implementări compatibile ale algoritmului. Una utilizează un nou set de instrucțiuni AVX-512 disponibil pe procesoarele Skylake-X. Cea de-a doua implementare se adresează calculatoarelor care nu suportă acest set de instrucțiuni.

Trasmiterea este măsurată pe un singur nucleu Skylake-X care rulează la 2,0 GHz.

Graficele următoare arată viteza de compresie și decompresie a ambelor implementări în comparație cu Gorilla de la Facebook.

Acest grafic arată viteza de compresie măsurată pe cele patru seturi de date discutate mai sus, plus viteza de compresie a unei serii cu procentul respectiv de valori care se repetă.

Viteza de compresie a Gorilla variază între 120-440 MB/s, cu o viteză medie de 185 MB/s. Cel mai mic randament al implementării noastre scalare comprimă în jur de 670 MB/s pentru 50% din valorile care se repetă. Acest lucru se datorează unui raport ridicat de eroare de anticipare a ramurii. Viteza medie de compresie este de 1,27 GB/s. Un algoritm care utilizează instrucțiuni vectoriale nu suferă de erori de predicție a ramurilor și comprimă datele de la 2,33 GB/s la 2,59 GB/s, cu o viteză medie de 2,48 GB/s. Nu e rău pentru un cip cu un singur nucleu de 2 GHz.

Gorilla poate decomprima aceste date la viteze cuprinse între 100 MB/s și 430 MB/s . Dar, după cum puteți vedea, decompresia noastră a acelorași date este chiar mai rapidă decât o compresie. Descompactarea nevectorizată funcționează la o viteză minimă de 2,36 GB/s și 2,7 GB/s în medie. Codurile vectorizate decomprimă datele de la 3,4 GB/s, atingând 4,86 GB/s pentru setul de date D. În medie, este capabil să decomprime datele la 4,0 GB/s.

Viteza medie globală pentru compresie este de 6,8x (implementare scalară) și de 13,4x (implementare vectorizată). Accelerarea medie pentru decompresie este de 16,1x și, respectiv, 22,5x.

Despre noi

Noi, la Schizofreny, suntem dedicați performanței și credem că limitele pot fi întotdeauna împinse mai departe. Ne plac provocările și suntem aici pentru a vă ajuta cu problemele dumneavoastră HPC.

Partea II

www.vldb.org/pvldb/vol8/p1816-teller.pdf

https://github.com/influxdata/influxdb-comparisons/

.