Este artículo ya es el segundo en el tema de la compresión de datos de alta velocidad. El primer artículo describe un compresor que funciona a una velocidad de 10 GB / s. por núcleo de procesador (compresión mínima, RTT-Min).
Este compresor ya se ha introducido en el equipo de duplicadores forenses para la compresión a alta velocidad de los volcados de medios de almacenamiento y para aumentar la fuerza de la criptografía, también se puede usar para comprimir imágenes de máquinas virtuales e intercambiar archivos RAM mientras se almacenan en unidades SSD de alta velocidad.
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. Hasta la fecha, este compresor está completamente listo y este artículo trata sobre él.
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. Además, su velocidad es al menos un orden de magnitud mayor.
La velocidad de empacar / desempacar datos es un parámetro crítico que determina el alcance de las tecnologías de compresión. Es poco probable que alguien piense en comprimir un terabyte de datos a una velocidad de 10-15 megabytes por segundo (esta es la velocidad de los archivadores en el modo de compresión estándar), porque llevará casi veinte horas cargar completamente el procesador ...
Por otro lado, el mismo terabyte se puede copiar a velocidades del orden de 2-3 Gigabytes por segundo durante aproximadamente diez minutos.
Por lo tanto, la compresión de información de un gran volumen es relevante si se realiza a una velocidad no inferior a la velocidad de entrada / salida real. Para sistemas modernos, esto es al menos 100 megabytes por segundo.
Los compresores modernos solo pueden producir tales velocidades en el modo "rápido". Es en este modo actual que compararemos el algoritmo RTT-Mid con los compresores tradicionales.
Pruebas comparativas del nuevo algoritmo de compresión.
El compresor RTT-Mid funcionó como parte de un programa de prueba. En una aplicación real "funcional", funciona mucho más rápido, el subprocesamiento múltiple se usa correctamente allí y se usa 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 utilizamos el método de medición de la "temperatura promedio en el hospital" ...
Se creó un archivo de volcado sector por sector de una unidad lógica con el sistema operativo Windows 10; esta es la mezcla más natural de varias estructuras de datos realmente disponibles en cada computadora. La compresión de 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 fue comprimido por compresores WinRar PTT-Mid, 7-zip. El compresor WinRar y el 7-zip se ajustaron a la velocidad máxima.
El compresor
7-zip funciona:
Carga el procesador al 100%, mientras que la velocidad de lectura promedio del volcado original es de aproximadamente 60 megabytes / seg.
El compresor
WinRar funciona:
La situación es similar, la carga del procesador es casi del 100%, la velocidad de lectura promedio del volcado es de aproximadamente 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
RTT-Mid ahora funciona:
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 para descargar los datos comprimidos. El disco de carga de datos (Disco 0) se carga casi por completo. La velocidad de lectura de datos (Disco 1) salta mucho, pero en promedio más de 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 manejó la compresión mejor que nadie, 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-Mid: 7 minutos y 30 segundos.
Por lo tanto, 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 los competidores ...
Aquellos que no creen en las capturas de pantalla pueden verificar su precisión por sí mismos. El programa de prueba está disponible
aquí , descargue y verifique.
Pero solo en procesadores con soporte para AVX-2, sin el soporte de estas instrucciones, el compresor no funciona y no prueba el algoritmo en procesadores AMD más antiguos, son lentos en términos de ejecución de comandos AVX ...
Método de compresión utilizado
El algoritmo utiliza el método de indexar fragmentos de texto repetidos en granulación de bytes. Este método de compresión se conoce desde hace mucho tiempo, pero no se ha utilizado, ya que la operación de búsqueda de coincidencias era muy costosa en términos de recursos necesarios y requería mucho más tiempo que construir un diccionario. Entonces, el algoritmo RTT-Mid es un ejemplo clásico del movimiento "de regreso al futuro" ...
El compresor PTT utiliza un escáner único de alta velocidad para encontrar coincidencias, fue él quien permitió acelerar el proceso de compresión. Un escáner hecho a sí mismo, es "mi encanto ...", "es un precio considerable, porque está completamente hecho a mano" (escrito en ensamblador).
El escáner de búsqueda de coincidencias se basa en un esquema probabilístico de dos niveles, primero se escanea la presencia de un "signo" de una coincidencia, y solo después de detectar el "signo" en este lugar comienza el procedimiento para detectar una coincidencia real.
La ventana de búsqueda de coincidencias tiene un tamaño impredecible, dependiendo del grado de entropía en el bloque de datos que se procesa. Para datos completamente aleatorios (incompresibles), tiene un tamaño de megabytes, para datos que tienen repeticiones siempre tiene un tamaño de más de un megabyte.
Pero muchos formatos de datos modernos son incompresibles y "manejar" un escáner que requiere muchos recursos es inútil y derrochador, por lo tanto, el escáner usa dos modos de funcionamiento. Primero, se buscan secciones del texto fuente con posibles repeticiones, esta operación también se lleva a cabo mediante el método probabilístico y se realiza muy rápidamente (a una velocidad de 4-6 Gigabytes / seg). Luego, las áreas con posibles coincidencias son procesadas por el escáner principal.
La compresión de índice no es muy eficiente, debe reemplazar los fragmentos repetidos con índices, y la matriz de índice reduce significativamente la relación de compresión.
Para aumentar la relación de compresión, no solo se indexan coincidencias completas de cadenas de bytes, sino también parciales cuando hay bytes coincidentes y no coincidentes en la cadena. Para hacer esto, el campo de máscara de índice se incluye en el formato de índice, que indica los bytes coincidentes de dos bloques. Para una compresión aún mayor, la indexación se utiliza con la superposición de varios bloques parcialmente coincidentes en el bloque actual.
Todo esto permitió obtener una relación de compresión en el compresor PTT-Mid, comparable con los compresores fabricados de acuerdo con el método del diccionario, pero que funcionan mucho más rápido.
La velocidad del nuevo algoritmo de compresión.
Si el compresor funciona con el uso exclusivo de la memoria caché (se requieren 4 megabytes por flujo), entonces la velocidad varía de 700-2000 megabytes / seg. por núcleo de procesador, dependiendo del tipo de datos que se comprimen y poco depende de la frecuencia de funcionamiento del procesador.
Con la implementación multiproceso del compresor, la escalabilidad efectiva está determinada por el volumen de memoria caché del tercer nivel. Por ejemplo, tener 9 Megabytes de memoria caché "a bordo" no tiene sentido ejecutar más de dos flujos de compresión, la velocidad no aumentará a partir de esto. Pero con un caché de 20 megabytes, ya puede ejecutar cinco secuencias de compresión.
Además, la latencia de RAM se convierte en un parámetro esencial que determina la velocidad del compresor. El algoritmo utiliza accesos aleatorios al OP, algunos de los cuales no entran en la memoria caché (aproximadamente el 10%) y tiene que permanecer inactivo, esperando los datos del OP, lo que reduce la velocidad del trabajo.
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 tasa de compresión. Este problema es significativo para las computadoras portátiles y de escritorio, para los servidores es menos significativo debido a la unidad de control de acceso más avanzada para el bus del sistema y la RAM multicanal.
En todas partes del texto, el artículo se refiere a la compresión, la descompresión está más allá del alcance de este artículo porque allí todo está en el 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 hilo proporciona calmadamente velocidades de descompresión en el nivel de 3-4 Gigabytes / seg.
Esto se debe a la ausencia de una operación de búsqueda de coincidencias durante el proceso de desempaquetado, que "come" el procesador principal y los recursos de caché durante la compresión.
Almacenamiento confiable de datos comprimidos
Como lo indica el nombre de toda la clase de herramientas de software que utilizan compresión de datos (archivadores), están diseñadas 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 de los datos, aquí hay un ejemplo:
Este medio de almacenamiento "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 digital y medios digitales para ellos ofrece garantías de seguridad de datos completa durante más de 75 años.
Y esto es un problema, pero el problema se pospone, nuestros descendientes lo resolverán ...
Los sistemas de almacenamiento de datos digitales pueden perder datos no solo después de 75 años, los errores de datos pueden aparecer en cualquier momento, incluso durante su grabación, intentan minimizar estas distorsiones utilizando redundancia y corrigiendo sistemas de corrección de errores. Los sistemas de redundancia y corrección no siempre pueden restaurar la información perdida, y si se restauran, no hay garantía de que la operación de recuperación sea correcta.
Y este también es un gran problema, pero no retrasado, sino el actual.
Los compresores modernos utilizados para archivar datos digitales se basan en varias modificaciones del método del diccionario, y para dichos archivos la pérdida de información será un evento fatal, incluso hay 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 datos comprimidos. La información en dicho archivo no contiene el texto fuente, los números de entradas en el diccionario se almacenan allí, el diccionario actual se modifica dinámicamente por el texto comprimido actual. Si un fragmento del archivo se pierde o se distorsiona, todas las entradas de archivo posteriores no pueden identificarse ni por el contenido ni por la longitud de las entradas en el diccionario, porque no está claro a qué corresponde el número de la entrada del diccionario.
Es imposible recuperar 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. Tal enfoque de compresión permite minimizar las consecuencias de la distorsión de la información en el medio y, en muchos casos, corregir automáticamente las distorsiones que surgen durante el almacenamiento de la información.
Esto se debe al hecho de que el archivo de almacenamiento en el caso de la compresión de índice contiene dos campos:
- campo de texto fuente con secciones repetidas eliminadas de él;
- campo de índice
El campo de índice crítico para la recuperación de datos no es de gran tamaño y puede duplicarse para un almacenamiento de datos confiable. Por lo tanto, incluso si se pierde un fragmento del texto fuente o la matriz de índice, toda la otra información se restaurará sin problemas, como en la imagen con el portador de información "analógico".
Deficiencias de algoritmo
Las ventajas no existen sin desventajas. El método de compresión de índice no comprime secuencias cortas repetitivas. Esto se debe a las limitaciones del método de índice. Los índices tienen un tamaño de al menos 3 bytes y pueden tener un tamaño de hasta 12 bytes. Si se produce una repetición con un tamaño más pequeño que el índice que lo describe, entonces no se tiene en cuenta, sin embargo, a menudo, tales repeticiones se detectan en un archivo compresible.
El método tradicional de compresión de vocabulario comprime eficazmente múltiples repeticiones cortas 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 de trabajo del procesador central, por lo que el método de vocabulario comienza a comprimir datos de manera más eficiente que el método de índice, tiene que reducir la velocidad de procesamiento de datos a 10-20 megabytes por segundo en instalaciones informáticas reales con carga de CPU completa.
Estas bajas velocidades 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 PTT (RTT-Max), que ya está en desarrollo.
Entonces, como siempre, continuará ...