Este artigo já é o segundo no tópico de compactação de dados em alta velocidade. O primeiro artigo descreveu um compressor operando a uma velocidade de 10 GB/seg. por núcleo do processador (compactação mínima, RTT-Min).
Este compressor já foi implementado em equipamentos de duplicadores forenses para compactação em alta velocidade de dumps de mídia de armazenamento e aumentando a força da criptografia; também pode ser usado para compactar imagens de máquinas virtuais e arquivos de troca de RAM ao salvá-los em alta velocidade Unidades SSD.
O primeiro artigo também anunciou o desenvolvimento de um algoritmo de compactação para compactação de cópias de backup de unidades de disco HDD e SSD (compressão média, RTT-Mid) com parâmetros de compactação de dados significativamente aprimorados. Neste momento este compressor está completamente pronto e este artigo é sobre isso.
Um compressor que implementa o algoritmo RTT-Mid fornece uma taxa de compactação comparável a arquivadores padrão como WinRar, 7-Zip, operando em modo de alta velocidade. Ao mesmo tempo, sua velocidade operacional é pelo menos uma ordem de grandeza maior.
A velocidade de empacotamento/descompactação de dados é um parâmetro crítico que determina o escopo de aplicação das tecnologias de compressão. É improvável que alguém pense em compactar um terabyte de dados a uma velocidade de 10 a 15 MegaBytes por segundo (essa é exatamente a velocidade dos arquivadores no modo de compactação padrão), porque levaria quase vinte horas com carga total do processador.. .
Por outro lado, o mesmo terabyte pode ser copiado a velocidades da ordem de 2-3Gigabytes por segundo em cerca de dez minutos.
Portanto, a compressão de informações de grande volume é importante se for realizada a uma velocidade não inferior à velocidade real de entrada/saída. Para sistemas modernos, isso representa pelo menos 100 Megabytes por segundo.
Os compressores modernos podem produzir tais velocidades apenas no modo “rápido”. É neste modo atual que compararemos o algoritmo RTT-Mid com compressores tradicionais.
Teste comparativo de um novo algoritmo de compressão
O compressor RTT-Mid funcionou como parte do programa de testes. Em um aplicativo real “funcional”, ele funciona muito mais rápido, usa multithreading com sabedoria e usa um compilador “normal”, não C#.
Como os compressores utilizados no teste comparativo são construídos com base em princípios diferentes e diferentes tipos de compressão de dados de forma diferente, para a objetividade do teste, foi utilizado o método de medição da “temperatura média no hospital”...
Foi criado um arquivo de despejo setor por setor de um disco lógico com o sistema operacional Windows 10; esta é 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 em arquivadores modernos.
Aqui está o arquivo de despejo:
O arquivo de despejo foi compactado usando compressores PTT-Mid, 7-zip e WinRar. O compressor WinRar e 7-zip foram configurados para velocidade máxima.
Compressor funcionando 7-zip:
Ele carrega o processador em 100%, enquanto a velocidade média de leitura do dump original é de cerca de 60 MegaBytes/seg.
Compressor funcionando WinRAR:
A situação é semelhante, a carga do processador é de quase 100%, a velocidade média de leitura de dump é de cerca de 125 Megabytes/seg.
Como no caso anterior, a velocidade do arquivador é limitada pelas capacidades do processador.
O programa de teste do compressor está em execução RTT-médio:
A captura de tela mostra que o processador está carregado em 50% e fica ocioso no resto do tempo, porque não há lugar para fazer upload dos dados compactados. O disco de upload de dados (Disco 0) está quase totalmente carregado. A velocidade de leitura de dados (Disco 1) varia muito, mas em média mais de 200 MegaBytes/seg.
A velocidade do compressor é limitada neste 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 fez o melhor trabalho de compactação; o arquivo criado era 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, foi capaz de criar um arquivo mais de duas vezes e meia mais rápido, enquanto o arquivo acabou sendo significativamente menor que o de seus concorrentes...
Aqueles que não acreditam nas capturas de tela podem verificar eles próprios sua autenticidade. O programa de testes está disponível em , baixe e verifique.
Mas apenas em processadores com suporte AVX-2, sem suporte para essas instruções o compressor não funciona, e não teste o algoritmo em processadores AMD mais antigos, eles são lentos em termos de execução de instruções AVX...
Método de compressão usado
O algoritmo usa um método para indexar fragmentos de texto repetidos em granularidade de bytes. Este método de compressão é conhecido há muito tempo, mas não foi utilizado porque a operação de correspondência era muito cara em termos de recursos necessários e exigia muito mais tempo do que construir um dicionário. Portanto, o algoritmo RTT-Mid é um exemplo clássico de movimento “de volta ao futuro”...
O compressor PTT usa um scanner exclusivo de busca de correspondência de alta velocidade, que nos permite acelerar o processo de compactação. Um scanner feito por mim mesmo, esse é “meu charme...”, “é bem caro, porque é totalmente feito à mão” (escrito em assembler).
O scanner de busca de correspondência é feito de acordo com um esquema probabilístico de dois níveis: primeiro, é verificada a presença de um “sinal” de uma correspondência, e somente após a identificação do “sinal” neste local, o procedimento para detectar uma correspondência real começou.
A janela de busca de correspondência tem um tamanho imprevisível, dependendo do grau de entropia no bloco de dados processado. Para dados completamente aleatórios (incompressíveis) tem tamanho de megabytes, para dados com repetições é sempre maior que um megabyte.
Mas muitos formatos de dados modernos são incompressíveis e executar um scanner que consome muitos recursos através deles é inútil e um desperdício, portanto, o scanner usa dois modos de operação. Primeiramente, são pesquisadas seções do texto fonte com possíveis repetições; esta operação também é realizada através de um método probabilístico e é realizada muito rapidamente (a uma velocidade de 4-6 GigaBytes/seg). As áreas com possíveis correspondências são então processadas pelo scanner principal.
A compactação de índice não é muito eficiente, você precisa substituir fragmentos duplicados por índices e a matriz de índice 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 a cadeia contém bytes correspondentes e não correspondentes. Para fazer isso, o formato do índice inclui um campo de máscara de correspondência que indica os bytes correspondentes de dois blocos. Para uma compactação ainda maior, a indexação é usada para sobrepor vários blocos parcialmente correspondentes ao bloco atual.
Tudo isso permitiu obter no compressor PTT-Mid uma taxa de compressão comparável aos compressores feitos pelo método de dicionário, mas trabalhando muito mais rápido.
Velocidade do novo algoritmo de compressão
Se o compressor operar com uso exclusivo de memória cache (são necessários 4 Megabytes por thread), então a velocidade operacional varia de 700-2000 Megabytes/s. por núcleo do processador, dependendo do tipo de dados que estão sendo compactados e depende pouco da frequência operacional do processador.
Com uma implementação multithread do compressor, a escalabilidade efetiva é determinada pelo tamanho do cache de terceiro nível. Por exemplo, tendo 9 MegaBytes de memória cache “on board”, não faz sentido lançar mais de dois threads de compressão, a velocidade não aumentará com isso. Mas com um cache de 20 Megabytes, você já pode executar cinco threads de compactação.
Além disso, a latência da RAM torna-se um parâmetro importante que determina a velocidade do compressor. O algoritmo utiliza acesso aleatório ao OP, alguns dos quais não entram na memória cache (cerca de 10%) e fica ocioso, aguardando dados do OP, o que reduz a velocidade de operação.
Afeta significativamente a velocidade do compressor e a operação do sistema de entrada/saída de dados. Solicitações ao OP de E/S bloqueiam solicitações de dados da CPU, o que também reduz a velocidade de compactação. Esse problema é significativo para laptops e desktops; para servidores é menos significativo devido a uma unidade de controle de acesso ao barramento de sistema mais avançada e à RAM multicanal.
Ao longo do texto do artigo falamos sobre compressão; a descompressão fica fora do escopo deste artigo já que “está tudo coberto de chocolate”. A descompressão é muito mais rápida e limitada pela velocidade de E/S. Um núcleo físico em um thread fornece facilmente velocidades de descompactação de 3 a 4 GB/s.
Isso se deve à ausência de uma operação de busca de correspondência durante o processo de descompactação, que “consome” os principais recursos do processador e da memória cache durante a compactação.
Confiabilidade do armazenamento de dados compactados
Como sugere o nome de toda a classe de software que utiliza compressão de dados (arquivadores), eles são projetados 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:
Este suporte de informação “analógico” tem mil anos, alguns fragmentos foram perdidos, mas em geral a informação é “legível”...
Nenhum dos fabricantes responsáveis de sistemas modernos de armazenamento de dados digitais e mídia digital para eles oferece garantias de segurança total de dados por mais de 75 anos.
E isso é um problema, mas um problema adiado, nossos descendentes vão resolver...
Os sistemas de armazenamento digital de dados podem perder dados não só após 75 anos, erros nos dados podem aparecer a qualquer momento, mesmo durante a sua gravação, eles tentam minimizar essas distorções usando redundância e corrigindo-as com sistemas de correção de erros. Os sistemas de redundância e correção nem sempre podem restaurar informações perdidas e, se o fizerem, não há garantia de que a operação de restauração tenha sido concluída corretamente.
E este também é um grande problema, mas não um problema diferido, mas atual.
Os compressores modernos usados para arquivar dados digitais são construídos sobre diversas modificações do método de dicionário, e para tais arquivos a perda de uma informação será um evento fatal; existe até um termo estabelecido para tal situação - um arquivo “quebrado”. ...
A baixa confiabilidade de 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 fonte, os números das entradas no dicionário são armazenados lá e o próprio dicionário é modificado dinamicamente pelo texto compactado atual. Se um fragmento de arquivo for perdido ou corrompido, todas as entradas subsequentes do arquivo não poderão ser identificadas nem pelo conteúdo nem pelo comprimento da entrada no dicionário, uma vez que não está claro a que corresponde o número da entrada do dicionário.
É impossível restaurar informações de um arquivo tão “quebrado”.
O algoritmo RTT é baseado em um método mais confiável de armazenamento de dados compactados. Ele usa o método de índice para contabilizar fragmentos repetidos. Essa abordagem de compactação permite minimizar as consequências da distorção das informações no meio de armazenamento e, em muitos casos, corrigir automaticamente as distorções que surgiram durante o armazenamento das informações.
Isso se deve ao fato de que o arquivo, no caso de compactação de índice, contém dois campos:
- um campo de texto fonte com seções repetidas removidas;
- campo de índice.
O campo de índice, que é crítico para a recuperação de informações, não é grande e pode ser duplicado para armazenamento confiável de dados. Portanto, mesmo que um fragmento do texto fonte ou matriz de índice seja perdido, todas as outras informações serão restauradas sem problemas, como na imagem com um meio de armazenamento “analógico”.
Desvantagens do algoritmo
Não existem vantagens sem desvantagens. O método de compactação de índice não compacta sequências curtas e repetidas. Isto se deve às limitações do método de índice. Os índices têm pelo menos 3 bytes de tamanho e podem ter até 12 bytes. Se for encontrada uma repetição com tamanho menor que o índice que a descreve, ela não será levada em consideração, independentemente da frequência com que tais repetições sejam detectadas no arquivo compactado.
O método tradicional de compactação de dicionário comprime efetivamente múltiplas repetições de curta duração e, portanto, atinge uma taxa de compactação mais alta do que a compactação de índice. É verdade que isso é conseguido devido à alta carga no processador central; para que o método de dicionário comece a compactar dados com mais eficiência do que o método de índice, ele precisa reduzir a velocidade de processamento de dados para 10-20 megabytes por segundo em tempo real. instalações de computação com carga total da CPU.
Essas velocidades baixas são inaceitáveis para sistemas modernos de armazenamento de dados e são de interesse mais “acadêmico” do que prático.
O grau de compressão da informação será aumentado significativamente na próxima modificação do algoritmo RTT (RTT-Max), que já está em desenvolvimento.
Então, como sempre, continua...
Fonte: habr.com