Schwere Quetschung

von Tam Hanna

Im Bereich der Datenkompression gibt es Dutzende verschiedene Formate, die um die Aufmerksamkeit des Administrators buhlen. Unser Artikel liefert einen praktischen Überblick zu den zugrundeliegenden Algorithmen und gibt Hinweise, welche Formate für welche Einsatzzwecke am sinnvollsten sind. Insbesondere gehen wir dabei auf das Anfertigen von Benchmarks unter Linux und deren Auswertung ein.

Auf Algorithmen zur Verkleinerung der Dateigröße trifft der Administrator in vielerlei Szenarien: Neben den Vorteilen beim Herunterladen von komprimierten Softwarepaketen gilt, dass gerade Images durch Kompression wesentlich kleiner ausfallen und sich damit schneller und kostensparender ausliefern lassen. Bei der Auswahl eines Kompressionsalgorithmus sind jedoch selbst IT-Profis oft dazu verleitet, nur auf das als Kompressionsfaktor bezeichnete Verhältnis zwischen der Eingangs- und der Ausgangsgröße zu achten.

Die Speicherkosten sind jedoch nur ein Teil der Gesamtkosten. Um beim Beispiel des Abbilds für eine virtuelle Maschine zu bleiben: Bis zur Verfügbarkeit des Systems gilt, dass neben dem Übertragen des Image-Archivs andere Prozessschritte zu berücksichtigen sind. Anders gesagt: Das Verpacken von Dateien ist nicht kostenlos. Denn je nach der Häufigkeit von Kompression und Dekompression gilt, dass ein in einer Situation optimal geeigneter Algorithmus in einer anderen Situation schlechter greift. Einen universell idealen Kompressionsalgorithmus gibt es also nicht.

Theorie nicht gleich Praxis

Die Theorie verspricht, dass ein Algorithmus in allen Betriebsszenarien Ergebnisse zurückliefert, die kleiner sind als die ursprünglich angelieferten Informationen. In der Praxis ist dies jedoch nicht immer so. Das von Dirichlet im Jahr 1834 formulierte Schubfachprinzip verhindert dies. Es besagt, dass jeder Kompressionsalgorithmus, der eine eindeutige Beziehung zwischen Eingangs- und Ausgangs-Fächermenge herstellt, insofern beschränkt ist, als dass die Anzahl der Ausgangsfächer die Anzahl der Eingangsfächer nicht unterschreiten kann.

Entwickler von Kompressionsverfahren treffen somit immer eine Abwägung, für welche Arten von Information ihr Algorithmus optimiert sein soll. Weiterhin gilt, dass Kompressionsalgorithmen mit Informationen der realen Welt arbeiten. Das Eingabematerial weist meist reiche Redundanz auf. Ein gutes Beispiel dafür ist die arabische Schrift, die in vielen Fällen das Weglassen von Vokalen erlaubt. Der Leser des Texts muss diese im Geist selbst ergänzen – höherer Leseaufwand steht reduzierter Aufwand beim Schreiben entgegen.

Die Wahl des passenden Algorithmus

Bei der Auswahl eines Algorithmus für den professionellen Einsatz sind diverse Kriterien zu beachten. Zum einen gilt es, verlustbehaftete und verlustlose Algorithmen zu unterscheiden (Bild 1). Die Nutzung verlustbehafteter Algorithmen ergibt in vielen Fällen wenig Sinn und kann sogar Gefahren bergen – ein Beispiel sind Röntgenbilder, deren verlustbehaftete Kompression oft sogar rechtlich untersagt ist. In diesem Artikel spielen verlustbehaftete Algorithmen deshalb eine untergeordnete Rolle. Denn Logdateien, Disk-Images und Quellcodearchive enthalten meist nur wenig Daten, die von verlustbehafteter Kompression profitieren.

Wer mit unixoiden Betriebssystemen arbeitet, sollte darauf achten, ob der Verschlüsselungsalgorithmus im Rahmen der Kompression Attribute wie das X-Bit mitführt. Gehen diese verloren, lassen sich die wiederhergestellten Dateien nur eingeschränkt nutzen. Zur Umgehung des Problems ist es möglich, ein TAR-Archiv zu erzeugen, das danach als Einzeldatei in den Kompressionsalgorithmus weiterwandert. Die Nutzung von TAR-Archiven ist außerdem erforderlich, wenn ein Algorithmus nur Einzeldateien verarbeitet – diese Optimierung ist insbesondere in akademischen Algorithmen nicht selten. Nachteil dieser Vorgehensweise ist, dass das Extrahieren einzelner Dateien aus dem Archiv in vielen Fällen dessen komplette Verarbeitung verlangt.

Wichtig ist außerdem, wie der Algorithmus dokumentiert ist. Ein warnendes Beispiel ist das von Marcel Lemke entwickelte ACE-Format: Es wurde nie öffentlich dokumentiert. Nachdem der Entwickler das Interesse an der weiteren Pflege verloren hat, ist das Format nicht mehr nutzbar – ob eines Sicherheitsproblems in der damals zur Verfügung gestellten kostenlosen DLL verweigern nämlich so gut wie alle Kompressionssysteme die Zusammenarbeit mit der DLL und somit auch mit ACE-Archiven. Unter [1] findet sich immerhin eine per Reverse Engineering erzeugte Bibliothek, die ACE-Archive aller Art extrahiert.

Nicht zuletzt kann entscheidend sein, für welche Zielsysteme ein Kompressionsprogramm zur Verfügung steht. Manuelle Portierungen von Kommandozeilen-Utilities stellen einen nicht zu unterschätzenden Arbeitsaufwand dar. Denn wenn das Werkzeug in jedem Container eine Kompilation durchläuft, geht Zeit verloren.

Eigenen Benchmark anstoßen

Vergleiche von Kompressionsalgorithmen sind aufgrund der genannten Einschränkungen nur begrenzt legitim, denn die Ergebnisse hängen stark von den verwendeten Testdaten ab, rechenintensive Prozesse zudem von der Gesamtkonfiguration. Für mathematische Algorithmen etwa gilt, dass die Nutzung eines auf den jeweiligen Zielprozessor optimierten Compilers eine Verdoppelung der Performance herbeiführen kann. Distributions-Paketquellen sind auf maximale Breitenwirkung kompiliert. Die Compiler für die Erzeugung der Pakete nutzen also Einstellungen, die auf Kosten der Performance mit so vielen Systemen wie möglich kompatibel sind.

Auf GitHub findet sich mit lzbench [2] eine relativ gut gepflegte Benchmark-Suite, die mehrere Dutzend Algorithmen in einem Paket zusammenfasst. Sie wird ausschließlich im Quellcode ausgeliefert. Das ist vorteilhaft, weil so der Standard-Compiler der jeweiligen Umgebung zum Einsatz kommt, um ein optimales Binary zu erzeugen. Als Erstes laden wir den lzbench-Code von GitHub über das Git-Kommandozeilenwerkzeug herunter:

Das eigentliche Kompilieren des heruntergeladenen Codes erfolgt durch Auswertung des Makefiles mit ~/compr/ lzbench$ make. Die Auftauchen von Warnungen während des Kompilierens ist normal, denn Kompressionsalgorithmen sind hoch optimiert; dies aber geht mit unsicheren Codeteilen einher, die moderne Compiler monieren. Lohn der Mühen ist jedenfalls die Erzeugung der ausführbaren Datei "lzbench", die ein Kompilat mit allen auf der vorliegenden Workstation unterstützten Kompressionsalgorithmen darstellt. Den eigentlichen Benchmark durchführen wollen wir mit dem unter [2] im Detail beschriebenen Kompressionsmuster Silesia Corpus. Dabei handelt es sich um eine Sammlung von Dateien, die im professionellen Einsatz häufig anzutreffen sind. Zum Herunterladen kommt wget zum Einsatz:

Das heruntergeladene Archiv entpacken wir in den Unterordner "Silesia". Die einzelnen Dateien kommen ohne Dateiendungen daher. Dies ist unbedenklich, weil Silesia Korpus aus Dateiströmen besteht, die als Ganzes komprimierbar sind. Das eigentliche Anwerfen des Benchmark-Testlaufs erfolgt nach folgendem Schema:

Die Übergabe des Parameters "-i" legt fest, wie viele Kompressions- und Dekompressions-Durchläufe mindestens und höchstens durchzuführen sind. Eine höhere Anzahl an Durchläufen führt auf Systemen mit dynamischer Taktanpassung wie etwa einem Notebook zu stabileren Ergebnissen. Der Grund liegt darin, dass eine Art gleitender Durchschnitt über die Ergebnisse entsteht. "-j" weist das System zum Zusammenfassen aller Eingangsdaten an, die im per "-r" übergebenen Verzeichnis liegen.

Im Interesse bestmöglicher Stabilität sollten Sie den Benchmark zunächst starten, dann durch Drücken von "Ctrl + C" aber gleich wieder beenden. Darauf folgt ein Neustart. Der Sinn dahinter ist, dass die ersten Durchläufe eventuell eine bessere Systemleistung sehen, weil sich die thermische Auslastung noch nicht auf normalem Niveau bewegt. Dieses Verhalten sollten Sie bei Benchmarks stets im Hinterkopf behalten.

Im Interesse der Vergleichbarkeit erfolgten alle von lzbench ausgelösten Benchmark-Tests für unseren Workshop im Einkernbetrieb. Damit müssen Sie eine gute Stunde Wartezeit einplanen, bevor die Ergebnisse zur Ernte bereitstehen. Zur Beschleunigung böte sich natürlich ein geringerer Wert im Parameter "-i" an – dies geht dann allerdings mit einer Verminderung der Genauigkeit einher.

Benchmark korrekt auswerten

Nach dem erfolgreichen Durchlaufen von lzbench erscheint die in Bild 2 dargestellte Tabelle. Besonders auffällig ist, dass manche Algorithmen mit sehr hohem Kompressionsfaktor im Bereich der für Kompression und Dekompression notwendigen Zeiten starke Unterschiede aufweisen. Ein gutes Beispiel dafür ist der ZSTD-Standard in der Parametrisierung "-5". Er komprimiert nur 155 MByte/s, dekomprimiert aber fast 1500 MByte/s.

Aus diesem Unterschied um den Faktor zehn lässt sich ableiten, dass eine derartig starke Kompression nicht unbedingt sinnvoll ist. Das ist insbesondere dann der Fall, wenn die hierfür verbrauchte Rechenleistung teuer oder beschränkt ist – Stichwort Datensicherung im laufenden Betrieb. Bei der Arbeit mit dem Algorithmus Lizard in Parametrisierung "-14" gilt, dass der erreichte Kompressionsfaktor etwas schlechter ist - andererseits arbeitet der Algorithmus wesentlich schneller.

Interessant ist auch lz4Fast in der Parametrisierung "-17": Er erreicht eine vergleichsweise hohe Kompressionsrate bei einer brauchbaren Geschwindigkeit; Density mit "-1" ist beim Komprimieren schneller, dekomprimiert aber langsamer. Unsere kompletten Testergebnisse stehen für eigene Vergleiche unter [4] als ZIP-Datei zum Download bereit.

Stark abhängig vom Archivinhalt

Situationen, in denen Kompressionsalgorithmen mit gut komprimierbaren, also entropiereichen Dateien konfrontiert sind, sind nicht unbedingt häufig. Deshalb möchten wir als Nächstes einen rund 200 MByte großen Ordner mit diversen JPEGs von einer Digitalkamera komprimieren. Auch diese wandern in einen Unterordner des lzbench-Verzeichnisses, wo sie analog zu Silesia Korpus ansprechbar sind. Der eigentliche Aufruf des zweiten Testlaufs erfolgt also folgendermaßen:

Da die Bilddateien in einem Unterordner des lzbench-Verzeichnisses liegen, reicht eine Anpassung des an "-r" übergebenen Ordnernamens. Die mit 16 GByte RAM ausgestattete Workstation scheiterte bei der Ausführung des tornado-Algorithmus. Da dies zu einem Stopp des gesamten Benchmarks führte, war eine Reduktion der Eingabedaten erforderlich, um den Testlauf wieder durchführbar zu machen.

Die meisten Algorithmen – siehe zum Beispiel lz4 – liefern nun größere Dateien und konsumieren trotzdem hohe Mengen an Rechenleistung. Daraus folgt, dass die Auslieferung statischer Testdateien nicht unter Kompression erfolgen soll. Denn das Packen und Entpacken verbraucht Leistung, was die Gesamtkosten erhöht. Im letzten Durchlauf versuchten wir uns an einer Kompression des Echtzeitbetriebssystems ESP_IDF. Da der Download aus GitHub mit

ebenfalls in einem Unterordner des lzbench-Verzeichnisses erfolgte, lässt sich die Ausführung mit /lzbench -i5,5 -j -r esp-idf/ ganz ähnlich anweisen. Allerdings hatte der Algorithmus lz4sse im Rahmen der Ausführung reproduzierbar die Fehlermeldung "Segmentation fault (core dumped)" mit einem Abbruch des Benchmarks zur Folge. Als Workaround nahmen wir den Umweg über eine TAR-Datei nach folgendem Schema:

Durch Nichtübergeben des z-Parameters erzeugt TAR ein nichtkomprimiertes Archiv. Es wandert in die Benchmark-Suite:

Die Ergebnisse dieses Durchlaufs: Die Kompression der IDF-Distribution erfolgt mit zstandard am effizientesten.

zstandard und LZ4 per Kommandozeile nutzen

Unsere Ergebnisse deuten auf eine deutliche Überlegenheit des von Facebook quelloffen entwickelten Algorithmus zstandard (zstd) hin. Er kommt einerseits mit unkomprimierbaren Eingabedaten gut zurecht und bietet andererseits hohe Kompressionsraten. Linux-Distributionen sind meist mit einer vorkompilierten Version der Referenzimplementierung ausgestattet, die sich mit sudo apt-get install zstd aus den Paketquellen installieren lässt. Zstd ist von Haus aus nur zur Kompression einzelner Dateien befähigt. Zur Verpackung von Verzeichnissen ist der erwähnte Umweg über ein TAR-Archiv erforderlich, was auf Kommandozeilenebene folgendermaßen aussieht:

Das Festlegen der Einstellungen für Threading und Kompressionsintensität erfolgt dabei durch Übergabe von Umgebungsvariablen. Alternativ dazu lässt sich das von TAR zurückgelieferte Archiv in einem Folgeschritt an zstd weiterleiten.

Ist sehr schnelles Agieren erforderlich, eignet sich der LZ4-Algorithmus noch besser. Auch er lässt sich mit sudo apt-get install lz4 auf Kommandozeilenebene aus den Paketquellen installieren. Wichtig ist, dass das Kommandozeilenwerkzeug eine durch Übergabe von "-m" beziehungsweise "-r" aktivierbare Option zur Verarbeitung von Ordnern oder mehreren Dateien mitbringt.

Fazit

Die richtige Wahl des Kompressionsalgorithmus setzt die Berücksichtigung verschiedenster Parameter voraus. Als Ermessensgrundlage können hier selbst durchgeführte Tests helfen. Denn gerade beim Betrieb von Microservices gilt, dass die korrekte Auswahl des Verfahrens zur Kostenreduktion und zum beschleunigten Start von Instanzen führt.

Kompressionsalgorithmen im Vergleich

Schwere Quetschung

Theorie nicht gleich Praxis

Theorie nicht gleich Praxis

Die Wahl des passenden Algorithmus

Eigenen Benchmark anstoßen

Benchmark korrekt auswerten

Stark abhängig vom Archivinhalt

zstandard und LZ4 per Kommandozeile nutzen

Fazit