En teoría de codificación , un código de borrado es un código de corrección de errores hacia adelante (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 mensaje original se pueda recuperar a partir de un subconjunto de los n símbolos. La fracción r = k / n se denomina 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áles de los n símbolos se pierden.
La codificación de borrado fue inventada por Irving Reed y Gustave Solomon en 1960. [1]
Existen muchos esquemas de codificación de borrado diferentes. 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 de almacenamiento de datos modernos se pueden diseñar para tolerar la falla completa de algunos discos sin pérdida de datos, utilizando uno de tres enfoques: [2] [3] [4]
Aunque técnicamente RAID puede verse como una especie de código de borrado, [5] "RAID" se aplica generalmente a una matriz conectada a una única computadora host (que es un único punto de falla), mientras que "codificación de borrado" generalmente implica múltiples hosts, [3] a veces llamado Matriz 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 bloques, 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 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 de máxima distancia separable (códigos MDS).
La comprobación de paridad es el caso especial en el que n = k + 1. A partir de un conjunto de k valores , se calcula una suma de comprobación y se agrega a los k valores de origen:
El conjunto de valores k + 1 es ahora coherente con respecto a la suma de comprobación. Si se borra uno de estos valores, , 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 ilustra 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 que
En lugar de pedirle a Bob que reconozca los mensajes que ella envía, Alice idea el siguiente plan.
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 correo electrónico, ya que contiene seis caracteres y la longitud máxima de un mensaje de correo electrónico es de cinco caracteres. Si enviara su número de teléfono en partes y le pidiera a Bob que acusara recibo de cada parte, tendría que enviar al menos cuatro mensajes de todas formas (dos de Alice y dos de Bob). Por lo tanto, el código de borrado en 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 a la f ( i ) indicada.
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 un orden de al menos n , pero usualmente 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 (de Lagrange) p ( x ) de orden k tal que p ( i ) sea igual al símbolo de datos i . Luego envía p ( k ), ..., p ( n − 1). El receptor ahora también puede usar la interpolación polinómica para recuperar los paquetes perdidos, siempre que reciba k símbolos exitosamente. 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 a n − 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ó correctamente y q ( i ) = 0 cuando el símbolo i < k no se recibió. 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 ). Así que tenemos suficientes puntos de datos para construir r y evaluarlo para encontrar los paquetes perdidos. Por lo tanto, tanto el emisor 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 .
La mayoría de los códigos de borrado 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. [12] (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 sacrifican las capacidades de corrección por la complejidad computacional: los algoritmos prácticos pueden codificar y decodificar con una complejidad temporal lineal.
Los códigos de fuente (también conocidos como códigos de borrado sin velocidad ) son ejemplos notables de códigos de borrado casi óptimos . Pueden transformar un mensaje de k símbolos en una forma codificada prácticamente infinita, es decir, pueden generar una cantidad arbitraria de símbolos de redundancia que pueden usarse para la 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 resuelven el problema de la reconstrucción (también llamada reparación) de fragmentos codificados perdidos a partir de fragmentos codificados existentes. Este problema se produce en sistemas de almacenamiento distribuido donde la comunicación para mantener la redundancia codificada es un problema. [12]
La codificación de borrado es ahora una práctica estándar para el almacenamiento confiable de datos. [13] [14] [15] En particular, Apache Hadoop , el RAID-6 integrado en Linux, Microsoft Azure, el almacenamiento en frío de Facebook y Backblaze Vaults utilizan varias implementaciones de la codificación de borrado Reed-Solomon . [15] [12]
La forma clásica de recuperarse de fallos en los sistemas de almacenamiento era utilizar la replicación. Sin embargo, la replicación supone una sobrecarga significativa en términos de bytes desperdiciados. Por lo tanto, los sistemas de almacenamiento cada vez más grandes, como los que se utilizan en los centros de datos, utilizan almacenamiento con codificación 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 fragmentos ( k + m ). El conjunto total de fragmentos comprende una franja . La codificación se realiza de tal manera que, siempre que estén disponibles al menos k de los fragmentos ( k + m ), se pueden recuperar todos los datos. Esto significa que un almacenamiento con codificación RS ( k , m ) puede tolerar hasta m fallos.
Ejemplo: En el código RS (10, 4), que se utiliza en Facebook para su HDFS , [16] 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 totalmente replicado, los 10 MB de datos de 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 que supone el almacenamiento con código de borrado en comparación con la replicación completa y, por tanto, su atractivo en los sistemas de almacenamiento actuales.
Inicialmente, los códigos de borrado se utilizaron para reducir el costo de almacenar datos "fríos" (a los que se accede raramente) de manera eficiente; pero los códigos de borrado también se pueden utilizar para mejorar el rendimiento al servir datos "calientes" (a los que se accede con mayor frecuencia). [12]
RAID N+M divide bloques de datos en N+M unidades y puede recuperar todos los datos cuando fallan M unidades. [1] En particular, RAID 7.3 se refiere a RAID de triple paridad y puede recuperar todos los datos cuando fallan 3 unidades. [17]
A continuación se muestran algunos ejemplos de implementaciones de los distintos códigos:
