En teoría de codificación , un código de borrado es un código de corrección de errores directa (FEC) bajo el supuesto de borrados de bits (en lugar de errores de bits), que transforma un mensaje de k símbolos en un mensaje más largo (palabra de código) con n símbolos de modo que el El mensaje original se puede recuperar a partir de un subconjunto de n símbolos. La fracción r = k / n se llama tasa de código . La fracción k'/k , donde k' denota el número de símbolos necesarios para la recuperación, se denomina eficiencia de recepción. El algoritmo de recuperación espera que se sepa cuál de los n símbolos se pierde, a diferencia de los códigos de corrección de errores directos .
La codificación de borrado fue inventada por Irving Reed y Gustave Solomon en 1960. [1]
Existen muchos esquemas diferentes de codificación de borrado. Los códigos de borrado más populares son la codificación Reed-Solomon , el código de verificación de paridad de baja densidad (códigos LDPC) y los códigos Turbo . [1]
A partir de 2023, los sistemas modernos de almacenamiento de datos podrán diseñarse para tolerar el fallo total de unos pocos discos sin pérdida de datos, utilizando uno de tres enfoques: [2] [3] [4]
Si bien técnicamente RAID puede verse como una especie de código de borrado, [5] "RAID" generalmente se aplica a una matriz conectada a una única computadora host (que es un único punto de falla), mientras que la "codificación de borrado" generalmente implica múltiples hosts. , [3] a veces denominado conjunto redundante de servidores económicos (RAIS). El código de borrado permite que las operaciones continúen cuando cualquiera de esos hosts se detiene. [4] [6]
En comparación con los sistemas RAID a nivel de bloque, la codificación de borrado de almacenamiento de objetos tiene algunas diferencias significativas que la hacen más resistente. [7] [8] [9] [10] [11]
Los códigos de borrado óptimos tienen la propiedad de que cualquier k de los n símbolos de palabras de código son suficientes para recuperar el mensaje original (es decir, tienen una eficiencia de recepción óptima). Los códigos de borrado óptimos son códigos separables por distancia máxima (códigos MDS).
La verificación de paridad es el caso especial donde n = k + 1. A partir de un conjunto de k valores , se calcula una suma de verificación y se agrega a los k valores de origen:
El conjunto de valores k + 1 ahora es consistente con respecto a la suma de verificación. Si uno de estos valores, , se borra, se puede recuperar fácilmente sumando las variables restantes:
RAID 5 es una aplicación ampliamente utilizada del código de borrado de verificación de paridad. [1]
En el caso simple en el que k = 2, se pueden crear símbolos de redundancia muestreando diferentes puntos a lo largo de la línea entre los dos símbolos originales. Esto se muestra con un ejemplo simple, llamado err-mail:
Alice quiere enviar su número de teléfono (555629) a Bob mediante err-mail. Err-mail funciona igual que el correo electrónico, excepto
En lugar de pedirle a Bob que reconozca los mensajes que envía, Alice idea el siguiente esquema.
Bob sabe que la forma de f ( k ) es , donde a y b son las dos partes del número de teléfono. Ahora supongamos que Bob recibe "D=777" y "E=851".
Bob puede reconstruir el número de teléfono de Alice calculando los valores de a y b a partir de los valores ( f (4) y f (5)) que ha recibido. Bob puede realizar este procedimiento utilizando dos mensajes de error cualesquiera, por lo que el código de borrado en este ejemplo tiene una tasa del 40%.
Tenga en cuenta que Alice no puede codificar su número de teléfono en un solo mensaje de error porque contiene seis caracteres y que la longitud máxima de un mensaje de error es de cinco caracteres. Si enviara su número de teléfono por partes, pidiéndole a Bob que acusara recibo de cada parte, de todos modos se tendrían que enviar al menos cuatro mensajes (dos de Alice y dos acuses de recibo de Bob). Por tanto, el código de borrado de este ejemplo, que requiere cinco mensajes, es bastante económico.
Este ejemplo es un poco artificial. Para códigos de borrado verdaderamente genéricos que funcionen con cualquier conjunto de datos, necesitaríamos algo distinto de f ( i ) dado.
La construcción lineal anterior se puede generalizar a la interpolación polinómica . Además, ahora los puntos se calculan sobre un campo finito .
Primero elegimos un campo finito F con orden de al menos n , pero generalmente una potencia de 2. El remitente numera los símbolos de datos de 0 a k − 1 y los envía. Luego construye un polinomio (Lagrange) p ( x ) de orden k tal que p ( i ) es igual al símbolo de datos i . Luego envía p ( k ), ..., p ( n − 1). El receptor ahora también puede utilizar la interpolación polinómica para recuperar los paquetes perdidos, siempre que reciba k símbolos con éxito. Si el orden de F es menor que 2 b , donde b es el número de bits en un símbolo, entonces se pueden usar múltiples polinomios.
El remitente puede construir símbolos k an − 1 'sobre la marcha', es decir, distribuir la carga de trabajo uniformemente entre la transmisión de los símbolos. Si el receptor quiere hacer sus cálculos "sobre la marcha", puede construir un nuevo polinomio q , tal que q ( i ) = p ( i ) si el símbolo i < k se recibió con éxito y q ( i ) = 0 cuando el símbolo i < k no fue recibido. Ahora sea r ( i ) = p ( i ) − q ( i ). En primer lugar, sabemos que r ( i ) = 0 si el símbolo i < k se ha recibido correctamente. En segundo lugar, si el símbolo i ≥ k se ha recibido correctamente, entonces se puede calcular r ( i ) = p ( i ) − q ( i ). Entonces tenemos suficientes puntos de datos para construir r y evaluarlo para encontrar los paquetes perdidos. Entonces, tanto el remitente como el receptor requieren O ( n ( n − k )) operaciones y solo O ( n − k ) espacio para operar 'sobre la marcha'.
Este proceso se implementa mediante códigos Reed-Solomon , con palabras de código construidas sobre un campo finito utilizando una matriz de Vandermonde .
Los códigos de borrado más prácticos son códigos sistemáticos : cada uno de los k símbolos originales se puede encontrar copiado, sin codificar, como uno de los n símbolos del mensaje. [13] (Los códigos de borrado que admiten el intercambio de secretos nunca utilizan un código sistemático).
Los códigos de borrado casi óptimos requieren (1 + ε) k símbolos para recuperar el mensaje (donde ε>0). La reducción de ε se puede realizar a costa del tiempo de CPU. Los códigos de borrado casi óptimos intercambian capacidades de corrección por complejidad computacional: los algoritmos prácticos pueden codificar y decodificar con complejidad de tiempo lineal.
Los códigos fuente (también conocidos como códigos de borrado sin tasa ) son ejemplos notables de códigos de borrado casi óptimos . Pueden transformar un mensaje de símbolo k en una forma codificada prácticamente infinita, es decir, pueden generar una cantidad arbitraria de símbolos de redundancia que pueden usarse para corrección de errores. Los receptores pueden comenzar a decodificar después de haber recibido un poco más de k símbolos codificados.
Los códigos de regeneración abordan el problema de reconstruir (también llamado reparar) fragmentos codificados perdidos a partir de fragmentos codificados existentes. Este problema ocurre en sistemas de almacenamiento distribuido donde la comunicación para mantener la redundancia codificada es un problema. [13]
La codificación de borrado es ahora una práctica estándar para el almacenamiento de datos confiable. [14] [15] [16] En particular, Apache Hadoop , el RAID-6 integrado en Linux, Microsoft Azure, almacenamiento en frío de Facebook y Backblaze Vaults, utiliza varias implementaciones de codificación de borrado Reed-Solomon. [16] [13]
La forma clásica de recuperarse de fallas en los sistemas de almacenamiento era utilizar la replicación. Sin embargo, la replicación genera una sobrecarga significativa en términos de bytes desperdiciados. Por lo tanto, los sistemas de almacenamiento cada vez más grandes, como los utilizados en los centros de datos, utilizan almacenamiento con código de borrado. La forma más común de codificación de borrado utilizada en los sistemas de almacenamiento es el código Reed-Solomon (RS) , una fórmula matemática avanzada que se utiliza para permitir la regeneración de datos faltantes a partir de fragmentos de datos conocidos, llamados bloques de paridad. En un código RS ( k , m ), un conjunto dado de k bloques de datos, llamados "fragmentos", se codifican en ( k + m ) fragmentos. El conjunto total de trozos comprende una raya . La codificación se realiza de manera que siempre que al menos k de ( k + m ) fragmentos estén disponibles, se puedan recuperar todos los datos. Esto significa que un almacenamiento codificado en RS ( k , m ) puede tolerar hasta m fallas.
Ejemplo: en el código RS (10, 4), que se utiliza en Facebook para su HDFS , [17] 10 MB de datos de usuario se dividen en diez bloques de 1 MB. Luego, se crean cuatro bloques de paridad adicionales de 1 MB para proporcionar redundancia. Esto puede tolerar hasta 4 fallas simultáneas. La sobrecarga de almacenamiento aquí es 14/10 = 1,4X.
En el caso de un sistema completamente replicado, los 10 MB de datos del usuario deberán replicarse 4 veces para tolerar hasta 4 fallas simultáneas. La sobrecarga de almacenamiento en ese caso será 50/10 = 5 veces.
Esto da una idea de la menor sobrecarga de almacenamiento del almacenamiento con código de borrado en comparación con la replicación completa y, por tanto, del atractivo de los sistemas de almacenamiento actuales.
Inicialmente, los códigos de borrado se utilizaban para reducir el costo de almacenar de manera eficiente datos "fríos" (a los que rara vez se accede); pero los códigos de borrado también se pueden utilizar para mejorar el rendimiento al entregar datos "calientes" (a los que se accede con más frecuencia). [13]
RAID N+M divide los bloques de datos en unidades N+M y puede recuperar todos los datos cuando falla alguna de las unidades M. [1] En particular, RAID 7.3 se refiere a RAID de triple paridad y puede recuperar todos los datos cuando fallan 3 unidades. [18]
A continuación se muestran algunos ejemplos de implementaciones de los distintos códigos:
