UPDATE: Algorytm jest teraz na licencji WTFPLv2. Kody źródłowe dostępne pod adresem https://github.com/schizofreny/middle-out.
Kompresja Middle-out nie jest już fikcyjnym wynalazkiem z serialu HBO Dolina Krzemowa. Zainspirowani zarówno programem telewizyjnym, jak i nowymi zestawami instrukcji wektorowych, wymyśliliśmy nowy algorytm kompresji bezstratnej dla danych szeregów czasowych. Kompresja zawsze polega na kompromisie między szybkością a współczynnikiem i nigdy nie jest łatwo zrównoważyć te kompromisy, ale cała koncepcja middle-out pozwala nam przesunąć wynik Weissmana jeszcze dalej.
Po prostu łamie zależność danych. Jeśli potrzebujemy poprzedniej wartości, aby obliczyć bieżącą, potrzebujemy wszystkich wartości poprzedzających. Ale jeśli rozpoczniemy przetwarzanie od wielu pozycji w chunk, zależymy tylko od wartości poprzedzających w obrębie tego fragmentu. Dzięki temu możemy na przykład efektywnie wykorzystywać instrukcje SIMD.
Jak to działa?
W zasadzie algorytm oblicza XOR nowej wartości i poprzedniej. W ten sposób otrzymujemy rodzaj różnicy między wartościami i możemy przechowywać tę różnicę samodzielnie. W zbiorach danych szeregów czasowych ta różnica ma zazwyczaj pewną liczbę zer wiodących i/lub końcowych. Stąd informacja, którą musimy przechowywać, jest zwykle znacznie mniejsza, ale musimy również przechowywać liczbę zer wiodących i długość niezerowego fragmentu XOR.
Te koncepcje są ogólnie stosowane w bieżących algorytmach kompresji, np. Facebook’s Gorilla . Ze względu na wydajność kompresji, Gorilla działa na poziomie bitów, ale te operacje są dość ekspansywne. My zaprojektowaliśmy naszą kompresję tak, aby była jak najszybsza, więc przeszliśmy z granulacji bitowej na bajtową. W konsekwencji można by się spodziewać gorszego współczynnika kompresji, ale nie zawsze tak jest.
W odniesieniu do middle-out, kompresja operuje na blokach danych, ale to nie jest problem, ponieważ bazy danych szeregów czasowych i tak używają bloków.
Co ze współczynnikiem kompresji?
Sprawdźmy współczynnik kompresji w dwóch różnych scenariuszach. Pierwszy scenariusz – bierzemy serię podwojonych punktów (np. 0.1, 0.2, 0.3, …) i mierzymy stopień kompresji w zależności od porcji powtarzających się punktów. Dla porównania użyjemy kompresji Gorilla z Facebooka. Domyślnie Gorilla kompresuje zarówno wartości jak i znaczniki czasowe danych szeregu czasowego. Dla celów naszego testu, kompresja znaczników czasu jest wyłączona.
Nie jest zaskakujące, że Gorilla ma nieco lepszy współczynnik kompresji dla tego typu danych. Ten sam trend możemy zaobserwować w przypadku sekwencji długich liczb całkowitych.
Scenariusz drugi – zestawy danych. Zbiory danych A i B mają te same dane minutowe. W przypadku zbioru danych A, punkty cenowe są kompresowane jako liczby zmiennoprzecinkowe. W przypadku zbioru B liczby te są najpierw mnożone w celu przesunięcia kropki dziesiętnej, dzięki czemu możemy reprezentować te liczby jako długie bez utraty precyzji.
Zestawy danych C i D są generowane przy użyciu narzędzia benchmarkingowego od InfluxData : reprezentują zapisy na dysku i użycie pamięci redis. W przypadku zbioru A, Gorilla kompresuje dane nieco lepiej niż nasz algorytm – ze współczynnikiem 1.45 vs 1.3. Pozostałe zbiory danych wykorzystujące liczby całkowite są lepiej kompresowane przez nasz nowy algorytm. Największą różnicę widać w zbiorze D, gdzie współczynnik kompresji Middle-out wynosi 3.3, podczas gdy Gorilla potrafi skompresować te dane tylko ze współczynnikiem 1.84. Współczynnik kompresji w znacznym stopniu zależy od danych wejściowych i oczywiście istnieją zbiory danych, w których jeden algorytm kompresuje lepiej niż inny. Ale jeśli wydajność jest twoim zmartwieniem – czytaj dalej.
Wydajność kompresji
Obecnie mamy dwie kompatybilne implementacje algorytmu. Jedna z nich wykorzystuje nowy zestaw instrukcji AVX-512 dostępny w procesorach Skylake-X. Druga implementacja jest przeznaczona dla komputerów bez obsługi tego zestawu instrukcji.
Przepustowość jest mierzona na pojedynczym rdzeniu Skylake-X pracującym z częstotliwością 2,0 GHz.
Następujące wykresy pokazują szybkość kompresji i dekompresji obu implementacji w porównaniu do Facebook’s Gorilla.
Wykres ten pokazuje przepustowość kompresji mierzoną na czterech zestawach danych omówionych powyżej, plus przepustowość serii z odpowiednim procentem powtarzających się wartości.
Przepustowość kompresji Gorilla waha się od 120-440 MB/s ze średnią prędkością 185 MB/s. Najniższa przepustowość naszej implementacji skalarnej kompresuje około 670 MB/s dla 50% powtarzających się wartości. Wynika to z wysokiego współczynnika błędnego przewidywania gałęzi. Średnia prędkość kompresji wynosi 1,27 GB/s. Algorytm wykorzystujący instrukcje wektorowe nie cierpi z powodu branch misprediction i kompresuje dane od 2,33 GB/s do 2,59 GB/s, ze średnią prędkością 2,48 GB/s. Nieźle jak na jednordzeniowy układ o taktowaniu 2 GHz.
Gorilla może dekompresować te dane z prędkością od 100 MB/s do 430 MB/s . Ale jak widać, nasza dekompresja tych samych danych jest jeszcze szybsza niż kompresja. Dekompresja bez wektoryzacji działa z minimalną prędkością 2,36 GB/s i średnio 2,7 GB/s. Kody wektorowe dekompresują dane z prędkością 3,4 GB/s, osiągając 4,86 GB/s dla zbioru danych D. Średnio są w stanie dekompresować dane z prędkością 4,0 GB/s.
Średnie ogólne przyspieszenie dla kompresji wynosi 6,8x (implementacja skalarna) i 13,4x (implementacja wektorowa). Średni wzrost prędkości dla dekompresji wynosi odpowiednio 16,1x i 22,5x.
O nas
W Schizofrenach jesteśmy oddani wydajności i wierzymy, że granice zawsze można przesunąć dalej. Uwielbiamy wyzwania i jesteśmy tutaj, aby pomóc w rozwiązywaniu problemów HPC.
Część II
www.vldb.org/pvldb/vol8/p1816-teller.pdf
https://github.com/influxdata/influxdb-comparisons/
.