PÄIVITYS: Algoritmi on nyt WTFPLv2-lisensoitu. Lähdekoodit saatavilla osoitteessa https://github.com/schizofreny/middle-out.
Middle-out-pakkaus ei ole enää HBO:n Silicon Valley -sarjan fiktiivinen keksintö. Sekä tv-sarjan että uusien vektorikomentosarjojen innoittamana keksimme uuden häviöttömän pakkausalgoritmin aikasarjadataa varten. Pakkaamisessa on aina kyse kompromissista nopeuden ja suhdeluvun välillä, eikä näiden kompromissien tasapainottaminen ole koskaan helppoa, mutta koko middle-out-konsepti antaa meille mahdollisuuden viedä Weissmanin pistemäärää vieläkin pidemmälle.
Se yksinkertaisesti katkaisee datan riippuvuuden. Jos tarvitsemme edellistä arvoa nykyisen arvon laskemiseen, tarvitsemme kaikki edeltävät arvot. Mutta jos aloitamme käsittelyn useammasta kohdasta lohkossa, olemme riippuvaisia vain tämän lohkon sisällä olevista edeltävistä arvoista. Näin voimme esimerkiksi käyttää tehokkaasti SIMD-käskyjä.
Miten se toimii?
Periaatteessa algoritmi laskee uuden arvon ja edellisen arvon XOR:n. Näin saamme eräänlaisen diffin arvojen välille ja voimme tallentaa vain tämän diffin. Aikasarjatietoaineistoissa tässä diffissä on tyypillisesti useita joko etu- ja/tai loppunollia. Näin ollen tallennettava tieto on yleensä huomattavasti pienempi, mutta meidän on myös tallennettava johtavien nollien määrä ja nollasta poikkeavan XOR-fragmentin pituus.
Näitä käsitteitä käytetään yleisesti nykyisissä pakkausalgoritmeissa, esim. Facebookin Gorillassa . Pakkauksen tehokkuuden vuoksi Gorilla toimii bittien tasolla, mutta nämä operaatiot ovat melko laajoja. Olemme suunnitelleet pakkauksemme mahdollisimman nopeaksi, joten siirryimme bittirajauksesta tavuihin. Tämän seurauksena voisi odottaa huonompaa pakkaussuhdetta, mutta näin ei aina ole.
Keskiulottuvuuden osalta pakkaus toimii tietolohkoilla, mutta tämä ei ole ongelma, koska aikasarjatietokannat käyttävät lohkoja joka tapauksessa.
Mikä on pakkaussuhde?
Tarkastellaan pakkaussuhdetta kahdessa eri skenaariossa. Ensimmäinen skenaario – otamme sarjan kaksoispisteitä (esim. 0.1, 0.2, 0.3, …) ja mittaamme pakkaussuhteen riippuen toistuvien pisteiden osuudesta. Vertailun vuoksi käytämme Facebookin Gorilla-pakkausta. Gorilla pakkaa oletusarvoisesti sekä aikasarjadatan arvot että aikaleimat. Testitarkoituksiamme varten aikaleimojen pakkaus on poistettu käytöstä.
Ei ole yllättävää havaita, että Gorillalla on hiukan parempi pakkaussuhde tämäntyyppisille tiedoille. Sama suuntaus on nähtävissä pitkien kokonaislukusekvenssien kohdalla.
Toinen skenaario – tietokokonaisuudet. Datasetit A ja B jakavat saman minuutin varastodatan. Tietokannan A tapauksessa hintapisteet on pakattu liukulukuina. Datasetissa B nämä luvut kerrotaan ensin desimaalipisteen siirtämiseksi, ja näin ollen voimme esittää nämä luvut pitkinä menettämättä tarkkuutta.
Datasetit C ja D luodaan InfluxDatan benchmarking-työkalulla : edustavat levyn kirjoitusmäärää ja rediksen muistin käyttöä. Aineiston A tapauksessa Gorilla pakkaa dataa hieman paremmin kuin algoritmimme – suhde on 1,45 vs. 1,3. Muut kokonaislukuja käyttävät tietokokonaisuudet pakataan paremmin uudella algoritmillamme. Suurin ero on havaittavissa tietokokonaisuudessa D, jossa Middle-out-pakkaussuhde on 3,3, kun taas Gorilla pystyy pakkaamaan nämä tiedot vain suhteessa 1,84. Pakkaussuhde riippuu olennaisesti syötetystä datasta, ja on tietysti tietokokonaisuuksia, joissa yksi algoritmi pakkaa paremmin kuin toinen. Mutta jos suorituskyky on huolenaiheesi – jatka lukemista.
Pakkauksen suorituskyky
Tällä hetkellä meillä on kaksi yhteensopivaa toteutusta algoritmista. Toinen hyödyntää uutta AVX-512-käskyjoukkoa, joka on saatavilla Skylake-X-suorittimissa. Toinen toteutus on suunnattu tietokoneille, jotka eivät tue tätä käskykokonaisuutta.
Läpimenoteho on mitattu Skylake-X:n yhdellä ytimellä, joka toimii 2,0 GHz:n kellotaajuudella.
Seuraavissa kaavioissa esitetään molempien toteutusten pakkaus- ja purkamisnopeus verrattuna Facebookin Gorillaan.
Tässä kaaviossa näkyy pakkauksen läpimenonopeus mitattuna neljällä edellä käsitellyllä tietokokonaisuudella sekä sarjan läpimenonopeus vastaavalla prosenttimäärällä toistuvia arvoja.
Gorilla-pakkauksen läpimenonopeus vaihtelee välillä 120-440 megatavua sekunnissa keskinopeuden ollessa 185 megatavua sekunnissa. Skalaarisen toteutuksemme alhaisin läpäisykyky pakkaa noin 670 MB/s, kun toistuvien arvojen osuus on 50 %. Tämä johtuu suuresta haarojen virheennustussuhteesta. Keskimääräinen pakkausnopeus on 1,27 Gt/s. Vektorikäskyjä käyttävä algoritmi ei kärsi haarautumisvirheiden ennustamisesta, ja se pakkaa tiedot 2,33 Gt/s:sta 2,59 Gt/s:iin, ja keskimääräinen nopeus on 2,48 Gt/s. Ei hullummin yhden ytimen 2 GHz:n piiriltä.
Gorilla voi purkaa nämä tiedot nopeuksilla, jotka vaihtelevat 100 MB/s:sta 430 MB/s:iin . Mutta kuten näet, saman datan purku on jopa nopeampaa kuin pakkaaminen. Vektoroimaton purku toimii vähintään 2,36 Gt/s ja keskimäärin 2,7 Gt/s nopeudella. Vektorisoidut koodit purkavat datan 3,4 GB/s, saavuttaen 4,86 GB/s datasetin D kohdalla. Keskimäärin se pystyy purkamaan datan 4,0 GB/s.
Keskimääräinen kokonaisnopeus pakkauksessa on 6,8-kertainen (skalaarinen toteutus) ja 13,4-kertainen (vektorisoitu toteutus). Keskimääräinen nopeutuminen purkamisessa on vastaavasti 16,1x ja 22,5x.
Tietoa meistä
Me Schizofrenyssä olemme omistautuneet suorituskyvylle ja uskomme, että rajoja voidaan aina pidentää. Rakastamme haasteita ja olemme täällä auttamassa HPC-ongelmissasi.
Part II
www.vldb.org/pvldb/vol8/p1816-teller.pdf
https://github.com/influxdata/influxdb-comparisons/