Este artículo ya es el segundo sobre el tema de la compresión de datos de alta velocidad. El primer artículo describía un compresor que funcionaba a una velocidad de 10 GB/seg. por núcleo de procesador (compresión mínima, RTT-Min).
Este compresor ya se ha implementado en los equipos de duplicadores forenses para la compresión de alta velocidad de volcados de medios de almacenamiento y mejorar la solidez de la criptografía; también se puede utilizar para comprimir imágenes de máquinas virtuales y archivos de intercambio de RAM al guardarlos en alta velocidad. Unidades SSD.
El primer artículo también anunció el desarrollo de un algoritmo de compresión para comprimir copias de seguridad de unidades de disco HDD y SSD (compresión media, RTT-Mid) con parámetros de compresión de datos significativamente mejorados. A estas alturas, este compresor está completamente listo y este artículo trata sobre ello.
Un compresor que implementa el algoritmo RTT-Mid proporciona una relación de compresión comparable a los archivadores estándar como WinRar, 7-Zip, que funcionan en modo de alta velocidad. Al mismo tiempo, su velocidad de funcionamiento es al menos un orden de magnitud mayor.
La velocidad de empaquetado/desempaquetado de datos es un parámetro crítico que determina el ámbito de aplicación de las tecnologías de compresión. Es poco probable que a alguien se le ocurra comprimir un terabyte de datos a una velocidad de 10 a 15 megabytes por segundo (esta es exactamente la velocidad de los archivadores en el modo de compresión estándar), porque con una carga completa del procesador se necesitarían casi veinte horas. .
Por otro lado, el mismo terabyte se puede copiar a velocidades del orden de 2 a 3 Gigabytes por segundo en unos diez minutos.
Por lo tanto, la compresión de información de gran volumen es importante si se realiza a una velocidad no inferior a la velocidad de entrada/salida real. Para los sistemas modernos esto es al menos 100 megabytes por segundo.
Los compresores modernos pueden producir tales velocidades sólo en modo "rápido". Es en este modo actual que compararemos el algoritmo RTT-Mid con los compresores tradicionales.
Prueba comparativa de un nuevo algoritmo de compresión.
El compresor RTT-Mid funcionó como parte del programa de prueba. En una aplicación real que "funciona", funciona mucho más rápido, utiliza multiproceso sabiamente y utiliza un compilador "normal", no C#.
Dado que los compresores utilizados en la prueba comparativa se basan en diferentes principios y diferentes tipos de datos se comprimen de manera diferente, para la objetividad de la prueba, se utilizó el método de medir la "temperatura promedio en el hospital"...
Se creó un archivo de volcado sector por sector de un disco lógico con el sistema operativo Windows 10; esta es la mezcla más natural de varias estructuras de datos disponibles en cada computadora. Comprimir este archivo le permitirá comparar la velocidad y el grado de compresión del nuevo algoritmo con los compresores más avanzados utilizados en los archivadores modernos.
Aquí está el archivo de volcado:
El archivo de volcado se comprimió utilizando compresores PTT-Mid, 7-zip y WinRar. El WinRar y el compresor 7-zip se configuraron a la velocidad máxima.
Compresor funcionando 7-zip:
Carga el procesador al 100%, mientras que la velocidad media de lectura del volcado original es de unos 60 MegaBytes/seg.
Compresor funcionando WinRAR:
La situación es similar, la carga del procesador es casi del 100%, la velocidad media de lectura del volcado es de unos 125 Megabytes/seg.
Como en el caso anterior, la velocidad del archivador está limitada por las capacidades del procesador.
El programa de prueba del compresor ahora se está ejecutando. RTT-medio:
La captura de pantalla muestra que el procesador está cargado al 50% y está inactivo el resto del tiempo, porque no hay ningún lugar donde cargar los datos comprimidos. El disco de carga de datos (Disco 0) está casi completamente cargado. La velocidad de lectura de datos (Disco 1) varía mucho, pero en promedio supera los 200 MegaBytes/seg.
La velocidad del compresor está limitada en este caso por la capacidad de escribir datos comprimidos en el Disco 0.
Ahora la relación de compresión de los archivos resultantes:
Se puede ver que el compresor RTT-Mid hizo el mejor trabajo de compresión; el archivo que creó fue 1,3 GigaBytes más pequeño que el archivo WinRar y 2,1 GigaBytes más pequeño que el archivo 7z.
Tiempo dedicado a crear el archivo:
- 7-zip – 26 minutos 10 segundos;
- WinRar – 17 minutos 40 segundos;
- RTT-Medio: 7 minutos 30 segundos.
Así, incluso un programa de prueba no optimizado, utilizando el algoritmo RTT-Mid, pudo crear un archivo más de dos veces y media más rápido, mientras que el archivo resultó ser significativamente más pequeño que el de sus competidores...
Aquellos que no crean en las capturas de pantalla pueden comprobar su autenticidad ellos mismos. El programa de prueba está disponible en , descargar y comprobar.
Pero sólo en procesadores con soporte AVX-2, sin soporte para estas instrucciones el compresor no funciona, y no pruebe el algoritmo en procesadores AMD más antiguos, son lentos en cuanto a ejecutar instrucciones AVX...
Método de compresión utilizado
El algoritmo utiliza un método para indexar fragmentos de texto repetidos en granularidad de bytes. Este método de compresión se conoce desde hace mucho tiempo, pero no se utilizó porque la operación de comparación era muy costosa en términos de recursos necesarios y requería mucho más tiempo que construir un diccionario. Así que el algoritmo RTT-Mid es un ejemplo clásico de “regreso al futuro”...
El compresor PTT utiliza un exclusivo escáner de búsqueda de coincidencias de alta velocidad, que nos permite acelerar el proceso de compresión. Un escáner hecho a sí mismo, este es “mi encanto…”, “es bastante caro, porque está completamente hecho a mano” (escrito en ensamblador).
El escáner de búsqueda de coincidencias se realiza de acuerdo con un esquema probabilístico de dos niveles: primero, se escanea la presencia de un "signo" de una coincidencia, y solo después de que se identifica el "signo" en este lugar, se inicia el procedimiento para detectar una coincidencia real. Está empezado.
La ventana de búsqueda de coincidencias tiene un tamaño impredecible, dependiendo del grado de entropía en el bloque de datos procesado. Para datos completamente aleatorios (incompresibles) tiene un tamaño de megabytes, para datos con repeticiones siempre es mayor que un megabyte.
Pero muchos formatos de datos modernos son incompresibles y ejecutar un escáner que consume muchos recursos a través de ellos es inútil y un desperdicio, por lo que el escáner utiliza dos modos de funcionamiento. En primer lugar, se buscan secciones del texto fuente con posibles repeticiones; esta operación también se realiza mediante un método probabilístico y se realiza muy rápidamente (a una velocidad de 4-6 GigaBytes/seg). A continuación, el escáner principal procesa las áreas con posibles coincidencias.
La compresión de índices no es muy eficiente, es necesario reemplazar fragmentos duplicados con índices y la matriz de índices reduce significativamente la relación de compresión.
Para aumentar la relación de compresión, no solo se indexan las coincidencias completas de cadenas de bytes, sino también las parciales, cuando la cadena contiene bytes coincidentes y no coincidentes. Para hacer esto, el formato de índice incluye un campo de máscara de coincidencia que indica los bytes coincidentes de dos bloques. Para una compresión aún mayor, la indexación se utiliza para superponer varios bloques parcialmente coincidentes al bloque actual.
Todo esto hizo posible obtener en el compresor PTT-Mid una relación de compresión comparable a la de los compresores fabricados con el método del diccionario, pero funcionando mucho más rápido.
Velocidad del nuevo algoritmo de compresión
Si el compresor funciona con uso exclusivo de memoria caché (se requieren 4 megabytes por subproceso), entonces la velocidad de funcionamiento oscila entre 700 y 2000 megabytes/seg. por núcleo de procesador, dependiendo del tipo de datos que se comprimen y depende poco de la frecuencia de funcionamiento del procesador.
Con una implementación multiproceso del compresor, la escalabilidad efectiva está determinada por el tamaño de la caché de tercer nivel. Por ejemplo, al tener 9 megabytes de memoria caché "a bordo", no tiene sentido ejecutar más de dos subprocesos de compresión; la velocidad no aumentará con esto. Pero con una caché de 20 Megabytes, ya puedes ejecutar cinco subprocesos de compresión.
Además, la latencia de la RAM se convierte en un parámetro importante que determina la velocidad del compresor. El algoritmo utiliza acceso aleatorio al OP, parte del cual no ingresa a la memoria caché (alrededor del 10%) y tiene que permanecer inactivo, esperando datos del OP, lo que reduce la velocidad de operación.
Afecta significativamente la velocidad del compresor y el funcionamiento del sistema de entrada/salida de datos. Las solicitudes al OP desde E/S bloquean las solicitudes de datos de la CPU, lo que también reduce la velocidad de compresión. Este problema es importante para las computadoras portátiles y de escritorio; para los servidores es menos significativo debido a una unidad de control de acceso al bus del sistema más avanzada y una RAM multicanal.
A lo largo del texto del artículo hablamos de compresión, la descompresión queda fuera del alcance de este artículo ya que “está todo cubierto de chocolate”. La descompresión es mucho más rápida y está limitada por la velocidad de E/S. Un núcleo físico en un subproceso proporciona fácilmente velocidades de descompresión de 3 a 4 GB/seg.
Esto se debe a la ausencia de una operación de búsqueda de coincidencias durante el proceso de descompresión, que "consume" los principales recursos del procesador y la memoria caché durante la compresión.
Fiabilidad del almacenamiento de datos comprimidos
Como sugiere el nombre de toda la clase de software que utiliza compresión de datos (archivadores), están diseñados para el almacenamiento de información a largo plazo, no durante años, sino durante siglos y milenios...
Durante el almacenamiento, los medios de almacenamiento pierden algunos datos; aquí hay un ejemplo:
Este soporte de información “analógico” tiene mil años, se han perdido algunos fragmentos, pero en general la información es “legible”...
Ninguno de los fabricantes responsables de sistemas modernos de almacenamiento de datos digitales y medios digitales para ellos ofrece garantías de seguridad total de los datos durante más de 75 años.
Y esto es un problema, pero un problema pospuesto, nuestros descendientes lo solucionarán...
Los sistemas de almacenamiento de datos digitales pueden perder datos no solo después de 75 años, los errores en los datos pueden aparecer en cualquier momento, incluso durante su registro, intentan minimizar estas distorsiones utilizando redundancia y corrigiéndolas con sistemas de corrección de errores. Los sistemas de redundancia y corrección no siempre pueden restaurar la información perdida y, si lo hacen, no hay garantía de que la operación de restauración se haya completado correctamente.
Y este también es un gran problema, pero no diferido, sino actual.
Los compresores modernos utilizados para archivar datos digitales se basan en diversas modificaciones del método del diccionario, y para tales archivos la pérdida de información será un evento fatal; incluso existe un término establecido para tal situación: un archivo "roto". ...
La baja confiabilidad del almacenamiento de información en archivos con compresión de diccionario está asociada con la estructura de los datos comprimidos. La información en dicho archivo no contiene el texto fuente, los números de entradas en el diccionario se almacenan allí y el diccionario en sí se modifica dinámicamente mediante el texto comprimido actual. Si un fragmento de archivo se pierde o se daña, todas las entradas de archivo posteriores no pueden identificarse ni por el contenido ni por la longitud de la entrada en el diccionario, ya que no está claro a qué corresponde el número de entrada del diccionario.
Es imposible restaurar información de un archivo tan "roto".
El algoritmo RTT se basa en un método más confiable para almacenar datos comprimidos. Utiliza el método de índice para contabilizar fragmentos repetidos. Este enfoque de compresión le permite minimizar las consecuencias de la distorsión de la información en el medio de almacenamiento y, en muchos casos, corregir automáticamente las distorsiones que surgieron durante el almacenamiento de la información.
Esto se debe al hecho de que el archivo comprimido en el caso de la compresión de índice contiene dos campos:
- un campo de texto fuente del que se han eliminado las secciones repetidas;
- campo de índice.
El campo de índice, que es fundamental para la recuperación de información, no es de gran tamaño y se puede duplicar para un almacenamiento confiable de datos. Por lo tanto, incluso si se pierde un fragmento del texto fuente o de la matriz de índice, toda la demás información se restaurará sin problemas, como en la imagen con un medio de almacenamiento "analógico".
Desventajas del algoritmo.
No hay ventajas sin desventajas. El método de compresión de índice no comprime secuencias cortas y repetidas. Esto se debe a las limitaciones del método del índice. Los índices tienen un tamaño mínimo de 3 bytes y pueden tener un tamaño de hasta 12 bytes. Si se encuentra una repetición con un tamaño menor que el índice que la describe, entonces no se tiene en cuenta, sin importar con qué frecuencia se detecten dichas repeticiones en el archivo comprimido.
El método tradicional de compresión de diccionario comprime eficazmente múltiples repeticiones de corta duración y, por lo tanto, logra una relación de compresión más alta que la compresión de índice. Es cierto que esto se logra debido a la alta carga en el procesador central; para que el método del diccionario comience a comprimir datos de manera más eficiente que el método del índice, es necesario reducir la velocidad de procesamiento de datos a 10-20 megabytes por segundo en tiempo real. Instalaciones informáticas con carga CPU completa.
Velocidades tan bajas son inaceptables para los sistemas modernos de almacenamiento de datos y tienen un interés más “académico” que práctico.
El grado de compresión de la información aumentará significativamente en la próxima modificación del algoritmo RTT (RTT-Max), que ya está en desarrollo.
Así que, como siempre, continuará...
Fuente: habr.com