Warum beseitigt die Gzip-Komprimierung keine doppelten Datenblöcke?

30

Ich habe gerade ein kleines Experiment gemacht, in dem ich ein Tar-Archiv mit doppelten Dateien erstellt habe, um zu sehen, ob es komprimiert werden würde. Zu meiner Ehrfurcht war es nicht! Details folgen (Ergebnisse für Lesevergnügen eingerückt):

$ dd if=/dev/urandom bs=1M count=1 of=a
  1+0 records in
  1+0 records out
  1048576 bytes (1.0 MB) copied, 0.114354 s, 9.2 MB/s
$ cp a b
$ ln a c
$ ll
  total 3072
  -rw-r--r-- 2 guido guido 1048576 Sep 24 15:51 a
  -rw-r--r-- 1 guido guido 1048576 Sep 24 15:51 b
  -rw-r--r-- 2 guido guido 1048576 Sep 24 15:51 c
$ tar -c * -f test.tar
$ ls -l test.tar 
  -rw-r--r-- 1 guido guido 2109440 Sep 24 15:51 test.tar
$ gzip test.tar 
$ ls -l test.tar.gz 
  -rw-r--r-- 1 guido guido 2097921 Sep 24 15:51 test.tar.gz
$ 

Zuerst habe ich eine 1MiB-Datei mit zufälligen Daten erstellt (a). Dann habe ich es in eine Datei b kopiert und es auch mit c verknüpft. Bei der Erstellung des Tarballs war tar anscheinend der Hardlink bekannt, da der Tarball nur ~ 2 MB und nicht ~ 3 MB groß war.

Nun erwartete ich, dass gzip die Größe des Tarballs auf ~ 1MiB reduziert, da a und b Duplikate sind, und es sollte 1MiB fortlaufende Daten geben, die im Tarball wiederholt werden, dies trat jedoch nicht auf.

Warum ist das? Und wie könnte ich das Archiv in diesen Fällen effizient komprimieren?

Guido
quelle

Antworten:

24

Gzip gzip basiert auf dem DEFLATE-Algorithmus, einer Kombination aus LZ77- und Huffman-Codierung. Es handelt sich um einen verlustfreien Datenkomprimierungsalgorithmus, der den Eingabestream mithilfe eines Wörterbuchs, das im laufenden Betrieb erstellt wurde, in komprimierte Symbole umwandelt und nach Duplikaten sucht. Es können jedoch keine Duplikate gefunden werden, die durch mehr als 32 KB getrennt sind. Es ist nicht realistisch, zu erwarten, dass Duplikate mit einem Abstand von 1 MB erkannt werden.

Nicole Hamilton
quelle
Meinetwegen! Kennen Sie eine Alternative, die bei Streams nicht funktioniert?
Guido
1
Ich kenne keine verpackte Lösung für Ihr Problem. Wenn ich erwartet hätte, dass dies ein wiederkehrendes, schwerwiegendes Problem sein würde, würde ich es (persönlich) mit einem Skript angreifen, das die n-Wege-Cmp-Operationen (Vergleiche) ausführt, um Duplikate zu finden, die Liste in eine Datei zu schreiben und dann nur tar + gzip einzigartige Gegenstände + die Liste. Zum Wiederherstellen würde ich ein zweites Skript zum Entpacken und Entpacken verwenden und dann die Duplikate aus der Liste erstellen. Eine andere Alternative wäre, die Dups in harte Verbindungen zu verwandeln, da Sie wissen, dass tar diese erkennt. Entschuldigung, ich weiß, dass Sie das wahrscheinlich nicht gehofft haben.
Nicole Hamilton
1
gzip und bzip2 müssen aufgrund ihres Designs relativ "stream-freundlich" sein - es ist absolut notwendig, als Teil einer Pipe arbeiten zu können. Was Sie hier suchen, ist eigentlich Deduplizierung und nicht nur Komprimierung. Da tar den Prozess in zwei Teile zerlegt - Archivierung nur mit tar und anschließende Verwendung eines zweiten Programms als Filter zum Komprimieren. Ich konnte in meinen Suchen kein komprimiertes Archiv mit Deduplizierung finden, aber ich fand diese vorhergehende verwandte Frage. superuser.com/questions/286414/…
Stephanie
2
@Stephanie, NicoleHamilton: Es gibt de.wikipedia.org/wiki/Lrzip#Lrzip .
Mechanische Schnecke
1
@Guido Natürlich kann nichts Duplikate von etwas entfernen, an das es sich in einem Stream nicht erinnert, aber probieren Sie etwas wie xz -9 -M 95%oder sogar xz -M 95% --lzma2=preset=9,dict=1610612736. Es wird nicht schnell gehen, aber es ist unwahrscheinlich, dass Ihre Duplikate im Ergebnis verbleiben.
Eroen
39

Nicole Hamilton merkt korrekterweise an, dass gzipaufgrund der geringen Größe des Wörterbuchs keine entfernten doppelten Daten gefunden werden.

bzip2 ist ähnlich, weil es auf 900 KB Speicher begrenzt ist.

Versuchen Sie stattdessen Folgendes:

LZMA / LZMA2-Algorithmus ( xz, 7z)

Der LZMA-Algorithmus gehört zur selben Familie wie Deflate, verwendet jedoch ein viel größeres Wörterbuch (anpassbar; Standard ist etwa 384 MB). Das xzDienstprogramm, das standardmäßig auf den neuesten Linux-Distributionen installiert werden sollte, ähnelt gzipund verwendet LZMA.

Da LZMA Redundanzen mit größerer Reichweite erkennt, kann es Ihre Daten hier deduplizieren. Es ist jedoch langsamer als Gzip.

Eine weitere Option ist 7-zip ( 7zim p7zipPaket enthalten). Hierbei handelt es sich um einen Archivierer (und nicht um einen Single-Stream-Kompressor), der standardmäßig LZMA verwendet (geschrieben vom Autor von LZMA). Der 7-zip-Archivierer führt eine eigene Deduplizierung auf Dateiebene durch (bei Dateien mit derselben Erweiterung), wenn er in seinem .7zFormat archiviert . Dies bedeutet , dass , wenn Sie bereit sind , ersetzen tarmit 7z, erhalten Sie identische Dateien dedupliziert. 7z behält jedoch keine Zeitstempel, Berechtigungen oder Xattrs für Nanosekunden bei, sodass es möglicherweise nicht Ihren Anforderungen entspricht.

lrzip

lrzipist ein Kompressor, der die Daten vorverarbeitet, um Fernredundanz zu beseitigen, bevor sie einem herkömmlichen Algorithmus wie Gzip / Deflate, bzip2, lzop oder LZMA zugeführt werden. Für die hier angegebenen Beispieldaten ist dies nicht erforderlich. Dies ist nützlich, wenn die Eingabedaten größer sind als der Speicherplatz.

Für diese Art von Daten (duplizierte inkomprimierbare Blöcke) sollten Sie die lzopKomprimierung (sehr schnell) mit verwenden lrzip, da es keinen Vorteil hat, sich nach der Deduplizierung mehr Mühe zu geben, vollständig zufällige Daten zu komprimieren.

Bup und Obnam

Da Sie die Frage getaggt , wenn Ihr Ziel ist die Sicherung von Daten, sollten Sie mit einem Deduplizierung Backup - Programm wie Bup oder Obnam .

Mechanische Schnecke
quelle
Dieser LRZIP sieht interessant aus. Es gibt sogar einen Autor, der für nicht traditionelle Lösungen bekannt ist. Jetzt muss ich meine Backup-Skripte überarbeiten. Nochmal.
Eroen
3
+1 Wow, was für ein Brunnen des Wissens / der Erfahrung dort. Geschätzt. Darf ich dedup-fähige Dateisysteme zum Mix hinzufügen? ZFS (und, ich denke, Btrfs ist geplant, um es zu haben) - würde mit Block ausgerichteten Duplikation arbeiten
sehe
7Zip mit LZMA2-Komprimierung und einer Wörterbuchgröße von 1536 MB (maximale Größe in der Windows-Benutzeroberfläche verfügbar) eignet sich hervorragend für mich!
Leopoldo Sanczyk
2

Im Falle einer Sicherung, möglicherweise mit einem größeren Satz kleinerer Dateien, besteht ein Trick, der für Sie möglicherweise funktioniert, darin, die Dateien im Teer nach Erweiterung zu sortieren:

find archive_dir -type f | rev | sort | rev | tar czf my_archive.tar.gz -I -
user216110
quelle
Ich schneide alle aus rev(warum sogar umkehren und dann sortieren?) Und schaue auf die sortOption "-r, --reverse" (obwohl ich nicht sicher bin, warum Sie überhaupt eine Umkehrung wollen). Aber ich denke, Ihre tarOption " -I" macht nicht das, was Sie denken, es macht " -I, --use-compress-program PROG" , Sie wollen wahrscheinlich "-T, --files-from FILE"
Xen2050
Ich glaube, das | tar czf my_archive.tar.gz -I -sollte sein| xargs tar Azf my_archive.tar.gz
Olivier Dulac
@ Xen2050, revkehrt die Reihenfolge der Zeichen in jeder Zeile um, nicht die Zeilenreihenfolge im Stream. Aus diesem Grund sortwerden die Dateien nach ihrer Erweiterung gruppiert. Ich vermute das -I -hätte sein sollen -T -, das die Dateiliste auf stdin liefert.
billyjmc
@billyjmc Ich sehe, das revwürde irgendwie durch Erweiterung arrangieren, nicht, dass es in Linux sowieso viele Erweiterungen gibt. Ich könnte mir vorstellen, dass das Sortieren nach Größe die Wahrscheinlichkeit erhöht, dass
Duplikate gefunden werden
2

gzipfindet keine Duplikate, auch xzbei einer riesigen Wörterbuchgröße nicht. Was Sie tun können, ist zu verwenden mksquashfs- dies spart in der Tat Platz für Duplikate.

Einige schnelle Testergebnisse mit xzund mksquashfsmit drei zufälligen Binärdateien (64 MB), von denen zwei gleich sind:

Installieren:

mkdir test
cd test
dd if=/dev/urandom of=test1.bin count=64k bs=1k
dd if=/dev/urandom of=test2.bin count=64k bs=1k
cp test{2,3}.bin
cd ..

Kürbisse:

mksquashfs test/ test.squash
> test.squash - 129M

xz:

XZ_OPT='-v --memlimit-compress=6G --memlimit-decompress=512M --lzma2=preset=9e,dict=512M --extreme -T4 ' tar -cJvf test.tar.xz test/
> test.tar.xz - 193M
Izzy
quelle
Findet mksquashfs Duplikate nur auf Dateiebene oder funktioniert es auch bei kleineren Stücken? Das heißt: Komprimiert es auch etwas andere, aber meistens dieselben Dateien?
Chaos_99
Dies funktioniert nur auf Dateibasis. Sie können das sehen, wenn Sie diese drei Testdateien in ein nicht komprimiertes tar-Archiv tarieren und sie anschließend mit mksquashfs komprimieren. Andererseits meldet mksqashfs, wenn Duplikate mit Number of duplicate files foundin stdout gefunden werden.
Izzy
1

Auf meinem System lzma test.tarwird die Datei test.tar.lzma mit 106'3175 Byte (1,1 MB) erstellt

rmweiss
quelle
1

Als Ergänzung zur Antwort von 'Mechanical Snail':

Selbst xz (oder lzma) findet keine Duplikate, wenn die Dateigröße der nicht komprimierten einzelnen Datei (oder genauer gesagt der Abstand zwischen den Duplikaten) die Wörterbuchgröße überschreitet. xz (oder lzma) reserviert auch bei höchster Einstellung -9enur 64MB dafür.

Glücklicherweise können Sie mit der Option Ihre eigene diktonische Größe angeben --lzma2=dict=256MB (nur --lzma1=dict=256MBzulässig, wenn Sie den Alias ​​lzma für den Befehl verwenden).

Leider werden beim Überschreiben der Einstellungen mit benutzerdefinierten Komprimierungsketten, wie im obigen Beispiel angegeben, die Standardwerte für alle anderen Parameter nicht auf den gleichen Wert wie mit -9e festgelegt. Daher ist die Komprimierungsdichte für einzelne Dateien nicht so hoch.

Chaos_99
quelle
-2

gzip ohne Befehlszeilenschalter verwendet den niedrigstmöglichen Algorithmus für die Komprimierung.

Versuchen Sie es mit:

gzip -9 test.tar

Sie sollten bessere Ergebnisse erzielen

J Baron
quelle
1
Nicht wirklich, der Unterschied ist minimal. Ich habe auch bzip2 mit ähnlichen ergebnissen ausprobiert.
Guido
gzip ohne Befehlszeilenschalter verwendet den niedrigstmöglichen Algorithmus für die Komprimierung. => Dies ist nicht wahr - "man gzip" gibt an, dass "(t) die Standardkomprimierungsstufe -6 ist (dh auf Kosten der Geschwindigkeit auf hohe Komprimierung eingestellt ist)." Dies gilt für alle mir bekannten gzip-Versionen, wenn die kompilierten Standardeinstellungen nicht von der Umgebungsvariablen GZIP überschrieben werden. Selbst die Stufe "-9" wird Ihnen hier nicht weiterhelfen, wie bereits in den gegebenen Antworten erläutert.
Gunter Ohrner