Reducción de datos por deduplicación o por compresión
Si hacemos caso de estudios como el del instituto internacional de estudios de mercado IDC, el volumen de los datos digitales almacenados se dobla a sí mismo cada dos años, de tal forma que, en 2020, el universo digital (la cantidad de datos que se producen o se copian en un año) alcanzaría un volumen de 44 zettabytes, o lo que es lo mismo, 44 trillones de gigabytes de datos generados en un solo año.
Los efectos de esta evolución se dejan ver especialmente en las técnicas de almacenamiento de información, en los procedimientos para realizar copias de seguridad y en los sistemas de recuperación, que han ser capaces de soportar y procesar una enorme cantidad de datos. Dada esta abundancia, los diferentes conceptos que guían su implementación técnica priorizan métodos que permiten minimizar la información depositada de forma física, reduciendo así los costes de mantenimiento de los datos.
Estos métodos se basan básicamente en dos enfoques: la compresión de datos por un lado y la deduplicación por otro. Mientras que la compresión sin pérdidas se basa en las redundancias dentro de un archivo para reducir el volumen de datos, los algoritmos de deduplicación comparan datos en todos los archivos para evitar repeticiones. De ahí que el ámbito de aplicación principal de la deduplicación sea la protección de los datos. A continuación pasamos a explicar ambos enfoques en produndidad.
Deduplicación de datos
El método de la deduplicación de datos tiene como objetivo primordial evitar la redundancia de datos en un sistema de almacenamiento o disco. Para ello utiliza un motor de deduplicación con algoritmos que identifican y eliminan datos o bloques de datos repetidos.
Como software puede integrarse en un programa para realizar backups y como hardware puede implementarse dentro de la matriz (array) de almacenamiento o como appliance intermedia.
El objetivo de la deduplicación es, básicamente, escribir en un soporte de almacenamiento no volátil solo la información estrictamente necesaria para poder reconstruir un archivo sin pérdidas, porque cuantos más duplicados se eliminen, más pequeño será el volumen de datos que ha de ser guardado o transferido. La identificación de duplicados puede realizarse, como en Git o en Dropbox, en los mismos archivos, pero los algoritmos de deduplicación que trabajan en los subarchivos son más eficientes. En este proceso, los archivos se fragmentan en bloques de datos o chunks, a los que se asignan sumas de verificación inequívocas, los denominados valores hash. La base de datos de seguimiento (tracking database), que contiene todas las sumas de verificación, actúa de instancia de control.
Este método de deduplicación basado en bloques se subdivide en dos variantes:
- Deduplicación con longitud de bloques fija: en este tipo de deduplicación el algoritmo subdivide los archivos en porciones de igual longitud, la cual, generalmente, se orienta por el tamaño del clúster del sistema de archivos o de RAID (típicamente 4 KB), aunque en ocasiones se puede configurar manualmente. En este caso, esta longitud ajustada de forma individual se tomará como estándar para todos los bloques de datos.
- Deduplicación con longitud de bloques variable: por el contrario, en este caso no se define ninguna longitud estándar. En lugar de ello, el algoritmo divide a los datos en bloques diferentes, cuya longitud varía en función del tipo de datos que se tengan que procesar.
La forma de dividir los bloques tiene una influencia enorme en la eficiencia de la deduplicación de datos. Esto se entiende con más claridad cuando los archivos deduplicados se han de modificar posteriormente. Si un bloque de datos con límites fijos se quiere ampliar con información adicional, el contenido de los bloques consecutivos se desplaza también, por lo general, en relación con los límites ya fijados. Aunque esta modificación solo afecte a un bloque de datos, el algoritmo de deduplicación clasifica otra vez a todos los segmentos de un archivo que le siguen debido al desplazamiento de los límites del bloque, a no ser que los bytes modificados supongan un múltiplo exacto de la longitud de bloque definida. Como los bloques de datos reclasificados tienen que ser guardados otra vez, un backup en una deduplicación con longitud de bloques fija implica un aumento de los requerimientos de cálculo y de la carga en el ancho de banda.
Si, por el contrario, un algoritmo utiliza límites variables, los cambios en un único bloque de datos no tienen efectos en los segmentos adyacentes, sino que solo se amplía y se almacena el bloque de datos modificado. Este método descarga a la red, ya que supone transmitir menos datos en un backup. En cambio, esta flexibilidad en cuanto a los cambios dentro de los archivos requiere más potencia de cálculo, ya que el algoritmo ha de averiguar primero cómo están distribuidos los chucks.
La identificación de bloques redundantes se apoya en la suposición de que los bloques de datos con idénticos valores hash contienen información idéntica. Para filtrar chunks redundantes, el algoritmo de deduplicacion solo necesita equiparar los valores hash nuevos con la base de datos de seguimiento. Si encuentra sumas de verificación idénticas, los chunks redundantes se sustituyen por un puntero (pointer), que indica el lugar donde está almacenado el bloque idéntico y cuyas necesidades de espacio son mucho menores que las del bloque de datos en sí. Cuantos más chunks dentro de un archivo se sustituyan por estos indicadores, menos memoria necesita este archivo.
Sin embargo, no es posible predecir la eficiencia de la reducción de datos con algoritmos de deduplicación al depender en gran medida del archivo original y de su estructura. A esto se suma la imposibilidad de reconocer patrones en los datos cifrados, ya que los sistemas de cifrado tienen como objetivo reducir las redundancias. Esto hace que este método de reducción de datos solo sea aplicable a datos sin cifrar.
La deduplicación se puede realizar tanto en el destino como en el origen de los datos.
Deduplicación en origen
Si los datos redundantes se eliminan ya antes de su transferencia al lugar del almacenamiento, se habla de deduplicación en origen. En este caso, el motor de deduplicación puede estar integrado en el software que lleva a cabo las copias de seguridad y elimina la información redundante ya en el sistema de archivos de partida. El software escanea para ello los bloques de datos nuevos en periodos regulares y los compara con aquellos que ya fueron asegurados en el servidor del backup. Si se encuentra un bloque redundante, se omite en el próximo backup, y si se modificó, el programa solo envía los elementos nuevos de este bloque.
La gran ventaja de este método de deduplicación es que solo se transfiere al servidor información nueva, lo que alivia tanto al ancho de banda como a la capacidad del almacenamiento de destino, pero, al contrario de lo que ocurre con la deduplicación en destino, este método conlleva un requerimiento de cálculo claramente más alto para el software de backup y por esto no es adecuado para cualquier escenario.
Deduplicación en destino
En este método la reducción de datos se produce en el exterior de la fuente de datos. El motor de deduplicación puede estar integrado en el hardware o estar conectado como appliance independiente. En ambos casos se reduce la necesidad de memoria pero, a diferencia de la deduplicación en fuente, esto no influye en la cantidad de datos que se transfiere durante el backup (con LAN o WAN) desde el origen al disco de almacenamiento. En función de la estructura que se escoja para la deduplicación en destino se diferencia entre offline e inline:
- Deduplicación offline o post process: si el motor de deduplicación está integrado en el hardware, los datos se depositan primero en el disco y allí se deduplican. Este tipo de deduplicación tiene la ventaja de que los datos pueden ser transferidos relativamente rápido al sistema de destino. Sin embargo, tras la transferencia, estos datos no están disponibles de forma inmediata para eliminar redundancias, sino que se ha de esperar a que finalice el procedimiento de backup. Los datos son redireccionados al disco duro tres veces antes de que se puedan replicar o se pueda acceder a ellos, lo que aumenta la carga del sistema de almacenamiento. El sistema de backup, además, ha de preparar primero dos zonas de almacenamiento separadas, una para los datos de salida y otra para los datos deduplicados. De esta forma se requiere, aunque solo sea de forma temporal, más espacio físico en el disco que en el caso de una deduplicación inline. Sin embargo, este método permite una reducción de datos más eficiente al funcionar con bloques de datos variables.
- Deduplicación inline: si el motor de deduplicación se coloca antes del disco, es posible eliminar los datos repetidos ya durante la transferencia y antes de que sean escritos en el disco. Esto, aunque disminuye la velocidad de escritura y limita la deduplicación a bloques de datos con longitud fija, reduce mucho más la necesidad de espacio en el sistema de destino que en el caso de la deduplicación offline. Los datos deduplicados de esta forma están disponibles inmediatamente para una recuperación de datos o para la copia, por ejemplo.
Compresión de datos
Mediante la compresión los archivos se transforman en una representación alternativa más eficiente que la original. El objetivo de esta codificación es reducir tanto el espacio de almacenamiento necesario como el tiempo de transferencia. Esta ganancia de codificación (coding gain) se puede obtener de dos formas:
- Compresión redundante: una compresión sin pérdidas basada en la reducción de redundancias permite descomprimir los datos de nuevo sin cambios. Los datos de entrada y de salida son idénticos. Una compresión de este tipo solo es posible cuando un archivo contiene información redundante.
- Compresión irrelevante: en una compresión con pérdidas se elimina información irrelevante, lo que normalmente va ligado a una pérdida de datos. Los datos de origen, tras esta compresión, solo se pueden restablecer de forma aproximada. No hay una norma que establezca qué datos se pueden considerar irrelevantes. En una compresión de audio con MP3, por ejemplo, se eliminan patrones de frecuencia que supuestamente el hombre no percibe o que lo hace apenas.
Mientras que la compresión en los sistemas de almacenamiento se produce fundamentalmente sin pérdidas, en otros ámbitos como en las conversiones de imagen, vídeo o audio, se tolera una cierta degradación imperceptible para lograr una reducción del tamaño de los archivos.
Tanto la codificación como la decodificación de un archivo tienen altos requerimientos de computación, que dependen, en primera instancia, del método de compresión utilizado. Si algunos métodos priorizan una representación lo más compacta posible de los datos de salida, otras tienen como objetivo la reducción del tiempo de cálculo necesario. En definitiva, la elección del método de compresión está vinculada a las necesidades de su ámbito de aplicación.
En el marco de una transmisión en directo de vídeo o de sonido, se recomienda, por ejemplo, un procedimiento que permita una compresión y una recomposición lo más rápidas posible. En este caso, una ganancia de codificación menor y una probable pérdida de calidad pueden estar justificadas. Lo contrario sucede con aquellos archivos que han de estar disponibles para un gran número de usuarios en un servidor de archivos (file server). Aquí puede tolerarse un empleo de tiempo mayor para la compresión utilizando un algoritmo de compresión más potente que permita obtener ganancias de codificación más altas sin pérdidas de calidad.
Compresión de datos sin pérdidas
Mientras que un algoritmo de deduplicación busca coincidencias en archivos diferentes y sustituye segmentos redundantes por indicadores, los procedimientos de compresión de datos sin pérdidas trabajan con las denominadas representaciones: los fragmentos que se repiten varias veces dentro de un archivo se sustituyen por una representación abreviada. Esto se puede entender con el siguiente ejemplo:
Archivo de entrada: ABCDEABCEEABCEE
Codificación: ABC = 1; EE = 2
Texto comprimido: 1DE1212
La codificación permite reducir un texto de origen de 15 caracteres de longitud a otro de 7, obteniendo una ganancia de codificación de más de un 50 por ciento.
La condición para poder realizar una compresión de este tipo es que tanto el sistema de codificación como el de decodificación conozcan el código.
La mayor parte de algoritmos de compresión sin pérdidas se basa en la repetición de signos o en combinaciones de ellos dentro de un archivo. Los más conocidos son word coding y el algoritmo de Lempel-Ziv (LZ77).
- Word coding: los algoritmos de compresión basados en la codificación de palabras están indicados sobre todo para archivos de texto, porque su principio fundamental consiste en la sustitución de palabras por representaciones más cortas. Para ello, en un primer paso, se elabora una lista de palabras, a cada una de las cuales se asigna un valor. De esta forma es posible transformar textos enteros en un código de cifras, como en este ejemplo:
Archivo de entrada: ser o no ser
Codificación: ser = 1; o = 2, no = 3
Texto comprimido: 1231
Como en este caso también se ha de almacenar la lista de palabras, además de los datos de uso, este algoritmo de compresión resulta especialmente efectivo en el caso de textos muy largos con muchas repeticiones.
- Algoritmo de Lempel-Ziv: también basado en diccionario, este método de compresión permite comprimir secuencias de caracteres sobre la base de redundancias. El algoritmo utiliza el contenido que ya ha leído como un diccionario, de tal forma que no ha de ser añadido. La referencia a una secuencia idéntica que ya ha sido procesada en el archivo de entrada tiene lugar mediante el llamado triple, que codifica la posición y el tamaño de la repetición, así como el primer byte o carácter no coincidente. Esta operación se realiza con la llamada sliding window o “ventana corredera” en dos búfers, uno de diccionario (dictionary buffer) y otro de vista previa (preview buffer). Si no se encuentra ninguna coincidencia para un carácter, el triple resultante es “0,0,x”, donde “x” representa al signo correspondiente. El siguiente ejemplo muestra una codificación LZ77 de la palabra “banana”:
Las secuencias de caracteres en la vista previa se van desplazando al diccionario (de ahí el sistema llamado de “ventana corredera”) y se comparan con los que ya han sido leídos en el diccionario. El resultado de la comparativa (output) toma la forma de un código triple.
En la línea 4 reconoce el patrón AN (2, 2) y añade la A:
2= Sustituye esta secuencia por una secuencia ya “vista” en la posición 2 (A)
2= la sustitución incluye dos caracteres (A y N)
A= es el siguiente signo que se coteja.
Como LZ77 permite comprimir de forma efectiva la mayoría de tipos de datos, sus sucesores, como LZSS, están muy extendidos. Se usan sobre todo para los formatos Zip, PNG o PDF.
Además de los procedimientos basados en la redundancia, en la compresión sin pérdidas también se usan los métodos basados en la frecuencia como la codificación Run-length encoding (RLE) o la codificación Huffman.
- RLE o Run-length encoding: se fija en las consecuciones de caracteres idénticos en una secuencia. Esto se ve de forma muy clara en la representación esquemática de una línea (scanline) de un gráfico en blanco y negro, donde B equivale al color blanco, y N al color negro:
BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB
Si aplicamos la codificación run-length a esta línea, convirtiendo a los signos que se repiten en el par de valores compuestos del valor-signo y del valor-cantidad de repeticiones, se reduce esta línea de forma considerable, dando como resultado:
12B1N12B3N24B1N14B
Utilizado en la compresión de imágenes, la contrapartida es que este método va perdiendo eficacia a medida que aumenta la cantidad de colores que se tienen que codificar. Mientras que los esquemas en blanco y negro se pueden simplificar con dos condiciones cromáticas, las imágenes en gradaciones de grises en 8 bits ya necesitan 256 tonos de gris. En las imágenes complejas con gradaciones delicadas de color, la probabilidad de reconocer más de dos píxeles consecutivos como idénticos se reduce drásticamente. Como la codificación en nuestro ejemplo se basa en pares binarios, solo se obtiene una ganancia de codificación cuando existen como mínimo 3 signos iguales consecutivos. Una forma que deriva de este método forma parte del conocido procedimiento de compresión de imagen JPG.
- Codificación Huffman: con este algoritmo de compresión se deduce primero la frecuencia de todos los signos contenidos en un archivo. En el siguiente paso se traducen en una secuencia de bits, donde la longitud de la representación depende de la frecuencia. La codificación Huffman se muestra gráficamente con el llamado “árbol de Huffman”, en el cual los signos a codificar se representan como sus hojas. Veamos cómo se procedería con la frase “This is an example of a huffman tree”:
Signo | Espacios | a | e | f | h | i | m | n | s | t | l | o | p | r | u | x |
Frecuencia | 7 | 4 | 4 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
Cada código binario de un signo resulta de la trayectoria que va de la raíz a la hoja. Una ramificación a la izquierda se traduce con un 0 y una a la derecha con un 1:
Los caracteres del ejemplo se codifican de la siguiente forma:
Espacio vacio | a | e | f | h | i | m | n |
111 | 010 | 000 | 1101 | 1010 | 1000 | 0111 | 0010 |
s | t | l | o | p | r | u | x |
1011 | 0110 | 11001 | 00110 | 10011 | 11000 | 00111 | 10010 |
Mientras que los signos muy usados como el espacio, “a” o “e” se pueden codificar con solo 3 bits, otros menos frecuentes como “r”, “u” o “x” requieren 5 bits. El código ASCII, por ejemplo, utiliza 7 bits por carácter. En códigos compatibles con ASCII como UTF-8 o ISO 8859-1 (Latin-1) se añade, sin embargo, un octavo bit al trabajar los ordenadores de hoy día con múltiplos de 8 bits (8, 16, 32 o 64 bits). Este sistema permite almacenar texto de una forma mucho más compacta.
La siguiente cadena de caracteres muestra la frase de nuestro ejemplo “This is an example of a huffman tree” como secuencia binaria según Huffman:
0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000
Y esta sería la secuencia de bits para el mismo contenido siguiendo una codificación ASCII con el octavo bit añadido (el primer cero):
01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 01100001 01101110 00100000 01110100 01110010 01100101 01100101
Con la codificación Huffman y en función de la distribución de la frecuencia de caracteres, los datos se pueden reducir hasta un tercio de su tamaño original. Sin embargo, hay que tener en cuenta que el árbol también tiene que guardarse para poder decodificarse después.
Este método no solo encuentra aplicación en la compresión de archivos de texto, sino también como una fase de la compresión JPEG y en el formato ZIP, que es una combinación entre LZSS y Huffman.
Compresión con pérdidas
Mientras que la compresión sin pérdidas solo es posible si se encuentran redundancias dentro de un archivo, la compresión con pérdidas basada en la reducción de irrelevancia es, en principio, siempre posible si se acepta la pérdida de información como parte del proceso. Por eso esta forma de compresión implica siempre tener que decidir qué porción de los datos originales son prescindibles. Un límite teórico para una compresión máxima se puede sondear con el teorema de tasa-distorsión (rate-distorsion theory), que describe la relación entre compresión y calidad de la señal.
Los procedimientos de compresión con pérdida se orientan por la percepción humana. En la compresión de datos de audio con MP3, AAC o WMA, por ejemplo, se descartan las frecuencias inaudibles para las personas. Un ejemplo muy utilizado para la reducción de irrelevancia en el ámbito de la imagen es el procedimiento JPEG, que combina métodos con y sin pérdida. Entre los primeros se cuentan la conversión cromática del sistema RGB al YCbCr, la transformada de coseno discreta (DCT del inglés Discrete Cosine Transform) y la cuantificación digital.
Deduplicación o compresión: cuál es la mejor opción
Las grandes compañías suelen apostar por la deduplicación para realizar copias de seguridad o para optimizar el almacenado en sistemas de archivos estándares. Esto es debido principalmente a que los sistemas de deduplicación son extremadamente eficientes cuando se han de guardar archivos idénticos. Por el contrario, los procedimientos de compresión de datos suelen estar ligados a unos altos requerimientos de computación y, con ello, a unos costes más elevados en cuanto a las plataformas que se requieren.
La forma más efectiva de usar los sistemas de almacenado consiste en combinar ambos procedimientos de reducción del volumen de datos, de tal forma que primero se eliminan las redundancias de los archivos que se tienen que guardar mediante deduplicación y a continuación se comprimen los datos resultantes.
Artículos similares
Mejora el rendimiento de tu servidor con el balanceo de carga
La disponibilidad de páginas corporativas, tiendas electrónicas y portales de información determina el éxito de un negocio. Es por eso que cada vez más empresas se valen de un balanceador de carga para una distribución equilibrada de las peticiones a los servidores por parte de los usuarios. Si se aplica bien, no solo garantiza una gran disponibilidad de las páginas web, sino que también facilita…
Las bases de datos y la importancia de sus copias de seguridad
Crear copias de seguridad es la estrategia preferida por muchos para proteger sus bases de datos. Para garantizar el correcto funcionamiento de estas, puede ser necesario el uso de hardware adicional, así como de dispositivos que proporcionen una infraestructura adecuada. ¿Cómo proteger una red o un servidor web de ataques externos sin comprometer la seguridad de tus bases de datos?
Copias de seguridad con rsync
Hacer copias de seguridad del servidor es la mejor manera de guardar los datos importantes de las páginas web. Es sobre todo en los entornos de servidor donde se recomienda contar con una buena estrategia de copias de seguridad que incluya todos los terminales. Esto requiere utilizar programas de copia de seguridad fiables. Además de software y servicios en línea de pago, hay aplicaciones gratis…
Niveles RAID: comparativa de los enfoques RAID más importantes
Quien quiera agrupar discos duros en un RAID, puede elegir entre una variedad de configuraciones de estándares, conocidas como niveles RAID. Estas agrupaciones predefinidas describen la disposición de los discos individuales, así como los procedimientos que utilizan para almacenar los archivos. ¿Qué enfoques aplican los niveles RAID más importantes? ¿Y para qué finalidad son más adecuados?
