Mengapa kompresi Gzip tidak menghilangkan duplikat data?

30

Saya baru saja melakukan percobaan kecil di mana saya membuat arsip tar dengan file duplikat untuk melihat apakah itu akan dikompresi, saya kagum, ternyata tidak! Detail mengikuti (hasil indentasi untuk kesenangan membaca):

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

Pertama saya membuat file data acak 1MiB (a). Kemudian saya menyalinnya ke file b dan juga menghubungkannya dengan c. Saat membuat tarball, tar tampaknya menyadari hardlink, karena tarball hanya ~ 2MiB dan bukan ~ 3Mib.

Sekarang saya berharap gzip mengurangi ukuran tarball menjadi ~ 1MiB karena a dan b adalah duplikat, dan harus ada 1MiB data kontinu diulang di dalam tarball, namun ini tidak terjadi.

Kenapa ini? Dan bagaimana saya bisa mengompres tarball secara efisien dalam kasus ini?

Guido
sumber

Jawaban:

24

Gzip gzip didasarkan pada algoritma DEFLATE, yang merupakan kombinasi dari kode LZ77 dan Huffman. Ini adalah algoritma kompresi data lossless yang bekerja dengan mengubah aliran input menjadi simbol terkompresi menggunakan kamus yang dibuat saat itu juga dan menonton duplikat. Tetapi tidak dapat menemukan duplikat yang dipisahkan oleh lebih dari 32 ribu. Mengharapkannya menemukan duplikat 1MB terpisah tidak realistis.

Nicole Hamilton
sumber
Cukup adil! Apakah Anda mengetahui ada alternatif lain yang tidak berfungsi pada stream?
Guido
1
Saya tidak tahu ada solusi untuk masalah Anda. Jika saya berharap ini akan menjadi masalah serius yang berulang, saya (secara pribadi) akan menyerangnya dengan skrip yang melakukan operasi n-way cmp (membandingkan) untuk menemukan duplikat, menulis daftar ke file, kemudian hanya tar + gzip saja item unik + daftar. Untuk memulihkan, saya akan menggunakan skrip kedua untuk ungzip dan untar, lalu buat dups dari daftar. Alternatif lain adalah mengubah dups menjadi tautan keras, karena Anda tahu tar menemukan itu. Maaf, saya tahu itu mungkin bukan yang Anda harapkan.
Nicole Hamilton
1
gzip dan bzip2 keduanya harus relatif "ramah aliran" karena desainnya - sangat penting untuk dapat bekerja sebagai bagian dari pipa. Apa yang Anda cari di sini sebenarnya adalah deduplikasi dan bukan hanya kompresi. Karena tar memecah proses menjadi dua bagian - pengarsipan hanya dengan tar, dan kemudian menggunakan program kedua sebagai filter untuk kompres. Saya tidak dapat menemukan arsip terkompresi dengan deduplikasi dalam pencarian saya, tetapi saya menemukan pertanyaan terkait sebelumnya ini. superuser.com/questions/286414/...
Stephanie
2
@Stephanie, NicoleHamilton: Ada en.wikipedia.org/wiki/Lrzip#Lrzip .
Siput mekanik
1
@ Guido Tentu saja tidak ada yang dapat menghapus duplikat dari sesuatu yang tidak diingat dalam aliran, tetapi coba sesuatu seperti xz -9 -M 95%, atau bahkan xz -M 95% --lzma2=preset=9,dict=1610612736. Itu tidak akan cepat, tetapi duplikat Anda tidak mungkin dibiarkan dalam hasil.
Eroen
39

Nicole Hamilton dengan benar mencatat bahwa gziptidak akan menemukan data duplikat yang jauh karena ukuran kamusnya yang kecil.

bzip2 mirip, karena terbatas pada memori 900 KB.

Sebagai gantinya, cobalah:

Algoritma LZMA / LZMA2 ( xz, 7z)

Algoritma LZMA berada dalam keluarga yang sama dengan Deflate, tetapi menggunakan ukuran kamus yang jauh lebih besar (dapat disesuaikan; standarnya kira-kira 384 MB). The xzutilitas, yang harus diinstal secara default pada kebanyakan distro Linux terbaru, mirip dengan gzipdan menggunakan LZMA.

Karena LZMA mendeteksi redundansi jarak yang lebih jauh, LZMA akan dapat menduplikasi data Anda di sini. Namun, ini lebih lambat dari Gzip.

Pilihan lain adalah 7-zip ( 7z, dalam p7zippaket), yang merupakan pengarsipan (daripada kompresor aliran tunggal) yang menggunakan LZMA secara default (ditulis oleh penulis LZMA). Pengarsip 7-zip menjalankan deduplikasi sendiri di tingkat file (melihat file dengan ekstensi yang sama) ketika pengarsipan ke .7zformatnya. Ini berarti bahwa jika Anda bersedia untuk mengganti tardengan 7z, Anda mendapatkan file identik deduplicated. Namun, 7z tidak mempertahankan stempel waktu nanodetik, izin, atau xattr, sehingga mungkin tidak sesuai dengan kebutuhan Anda.

lrzip

lrzipadalah kompresor yang memproses data untuk menghilangkan redundansi jarak jauh sebelum memasukkannya ke algoritma konvensional seperti Gzip / Deflate, bzip2, lzop, atau LZMA. Untuk data sampel yang Anda berikan di sini, itu tidak perlu; ini berguna untuk saat input data lebih besar dari apa yang dapat ditampung dalam memori.

Untuk jenis data ini (duplikat potongan yang tidak dapat dikompres), Anda harus menggunakan lzopkompresi (sangat cepat) dengan lrzip, karena tidak ada manfaatnya untuk berusaha lebih keras untuk mengompresi data yang benar-benar acak setelah data itu didupuplikasi.

Bup dan Obnam

Karena Anda menandai pertanyaan , jika tujuan Anda di sini mencadangkan data, pertimbangkan untuk menggunakan program cadangan deduplicating seperti Bup atau Obnam .

Siput mekanik
sumber
Lrzip ini terlihat menarik. Bahkan memiliki penulis yang dikenal untuk solusi non-tradisional. Sekarang saya harus merevisi skrip cadangan saya. Lagi.
Eroen
3
+1 Wow, sungguh sumber pengetahuan / pengalaman di sana. Dihargai Bisakah saya menambahkan sistem file yang diaktifkan dedup ke dalam campuran? ZFS (dan, saya pikir Btrfs dijadwalkan untuk memilikinya) - akan bekerja dengan duplikasi blok aligned
sehe
7Zip menggunakan kompresi LZMA2 dan ukuran dicctionary 1536Mb (ukuran maksimum tersedia di Windows GUI) sangat bagus untuk saya!
Leopoldo Sanczyk
2

Dalam hal cadangan, mungkin dengan sekumpulan file yang lebih kecil, satu trik yang mungkin bisa dilakukan untuk Anda adalah mengurutkan file dalam tar dengan ekstensi:

find archive_dir -type f | rev | sort | rev | tar czf my_archive.tar.gz -I -
pengguna216110
sumber
Saya akan memotong semua revitu (mengapa bahkan membalikkan dan kemudian mengurutkan?) Dan melihat sortopsi "-r, --reverse" (meskipun saya tidak yakin mengapa Anda ingin membalikkan apa pun). Tapi saya pikir tarpilihan Anda " -I" tidak melakukan apa yang menurut Anda " -I, --use-compress-program PROG" , Anda mungkin ingin "-T, --files-from FILE"
Xen2050
Saya percaya | tar czf my_archive.tar.gz -I -seharusnya| xargs tar Azf my_archive.tar.gz
Olivier Dulac
@ Xen2050, revmembalik urutan karakter di setiap baris, bukan urutan baris di aliran. Karena itu, sortkelompokkan file dengan ekstensi mereka. Saya menduga -I -seharusnya -T -, yang menyediakan daftar file di stdin.
billyjmc
@ Billyjmc saya melihat, itu revakan semacam mengatur dengan ekstensi, bukan berarti ada banyak ekstensi di linux pula. Saya membayangkan mengurutkan berdasarkan ukuran akan memiliki peluang lebih tinggi untuk menemukan dup
Xen2050
2

gziptidak akan menemukan duplikat, bahkan xzdengan ukuran kamus yang besar tidak akan menemukan. Apa yang dapat Anda lakukan adalah menggunakan mksquashfs- ini memang akan menghemat ruang duplikat.

Beberapa hasil pengujian cepat dengan xzdan mksquashfsdengan tiga file biner acak (64MB) yang keduanya sama:

Mendirikan:

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
sumber
Apakah mksquashfs hanya menemukan duplikat pada tingkat file, atau apakah itu juga berfungsi pada potongan yang lebih kecil? Yaitu: Apakah itu juga akan mengkompres file yang sedikit berbeda-tapi-kebanyakan-yang-sama?
Chaos_99
Ini bekerja afaik hanya pada file-basis. Anda dapat melihat bahwa ketika mengaitkan ketiga file uji ke arsip tar yang tidak dikompresi dan mengompresnya dengan mksquashfs sesudahnya. Di sisi lain, mksqashfs akan melaporkan, ketika menemukan duplikat dengan Number of duplicate files founddi stdout.
Izzy
1

Pada sistem saya lzma test.tarmenghasilkan file test.tar.lzma 106'3175 byte (1,1M)

rwewe
sumber
1

Sebagai tambahan untuk jawaban 'keong mekanik':

Bahkan xz (atau lzma) tidak akan menemukan duplikat jika ukuran file dari file tunggal terkompresi (atau, lebih tepatnya, jarak antara duplikat) melebihi ukuran kamus. xz (atau lzma) bahkan pada pengaturan tertinggi -9ehanya mencadangkan 64MB untuk ini.

Untungnya Anda dapat menentukan ukuran kamus Anda sendiri dengan opsi --lzma2=dict=256MB (hanya --lzma1=dict=256MBdiizinkan saat menggunakan lzma alias ke perintah)

Sayangnya, ketika mengesampingkan pengaturan dengan rantai kompresi khusus seperti yang diberikan dalam contoh di atas, nilai default untuk semua parameter lainnya tidak diatur ke level yang sama dengan -9e. Jadi kepadatan kompresi tidak setinggi untuk file tunggal.

Kekacauan_99
sumber
-2

gzip tanpa saklar baris perintah menggunakan algoritma kompresi yang serendah mungkin.

Coba gunakan:

gzip -9 test.tar

Anda harus mendapatkan hasil yang lebih baik

J Baron
sumber
1
Tidak juga, perbedaannya minimal. Saya juga mencoba bzip2 dengan hasil yang serupa.
Guido
gzip tanpa saklar baris perintah menggunakan algoritma kompresi yang serendah mungkin. => Ini tidak benar - "man gzip" menyatakan bahwa "(t) dia tingkat kompresi default adalah -6 (yaitu, bias terhadap kompresi tinggi dengan mengorbankan kecepatan)." Ini benar untuk semua versi gzip yang saya tahu, jika pengaturan default yang dikompilasi tidak ditimpa oleh variabel lingkungan GZIP. Bahkan level "-9" tidak akan membantu Anda di sini, seperti yang sudah dijelaskan dalam jawaban yang diberikan.
Gunter Ohrner