Почему сжатие Gzip не устраняет дубликаты данных?

Question

Я просто провел небольшой эксперимент, где создал архив tar с дубликатами файлов, чтобы посмотреть, будет ли он сжат, к моему ужасу, это не так! Подробности следуют (результаты с отступом для удовольствия от чтения):

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

Сначала я создал файл случайных данных размером 1 МБ (а). Затем я скопировал его в файл b и также связал его с c. При создании тарбола tar явно знал о жесткой связи, поскольку тарбол был всего ~ 2MiB, а не ~ 3Mib.

Теперь я ожидал, что gzip уменьшит размер архива до ~ 1 МБ, так как a и b являются дубликатами, и внутри архива должно быть 1 МБ непрерывных данных, но этого не произошло.

Почему это? И как мне эффективно сжать тарбол в этих случаях?

Answer 1

Николь Хэмилтон правильно отмечает, что gzip не найдет удаленные дубликаты данных из-за небольшого размера словаря.

bzip2 похож, потому что он ограничен 900 КБ памяти.

Вместо этого попробуйте:

Алгоритм LZMA/LZMA2 (xz , 7z)

Алгоритм LZMA принадлежит тому же семейству, что и Deflate, но использует гораздо больший размер словаря (настраивается; по умолчанию это что-то вроде 384 МБ). Утилита xz , которая должна быть установлена по умолчанию в большинстве последних дистрибутивов Linux, похожа на gzip и использует LZMA.

Поскольку LZMA обнаруживает избыточность на большие расстояния, она сможет дедуплицировать ваши данные здесь. Тем не менее, это медленнее, чем Gzip.

Другой вариант - 7-zip (7z , в пакете p7zip ), который является архиватором (а не однопотоковым компрессором), который по умолчанию использует LZMA (написанный автором LZMA). 7-zip-архиватор выполняет собственную дедупликацию на уровне файлов (просматривая файлы с одинаковым расширением) при архивировании в свой формат .7z . Это означает, что если вы захотите заменить tar на 7z , вы получите идентичные файлы с дедупликацией. Однако 7z не сохраняет наносекундные временные метки, разрешения или xattrs, поэтому может не соответствовать вашим потребностям.

lrzip

lrzip - это компрессор, который предварительно обрабатывает данные для удаления избыточности на большие расстояния, а затем передает их в обычный алгоритм, такой как Gzip/Deflate, bzip2, lzop или LZMA. Для приведенных здесь образцов данных это необязательно; это полезно, когда входные данные больше, чем могут поместиться в памяти.

Для данных такого типа (дублированные несжимаемые фрагменты) вы должны использовать сжатие lzop (очень быстрое) с lrzip , потому что нет смысла пытаться сложнее сжимать полностью случайные данные после их дедупликации.

Буп и Обнам

Так как вы помечены на вопрос подпорке, если ваша цель здесь резервное копирование данные, рекомендуется использовать программу резервного копирования дедуплицирующего как БУП или Obnam.

Answer 2

Gzip gzip основан на алгоритме DEFLATE, который представляет собой комбинацию кодирования LZ77 и Хаффмана. Это алгоритм сжатия данных без потерь, который работает путем преобразования входного потока в сжатые символы, используя словарь, созданный на лету, и отслеживая дубликаты. Но он не может найти дубликаты, разделенные более чем 32K. Ожидать, что он обнаружит дубликаты на расстоянии 1 МБ, нереально.

Answer 3

gzip не найдет дубликаты, даже xz с огромным размером словаря не найдет. Что вы можете сделать, это использовать mksquashfs - это действительно сэкономит место дубликатов.

Некоторые быстрые результаты теста с xz и mksquashfs с тремя случайными двоичными файлами (64 МБ), из которых два одинаковы:

Настроить:

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

Answer 4

В случае резервного копирования, возможно, с большим набором файлов меньшего размера, одна хитрость, которая может работать для вас, заключается в сортировке файлов в tar по расширению:

find archive_dir -type f | rev | sort | rev | tar czf my_archive.tar.gz -I -

Answer 5

В моей системе lzma test.tar приводит к файлу test.tar.lzma размером 106'3175 байт (1.1M)

Answer 6

Как дополнение к ответу механической улитки:

Даже xz (или lzma) не найдет дубликаты, если размер несжатого отдельного файла (или, точнее, расстояние между дубликатами) превышает размер словаря. xz (или lzma) даже при самых высоких настройках -9e резервирует для этого только 64 МБ.

К счастью, вы можете указать свой собственный размер диктона с опцией --lzma2=dict=256MB (только --lzma1=dict=256MB разрешено при использовании псевдонима lzma для команды)

К сожалению, при переопределении настроек с помощью пользовательских цепочек сжатия, как указано в примере выше, значения по умолчанию для всех других параметров не устанавливаются на тот же уровень, что и с -9e. Таким образом, плотность сжатия не так высока для отдельных файлов.

Answer 7

В gzip без ключей командной строки используется минимально возможный алгоритм сжатия.

Попробуйте использовать:

gzip -9 test.tar

Вы должны получить лучшие результаты