☰

Como compactar arquivos serverais, grandes, de alta entropia, mas muito semelhantes?

tag-icon • tag-icon linux backup compression archiving
Como compactar arquivos serverais, grandes, de alta entropia, mas muito semelhantes?

Eu tenho vários arquivos grandes (como: maiores que qualquer dicionário, centenas de GB). Esses arquivos têm entropia muito alta e são muito mal compactados. No entanto, esses arquivos são (até onde eu sei) quase completamente idênticos. (E não realmente compactado)

Como caso de teste, tentei uma simulação em pequena escala:

dd if=/dev/urandom of=random count=1G

cat random random random > 3random

gz -1 < 3random > 3random.gz
xz -1 < 3random > 3random.xz

Acho que isso simula muito bem o empacotamento de um tar com meus arquivos. Não estou surpreso que nem gz nem xz possam compactar esses arquivos; na verdade, eles ficam um pouco maiores.

Existe uma maneira sensata de compactar esses arquivos? Isto é apenas para fins de arquivamento (offline), a descompactação não será feita com frequência.

Responder1

Vamos começar com um arquivo de 10 MB de dados pseudo-aleatórios e fazer duas cópias dele:

$ dd if=/dev/urandom of=f1 bs=1M count=10
$ cp f1 f2
$ cp f1 f3

Vamos alterar essas cópias para que sejam "quase completamente idênticas" (como você disse):

$   # Avoid typos and improve readability
$ alias random='od -t u4 -N 4 /dev/urandom |
  sed -n "1{s/^\S*\s//;s/\s/${fill}/g;p}"'
$ alias randomize='dd if=/dev/urandom bs=1 seek="$(
    echo "scale=0;$(random)$(random)$(random)$(random) % (1024*1024*10)" | bc -l
  )" count="$( echo "scale=0;$(random)$(random) % 512 + 1" |
    bc -l )" conv=notrunc'
$   # In files "f2" and "f3, replace 1 to 512Bytes of data with other
$   #+ pseudo-random data in a pseudo-random position. Do this 3
$   #+ times for each file
$ randomize of=f2
$ randomize of=f2
$ randomize of=f2
$ randomize of=f3
$ randomize of=f3
$ randomize of=f3

Agora podemos compactar os dados em cada arquivo para ver o que acontece:

$ xz -1 < f1 > f1.xz
$ xz -1 < f2 > f2.xz
$ xz -1 < f3 > f3.xz
$ ls -lh f{1..3}{,.xz}
-rw-rw-r-- 1 myuser mygroup 10M may 29 09:31 f1
-rw-rw-r-- 1 myuser mygroup 11M may 29 10:07 f1.xz
-rw-rw-r-- 1 myuser mygroup 10M may 29 10:00 f2
-rw-rw-r-- 1 myuser mygroup 11M may 29 10:07 f2.xz
-rw-rw-r-- 1 myuser mygroup 10M may 29 10:05 f3
-rw-rw-r-- 1 myuser mygroup 11M may 29 10:07 f3.xz

Podemos ver que isso realmente aumenta o tamanho dos dados. Agora vamos transformar os dados em dados hexadecimais legíveis por humanos (bem, mais ou menos) e compactar o resultado:

$ xxd f1 | tee f1.hex | xz -1 > f1.hex.xz
$ xxd f2 | tee f2.hex | xz -1 > f2.hex.xz
$ xxd f3 | tee f3.hex | xz -1 > f3.hex.xz
$ ls -lh f{1..3}.hex*
-rw-rw-r-- 1 myuser mygroup 42M may 29 10:03 f1.hex
-rw-rw-r-- 1 myuser mygroup 22M may 29 10:04 f1.hex.xz
-rw-rw-r-- 1 myuser mygroup 42M may 29 10:04 f2.hex
-rw-rw-r-- 1 myuser mygroup 22M may 29 10:07 f2.hex.xz
-rw-rw-r-- 1 myuser mygroup 42M may 29 10:05 f3.hex
-rw-rw-r-- 1 myuser mygroup 22M may 29 10:07 f3.hex.xz

Os dados ficaram muito grandes. Quatro vezes em hexadecimal, duas vezes se hexadecimal estiver compactado. Agora a parte divertida: vamos calcular a diferença entre o hexadecimal e comprimir isso:

$ diff f{1,2}.hex | tee f1-f2.diff | xz -1 > f1-f2.diff.xz
$ diff f{1,3}.hex | tee f1-f3.diff | xz -1 > f1-f3.diff.xz
$ ls -lh f1-*
-rw-rw-r-- 1 myuser mygroup 7,8K may 29 10:04 f1-f2.diff
-rw-rw-r-- 1 myuser mygroup 4,3K may 29 10:06 f1-f2.diff.xz
-rw-rw-r-- 1 myuser mygroup 2,6K may 29 10:06 f1-f3.diff
-rw-rw-r-- 1 myuser mygroup 1,7K may 29 10:06 f1-f3.diff.xz

E isso é adorável. Vamos resumir:

$   # All you need to save to disk is this
$ du -cb f1{,-*z}
10485760        f1
4400    f1-f2.diff.xz
1652    f1-f3.diff.xz
10491812        total
$   # This is what you would have had to store
$ du -cb f{1..3}
10485760        f1
10485760        f2
10485760        f3
31457280        total
$   # Compared to "f2"'s original size, this is the percentage
$   #+ of all the new information you need to store about it
$ echo 'scale=4; 4400 * 100 / 31457280' | bc -l
.0419
$   # Compared to "f3"'s original size, this is the percentage
$   #+ of all the new information you need to store about it
$ echo 'scale=4; 1652 * 100 / 10485760' | bc -l
.0157
$   # So, compared to the grand total, this is the percetage
$   #+ of information you need to store 
$ echo 'scale=2; 10491812 * 100 / 10485760' | bc -l
33.35

Quanto mais arquivos você tiver, melhor funcionará. Para fazer um teste de restauração dos dados das suas diferenças compactadas de "f2":

$ xz -d < f1-f2.diff.xz > f1-f2.diff.restored
$   # Assuming you haven't deleted "f1.diff":
$ patch -o f2.hex.restored f1.hex f1-f2.diff.restored
patching file f1.hex
$ diff f2.hex.restored f2.hex # No diffs will be found unless corrupted
$ xxd -r f2.hex.restored f2.restored # We get the completely restored file
$ diff -q f2 f2.restored # No diffs will be found unless corrupted

OBSERVAÇÕES

  • Você não precisa de alguns dos arquivos gerados aqui, como as versões compactadas dos arquivos originais e o hexadecimal compactado. Eu fiz isso apenas para deixar claro.
  • O sucesso deste método depende muito do significado de “quase completamente idêntico”. Você precisa fazer testes. Fiz alguns testes e isso funciona muito bem para muitos tipos de dados (ou seja, dumps de banco de dados e até imagens e vídeos editados). Na verdade, eu uso isso para alguns backups.
  • Um método mais sofisticado é usar librsync, mas funciona muito bem em muitas situações e funcionará perfeitamente em quase qualquer ambiente *nix sem a necessidade de instalação de novo software.
  • Por outro lado, isso pode exigir alguns scripts.
  • Não conheço nenhuma ferramenta que faça tudo isso.

Responder2

gzip funciona em blocos de 32 KB, então ajudaria apenas se os mesmos padrões estivessem em um intervalo de 32 KB (o que não é o seu caso). Para xz você poderia tentar passar um valor muito grande--tamanho do blocomas você precisa de muita memória extra (veja o--memlimitopções).

informação relacionada