Dlaczego kompresja Gzip nie eliminuje duplikatów danych?

30

Właśnie wykonałem mały eksperyment, w którym utworzyłem archiwum tar ze zduplikowanymi plikami, aby sprawdzić, czy będzie ono skompresowane, ku mojemu podziwowi, nie było! Szczegóły poniżej (wyniki wcięte dla przyjemności czytania):

$ 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
$ 

Najpierw stworzyłem plik 1 MB losowych danych (a). Następnie skopiowałem go do pliku b, a także połączyłem go do c. Podczas tworzenia tarballa, tar najwyraźniej był świadomy twardego linku, ponieważ tarball miał tylko ~ 2MiB, a nie ~ 3Mib.

Teraz spodziewałem się, że gzip zmniejszy rozmiar tarballa do ~ 1MiB, ponieważ aib są duplikatami, a wewnątrz tarballa powinien być powtarzany 1MiB ciągłych danych, ale tak się nie stało.

Dlaczego to? I w jaki sposób mogę skutecznie skompresować archiwum w tych przypadkach?

Guido
źródło

Odpowiedzi:

24

Gzip gzip jest oparty na algorytmie DEFLATE, który jest kombinacją kodowania LZ77 i Huffmana. Jest to bezstratny algorytm kompresji danych, który działa poprzez przekształcenie strumienia wejściowego w skompresowane symbole za pomocą słownika zbudowanego w locie i sprawdzanie duplikatów. Ale nie może znaleźć duplikatów oddzielonych więcej niż 32 KB. Oczekiwanie, że wykryje duplikaty w odległości 1 MB, nie jest realistyczne.

Nicole Hamilton
źródło
Słusznie! Czy zdarza Ci się znać jakąś alternatywę, która nie działa na strumieniach?
Guido
1
Nie znam żadnego rozwiązania problemu w pakiecie. Gdybym spodziewał się, że będzie to powtarzający się, poważny problem, ja (osobiście) zaatakowałbym go za pomocą skryptu, który wykonał n-way cmp (porównaj), aby znaleźć duplikaty, zapisać listę do pliku, a następnie tar + gzip tylko unikalne przedmioty + lista. Aby przywrócić, użyję drugiego skryptu, aby rozpakować i rozpakować, a następnie utworzyć dups z listy. Inną alternatywą byłoby przekształcenie dupków w twarde linki, ponieważ wiesz, że tar je rozpoznaje. Przepraszam, wiem, że prawdopodobnie nie tego chciałeś.
Nicole Hamilton,
1
Zarówno gzip, jak i bzip2 muszą być względnie „przyjazne dla strumieni” ze względu na ich konstrukcję - absolutnie konieczne jest, aby móc pracować jako część potoku. To, czego tu szukasz, to właściwie deduplikacja, a nie tylko kompresja. Ponieważ tar dzieli proces na dwie części - archiwizacja tylko za pomocą tar, a następnie użycie drugiego programu jako filtra do kompresji. Nie mogłem znaleźć żadnego skompresowanego archiwum z deduplikacją w moich wyszukiwaniach, ale znalazłem to poprzednie powiązane pytanie. superuser.com/questions/286414/...
Stephanie
2
@Stephanie, NicoleHamilton: Istnieje en.wikipedia.org/wiki/Lrzip#Lrzip .
Ślimak mechaniczny
1
@Guido Oczywiście nic nie może usunąć duplikatów czegoś, czego nie pamięta w strumieniu, ale spróbuj czegoś takiego xz -9 -M 95%, a nawet xz -M 95% --lzma2=preset=9,dict=1610612736. Nie będzie to szybkie, ale twoje duplikaty raczej nie zostaną w wyniku.
Eroen
39

Nicole Hamilton poprawnie zauważa, że gzipze względu na mały rozmiar słownika nie znajdzie odległych zduplikowanych danych.

bzip2 jest podobny, ponieważ jest ograniczony do 900 KB pamięci.

Zamiast tego spróbuj:

Algorytm LZMA / LZMA2 ( xz, 7z)

Algorytm LZMA należy do tej samej rodziny co Deflate, ale wykorzystuje znacznie większy rozmiar słownika (konfigurowalny; domyślnie jest to około 384 MB). xzNarzędzie, które powinny być instalowane domyślnie w najnowszych dystrybucjach systemu Linux, jest podobny do gzipi używa lzma.

Ponieważ LZMA wykryje nadmiarowość w większym zakresie, będzie w stanie deduplikować twoje dane tutaj. Jest jednak wolniejszy niż Gzip.

Inną opcją jest 7-zip ( 7zw p7zippakiecie), który jest archiwizatorem (a nie kompresorem jedno-strumieniowym), który domyślnie korzysta z LZMA (napisany przez autora LZMA). Archiwizator 7-zip uruchamia własną deduplikację na poziomie pliku (patrząc na pliki z tym samym rozszerzeniem) podczas archiwizacji do swojego .7zformatu. Oznacza to, że jeśli jesteś w stanie wymienić tarz 7z, masz identyczne pliki deduplikacji. Jednak 7z nie zachowuje nanosekundowych znaczników czasu, uprawnień ani xattrów, więc może nie odpowiadać twoim potrzebom.

lrzip

lrzipto kompresor, który wstępnie przetwarza dane w celu usunięcia nadmiarowości na duże odległości przed przekazaniem ich do konwencjonalnego algorytmu, takiego jak Gzip / Deflate, bzip2, lzop lub LZMA. W przypadku podanych tutaj przykładowych danych nie jest to konieczne; przydaje się, gdy dane wejściowe są większe niż mogą zmieścić się w pamięci.

W przypadku tego rodzaju danych (zduplikowane fragmenty nieściśliwe) należy zastosować lzopkompresję (bardzo szybko) lrzip, ponieważ nie ma korzyści z trudniejszej kompresji całkowicie losowych danych po ich deduplikacji.

Bup i Obnam

Ponieważ otagowałeś pytania , jeśli Twoim celem jest tworzenie kopii zapasowej danych, rozważ użycie programu do tworzenia kopii zapasowych deduplikacji, takiego jak Bup lub Obnam .

Ślimak mechaniczny
źródło
Ten Lrzip wygląda interesująco. Ma nawet autora znanego z nietradycyjnych rozwiązań. Teraz będę musiał zmienić moje skrypty kopii zapasowej. Jeszcze raz.
Eroen
3
+1 Wow, co za fontanna wiedzy / doświadczenia. Doceniany. Czy mogę dodać do miksu systemy plików z włączoną funkcją deduplikacji? ZFS (i myślę, że Btrfs trafi go mieć) - będzie działać z bloku wyrównane powielania
sehe
7Zip przy użyciu kompresji LZMA2 i rozmiaru słownika 1536Mb (maksymalny rozmiar dostępny w GUI systemu Windows) działa świetnie dla mnie!
Leopoldo Sanczyk
2

W przypadku kopii zapasowej, prawdopodobnie z dużym zestawem mniejszych plików, jedną sztuczką, która może Ci pomóc, jest posortowanie plików w pliku tar według rozszerzenia:

find archive_dir -type f | rev | sort | rev | tar czf my_archive.tar.gz -I -
użytkownik216110
źródło
Odetnę wszystkie rev(dlaczego odwrócić, a potem posortować?) I spojrzę na sortopcję „-r, --reverse” (choć nie jestem pewien, dlaczego miałbyś chcieć odwrócić). Ale myślę, że twoja taropcja „ -I” nie robi tego, co myślisz, że -I, --use-compress-program PROG , prawdopodobnie chcesz „-T, --files-from FILE”
Xen2050
Uważam, że tak | tar czf my_archive.tar.gz -I -powinno być| xargs tar Azf my_archive.tar.gz
Olivier Dulac
@ Xen2050, revodwraca kolejność znaków w każdej linii, a nie kolejność linii w strumieniu. Z tego powodu sortgrupuje pliki według ich rozszerzeń. Podejrzewam, że -I -powinienem był -T -, który zapewnia listę plików na stdin.
billyjmc
@billyjmc Rozumiem, że to revbyłoby uporządkowane według rozszerzenia, nie że i tak jest wiele rozszerzeń w Linuksie. Wyobrażam sobie, że sortowanie według rozmiaru miałoby większą szansę na znalezienie dup
Xen2050
2

gzipnie znajdzie duplikatów, nawet xzprzy dużym rozmiarze słownika nie. Możesz użyć mksquashfs- to rzeczywiście pozwoli zaoszczędzić miejsce na duplikaty.

Kilka szybkich wyników badań z xzoraz mksquashfsz trzech przypadkowych plików binarnych (64MB), z których dwa są takie same:

Ustawiać:

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 ..

Squashfs:

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
źródło
Czy mksquashfs znajduje duplikaty tylko na poziomie plików, czy działa również na mniejszych porcjach? To znaczy: czy będzie również kompresował nieco inne, ale w większości te same pliki?
Chaos_99
Działa to tylko w przypadku plików. Widać to podczas tarowania tych trzech plików testowych do nieskompresowanego archiwum tar, a następnie kompresji ich za pomocą mksquashfs. Z drugiej strony, mksqashfs zgłosi, gdy znajdzie duplikaty Number of duplicate files foundw stdout.
Izzy
1

W moim systemie lzma test.tarpowstaje plik test.tar.lzma o wielkości 106'3175 bajtów (1,1M)

rmweiss
źródło
1

Jako dodatek do odpowiedzi „ślimaka mechanicznego”:

Nawet xz (lub lzma) nie znajdzie duplikatów, jeśli rozmiar nieskompresowanego pojedynczego pliku (lub, dokładniej, odległość między duplikatami) przekracza rozmiar słownika. xz (lub lzma) nawet przy najwyższych ustawieniach -9erezerwuje na to tylko 64 MB.

Na szczęście możesz określić swój własny rozmiar dyktafonu za pomocą opcji --lzma2=dict=256MB ( --lzma1=dict=256MBdozwolone tylko przy użyciu aliasu lzma do polecenia)

Niestety, podczas nadpisywania ustawień niestandardowymi łańcuchami kompresji, jak podano w powyższym przykładzie, wartości domyślne dla wszystkich innych parametrów nie są ustawione na tym samym poziomie, co w przypadku -9e. Zatem gęstość kompresji nie jest tak wysoka dla pojedynczych plików.

Chaos_99
źródło
-2

gzip bez przełączników wiersza poleceń używa najniższego możliwego algorytmu kompresji.

Spróbuj użyć:

gzip -9 test.tar

Powinieneś uzyskać lepsze wyniki

J Baron
źródło
1
Nie bardzo, różnica jest minimalna. Próbowałem również bzip2 z podobnymi wynikami.
Guido
gzip bez przełączników wiersza poleceń używa najniższego możliwego algorytmu kompresji. => To nie jest prawda - „man gzip” stwierdza, że „(t) domyślny poziom kompresji to -6 (to znaczy tendencja do wysokiej kompresji kosztem szybkości).” Dotyczy to wszystkich wersji gzip, które znam, jeśli skompilowane ustawienia domyślne nie zostaną zastąpione przez zmienną środowiskową GZIP. Nawet poziom „-9” nie pomoże ci tutaj, jak już wyjaśniono w podanych odpowiedziach.
Gunter Ohrner