2022-10-28

Leichtgewichtige Kompression in DuckDB

Mark Raasveldt

Bei der Arbeit mit großen Datenmengen ist Kompression entscheidend, um Speichergröße und Egress-Kosten zu senken. Kompressionsalgorithmen reduzieren die Datensatzgröße typischerweise um 75–95 %, je nachdem, wie komprimierbar die Daten sind. Kompression verringert nicht nur den Speicher-Footprint eines Datensatzes, sie verbessert oft auch die Leistung, weil weniger Daten von der Platte oder über eine Netzwerkverbindung gelesen werden müssen.

Spaltenformate wie DuckDBs natives Dateiformat oder Parquet profitieren besonders von Kompression. Daten innerhalb einer einzelnen Spalte sind im Allgemeinen sehr ähnlich, was Kompressionsalgorithmen wirksam ausnutzen können. Daten zeilenweise zu speichern, führt dazu, dass Daten verschiedener Spalten verschachtelt werden, was zu niedrigeren Kompressionsraten führt.

DuckDB hat Ende letzten Jahres Unterstützung für Kompression ergänzt. Wie die Tabelle unten zeigt, hat sich das Kompressionsverhältnis von DuckDB seither stetig verbessert und wird weiter aktiv verbessert. In diesem Beitrag besprechen wir, wie Kompression in DuckDB funktioniert und welche Designentscheidungen und Abwägungen wir bei der Umsetzung der Kompression für DuckDBs Speicherformat getroffen haben.

Einführung in Kompression

Im Kern versuchen Kompressionsalgorithmen, Muster in einem Datensatz zu finden, um ihn geschickter zu speichern. Die Komprimierbarkeit eines Datensatzes hängt daher davon ab, ob solche Muster gefunden werden können und ob sie überhaupt existieren. Daten, die einem festen Muster folgen, lassen sich deutlich komprimieren. Daten ohne Muster, etwa Zufallsrauschen, lassen sich nicht komprimieren. Formal ist die Komprimierbarkeit eines Datensatzes als seine Entropie bekannt.

Als Beispiel für dieses Konzept betrachten wir die folgenden zwei Datensätze.

Der konstante Datensatz lässt sich komprimieren, indem einfach der Wert des Musters und die Anzahl der Wiederholungen gespeichert werden (z. B. 1x8). Das Zufallsrauschen hat dagegen kein Muster und ist daher nicht komprimierbar.

Allzweck-Kompressionsalgorithmen

Die Kompressionsalgorithmen, die die meisten kennen, sind Allzweck-Kompressionsalgorithmen wie Zip, Gzip oder Zstd. Allzweck-Kompressionsalgorithmen finden Muster in Bits. Sie sind daher unabhängig vom Datentyp und können auf jeden Bitstrom angewendet werden. Sie können Dateien komprimieren, aber auch auf beliebige Daten angewendet werden, die über eine Socket-Verbindung gesendet werden.

Allzweck-Kompression ist flexibel und sehr einfach einzurichten. Es gibt eine Reihe hochwertiger Bibliotheken (etwa Zstd, Snappy oder LZ4), die Kompression bereitstellen, und sie können auf jeden Datensatz in beliebiger Ablage angewendet werden.

Der Nachteil von Allzweck-Kompression ist, dass (De-)Kompression im Allgemeinen teuer ist. Das spielt keine Rolle, wenn wir von einer Festplatte oder über eine langsame Internetverbindung lesen und schreiben, die Geschwindigkeit der (De-)Kompression kann aber zum Nadelöhr werden, wenn Daten im RAM liegen.

Ein weiterer Nachteil: Diese Bibliotheken arbeiten als Blackbox. Sie arbeiten auf Bitströmen und geben dem Nutzer keinen Einblick in ihren internen Zustand. Das ist kein Problem, wenn Sie nur die Größe Ihrer Daten senken wollen, es verhindert aber, dass das System die vom Kompressionsalgorithmus gefundenen Muster während der Ausführung nutzen kann.

Schließlich funktionieren Allzweck-Kompressionsalgorithmen besser, wenn große Datenchunks komprimiert werden. Wie die Tabelle unten zeigt, leiden die Kompressionsverhältnisse deutlich, wenn kleine Datenmengen komprimiert werden. Für ein gutes Kompressionsverhältnis müssen Blöcke von mindestens 256 kB genutzt werden.

Das ist relevant, weil die Blockgröße die Mindestmenge an Daten ist, die beim Lesen einer einzelnen Zeile von der Platte dekomprimiert werden muss. Schlimmer noch: Da DuckDB Daten pro Spalte komprimiert, wäre die Blockgröße die Mindestmenge an Daten, die pro Spalte dekomprimiert werden muss. Bei einer Blockgröße von 256 kB könnte das Holen einer einzelnen Zeile das Dekomprimieren mehrerer Megabyte erfordern. Das kann Abfragen, die wenige Zeilen holen, etwa SELECT * FROM tbl LIMIT 5 oder SELECT * FROM tbl WHERE id = 42, teuer machen, obwohl sie an der Oberfläche sehr günstig wirken.

Leichtgewichtige Kompressionsalgorithmen

Eine andere Option für Kompression sind spezialisierte leichtgewichtige Kompressionsalgorithmen. Auch sie finden Muster in Daten. Anders als Allzweck-Kompression versuchen sie jedoch nicht, generische Muster in Bitströmen zu finden. Stattdessen finden sie bestimmte Muster in Datensätzen.

Durch das Erkennen bestimmter Muster können spezialisierte Kompressionsalgorithmen deutlich leichter sein und viel schnellere Kompression und Dekompression bieten. Außerdem können sie auf viel kleineren Datengrößen wirksam sein. So können wir ein paar Zeilen auf einmal dekomprimieren, statt große Datenblöcke auf einmal dekomprimieren zu müssen. Diese spezialisierten Kompressionsalgorithmen können auch effiziente Unterstützung für Random Seeks bieten, was den Datenzugriff über einen Index deutlich schneller macht.

Leichtgewichtige Kompressionsalgorithmen geben uns außerdem feinere Kontrolle über den Kompressionsprozess. Das ist für uns besonders relevant, weil DuckDBs Dateiformat Blöcke fester Größe nutzt, um Fragmentierung bei Workloads mit Deletes und Updates zu vermeiden. Die feinere Kontrolle erlaubt uns, diese Blöcke wirksamer zu füllen und nicht raten zu müssen, wie viel komprimierte Daten in einen Buffer passen.

Auf der anderen Seite sind diese Algorithmen unwirksam, wenn die bestimmten Muster, für die sie gebaut sind, in den Daten nicht vorkommen. Einzeln sind diese leichtgewichtigen Kompressionsalgorithmen daher kein Ersatz für Allzweck-Algorithmen. Stattdessen müssen mehrere spezialisierte Algorithmen kombiniert werden, um viele verschiedene häufige Muster in Datensätzen einzufangen.

Kompressions-Framework

Wegen der oben beschriebenen Vorteile nutzt DuckDB nur spezialisierte leichtgewichtige Kompressionsalgorithmen. Da jeder dieser Algorithmen auf unterschiedlichen Mustern in den Daten optimal arbeitet, muss DuckDBs Kompressions-Framework zuerst entscheiden, welcher Algorithmus zum Speichern der Daten jeder Spalte genutzt wird.

DuckDBs Speicher teilt Tabellen in Row Groups. Das sind Gruppen von 120K Zeilen, gespeichert in spaltenweisen Chunks namens Column Segments. Dieses Speicherlayout ähnelt Parquet – mit einem wichtigen Unterschied: Spalten werden in Blöcke fester Größe geteilt. Diese Designentscheidung wurde getroffen, weil DuckDBs Speicherformat In-Place-ACID-Änderungen am Speicherformat unterstützt, einschließlich Löschen und Aktualisieren von Zeilen sowie Hinzufügen und Entfernen von Spalten. Durch das Partitionieren der Daten in Blöcke fester Größe können die Blöcke leicht wiederverwendet werden, wenn sie nicht mehr benötigt werden, und Fragmentierung wird vermieden.

Das Kompressions-Framework arbeitet im Kontext der einzelnen Column Segments. Es arbeitet in zwei Phasen. Zuerst werden die Daten im Column Segment analysiert. In dieser Phase scannen wir die Daten im Segment und finden den besten Kompressionsalgorithmus für dieses Segment. Danach wird die Kompression ausgeführt, und die komprimierten Daten werden auf die Blöcke auf der Platte geschrieben.

Dieser Ansatz erfordert zwei Durchläufe über die Daten in einem Segment, das verursacht aber keine erheblichen Kosten, weil die Datenmenge in einem Segment im Allgemeinen klein genug ist, um in die CPU-Caches zu passen. Ein Sampling-Ansatz für den Analyse-Schritt käme auch in Frage, im Allgemeinen schätzen wir aber die Wahl des besten Kompressionsalgorithmus und die Reduktion der Dateigröße höher als eine geringfügige Erhöhung der Kompressionsgeschwindigkeit.

Kompressionsalgorithmen

DuckDB setzt mehrere leichtgewichtige Kompressionsalgorithmen um, und wir sind dabei, weitere ins System aufzunehmen. In den folgenden Abschnitten gehen wir auf einige dieser Kompressionsalgorithmen und ihre Arbeitsweise ein.

Constant Encoding

Constant Encoding ist der geradlinigste Kompressionsalgorithmus in DuckDB. Constant Encoding wird genutzt, wenn jeder einzelne Wert in einem Column Segment derselbe Wert ist. In dem Fall speichern wir nur diesen einzelnen Wert. Diese Kodierung ist unten visualisiert.

Wenn anwendbar, führt diese Kodierungstechnik zu enormen Platzeinsparungen. Es mag wirken, als wäre sie selten anwendbar – in der Praxis kommt sie relativ häufig vor. Spalten können mit NULL-Werten gefüllt sein oder Werte haben, die sich selten ändern (etwa eine year-Spalte in einem Strom von Sensordaten). Dank dieses Kompressionsalgorithmus brauchen solche Spalten in DuckDB fast keinen Platz.

Run-Length Encoding (RLE)

Run-Length Encoding (RLE) ist ein Kompressionsalgorithmus, der wiederholte Werte in einem Datensatz ausnutzt. Statt einzelner Werte wird der Datensatz in Paare von (Wert, Anzahl)-Tupeln zerlegt, wobei die Anzahl angibt, wie oft der Wert wiederholt wird. Diese Kodierung ist unten visualisiert.

RLE ist stark, wenn es viele wiederholte Werte in den Daten gibt. Das kann vorkommen, wenn Daten nach einem bestimmten Attribut sortiert oder partitioniert sind. Es ist auch nützlich für Spalten mit vielen fehlenden (NULL) Werten.

Bit Packing

Bit Packing ist eine Kompressionstechnik, die ausnutzt, dass ganzzahlige Werte selten den vollen Bereich ihres Datentyps ausschöpfen. Vier-Byte-Integer können zum Beispiel Werte von minus zwei Milliarden bis plus zwei Milliarden speichern. Häufig wird der volle Bereich dieses Datentyps nicht genutzt, und es werden nur kleine Zahlen gespeichert. Bit Packing nutzt das, indem alle unnötigen führenden Nullen beim Speichern der Werte entfernt werden. Ein Beispiel (dezimal) steht unten.

Für Bit-Packing-Kompression merken wir uns den Maximalwert für jeweils 1024 Werte. Der Maximalwert bestimmt die Bit-Packing-Breite, also die Anzahl Bits, die nötig sind, um diesen Wert zu speichern. Beim Speichern einer Menge von Werten mit Maximalwert 32 ist die Bit-Packing-Breite zum Beispiel 5 Bits, gegenüber den 32 Bits pro Wert, die für unkomprimierte Vier-Byte-Integer nötig wären.

Bit Packing ist in der Praxis sehr stark. Es ist auch bequem für Nutzer – dank dieser Technik gibt es keine Speichergrößenunterschiede zwischen den verschiedenen Integer-Typen. Eine BIGINT-Spalte wird in genau demselben Platz gespeichert wie eine INTEGER-Spalte. Das entlastet den Nutzer davon, sich Gedanken über die Wahl des Integer-Typs zu machen.

Frame of Reference

Frame-of-Reference-Kodierung ist eine Erweiterung von Bit Packing, bei der wir auch einen Frame einbeziehen. Der Frame ist der Minimalwert in der Menge der Werte. Die Werte werden als Offset von diesem Frame gespeichert. Ein Beispiel steht unten.

Das mag auf den ersten Blick nicht besonders nützlich wirken, ist aber sehr stark beim Speichern von Daten und Timestamps. Daten und Timestamps werden in DuckDB als Unix-Timestamps gespeichert, also als Offset seit 1970-01-01 in Tagen (für Daten) oder Mikrosekunden (für Timestamps). Bei einer Menge von Datums- oder Timestamp-Werten können die absoluten Zahlen sehr hoch sein, die Zahlen liegen aber alle sehr nah beieinander. Indem wir vor dem Bit Packing einen Frame anwenden, können wir unser Kompressionsverhältnis oft enorm verbessern.

Dictionary Encoding

Dictionary Encoding extrahiert häufige Werte in ein separates Dictionary und ersetzt die Originalwerte dann durch Verweise auf dieses Dictionary. Ein Beispiel steht unten.

Dictionary Encoding ist besonders effizient beim Speichern von Textspalten mit vielen Duplikaten. Die viel größeren Textwerte können durch kleine Zahlen ersetzt werden, die wiederum effizient bit-gepackt werden können.

FSST

Fast Static Symbol Table-Kompression ist eine Erweiterung der Dictionary-Kompression, die nicht nur Wiederholungen ganzer Strings extrahiert, sondern auch Wiederholungen innerhalb von Strings. Das ist wirksam beim Speichern von Strings, die selbst eindeutig sind, aber viel Wiederholung innerhalb der Strings haben, etwa URLs oder E-Mail-Adressen. Ein Bild, das das illustriert, steht unten.

Wer mehr erfahren möchte, kann den Vortrag von Peter Boncz hier ansehen.

Chimp & Patas

Chimp ist ein sehr neuer Kompressionsalgorithmus, der zum Komprimieren von Gleitkommawerten entworfen ist. Er basiert auf Gorilla-Kompression. Die Kernidee hinter Gorilla und Chimp ist, dass Gleitkommawerte, wenn sie miteinander XOR-verknüpft werden, kleine Werte mit vielen nachlaufenden und führenden Nullen zu erzeugen scheinen. Diese Algorithmen arbeiten dann daran, einen effizienten Weg zu finden, die nachlaufenden und führenden Nullen zu speichern.

Nach der Umsetzung von Chimp waren wir inspiriert und haben Patas umgesetzt, das viele derselben Ideen nutzt, aber weiter auf höhere Dekompressionsgeschwindigkeit optimiert. Erwarten Sie bald einen weiteren Blogbeitrag, der das genauer erklärt!

Kompression inspizieren

PRAGMA storage_info kann genutzt werden, um das Speicherlayout von Tabellen und Spalten zu inspizieren. Damit lässt sich prüfen, welchen Kompressionsalgorithmus DuckDB gewählt hat, um bestimmte Spalten einer Tabelle zu komprimieren.

SELECT * EXCLUDE (column_path, segment_id, start, stats, persistent, block_id, block_offset, has_updates)
FROM pragma_storage_info('taxi')
USING SAMPLE 10 ROWS
ORDER BY row_group_id;

Fazit und zukünftige Ziele

Kompression war in DuckDB enorm erfolgreich, und wir haben große Fortschritte dabei gemacht, den Speicherbedarf des Systems zu senken. Wir arbeiten weiter aktiv daran, die Kompression in DuckDB zu erweitern, und wollen das Kompressionsverhältnis des Systems weiter verbessern, sowohl durch Verbesserungen bestehender Techniken als auch durch die Umsetzung weiterer. Unser Ziel ist Kompression auf Augenhöhe mit Parquet mit Snappy, bei ausschließlich leichtgewichtigen spezialisierten Kompressionstechniken, die sehr schnell zu verarbeiten sind.