A világ első Middle-Out tömörítése idősoros adatokhoz - 1. rész

frissítés: Az algoritmus már WTFPLv2 licenc alatt áll. A forráskódok elérhetőek a https://github.com/schizofreny/middle-out.

A Middle-out tömörítés már nem az HBO Silicon Valley című műsorának kitalált találmánya. A tévésorozat és az új vektoros utasításkészletek által egyaránt inspirálva egy új veszteségmentes tömörítési algoritmust találtunk ki idősoros adatokhoz. A tömörítés mindig a sebesség és az arány közötti kompromisszumról szól, és sosem könnyű egyensúlyt teremteni ezen kompromisszumok között, de az egész middle-out koncepció lehetővé teszi számunkra, hogy a Weissman-pontszámot még tovább növeljük.

A Pied Paper tömörítési algoritmusának forráskódja

Ez egyszerűen megtöri az adatfüggőséget. Ha egy korábbi értékre van szükségünk egy aktuális érték kiszámításához, akkor szükségünk van az összes előzményértékre. De ha a chunk több pozíciójából kezdjük a feldolgozást, akkor csak az adott töredéken belüli antecedens értékektől függünk. Ez lehetővé teszi például a SIMD utasítások hatékony használatát.

Hogyan működik?
Mi a helyzet a tömörítési aránnyal?
Tömörítési teljesítmény
Rólunk

Hogyan működik?

Az algoritmus elvileg az új és az előző érték XOR-ját számítja ki. Így egyfajta diff-et kapunk az értékek között, és csak ezt a diff-et tudjuk tárolni. Idősorozatos adatkészletekben ez a diff tipikusan tartalmaz egy számot, amely vagy elöl és/vagy hátul nullákat tartalmaz. Ezért a tárolandó információ általában jelentősen kisebb, de a vezető nullák számát és a nem nulla XOR-fragmentum hosszát is tárolnunk kell.

Ezeket a koncepciókat általában a jelenlegi tömörítési algoritmusok használják, pl. a Facebook Gorilla . A tömörítés hatékonysága érdekében a Gorilla bitek szintjén működik, de ezek a műveletek meglehetősen kiterjedtek. Mi úgy terveztük a tömörítést, hogy a lehető leggyorsabb legyen, ezért áttértünk a bites granularitásról a bájtosra. Ennek következtében rosszabb tömörítési arányra számítanánk, de ez nem mindig van így.

A közép-külsőt tekintve a tömörítés blokkos adatokon működik, de ez nem jelent problémát, mivel az idősoros adatbázisok amúgy is blokkokat használnak.

Mi a helyzet a tömörítési aránnyal?

Vizsgáljuk meg a tömörítési arányt két különböző forgatókönyvben. Az első forgatókönyv – veszünk egy kétszeres sorozatot (pl. 0,1, 0,2, 0,3, …) és mérjük a tömörítési arányt az ismétlődő pontok részarányától függően. Az összehasonlításhoz a Facebook Gorilla tömörítést használjuk. A Gorilla alapértelmezés szerint tömöríti az idősoros adatok értékeit és időbélyegeit is. Tesztünkhöz az időbélyegek tömörítése ki van kapcsolva.

Nem meglepő, hogy a Gorilla valamivel jobb tömörítési aránnyal rendelkezik az ilyen típusú adatok esetében. Ugyanezt a tendenciát láthatjuk a hosszú egész számsorozatok esetében is.

Második forgatókönyv – adatkészletek. Az A és B adatkészletek ugyanazokat a percenkénti állományadatokat osztják meg. Az A adatkészlet esetében az árpontok lebegőpontos számokként vannak tömörítve. A B adatkészletben ezeket a számokat először megszorozzuk a tizedespont eltolására, és így ezeket a számokat hosszúként tudjuk ábrázolni a pontosság elvesztése nélkül.

A C és D adatkészleteket az InfluxData egyik benchmarking eszközével generáltuk : a lemezírást és a redis memóriahasználatot reprezentálja. Az A adatkészlet esetében a Gorilla valamivel jobban tömöríti az adatokat, mint a mi algoritmusunk – az arány 1,45 vs. 1,3. A többi, egész számokat használó adatkészletet jobban tömöríti az új algoritmusunk. A legnagyobb különbség a D adatkészletnél látható, ahol a Middle-out tömörítési aránya 3,3, míg a Gorilla csak 1,84 arányban tudja tömöríteni ezeket az adatokat. A tömörítési arány lényegesen függ az adatok bemenetétől, és nyilvánvalóan vannak olyan adatkészletek, ahol az egyik algoritmus jobban tömörít, mint a másik. De ha a teljesítmény a fontos – olvasson tovább.

Tömörítési teljesítmény

Az algoritmusnak jelenleg két kompatibilis implementációja van. Az egyik a Skylake-X CPU-kon elérhető új AVX-512 utasításkészletet használja. A második implementáció olyan számítógépeket céloz meg, amelyek nem támogatják ezt az utasításkészletet.

Az átviteli teljesítményt egy Skylake-X egyetlen, 2,0 GHz-en futó magján mértük.

A következő ábrák a két implementáció tömörítési és dekompressziós sebességét mutatják a Facebook Gorillájával összehasonlítva.

Ez a grafikon a fent tárgyalt négy adatkészleten mért tömörítési átviteli sebességet mutatja, valamint egy sorozat átviteli sebességét a megfelelő százalékos ismétlődő értékekkel.

A Gorilla tömörítés átviteli sebessége 120-440 MB/s között változik, átlagosan 185 MB/s sebességgel. A mi skalár implementációnk legalacsonyabb áteresztőképessége 670 MB/s körül van az ismétlődő értékek 50%-ának tömörítése esetén. Ez a magas elágazási téves előrejelzési aránynak köszönhető. Az átlagos tömörítési sebesség 1,27 GB/s. A vektoros utasításokat használó algoritmus nem szenved az elágazási hibás előrejelzésektől, és 2,33 GB/s-tól 2,59 GB/s-ig tömöríti az adatokat, 2,48 GB/s-os átlagos sebességgel. Nem rossz egy 2 GHz-es chip egyetlen magjától.