UPDATE: Algoritme is nu gelicenseerd onder WTFPLv2. Broncodes beschikbaar op https://github.com/schizofreny/middle-out.

Middle-out compressie is niet langer een fictieve uitvinding uit HBO’s show Silicon Valley. Geïnspireerd door zowel de TV show als de nieuwe vector instructie sets, hebben we een nieuw lossless compressie algoritme bedacht voor time-series data. Bij compressie gaat het altijd om een compromis tussen snelheid en ratio en het is nooit eenvoudig om deze afwegingen te maken, maar met het hele middle-out-concept kunnen we de Weissman-score nog verder opvoeren.

Het doorbreekt simpelweg de afhankelijkheid van gegevens. Als we een eerdere waarde nodig hebben om een huidige waarde te berekenen, hebben we alle antecedente waarden nodig. Maar als we de verwerking starten vanaf meerdere posities van het fragment, zijn we alleen afhankelijk van antecedentwaarden binnen dit fragment. Hierdoor kunnen we bijvoorbeeld SIMD-instructies effectief gebruiken.

Hoe werkt het?

In principe berekent het algoritme de XOR van een nieuwe waarde en de vorige. Op deze manier krijgen we een soort verschil tussen waarden en kunnen we dit verschil alleen opslaan. In datasets met tijdreeksen heeft dit verschil gewoonlijk een aantal voorloop- en/of naloopnullen. Daarom is de informatie die we moeten opslaan meestal aanzienlijk kleiner, maar we moeten ook het aantal voorloopnullen en de lengte van het niet-nul XOR-fragment opslaan.

Deze concepten worden over het algemeen gebruikt in de huidige compressie-algoritmen, bijvoorbeeld Facebook’s Gorilla . Omwille van de efficiëntie van de compressie werkt Gorilla op bits-niveau, maar deze operaties zijn vrij omvangrijk. Wij hebben onze compressie ontworpen om zo snel mogelijk te zijn, dus zijn we van bit- naar byte-granulariteit gegaan. Als gevolg daarvan zou je een slechtere compressie ratio verwachten, maar dat is niet altijd het geval.

Met betrekking tot middle-out, compressie werkt op blokken van gegevens, maar dit is geen probleem omdat tijdreeks databases toch blokken gebruiken.

Hoe zit het met de compressie ratio?

Laten we compressie ratio onderzoeken in twee verschillende scenario’s. Het eerste scenario – we nemen een reeks dubbele punten (d.w.z. 0,1, 0,2, 0,3, …) en meten de compressieverhouding afhankelijk van het aantal herhalende punten. Ter vergelijking gebruiken we Facebook’s Gorilla compressie. Standaard comprimeert Gorilla zowel de waarden als de tijdstempels van tijdreeksgegevens. Voor onze testdoeleinden is de compressie van timestamps uitgeschakeld.

Het is niet verrassend dat Gorilla een iets betere compressieratio heeft voor dit soort gegevens. We zien dezelfde trend met lange-integer reeksen.

Tweede scenario – datasets. Datasets A en B hebben dezelfde minuutvoorraadgegevens. In dataset A zijn de koerspunten gecomprimeerd als floating point getallen. In dataset B worden deze getallen eerst vermenigvuldigd om het decimaalteken te verschuiven, zodat we deze getallen als lang kunnen weergeven zonder verlies van precisie.

Datasets C en D worden gegenereerd met behulp van een benchmarking tool van InfluxData : die disk writes en redis geheugengebruik weergeeft. In het geval van dataset A, comprimeert Gorilla gegevens iets beter dan ons algoritme – met een ratio van 1,45 vs 1,3. Andere datasets met gehele getallen worden beter gecomprimeerd met ons nieuwe algoritme. Het grootste verschil is te zien in dataset D waar de Middle-out compressie ratio 3.3 is, terwijl Gorilla deze gegevens slechts kan comprimeren met een ratio van 1.84. De compressie ratio hangt sterk af van de invoer van gegevens en er zijn duidelijk datasets waar het ene algoritme beter comprimeert dan het andere. Maar als de prestaties uw zorg zijn – lees dan verder.

Compressieprestaties

Huidig hebben we twee compatibele implementaties van het algoritme. De ene maakt gebruik van een nieuwe AVX-512 instructieset die beschikbaar is op Skylake-X CPU’s. De tweede implementatie is gericht op computers zonder ondersteuning van deze instructieset.

Doorvoer is gemeten op een enkele kern van Skylake-X die draait op 2,0 GHz.

De volgende grafieken tonen de compressie- en decompressiesnelheid van beide implementaties in vergelijking met Facebook’s Gorilla.

Deze grafiek toont de compressiedoorvoer zoals gemeten op de vier datasets die hierboven zijn besproken, plus de doorvoer van een reeks met het respectieve percentage herhalende waarden.

De doorvoer van Gorilla-compressie varieert van 120-440 MB/s met een gemiddelde snelheid van 185 MB/s. De laagste doorvoer van onze scalaire implementatie comprimeert rond de 670 MB/s voor 50% van de herhalende waarden. Dit is te wijten aan een hoge branch misprediction ratio. De gemiddelde compressiesnelheid is 1,27 GB/s. Een algoritme dat gebruik maakt van vector instructies heeft geen last van branch misprediction en comprimeert data van 2.33 GB/s tot 2.59 GB/s, met een gemiddelde snelheid van 2.48 GB/s. Niet slecht voor een enkele core van 2 GHz chip.

Gorilla kan deze gegevens decomprimeren met snelheden die variëren van 100 MB/s tot 430 MB/s . Maar zoals u kunt zien, is onze decompressie van dezelfde gegevens nog sneller dan een compressie. Niet-gevectoriseerde decompressie werkt met een minimale snelheid van 2,36 GB/s en gemiddeld 2,7 GB/s. Gevectoriseerde codes decomprimeren gegevens met een snelheid van 3,4 GB/s, tot 4,86 GB/s voor dataset D. Gemiddeld is het mogelijk de gegevens te decomprimeren met 4,0 GB/s.

De gemiddelde totale speedup voor compressie is 6,8x (scalaire implementatie) en 13,4x (gevectoriseerde implementatie). De gemiddelde snelheid voor decompressie is respectievelijk 16,1x en 22,5x.

Over ons

Wij bij Schizofreny zijn toegewijd aan prestaties en we geloven dat grenzen altijd verder kunnen worden verlegd. We houden van uitdagingen en we zijn er om u te helpen met uw HPC-problemen.

Part II

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

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