UPDATE: Algorithmus ist jetzt unter WTFPLv2 lizenziert. Quellcodes verfügbar unter https://github.com/schizofreny/middle-out.

Middle-Out-Kompression ist nicht länger eine fiktive Erfindung aus der HBO-Serie Silicon Valley. Inspiriert von der Fernsehserie und neuen Vektorbefehlssätzen haben wir einen neuen verlustfreien Kompressionsalgorithmus für Zeitreihendaten entwickelt. Bei der Komprimierung geht es immer um einen Kompromiss zwischen Geschwindigkeit und Ratio, und es ist nie einfach, diese Kompromisse auszubalancieren, aber das gesamte Middle-Out-Konzept ermöglicht es uns, den Weissman-Score noch weiter zu steigern.

Es bricht einfach die Datenabhängigkeit. Wenn wir einen früheren Wert benötigen, um einen aktuellen Wert zu berechnen, brauchen wir alle vorhergehenden Werte. Wenn wir jedoch die Verarbeitung an mehreren Stellen des Fragments beginnen, sind wir nur von den Vorgängerwerten innerhalb dieses Fragments abhängig. Auf diese Weise können wir zum Beispiel SIMD-Befehle effektiv nutzen.

Wie funktioniert das?

Im Prinzip berechnet der Algorithmus das XOR eines neuen Wertes mit dem vorherigen. Auf diese Weise erhält man eine Art Diff zwischen den Werten und kann nur diesen Diff speichern. In Zeitreihendatensätzen enthält diese Differenz in der Regel eine Reihe von führenden und/oder nachgestellten Nullen. Daher ist die zu speichernde Information in der Regel wesentlich kleiner, aber wir müssen auch die Anzahl der führenden Nullen und die Länge des XOR-Fragments, das nicht Null ist, speichern.

Diese Konzepte werden im Allgemeinen in aktuellen Kompressionsalgorithmen verwendet, z. B. in Facebooks Gorilla . Aus Gründen der Komprimierungseffizienz arbeitet Gorilla auf Bitebene, aber diese Operationen sind recht umfangreich. Wir haben unsere Kompression so konzipiert, dass sie so schnell wie möglich ist, und sind daher von der Bit- zur Byte-Granularität übergegangen. Infolgedessen würde man ein schlechteres Kompressionsverhältnis erwarten, aber das ist nicht immer der Fall.

Im Hinblick auf die Mitte arbeitet die Komprimierung auf Datenblöcken, aber das ist kein Problem, da Zeitreihendatenbanken ohnehin Blöcke verwenden.

Was ist mit dem Kompressionsverhältnis?

Untersuchen wir das Kompressionsverhältnis in zwei verschiedenen Szenarien. Im ersten Szenario nehmen wir eine Reihe von Doppelpunkten (d.h. 0,1, 0,2, 0,3, …) und messen die Kompressionsrate in Abhängigkeit vom Anteil der sich wiederholenden Punkte. Zum Vergleich verwenden wir die Gorilla-Kompression von Facebook. Gorilla komprimiert standardmäßig sowohl die Werte als auch die Zeitstempel von Zeitreihendaten. Für unsere Testzwecke ist die Komprimierung von Zeitstempeln deaktiviert.

Es ist nicht überraschend, dass Gorilla bei diesen Datentypen ein etwas besseres Komprimierungsverhältnis aufweist. Derselbe Trend ist bei lang-ganzzahligen Sequenzen zu beobachten.

Zweites Szenario – Datensätze. Die Datensätze A und B haben die gleichen Minutenbestandsdaten. Im Fall von Datensatz A sind die Kurspunkte als Gleitkommazahlen komprimiert. In Datensatz B werden diese Zahlen zunächst multipliziert, um das Dezimalkomma zu verschieben, so dass wir diese Zahlen als lange Zahlen darstellen können, ohne an Präzision zu verlieren.

Datensätze C und D werden mit einem Benchmarking-Tool von InfluxData generiert: Darstellung von Festplattenschreibvorgängen und Redis-Speicherverbrauch. Im Fall von Datensatz A komprimiert Gorilla die Daten etwas besser als unser Algorithmus – mit einem Verhältnis von 1,45 zu 1,3. Andere Datensätze, die Ganzzahlen verwenden, werden mit unserem neuen Algorithmus besser komprimiert. Der größte Unterschied ist im Datensatz D zu sehen, wo die Komprimierungsrate von Middle-out 3,3 beträgt, während Gorilla diese Daten nur mit einer Rate von 1,84 komprimieren kann. Das Komprimierungsverhältnis hängt wesentlich von den eingegebenen Daten ab, und es gibt natürlich Datensätze, bei denen ein Algorithmus besser komprimiert als ein anderer. Aber wenn die Leistung Ihr Anliegen ist – lesen Sie weiter.

Komprimierungsleistung

Zurzeit haben wir zwei kompatible Implementierungen des Algorithmus. Eine nutzt einen neuen AVX-512-Befehlssatz, der auf Skylake-X-CPUs verfügbar ist. Die zweite Implementierung zielt auf Computer ohne Unterstützung dieses Befehlssatzes ab.

Der Durchsatz wird auf einem einzelnen Skylake-X-Kern mit 2,0 GHz gemessen.

Die folgenden Diagramme zeigen die Kompressions- und Dekompressionsgeschwindigkeit beider Implementierungen im Vergleich zu Facebooks Gorilla.

Dieses Diagramm zeigt den Komprimierungsdurchsatz, wie er bei den vier oben besprochenen Datensätzen gemessen wurde, sowie den Durchsatz einer Serie mit dem jeweiligen Prozentsatz der sich wiederholenden Werte.

Der Durchsatz der Gorilla-Komprimierung schwankt zwischen 120-440 MB/s mit einer Durchschnittsgeschwindigkeit von 185 MB/s. Der niedrigste Durchsatz unserer skalaren Implementierung liegt bei etwa 670 MB/s für 50 % der sich wiederholenden Werte. Dies ist auf eine hohe Quote von Fehlvorhersagen bei Verzweigungen zurückzuführen. Die durchschnittliche Kompressionsgeschwindigkeit beträgt 1,27 GB/s. Ein Algorithmus, der Vektorbefehle verwendet, leidet nicht unter Verzweigungsfehlvorhersagen und komprimiert Daten von 2,33 GB/s bis 2,59 GB/s, mit einer durchschnittlichen Geschwindigkeit von 2,48 GB/s. Nicht schlecht für einen Einkern-Chip mit 2 GHz.

Gorilla kann diese Daten mit Geschwindigkeiten von 100 MB/s bis 430 MB/s dekomprimieren. Aber wie Sie sehen können, ist unsere Dekompression der gleichen Daten sogar schneller als eine Kompression. Die nicht vektorisierte Dekompression arbeitet mit einer minimalen Geschwindigkeit von 2,36 GB/s und 2,7 GB/s im Durchschnitt. Vektorisierte Codes dekomprimieren Daten ab 3,4 GB/s und erreichen 4,86 GB/s für den Datensatz D. Im Durchschnitt können die Daten mit 4,0 GB/s dekomprimiert werden.

Die durchschnittliche Gesamtbeschleunigung bei der Kompression beträgt 6,8x (skalare Implementierung) und 13,4x (vektorisierte Implementierung). Die durchschnittliche Beschleunigung bei der Dekomprimierung beträgt 16,1x bzw. 22,5x.

Über uns

Wir bei Schizofreny haben uns der Leistung verschrieben und glauben, dass Grenzen immer weiter verschoben werden können. Wir lieben Herausforderungen und wir sind hier, um Ihnen bei Ihren HPC-Problemen zu helfen.

Teil II

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

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