Verdens første Middle-Out-komprimering af tidsseriedata - Del 1

OPDATERING: Algoritmen er nu licenseret under WTFPLv2. Kildekoder tilgængelige på https://github.com/schizofreny/middle-out.

Middle-out-komprimering er ikke længere en fiktiv opfindelse fra HBO’s show Silicon Valley. Inspireret af både tv-showet og nye vektorinstruktionssæt fandt vi frem til en ny tabsfri komprimeringsalgoritme til tidsseriedata. Komprimering handler altid om et kompromis mellem hastighed og ratio, og Det er aldrig let at balancere disse kompromiser, men hele middle-out-konceptet giver os mulighed for at skubbe Weissman-scoren endnu længere.

Kildekode til Pied Papers komprimeringsalgoritme

Den bryder simpelthen dataafhængigheden. Hvis vi har brug for en tidligere værdi for at beregne en aktuel værdi, har vi brug for alle forudgående værdier. Men hvis vi starter behandlingen fra flere positioner i fragmentet, er vi kun afhængige af antecedentværdier inden for dette fragment. Dette giver os f.eks. mulighed for effektivt at bruge SIMD-instruktioner.

Hvordan virker det?
Hvad med kompressionsforholdet?
Komprimeringspræstationer
Om os

Hvordan virker det?

I princippet beregner algoritmen XOR af en ny værdi og den foregående værdi. På denne måde får vi en slags diff mellem værdierne, og vi kan gemme denne diff alene. I tidsseriedatasæt har denne diff typisk et antal enten ledende og/eller bagudgående nuller. Derfor er de oplysninger, vi skal gemme, normalt betydeligt mindre, men vi skal også gemme antallet af ledende nuller og længden af XOR-fragmentet uden nul.

Disse koncepter anvendes generelt i nuværende komprimeringsalgoritmer, f.eks. Facebooks Gorilla . Af hensyn til komprimeringseffektiviteten opererer Gorilla på bits-niveau, men disse operationer er ret vidtrækkende. Vi har designet vores komprimering for at være så hurtig som muligt, så vi er gået fra bit- til byte-granularitet. Som følge heraf ville man forvente dårligere kompressionsforhold, men det er ikke altid tilfældet.

Med hensyn til middle-out opererer kompressionen på blokke af data, men det er ikke et problem, da tidsseriedatabaser alligevel bruger blokke.

Hvad med kompressionsforholdet?

Lad os undersøge kompressionsforholdet i to forskellige scenarier. Det første scenarie – vi tager en serie af fordoblinger (dvs. 0,1, 0,2, 0,3, …) og måler kompressionsforholdet afhængigt af andelen af gentagne punkter. Til sammenligning bruger vi Facebooks Gorilla-komprimering. Som standard komprimerer Gorilla både værdierne og tidsstemplerne i tidsseriedata. Til vores testformål er komprimering af tidsstempler deaktiveret.

Det er ikke overraskende at finde, at Gorilla har et lidt bedre kompressionsforhold for disse typer af data. Vi kan se den samme tendens med sekvenser med lange hele tal.

Det andet scenarie – datasæt. Datasæt A og B deler de samme minutlagerdata. I datasæt A er prispunkterne komprimeret som flydende tal. I datasæt B er disse tal først ganget for at flytte decimalpunktet, og derfor kan vi repræsentere disse tal som lange uden at miste præcision.

Datasæt C og D er genereret ved hjælp af et benchmarkingværktøj fra InfluxData : repræsenterer disk writes og redis memory use. I tilfælde af datasæt A komprimerer Gorilla data lidt bedre end vores algoritme – med et forhold på 1,45 vs. 1,3. Andre datasæt med hele tal er bedre komprimeret med vores nye algoritme. Den største forskel kan ses i datasæt D, hvor Middle-out-komprimeringsforholdet er 3,3, mens Gorilla kun kan komprimere disse data med et forhold på 1,84. Komprimeringsforholdet afhænger i høj grad af de indgående data, og der er naturligvis datasæt, hvor en algoritme komprimerer bedre end en anden. Men hvis ydeevne er din bekymring – læs videre.

Komprimeringspræstationer

For øjeblikket har vi to kompatible implementeringer af algoritmen. Den ene udnytter et nyt AVX-512-instruktionssæt, der er tilgængeligt på Skylake-X CPU’er. Den anden implementering er rettet mod computere uden understøttelse af dette instruktionssæt.

Gennemstrømningen er målt på en enkelt kerne på Skylake-X, der kører ved 2,0 GHz.

De følgende diagrammer viser komprimerings- og dekomprimeringshastigheden for begge implementeringer sammenlignet med Facebooks Gorilla.

Denne graf viser kompressionsgennemstrømningen som målt på de fire datasæt, der er omtalt ovenfor, samt gennemstrømningen for en serie med den respektive procentdel af gentagne værdier.

Gorilla-komprimeringens gennemstrømning varierer fra 120-440 MB/s med en gennemsnitshastighed på 185 MB/s. Det laveste gennemløb for vores skalarimplementering komprimerer omkring 670 MB/s for 50 % af gentagne værdier. Dette skyldes en høj fejlforudsigelsesprocent for grene. Den gennemsnitlige komprimeringshastighed er 1,27 GB/s. En algoritme, der anvender vektorinstruktioner, lider ikke under fejlforudsigelse af forgreninger og komprimerer data fra 2,33 GB/s til 2,59 GB/s med en gennemsnitshastighed på 2,48 GB/s. Ikke dårligt for en enkelt kerne på en 2 GHz-chip.