Este artigo já é o segundo no tópico de compactação de dados de alta velocidade. O primeiro artigo descreveu um compressor operando a uma velocidade de 10 GB / s. por núcleo do processador (compactação mínima, RTT-Min).
Este compressor já foi introduzido no equipamento de duplicadores forenses para compactação de alta velocidade de despejos de mídia de armazenamento e, para aumentar a força da criptografia, também pode ser usado para compactar imagens de máquinas virtuais e trocar arquivos RAM enquanto os armazena em unidades SSD de alta velocidade.
O primeiro artigo também anunciou o desenvolvimento de um algoritmo de compactação para compactar backups de unidades de disco HDD e SSD (compactação média, RTT-Mid) com parâmetros de compactação de dados significativamente aprimorados. Até o momento, este compressor está completamente pronto e este artigo é sobre ele.
Um compressor que implementa o algoritmo RTT-Mid fornece uma taxa de compactação comparável aos arquivadores padrão, como WinRar, 7-Zip, operando no modo de alta velocidade. Além disso, sua velocidade é pelo menos uma ordem de magnitude maior.
A velocidade de empacotar / descompactar dados é um parâmetro crítico que determina o escopo das tecnologias de compactação. É improvável que alguém pense em compactar um terabyte de dados a uma velocidade de 10 a 15 megabytes por segundo (essa é a velocidade dos arquivadores no modo de compactação padrão), porque levará quase vinte horas para carregar completamente o processador ...
Por outro lado, o mesmo terabyte pode ser copiado em velocidades da ordem de 2-3 gigabytes por segundo por cerca de dez minutos.
Portanto, a compactação de informações de um grande volume é relevante se for executada a uma velocidade não inferior à velocidade da entrada / saída real. Para sistemas modernos, isso é pelo menos 100 megabytes por segundo.
Os compressores modernos só podem produzir essas velocidades no modo "rápido". É neste modo atual que compararemos o algoritmo RTT-Mid com os compressores tradicionais.
Teste comparativo do novo algoritmo de compactação
O compressor RTT-Mid funcionou como parte de um programa de teste. Em um aplicativo "funcional" real, ele funciona muito mais rapidamente, o multithreading é usado corretamente e um compilador "normal" é usado, não o C #.
Como os compressores utilizados no teste comparativo são construídos sobre princípios diferentes e diferentes tipos de dados são compactados de maneira diferente, para a objetividade do teste, usamos o método de medir a "temperatura média no hospital" ...
Foi criado um arquivo de despejo setor por setor de uma unidade lógica com o sistema operacional Windows 10; essa é a mistura mais natural de várias estruturas de dados realmente disponíveis em cada computador. A compactação deste arquivo permitirá comparar a velocidade e o grau de compactação do novo algoritmo com os compressores mais avançados usados nos arquivadores modernos.
Aqui está o arquivo de despejo:
O arquivo de despejo foi compactado por compressores WinRar PTT-Mid, 7 zip. O compressor WinRar e o 7-zip foram ajustados para a velocidade máxima.
Compressor de
7 zip funciona:
Carrega o processador 100%, enquanto a velocidade média de leitura do despejo original é de cerca de 60 megabytes / s.
O compressor
WinRar funciona:
A situação é semelhante, a carga do processador é quase 100%, a velocidade de leitura média do despejo é de cerca de 125 Megabytes / s.
Como no caso anterior, a velocidade do arquivador é limitada pelos recursos do processador.
O programa de teste do compressor
RTT-Mid agora funciona:
A captura de tela mostra que o processador está 50% carregado e fica ocioso o resto do tempo, porque não há onde baixar os dados compactados. O disco de carregamento de dados (Disco 0) é carregado quase completamente. A velocidade de leitura dos dados (disco 1) aumenta muito, mas em média mais de 200 megabytes / s.
A velocidade do compressor é limitada nesse caso pela capacidade de gravar dados compactados no Disco 0.
Agora, a taxa de compactação dos arquivos resultantes:
Pode-se observar que o compressor RTT-Mid lidou com a compressão melhor do que ninguém, o arquivo criado foi 1,3 Gigabytes menor que o arquivo WinRar e 2,1 Gigabytes menor que o arquivo 7z.
Tempo gasto na criação do arquivo:
- 7 zip - 26 minutos e 10 segundos;
- WinRar - 17 minutos e 40 segundos;
- RTT-Mid - 7 minutos e 30 segundos.
Assim, mesmo um programa de teste, não otimizado, usando o algoritmo RTT-Mid, conseguiu criar um arquivo duas vezes e meia mais rápido, enquanto o arquivo acabou sendo significativamente menor que o dos concorrentes ...
Quem não acredita nas capturas de tela pode verificar sua precisão por conta própria. O programa de teste está disponível
aqui , faça o download e verifique.
Mas apenas em processadores com suporte para AVX-2, sem o suporte dessas instruções, o compressor não funciona e não testa o algoritmo em processadores AMD mais antigos, eles são lentos em termos de execução de comandos AVX ...
Método de compressão usado
O algoritmo usa o método de indexação de fragmentos de texto repetidos na granulação de bytes. Esse método de compactação é conhecido há muito tempo, mas não foi usado, pois a operação de busca de resultados era muito cara em termos de recursos necessários e exigia muito mais tempo do que a construção de um dicionário. Portanto, o algoritmo RTT-Mid é um exemplo clássico do movimento "de volta ao futuro" ...
O compressor PTT usa um scanner de alta velocidade exclusivo para encontrar correspondências, foi ele quem permitiu acelerar o processo de compactação. Um scanner de fabricação própria, é "meu charme ...", "é um preço considerável, porque é totalmente artesanal" (escrito em montador).
O scanner de pesquisa de correspondências é baseado em um esquema probabilístico de dois níveis, a presença de um "sinal" de uma correspondência é examinada primeiro e somente depois que o "sinal" for detectado neste local é iniciado o procedimento para detectar uma correspondência real.
A janela de pesquisa de correspondências possui um tamanho imprevisível, dependendo do grau de entropia no bloco de dados que está sendo processado. Para dados completamente aleatórios (incompressíveis), ele possui um tamanho de megabytes; para dados com repetições, sempre tem um tamanho superior a um megabyte.
Porém, muitos formatos de dados modernos são incompressíveis e “acionar” um scanner com muitos recursos é inútil e inútil; portanto, o scanner usa dois modos de operação. Primeiro, são pesquisadas seções do texto de origem com possíveis repetições, esta operação também é realizada pelo método probabilístico e é executada muito rapidamente (a uma velocidade de 4-6 Gigabytes / s). Em seguida, as áreas com possíveis correspondências são processadas pelo scanner principal.
A compactação de índice não é muito eficiente, você deve substituir fragmentos repetidos por índices e a matriz de índices reduz significativamente a taxa de compactação.
Para aumentar a taxa de compactação, não apenas as correspondências completas das cadeias de bytes são indexadas, mas também as parciais quando houver bytes correspondentes e não correspondentes na cadeia. Para fazer isso, o campo de máscara de índice é incluído no formato de índice, que indica os bytes coincidentes de dois blocos. Para uma compressão ainda maior, a indexação é usada com a sobreposição de vários blocos parcialmente correspondentes no bloco atual.
Tudo isso permitiu obter uma taxa de compressão no compressor PTT-Mid, comparável aos compressores fabricados de acordo com o método do dicionário, mas trabalhando muito mais rapidamente.
A velocidade do novo algoritmo de compactação
Se o compressor trabalha com uso exclusivo do cache de memória (são necessários 4 megabytes por fluxo), a velocidade varia de 700 a 2000 megabytes / s. por núcleo do processador, dependendo do tipo de dados que está sendo compactado e pouco depende da frequência de operação do processador.
Com a implementação multithread do compressor, a escalabilidade efetiva é determinada pelo volume de memória cache do terceiro nível. Por exemplo, tendo 9 Megabytes de memória cache “on board”, não faz sentido executar mais de dois fluxos de compactação, a velocidade não aumentará com isso. Mas com um cache de 20 megabytes, você já pode executar cinco fluxos de compactação.
Além disso, a latência da RAM se torna um parâmetro essencial para determinar a velocidade do compressor. O algoritmo usa acessos aleatórios ao OP, alguns dos quais não entram na memória cache (cerca de 10%) e precisam ficar ociosos, aguardando dados do OP, o que reduz a velocidade do trabalho.
Afeta significativamente a velocidade do compressor e a operação do sistema de entrada / saída de dados. Solicitações ao OP de pedidos de dados de bloco de E / S da CPU, o que também reduz a taxa de compactação. Esse problema é significativo para laptops e desktops; para servidores, é menos significativo devido à unidade de controle de acesso mais avançada do barramento do sistema e da RAM multicanal.
Em qualquer parte do texto, o artigo se refere à compactação, a descompactação está além do escopo deste artigo, porque tudo está presente no chocolate. A descompressão é muito mais rápida e é limitada pela velocidade de E / S. Um núcleo físico em um thread fornece calmamente velocidades de descompressão no nível de 3-4 Gigabytes / s.
Isso ocorre devido à ausência de uma operação de busca de resultados durante o processo de descompactação, que "come" o processador principal e armazena em cache os recursos durante a compactação.
Armazenamento confiável de dados compactados
Como o nome de toda a classe de ferramentas de software que usam compressão de dados (arquivadores) implica, elas são projetadas para armazenamento de informações a longo prazo, não por anos, mas por séculos e milênios ...
Durante o armazenamento, a mídia de armazenamento perde alguns dados, aqui está um exemplo:
Esse meio de armazenamento "analógico" tem mil anos, alguns fragmentos foram perdidos, mas em geral as informações são "legíveis" ...
Nenhum dos fabricantes responsáveis de modernos sistemas de armazenamento digital e mídia digital fornece garantias de segurança completa dos dados por mais de 75 anos.
E isso é um problema, mas o problema é adiado, nossos descendentes o resolverão ...
Os sistemas de armazenamento de dados digitais podem perder dados não apenas após 75 anos, os erros de dados podem aparecer a qualquer momento, mesmo durante a gravação, eles tentam minimizar essas distorções usando redundância e corrigindo sistemas de correção de erros. Os sistemas de redundância e correção nem sempre podem restaurar as informações perdidas e, se forem restauradas, não há garantia de que a operação de recuperação esteja correta.
E esse também é um grande problema, mas não atrasado, mas o atual.
Os compressores modernos usados para arquivar dados digitais são construídos com base em várias modificações do método do dicionário e, para esses arquivos, a perda de uma informação será um evento fatal, há até um termo estabelecido para tal situação - um arquivo "quebrado" ...
A baixa confiabilidade do armazenamento de informações em arquivos com compactação de dicionário está associada à estrutura dos dados compactados. As informações nesse arquivo não contêm o texto de origem, os números de entradas no dicionário são armazenados lá, o próprio dicionário é modificado dinamicamente pelo texto atual compactável. Se um fragmento do arquivo for perdido ou distorcido, todas as entradas subsequentes do arquivo não poderão ser identificadas pelo conteúdo ou pelo tamanho das entradas no dicionário, porque não está claro a que corresponde o número da entrada do dicionário.
É impossível recuperar informações de um arquivo "quebrado".
O algoritmo RTT é baseado em um método mais confiável de armazenamento de dados compactados. Ele usa o método de índice de contabilidade para repetir fragmentos. Essa abordagem da compactação permite minimizar as consequências da distorção da informação no meio e, em muitos casos, corrigir automaticamente as distorções que surgem durante o armazenamento da informação.
Isso ocorre porque o arquivo morto no caso de compactação de índice contém dois campos:
- campo de texto de origem com seções repetidas removidas;
- campo de índice.
O campo de índice crítico para recuperação de dados não é grande em tamanho e pode ser duplicado para armazenamento confiável de dados. Portanto, mesmo que um fragmento do texto de origem ou da matriz de índice seja perdido, todas as outras informações serão restauradas sem problemas, como na figura do suporte de informações "analógico".
Deficiências do algoritmo
Vantagens não existem sem desvantagens. O método de compactação de índice não compacta sequências curtas repetitivas. Isso ocorre devido às limitações do método de índice. Os índices têm pelo menos 3 bytes e podem ter até 12 bytes. Se ocorrer uma repetição com um tamanho menor que o índice que a descreve, ela não será levada em consideração; no entanto, muitas vezes essas repetições são detectadas em um arquivo compactável.
O método tradicional de compactação de vocabulário compacta efetivamente várias repetições curtas e, portanto, atinge uma taxa de compactação mais alta que a compactação de índice. É verdade que isso é alcançado devido à alta carga de trabalho do processador central, para que o método de vocabulário comece a compactar os dados com mais eficiência do que o método de índice, ele deve reduzir a velocidade de processamento de dados para 10-20 megabytes por segundo em instalações de computação reais com carga total da CPU.
Essas velocidades baixas são inaceitáveis para sistemas modernos de armazenamento de dados e têm mais interesse "acadêmico" do que prático.
O grau de compactação de informações será significativamente aumentado na próxima modificação do algoritmo PTT (RTT-Max), que já está em desenvolvimento.
Então, como sempre, para continuar ...