DOPLNĚNO: Algoritmus je nyní licencován pod WTFPLv2. Zdrojové kódy jsou k dispozici na adrese https://github.com/schizofreny/middle-out.

Middle-out komprese už není fiktivní vynález ze seriálu HBO Silicon Valley. Inspirováni televizním seriálem i novými vektorovými instrukčními sadami jsme přišli s novým algoritmem bezeztrátové komprese pro data časových řad. Komprese je vždy o kompromisu mezi rychlostí a poměrem a Nikdy není snadné tyto kompromisy vyvážit, ale celý koncept middle-out nám umožňuje posunout Weissmanovo skóre ještě dál.

Prostě přeruší závislost dat. Pokud potřebujeme předchozí hodnotu k výpočtu aktuální hodnoty, potřebujeme všechny předchozí hodnoty. Pokud však začínáme zpracování z více pozic fragmentu, jsme závislí pouze na antecedentních hodnotách v rámci tohoto fragmentu. To nám umožňuje například efektivně využívat instrukce SIMD.

Jak to funguje?

V principu algoritmus počítá XOR nové a předchozí hodnoty. Tímto způsobem získáme jakýsi rozdíl mezi hodnotami a tento rozdíl můžeme uložit samostatně. V souborech dat časových řad má tento rozdíl obvykle řadu buď počátečních a/nebo koncových nul. Proto je informace, kterou potřebujeme uložit, obvykle podstatně menší, ale musíme také uložit počet předních nul a délku nenulového fragmentu XOR.

Tyto koncepty se obecně používají v současných kompresních algoritmech, např. v algoritmu Gorilla společnosti Facebook . Kvůli efektivitě komprese pracuje Gorilla na úrovni bitů, ale tyto operace jsou poměrně rozsáhlé. Naši kompresi jsme navrhli tak, aby byla co nejrychlejší, takže jsme přešli z bitové na bajtovou granularitu. V důsledku toho by se dal očekávat horší kompresní poměr, ale není tomu tak vždy.

S ohledem na middle-out pracuje komprese na blocích dat, ale to není problém, protože databáze časových řad stejně používají bloky.

Jak je to s kompresním poměrem?

Prozkoumejme kompresní poměr ve dvou různých scénářích. První scénář – vezmeme řadu dvojnásobků (tj. 0,1, 0,2, 0,3, …) a změříme kompresní poměr v závislosti na podílu opakujících se bodů. Pro srovnání použijeme kompresi Gorilla společnosti Facebook. Ve výchozím nastavení Gorilla komprimuje hodnoty i časové značky dat časových řad. Pro účely našeho testu je komprese časových značek vypnuta.

Není překvapivé zjištění, že Gorilla má pro tyto typy dat o něco lepší kompresní poměr. Stejný trend můžeme pozorovat i u dlouhých celočíselných posloupností.

Druhý scénář – datové sady. Datové sady A a B sdílejí stejná minutová skladová data. V případě datové sady A jsou cenové body komprimovány jako čísla s pohyblivou řádovou čárkou. V datasetu B jsou tato čísla nejprve vynásobena, aby se posunula desetinná čárka, a proto můžeme tato čísla reprezentovat jako dlouhá bez ztráty přesnosti.

Datasety C a D jsou generovány pomocí benchmarkovacího nástroje od InfluxData : představují zápisy na disk a využití paměti redis. V případě datové sady A komprimuje Gorilla data o něco lépe než náš algoritmus – s poměrem 1,45 vs. 1,3. V případě datové sady A komprimuje Gorilla data o něco lépe než náš algoritmus. Ostatní datové sady využívající celá čísla jsou lépe komprimovány naším novým algoritmem. Největší rozdíl je vidět u datové sady D, kde je kompresní poměr Middle-out 3,3, zatímco Gorilla dokáže tato data komprimovat pouze s poměrem 1,84. Kompresní poměr podstatně závisí na vstupu dat a zřejmě existují datové sady, kde jeden algoritmus komprimuje lépe než druhý. Pokud vám však jde o výkon – čtěte dál.

Výkon komprese

V současné době máme dvě kompatibilní implementace algoritmu. Jedna využívá novou instrukční sadu AVX-512, která je k dispozici v procesorech Skylake-X. Druhá využívá novou instrukční sadu AVX-512, která je k dispozici v procesorech Skylake-X. Druhá implementace se zaměřuje na počítače bez podpory této instrukční sady.

Propustnost je měřena na jednom jádře Skylake-X běžícím na frekvenci 2,0 GHz.

Následující grafy ukazují rychlost komprese a dekomprese obou implementací ve srovnání s Gorillou společnosti Facebook.

Tento graf ukazuje propustnost komprese naměřenou na čtyřech sadách dat popsaných výše a navíc propustnost série s příslušným procentem opakujících se hodnot.

Propustnost komprese Gorilla se pohybuje v rozmezí 120-440 MB/s s průměrnou rychlostí 185 MB/s. Nejnižší propustnost naší skalární implementace komprimuje kolem 670 MB/s pro 50 % opakujících se hodnot. To je způsobeno vysokým poměrem chybných předpovědí větví. Průměrná rychlost komprese je 1,27 GB/s. Algoritmus využívající vektorové instrukce netrpí chybnou predikcí větví a komprimuje data od 2,33 GB/s do 2,59 GB/s, přičemž průměrná rychlost je 2,48 GB/s. To není špatné na jedno jádro čipu s frekvencí 2 GHz.

Gorilla dokáže tato data dekomprimovat rychlostí od 100 MB/s do 430 MB/s . Jak ale vidíte, naše dekomprese stejných dat je ještě rychlejší než komprese. Dekomprese bez vektorizace pracuje s minimální rychlostí 2,36 GB/s a průměrnou rychlostí 2,7 GB/s. Vektorizované kódy dekomprimují data od 3,4 GB/s a u datové sady D dosahují 4,86 GB/s. V průměru jsou schopny dekomprimovat data rychlostí 4,0 GB/s.

Průměrné celkové zrychlení komprese je 6,8x (skalární implementace) a 13,4x (vektorizovaná implementace). Průměrné zrychlení pro dekompresi je 16,1x, resp. 22,5x.

O nás

V Schizofrenii se věnujeme výkonu a věříme, že hranice lze vždy posouvat dál. Milujeme výzvy a jsme tu, abychom vám pomohli s vašimi problémy v oblasti HPC.

Část II

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

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

.