Mir schwirren Ideen für einige Progamme im Kopf rum, die ich zwar gerne schreiben würde, aber leider keine Zeit dafür habe. Eine Idee wäre ein adaptives GZip oder auch Max-Throughput GZip.
Problem
gzip ist ein Streamkompressor, es komprimiert einfach einen Strom von Daten ohne auf eine besondere Struktur oder auf besondere Inhalte acht zu geben, kurz was es komprimiert, das ist ihm egal. Meist wird explizit oder implizit in einer Pipe verwendet, also Quelle | gzip | Ziel. Beispielsweise tar -c irgendwas | gzip | netcat anderer_rechner um ein Backup auf einem anderen Rechner zu speichern. Statt tar könnte man jetzt auch dd nehmen, oder netcat einfach durch eine Datei ersetzen. Nutzt man tar mit der -z Option, dann macht es implizit eine interne Pipe auf.
Hier hat man schon zwei Ziele:
-
Höchstmöglichste Kompression
-
Kurzmöglichste Laufzeit (aka Geschwindigkeit, Durchsatz/Throughput)
Hier ist schon der erste Gegensatz, heutige PCs sind selten schnell genug um beides zu liefern. Zu den Beschränkungen (Randbedingungen) gehören
-
Geschwindigkeit der Quelle (wie schnell kann ich lesen)
-
Geschwindigkeit des Ziel (wie schnell kann ich schreiben)
-
Geschwindigkeit der Komprimierung (wie schnell sind CPU/Speicher)
-
Art der Daten (gut komprimierbarer Text, schlecht komprimierbare Binärdaten)
-
Geschwindigkeit der Pipes, der Einfachheit halber den Geschwindigkeiten der Quelle und des Ziels zugeschlagen.
-
Einstellbarer Kompressionsgrad (bei gzip -1 bis -9)
Das bringt uns dann zu folgenden Extremen:
-
Die Quelle ist langsamer als der Kompressor -> stärkere Kompression möglich da Kompressor nicht ausgelastet ist
-
Das Ziel ist langsamer als der Kompressor -> stärkere Kompression möglich, da Kompressor nicht ausgelastet ist
-
Der Kompressor ist langsamer als die Quelle und/oder Ziel -> Kompression runterschalten um den Durchsatz nicht zu bremsen
Natürlich kann sich auch alles während der Ausführung ändern, beispielsweise weil die Daten sich ändern (Text führt zu weniger komprimierten Bytes, Ziel muss weniger entgegennehmen), andere Prozesse dem Kompressor die Rechenleistung stehlen, oder Quelle und Ziel ihre Geschwindigkeit ändern, weil beispielsweise in langsamere Bereiche der Festplatten geschrieben werden.
Der Nutzer kann zwar eine Vermutung anstellen, was die Hardware schaffen könnten und eine angemesse Kompressionsstufe wählen, aber ich bezweilfe dass er jemals das Optimum treffen wrd. Und oftmals werden Backups unter Zeitdruck angefertigt, die möglichst kurze Ausführungzeit ist da Pflicht..
Die Lösung
Adaptive gzip sollte automatisch die Kompressionsstufe anpassen können, sobald es merkt, dass die CPU nicht ausgelastet ist, weil Quelle und/oder Ziel nicht mitkommen, oder es merklich bremst und daher schneller und mit weniger Kompression laufen sollte. Optimalerweise sollte es heutzutage auch multi-threaded sein umd mehrere Prozessoren und Kerne nutzen zu können.
Meines Wissens nach sind mehrere aneinandergefügte gzip Ströme oder Dateien auch ein gültiger gzip Stream, so das man quasi bei Änderung der Kompressionsstufe einfach den alten Stream abschliesst und einen neuen Stream anfängt und diesen bis zur nächsten Änderung bei behält. Dabei muss natürlich immer ein Blick auf den Füllstand der Ein- und Ausgabepuffer geachtet werden. Die Verarbeitung sollte dabei immer Blockweise geschehen und nach Abarbeitung eins Blocks und vor verarbeiten des nächsten Blocks sollte überprüft werden ob eine Änderung der Kompressionsstufe sinnvoll wäre, basierend auf Pufferfüllstand und wie lange die Puffer bereits gefüllt sind, also warten. Hier könnte sich schon eine threadbasierte Lösung für Eingabe, Verarbeitung, Ausgabe anbieten.
Von gzip existiert bereits eine parallelisierte Variante namens pigz, welches auf der zlib basiert. Alle drei Programme sind von den gleichen Entwicklern. Als Weiterentwicklung von adaptive gzip könnte man die blockweise Verarbeitung auf mehrere Threads verteilen, dabei müsste die Ausgabe wieder in der korrekten Reihenfolge serialisiert werden, da durch unterschiedliche Kompressionsstufen evt. schwächer komprimierte Blöcke vorherige stärker komprimierte Blöcke überholen könnten.
Wiederholte gzip header könnten evt. den finalen Kompressionsgrad verschlechtern.
Die Entwicklung der Fomel oder des Algorithmus für die Anpassung des Kompressionsgrad könnte durchaus interessant sein....
Leider keine Zeit
Der Teufel steckt bei der Idee wie so oft im Detail und die Details oder Features könnten überhand nehmen. Vielleicht möchte man früher oder später per Parameter die Größe der Blöcke, Puffer, min threads, max threads und einen bereich für Kompressionsgrad angeben. Wer weiss was sonst für Probleme bei der Implementierung auftreten können. Vielleicht ist die Idee auch nicht zu Ende gedacht. So oder so. Momentan hab ich leider keine Zeit dafür 
.
Recent comments