Por que a compactação do Gzip não elimina fragmentos de dados duplicados?

Question

Eu fiz um pequeno experimento onde criei um arquivo tar com arquivos duplicados para ver se ele seria compactado, para minha surpresa, não foi! Os detalhes seguem (resultados recuados para prazer de leitura):

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

Primeiro eu criei um arquivo 1MiB de dados aleatórios (a). Então eu copiei para um arquivo b e também liguei para c. Ao criar o tarball, o tar aparentemente estava ciente do hardlink, já que o tarball era apenas ~ 2MiB e não ~ 3Mib.

Agora eu esperava que o gzip reduzisse o tamanho do tarball para ~ 1MiB já que a e b são duplicatas, e deveria haver 1MiB de dados contínuos repetidos dentro do tarball, mas isso não ocorreu.

Por que isso? E como eu poderia compactar o tarball eficientemente nesses casos?

    

Answer 1

O gzip gzip é baseado no algoritmo DEFLATE, que é uma combinação da codificação LZ77 e Huffman. É um algoritmo de compactação de dados sem perdas que funciona transformando o fluxo de entrada em símbolos compactados usando um dicionário construído on-the-fly e assistindo a duplicatas. Mas não é possível encontrar duplicatas separadas por mais de 32K. Esperando que ele detecte duplicatas, 1MB de intervalo não é realista.

    

Answer 2

Nicole Hamilton observa corretamente que gzip não encontrará dados duplicados distantes devido ao tamanho pequeno do dicionário.

bzip2 é semelhante, porque está limitado a 900 KB de memória.

Em vez disso, tente:

Algoritmo LZMA / LZMA2 ( xz , 7z )

O algoritmo LZMA é da mesma família que o Deflate, mas usa um tamanho de dicionário muito maior (personalizável; o padrão é algo como 384 MB). O utilitário xz , que deve ser instalado por padrão nas distribuições Linux mais recentes, é semelhante a gzip e usa LZMA.

Como o LZMA detecta redundância de longo alcance, ele poderá desduplicar seus dados aqui. No entanto, é mais lento que o Gzip.

Outra opção é o 7-zip ( 7z , no pacote p7zip ), que é um arquivador (em vez de um compressor de fluxo único) que usa o LZMA por padrão (escrito pelo autor do LZMA). O arquivador 7-zip executa sua própria desduplicação no nível do arquivo (examinando arquivos com a mesma extensão) ao arquivar no formato .7z . Isso significa que, se você estiver disposto a substituir tar por 7z , obterá arquivos idênticos desduplicados. No entanto, 7z não preserva timestamps, permissões ou xattrs em nanossegundos, portanto, pode não atender às suas necessidades.

lrzip

lrzip é um compressor que pré-processa os dados para remover a redundância de longa distância antes de alimentar um Algoritmo convencional como Gzip / Deflate, bzip2, lzop ou LZMA. Para os dados de amostra que você fornece aqui, não é necessário; é útil quando os dados de entrada são maiores do que os que podem caber na memória.

Para esse tipo de dado (fragmentos incompressíveis duplicados), você deve usar lzop de compactação (muito rápida) com lrzip , porque não há nenhum benefício em tentar compactar dados completamente aleatórios depois de desduplicar.

Bup e Obnam

Como você marcou a pergunta backup , se sua meta aqui é de apoio Para cima, considere o uso de um programa de backup de desduplicação como Bup ou Obnam .

    

Answer 3

No caso de um backup, possivelmente com um grande conjunto de arquivos menores, um truque que pode funcionar para você é classificar os arquivos no tar por extensão:

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

    

Answer 4

gzip não encontrará duplicatas, até xz com tamanho de dicionário enorme não. O que você pode fazer é usar mksquashfs - isso realmente economizará espaço de duplicatas.

Alguns resultados de testes rápidos com xz e mksquashfs com três arquivos binários aleatórios (64MB), dos quais dois são os mesmos:

Configuração:

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 5

No meu sistema lzma test.tar resulta em um arquivo test.tar.lzma de 106'3175 bytes (1.1M)

    

Answer 6

Como complemento à resposta do "caracol mecânico":

Mesmo xz (ou lzma) não encontrará duplicatas se o tamanho do arquivo único descompactado (ou, mais precisamente, a distância entre as duplicatas) exceder o tamanho do dicionário. xz (ou lzma) mesmo na configuração mais alta -9e apenas reserva 64MB para isso.

Felizmente, você pode especificar seu próprio tamanho de dicionário com a opção --lzma2=dict=256MB (somente --lzma1=dict=256MB é permitido ao usar o alias lzma no comando)

Infelizmente, ao substituir as configurações por cadeias de compactação personalizadas como as fornecidas no exemplo acima, os valores padrão para todos os outros parâmetros não são definidos para o mesmo nível de -9e. Portanto, a densidade de compactação não é tão alta para arquivos únicos.

    

Answer 7

O gzip sem opções de linha de comando usa o algoritmo mais baixo possível para compactação.

Tente usar:

gzip -9 test.tar

Você deve obter melhores resultados