2024-03-26

42.parquet – Eine Zip-Bombe für das Big-Data-Zeitalter

Hannes Mühleisen

Apache Parquet ist der de-facto-Standard für den Austausch tabellarischer Daten. Es ist seinem unheimlichen Cousin CSV weit überlegen, weil es eine binäre, spaltenorientierte und komprimierte Darstellung nutzt. Außerdem bringen Parquet-Dateien genug Metadaten mit, damit Dateien ohne Zusatzinformationen korrekt interpretiert werden können. Die meisten modernen Datenwerkzeuge und -dienste unterstützen das Lesen und Schreiben von Parquet-Dateien.

Parquet-Dateien sind aber nicht ohne Gefahr: Beschädigte Dateien können zum Beispiel Reader zum Absturz bringen, die interne Offsets nicht vorsichtig genug interpretieren. Aber selbst vollkommen gültige Dateien können problematisch sein und zu Abstürzen und Dienstausfällen führen, wie wir unten zeigen.

Ein ziemlich bekannter Angriff auf naive Firewalls und Virenscanner ist eine Zip-Bombe; ein berühmtes Beispiel ist 42.zip, so genannt, weil 42 natürlich die perfekte Zahl ist und die Datei nur 42 Kilobyte groß ist. Diese vollkommen gültige Zip-Datei enthält eine Reihe weiterer Zip-Dateien, die wiederum andere Zip-Dateien enthalten, und so weiter. Würde man das alles entpacken, käme man auf 4 Petabyte Daten. Wirklich Big Data.

Parquet-Dateien unterstützen verschiedene Methoden zur Datenkompression. Wie groß kann man eine Tabelle mit einer Parquet-Datei machen, die im Geist einer Zip-Bombe nur 42 Kilobyte groß ist? Finden wir es heraus! Aus Portabilitätsgründen haben wir eigene Parquet-Reader und -Writer für DuckDB implementiert. Beim Implementieren lernt man unvermeidlich eine Menge über das Parquet-Format.

Eine Parquet-Datei besteht aus einer oder mehreren Row Groups, die Spalten enthalten, die wiederum sogenannte Pages enthalten, in denen die eigentlichen Daten kodiert liegen. Unter anderem unterstützt Parquet Dictionary Encoding: Zuerst kommt eine Page mit einem Dictionary, danach Data Pages, die statt Klarwerten auf das Dictionary verweisen. Das ist effizienter bei Spalten, in denen lange Werte wie kategoriale Strings oft wiederholt werden, weil die Dictionary-Referenzen deutlich kleiner sein können.

Das nutzen wir aus. Wir schreiben ein Dictionary mit einem einzigen Wert und verweisen immer wieder darauf. In unserem Beispiel verwenden wir eine einzelne 64-Bit-Ganzzahl, den größtmöglichen Wert, weil warum nicht. Dann verweisen wir mit der in Parquet spezifizierten RLE_DICTIONARY-Run-Length Encoding auf diesen Dictionary-Eintrag. Die spezifizierte Kodierung ist etwas merkwürdig, weil sie aus irgendeinem Grund Bit Packing und Run-Length Encoding kombiniert, aber im Wesentlichen können wir die größtmögliche Run-Length verwenden, nämlich 2^31-1, etwas über 2 Milliarden. Da das Dictionary winzig ist (ein Eintrag), ist der wiederholte Wert 0 und verweist auf den einzigen Eintrag. Einschließlich der nötigen Metadata-Header und -Footer (wie alle Metadaten in Parquet mit Thrift kodiert) ist diese Datei nur 133 Byte groß. 133 Byte für 2 Milliarden 8-Byte-Ganzzahlen ist nicht schlecht, selbst wenn sie alle gleich sind.

Aber wir können noch höher gehen. Spalten können mehrere Pages enthalten, die auf dasselbe Dictionary verweisen, also können wir unsere Data Page einfach immer wieder wiederholen und fügen jedes Mal nur 31 Byte zur Datei hinzu, aber 2 Milliarden Werte zur Tabelle, die die Datei darstellt. Wir können noch einen weiteren Trick nutzen, um die Datenmenge aufzublähen: Wie erwähnt enthalten Parquet-Dateien eine oder mehrere Row Groups; die stehen in einem Thrift-Footer am Ende der Datei. Jede Spalte in dieser Row Group enthält Byte-Offsets (data_page_offset und Freunde) in die Datei, wo die Pages der Spalten liegen. Nichts hindert uns daran, mehrere Row Groups hinzuzufügen, die alle auf denselben Byte-Offset verweisen, nämlich den, an dem wir unser etwas schelmisches Dictionary und unsere Data Pages abgelegt haben. Jede hinzugefügte Row Group wiederholt logisch alle Pages. Natürlich brauchen zusätzliche Row Groups auch Metadaten-Speicher, es gibt also einen Trade-off zwischen dem Hinzufügen von Pages (2 Milliarden Werte) und Row Groups (2× das, was eine andere Row Group dupliziert).

Nach etwas Herumprobieren haben wir gefunden: Wenn wir die Data Page 1000-mal und die Row Group 290-mal wiederholen, erhalten wir eine Parquet-Datei (abrufbar im fortytwodotparquet-Repository), die 42 Kilobyte groß ist, aber 622 Billionen Werte enthält (genau 622.770.257.630.000). Würde man diese Tabelle im Speicher materialisieren, bräuchte sie über 4 Petabyte Speicher – endlich ein echtes Beispiel für Big Data, zufällig ungefähr so groß wie das oben erwähnte originale 42.zip.

Wir haben das Skript, mit dem wir diese Datei erzeugen, ebenfalls bereitgestellt; wir hoffen, dass es zum besseren Testen von Parquet-Readern genutzt werden kann. Wir hoffen gezeigt zu haben, dass Parquet-Dateien als schädlich betrachtet werden können und sicher nicht ungeprüft in eine Pipeline gesteckt werden sollten. Und obwohl DuckDB Daten aus unserer Datei lesen kann (z. B. mit einem LIMIT), sollten Sie sich Kaffee holen, wenn Sie sie komplett durchlesen lassen.