UPDATE: Algoritmen är nu licensierad under WTFPLv2. Källkoder finns på https://github.com/schizofreny/middle-out.

Middle-out compression är inte längre en fiktiv uppfinning från HBO:s show Silicon Valley. Inspirerade av både TV-serien och nya vektorinstruktionsuppsättningar tog vi fram en ny förlustfri komprimeringsalgoritm för tidsseriedata. Komprimering handlar alltid om en kompromiss mellan hastighet och förhållande och Det är aldrig lätt att balansera dessa kompromisser, men hela middle-out-konceptet gör det möjligt för oss att driva Weissman-poängen ännu längre.

Den bryter helt enkelt databeroendet. Om vi behöver ett tidigare värde för att beräkna ett aktuellt värde behöver vi alla föregående värden. Men om vi börjar bearbetningen från flera olika positioner i fragmentet är vi bara beroende av föregående värden inom detta fragment. Detta gör att vi till exempel effektivt kan använda SIMD-instruktioner.

Hur fungerar det?

I princip beräknar algoritmen XOR av ett nytt värde och det föregående värdet. På så sätt får vi ett slags diff mellan värdena och vi kan lagra enbart denna diff. I datamängder med tidsserier har denna diff vanligtvis ett antal antingen ledande och/eller efterföljande nollor. Därför är den information vi behöver lagra vanligtvis betydligt mindre, men vi måste också lagra antalet ledande nollor och längden på XOR-fragment som inte är nollor.

Dessa begrepp används i allmänhet i nuvarande komprimeringsalgoritmer, till exempel Facebooks Gorilla . För att komprimeringen ska bli effektiv arbetar Gorilla på bitnivå, men dessa operationer är ganska omfattande. Vi har utformat vår komprimering för att den ska vara så snabb som möjligt, så vi övergick från bit- till byte-granularitet. Som en konsekvens av detta skulle man förvänta sig sämre kompressionsförhållande, men det är inte alltid fallet.

Med avseende på middle-out opererar kompressionen på block av data, men detta är inget problem eftersom tidsseriedatabaser ändå använder block.

Hur är det med kompressionsförhållandet?

Låtsas vi undersöka kompressionsförhållandet i två olika scenarier. Det första scenariot – vi tar en serie dubbleringar (dvs. 0,1, 0,2, 0,3, …) och mäter kompressionsförhållandet beroende på andelen upprepade punkter. Som jämförelse använder vi Facebooks Gorilla-komprimering. Som standard komprimerar Gorilla både värden och tidsstämplar i tidsseriedata. För våra teständamål är komprimeringen av tidsstämplar inaktiverad.

Det är inte förvånande att konstatera att Gorilla har ett något bättre kompressionsförhållande för dessa typer av data. Vi kan se samma trend med långa heltalssekvenser.

Det andra scenariot – dataset. Dataset A och B delar samma minutbeståndsdata. När det gäller dataset A komprimeras prispunkterna som flyttal. I dataset B multipliceras dessa siffror först för att flytta decimalpunkten och därmed kan vi representera dessa siffror som långa utan att förlora precision.

Datasetterna C och D genereras med hjälp av ett benchmarkingverktyg från InfluxData : representerar diskskrivningar och minnesanvändning av redis. När det gäller dataset A komprimerar Gorilla data något bättre än vår algoritm – med ett förhållande på 1,45 mot 1,3. Andra dataset som använder heltal komprimeras bättre med vår nya algoritm. Den största skillnaden kan ses i dataset D där Middle-out komprimeringskvoten är 3,3, medan Gorilla endast kan komprimera dessa data med en kvot på 1,84. Kompressionskvoten beror i hög grad på de inmatade uppgifterna och det finns uppenbarligen dataset där en algoritm komprimerar bättre än en annan. Men om prestanda är ditt bekymmer – fortsätt läsa.

Kompressionsprestanda

För närvarande har vi två kompatibla implementeringar av algoritmen. Den ena använder en ny AVX-512-instruktionsuppsättning som är tillgänglig på Skylake-X-processorer. Den andra implementationen riktar sig till datorer utan stöd för denna instruktionsuppsättning.

Genomströmningen mäts på en enda kärna i Skylake-X som körs på 2,0 GHz.

De följande diagrammen visar komprimerings- och dekomprimeringshastigheten för de båda implementationerna jämfört med Facebooks Gorilla.

Denna graf visar komprimeringsgenomströmningen som uppmättes på de fyra datamängder som diskuterats ovan, plus genomströmningen för en serie med respektive procentuell andel av upprepade värden.

Gorillas komprimeringsgenomströmning varierar från 120-440 MB/s med en genomsnittlig hastighet på 185 MB/s. Den lägsta genomströmningen för vår skalära implementering komprimerar omkring 670 MB/s för 50 % av upprepande värden. Detta beror på en hög andel felförutsägelser för grenar. Den genomsnittliga komprimeringshastigheten är 1,27 GB/s. En algoritm som använder vektorinstruktioner lider inte av felförutsägelser för grenar och komprimerar data från 2,33 GB/s till 2,59 GB/s, med en genomsnittlig hastighet på 2,48 GB/s. Inte illa för ett chip med en enda kärna på 2 GHz.

Gorilla kan dekomprimera dessa data med hastigheter från 100 MB/s till 430 MB/s . Men som du kan se är vår dekomprimering av samma data ännu snabbare än en komprimering. Icke-vektoriserad dekomprimering fungerar med en minimal hastighet på 2,36 GB/s och 2,7 GB/s i genomsnitt. Vektoriserade koder dekomprimerar data från 3,4 GB/s och når 4,86 GB/s för dataset D. I genomsnitt kan den dekomprimera data med 4,0 GB/s.

Den genomsnittliga totala hastighetsökningen för komprimering är 6,8x (skalär implementering) och 13,4x (vektoriserad implementering). Den genomsnittliga hastighetsökningen för dekomprimering är 16,1x respektive 22,5x.

Om oss

Vi på Schizofreny är hängivna prestanda och vi tror att gränserna alltid kan flyttas ytterligare. Vi älskar utmaningar och vi är här för att hjälpa dig med dina HPC-problem.

Del II

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

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