Este artigo xa é o segundo no tema da compresión de datos de alta velocidade. O primeiro artigo describía un compresor que funcionaba a unha velocidade de 10 GB/s. por núcleo de procesador (compresión mínima, RTT-Min).
Este compresor xa se implantou nos equipos de duplicadores forenses para a compresión a alta velocidade de vertedoiros de medios de almacenamento e para mellorar a forza da criptografía; tamén se pode usar para comprimir imaxes de máquinas virtuais e ficheiros de intercambio de RAM ao gardalos en alta velocidade. Unidades SSD.
O primeiro artigo tamén anunciou o desenvolvemento dun algoritmo de compresión para comprimir copias de seguridade das unidades de disco duro e SSD (compresión media, RTT-Mid) con parámetros de compresión de datos significativamente mellorados. Neste momento, este compresor está completamente listo e este artigo trata sobre el.
Un compresor que implementa o algoritmo RTT-Mid proporciona unha relación de compresión comparable aos arquivadores estándar como WinRar, 7-Zip, que operan en modo de alta velocidade. Ao mesmo tempo, a súa velocidade de funcionamento é polo menos unha orde de magnitude superior.
A velocidade de empaquetado/descompresión de datos é un parámetro crítico que determina o ámbito de aplicación das tecnoloxías de compresión. É pouco probable que a alguén se lle ocorre comprimir un terabyte de datos a unha velocidade de 10-15 megabytes por segundo (esta é exactamente a velocidade dos arquivadores no modo de compresión estándar), porque levaría case vinte horas cunha carga completa do procesador. .
Por outra banda, o mesmo terabyte pódese copiar a velocidades da orde de 2-3 Gigabytes por segundo nuns dez minutos.
Polo tanto, a compresión de información de gran volume é importante se se realiza a unha velocidade non inferior á velocidade de entrada/saída real. Para os sistemas modernos, isto é polo menos 100 Megabytes por segundo.
Os compresores modernos poden producir tales velocidades só en modo "rápido". Neste modo actual compararemos o algoritmo RTT-Mid cos compresores tradicionais.
Proba comparativa dun novo algoritmo de compresión
O compresor RTT-Mid funcionou como parte do programa de proba. Nunha aplicación "funcionante" real funciona moito máis rápido, usa o multithreading con prudencia e usa un compilador "normal", non C#.
Dado que os compresores utilizados na proba comparativa están construídos sobre diferentes principios e diferentes tipos de datos comprimen de forma diferente, para a obxectividade da proba, utilizouse o método de medición da "temperatura media no hospital"...
Creouse un ficheiro de volcado sector por sector dun disco lóxico co sistema operativo Windows 10; esta é a mestura máis natural de varias estruturas de datos dispoñibles en cada ordenador. A compresión deste ficheiro permitirache comparar a velocidade e o grao de compresión do novo algoritmo cos compresores máis avanzados empregados nos arquivadores modernos.
Aquí está o ficheiro de volcado:
O ficheiro de volcado comprimiuse mediante compresores PTT-Mid, 7-zip e WinRar. O WinRar e o compresor de 7 zip foron configurados á velocidade máxima.
Compresor en marcha 7-zip:
Carga o procesador ao 100%, mentres que a velocidade media de lectura do volcado orixinal é duns 60 MegaBytes/seg.
Compresor en marcha Winrar:
A situación é similar, a carga do procesador é case do 100%, a velocidade media de lectura de descarga é duns 125 Megabytes/seg.
Como no caso anterior, a velocidade do arquivador está limitada polas capacidades do procesador.
O programa de proba do compresor está a executarse RTT-Medio:
A captura de pantalla mostra que o procesador está cargado ao 50% e está inactivo o resto do tempo, porque non hai onde cargar os datos comprimidos. O disco de carga de datos (disco 0) está case totalmente cargado. A velocidade de lectura de datos (disco 1) varía moito, pero de media máis de 200 megabytes/seg.
Neste caso, a velocidade do compresor está limitada pola capacidade de escribir datos comprimidos no disco 0.
Agora a relación de compresión dos arquivos resultantes:
Pódese ver que o compresor RTT-Mid fixo o mellor traballo de compresión; o arquivo que creou era 1,3 GigaBytes máis pequeno que o WinRar e 2,1 GigaBytes máis pequeno que o 7z.
Tempo dedicado á creación do arquivo:
- 7-zip - 26 minutos 10 segundos;
- WinRar - 17 minutos 40 segundos;
- RTT-Mid: 7 minutos e 30 segundos.
Así, mesmo un programa de proba non optimizado, utilizando o algoritmo RTT-Mid, foi capaz de crear un arquivo máis de dúas veces e media máis rápido, mentres que o arquivo resultou ser significativamente máis pequeno que o dos seus competidores...
Aqueles que non crean as capturas de pantalla poden comprobar eles mesmos a súa autenticidade. O programa de proba está dispoñible en , descarga e verifica.
Pero só nos procesadores con compatibilidade con AVX-2, sen soporte para estas instrucións o compresor non funciona e non proba o algoritmo en procesadores AMD máis antigos, son lentos en canto a executar instrucións AVX...
Método de compresión utilizado
O algoritmo usa un método para indexar fragmentos de texto repetidos en granularidade de bytes. Este método de compresión coñécese desde hai moito tempo, pero non se utilizou porque a operación de emparellamento era moi cara en canto aos recursos necesarios e requiría moito máis tempo que construír un dicionario. Polo tanto, o algoritmo RTT-Mid é un exemplo clásico de "volver ao futuro"...
O compresor PTT utiliza un único escáner de busca de coincidencias de alta velocidade, que nos permite acelerar o proceso de compresión. Un escáner feito por si mesmo, este é "o meu encanto...", "é bastante caro, porque está totalmente feito a man" (escrito en ensamblador).
O escáner de busca de coincidencias realízase segundo un esquema probabilístico de dous niveis: primeiro, escanease a presenza dun "sinal" dunha coincidencia e só despois de que o "sinal" se identifique neste lugar, o procedemento para detectar unha coincidencia real. comeza.
A xanela de busca de coincidencias ten un tamaño imprevisible, dependendo do grao de entropía do bloque de datos procesado. Para datos completamente aleatorios (incompresibles) ten un tamaño de megabytes, para datos con repeticións sempre é maior que un megabyte.
Pero moitos formatos de datos modernos son incompresibles e executar un escáner de recursos intensivos a través deles é inútil e un despilfarro, polo que o escáner usa dous modos de funcionamento. En primeiro lugar, búscanse seccións do texto fonte con posibles repeticións; esta operación tamén se realiza mediante un método probabilístico e realízase moi rapidamente (a unha velocidade de 4-6 GigaBytes/seg). As áreas con posibles coincidencias son entón procesadas polo escáner principal.
A compresión do índice non é moi eficiente, tes que substituír os fragmentos duplicados por índices e a matriz de índices reduce significativamente a relación de compresión.
Para aumentar a relación de compresión, non só se indexan as coincidencias completas das cadeas de bytes, senón tamén as parciais, cando a cadea contén bytes coincidentes e non coincidentes. Para iso, o formato de índice inclúe un campo de máscara de coincidencia que indica os bytes coincidentes de dous bloques. Para unha compresión aínda maior, a indexación úsase para superpoñer varios bloques parcialmente coincidentes ao bloque actual.
Todo isto permitiu obter no compresor PTT-Mid unha relación de compresión comparable aos compresores feitos co método do dicionario, pero traballando moito máis rápido.
Velocidade do novo algoritmo de compresión
Se o compresor funciona co uso exclusivo da memoria caché (requírense 4 megabytes por fío), entón a velocidade de funcionamento oscila entre 700 e 2000 megabytes/seg. por núcleo do procesador, dependendo do tipo de datos que se comprimen e depende pouco da frecuencia de funcionamento do procesador.
Cunha implementación multiproceso do compresor, a escalabilidade efectiva está determinada polo tamaño da caché de terceiro nivel. Por exemplo, tendo 9 megabytes de memoria caché "a bordo", non ten sentido lanzar máis de dous fíos de compresión; a velocidade non aumentará. Pero cunha caché de 20 Megabytes, xa pode executar cinco fíos de compresión.
Ademais, a latencia da memoria RAM convértese nun parámetro importante que determina a velocidade do compresor. O algoritmo utiliza un acceso aleatorio ao OP, algúns dos cales non entran na memoria caché (un 10%) e ten que estar inactivo, esperando os datos do OP, o que reduce a velocidade de operación.
Afecta significativamente a velocidade do compresor e o funcionamento do sistema de entrada/saída de datos. Solicitudes ao OP do bloque de E/S solicitudes de datos da CPU, o que tamén reduce a velocidade de compresión. Este problema é significativo para portátiles e escritorios; para os servidores é menos significativo debido a unha unidade de control de acceso ao bus do sistema máis avanzada e a memoria RAM multicanle.
Ao longo do texto do artigo falamos de compresión; a descompresión queda fóra do ámbito deste artigo xa que "todo está cuberto de chocolate". A descompresión é moito máis rápida e está limitada pola velocidade de E/S. Un núcleo físico nun fío proporciona facilmente velocidades de desempaquetado de 3-4 GB/s.
Isto débese á ausencia dunha operación de busca de coincidencias durante o proceso de descompresión, que "come" os principais recursos do procesador e da memoria caché durante a compresión.
Fiabilidade do almacenamento de datos comprimidos
Como suxire o nome de toda a clase de software que usa compresión de datos (arquivadores), están deseñados para almacenar información a longo prazo, non durante anos, senón durante séculos e milenios...
Durante o almacenamento, os medios de almacenamento perden algúns datos, aquí tes un exemplo:
Este soporte de información "analóxico" ten mil anos de antigüidade, perdéronse algúns fragmentos, pero en xeral a información é "lexible"...
Ningún dos fabricantes responsables dos modernos sistemas de almacenamento de datos dixitais e medios dixitais para eles ofrece garantías de seguridade completa dos datos durante máis de 75 anos.
E isto é un problema, pero un problema adiado, os nosos descendentes resolverano...
Os sistemas de almacenamento de datos dixitais poden perder datos non só despois de 75 anos, os erros nos datos poden aparecer en calquera momento, mesmo durante a súa gravación, intentan minimizar estas distorsións mediante a redundancia e corrixilas con sistemas de corrección de erros. Os sistemas de redundancia e corrección non sempre poden restaurar a información perdida e, se o fan, non hai garantía de que a operación de restauración se realizou correctamente.
E este tamén é un gran problema, pero non diferido, senón actual.
Os compresores modernos utilizados para arquivar datos dixitais baséanse en varias modificacións do método do dicionario, e para tales arquivos a perda dunha información será un evento fatal; incluso hai un termo establecido para tal situación: un arquivo "roto" ...
A baixa fiabilidade de almacenar información en arquivos con compresión de dicionario está asociada á estrutura dos datos comprimidos. A información deste arquivo non contén o texto de orixe, alí gárdanse o número de entradas do dicionario e o propio dicionario é modificado dinámicamente polo texto comprimido actual. Se un fragmento de arquivo se perde ou está corrompido, todas as entradas de arquivo posteriores non se poden identificar nin polo contido nin pola lonxitude da entrada no dicionario, xa que non está claro a que corresponde o número de entrada do dicionario.
É imposible restaurar a información dun arquivo "roto".
O algoritmo RTT baséase nun método máis fiable de almacenar datos comprimidos. Usa o método de índice para contabilizar fragmentos repetitivos. Este enfoque da compresión permítenos minimizar as consecuencias da distorsión da información no soporte de almacenamento e, en moitos casos, corrixir automaticamente as distorsións que se producen durante o almacenamento da información.
Isto débese a que o ficheiro de arquivo no caso de compresión de índice contén dous campos:
- un campo de texto fonte con seccións repetidas eliminadas del;
- campo índice.
O campo de índice, que é fundamental para a recuperación da información, non é de gran tamaño e pódese duplicar para almacenar datos fiables. Polo tanto, aínda que se perda un fragmento do texto de orixe ou da matriz de índices, toda a outra información restaurarase sen problemas, como na imaxe cun medio de almacenamento "analóxico".
Desvantaxes do algoritmo
Non hai vantaxes sen inconvenientes. O método de compresión do índice non comprime secuencias repetidas curtas. Isto débese ás limitacións do método de índice. Os índices teñen polo menos 3 bytes de tamaño e poden ter ata 12 bytes. Se se atopa unha repetición cun tamaño menor que o índice que a describe, non se ten en conta, por moito que se detecten tales repeticións no ficheiro comprimido.
O método tradicional de compresión do dicionario comprime eficazmente varias repeticións de curta duración e, polo tanto, consegue unha relación de compresión máis alta que a compresión do índice. É certo que isto conséguese debido á alta carga do procesador central; para que o método de dicionario comece a comprimir os datos de forma máis eficiente que o método de índice, ten que reducir a velocidade de procesamento de datos a 10-20 megabytes por segundo no real. instalacións informáticas con carga completa de CPU.
Velocidades tan baixas son inaceptables para os sistemas de almacenamento de datos modernos e teñen un interese máis "académico" que práctico.
O grao de compresión da información incrementarase significativamente na próxima modificación do algoritmo RTT (RTT-Max), que xa está en desenvolvemento.
Así que, coma sempre, a seguir...
Fonte: www.habr.com