En la teoría de la codificación , un código de borrado es un código de corrección de errores de reenvío (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 manera que el el mensaje original se puede recuperar a partir de un subconjunto de los 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 .
Códigos de borrado óptimos
Los códigos de borrado óptimos tienen la propiedad de que cualquier k de los n símbolos de palabras de código es suficiente para recuperar el mensaje original (es decir, tienen una eficiencia de recepción óptima). Los códigos de borrado óptimos son códigos separables de distancia máxima (códigos MDS).
Comprobación de paridad
La verificación de paridad es el caso especial donde n = k + 1. 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 + 1ahora es coherente con respecto a la suma de comprobación. Si uno de estos valores,, se borra, se puede recuperar fácilmente sumando las variables restantes:
Sobremuestreo de polinomios
Ejemplo: Err-mail ( k = 2)
En el caso simple donde k = 2, los símbolos de redundancia pueden crearse 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 usando err-mail. Err-mail funciona igual que el correo electrónico, excepto
- Aproximadamente la mitad de todo el correo se pierde. [1]
- Los mensajes de más de 5 caracteres son ilegales.
- Es muy caro (similar al correo aéreo).
En lugar de pedirle a Bob que reconozca los mensajes que envía, Alice diseña el siguiente esquema.
- Divide su número de teléfono en dos partes a = 555, b = 629 y envía 2 mensajes - "A = 555" y "B = 629" - a Bob.
- Ella construye una función lineal, , en este caso , tal que y .
- Calcula los valores f (3), f (4) yf (5) y luego transmite tres mensajes redundantes: "C = 703", "D = 777" y "E = 851".
Bob sabe que la forma de f ( k ) es, Donde un y b son las dos partes del número de teléfono. Ahora suponga que Bob recibe "D = 777" y "E = 851".
Bob puede reconstruir el número de teléfono de Alice mediante el cálculo de los valores de una y b a partir de los valores ( f (4) y f (5)) que ha recibido. Bob puede realizar este procedimiento utilizando dos correos electrónicos 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 enviaba su número de teléfono por partes, pidiéndole a Bob que acuse recibo de cada pieza, de todos modos se tendrían que enviar al menos cuatro mensajes (dos de Alice y dos de Bob). Entonces, 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 sobre cualquier conjunto de datos, necesitaríamos algo diferente al f ( i ) dado.
Caso general
La construcción lineal anterior se puede generalizar a la interpolación polinómica . Además, los puntos ahora 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 (de 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 correctamente. 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 de manera uniforme 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 con éxito. En segundo lugar, si el símbolo i ≥ k se ha recibido con éxito, entonces se puede calcular r ( i ) = p ( i ) - q ( i ). Entonces tenemos suficientes puntos de datos para construir ry evaluarlo para encontrar los paquetes perdidos. Por tanto, tanto el emisor como el receptor requieren O ( n ( n - k )) operaciones y solo O ( n - k ) espacio para operar "sobre la marcha".
Implementación en el mundo real
Este proceso se implementa mediante códigos Reed-Solomon , con palabras de código construidas sobre un campo finito utilizando una matriz de Vandermonde .
Códigos de borrado casi óptimos
Los códigos de borrado casi óptimos requieren (1 + ε) k símbolos para recuperar el mensaje (donde ε> 0). La reducción de ε se puede hacer a costa del tiempo de la 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 velocidad ) 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 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 abordan el problema de la reconstrucción (también llamada reparación) de 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.
Aplicaciones de la codificación de borrado en sistemas de almacenamiento
La forma clásica de recuperarse de fallas en los sistemas de almacenamiento era utilizar la replicación. [2] Sin embargo, la replicación incurre en 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 codificado por 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) . En un código RS ( k , m ), un conjunto dado de k bloques de datos, llamados "trozos", se codifican en trozos ( k + m ). El conjunto total de trozos comprende una raya . La codificación se realiza de manera que siempre que estén disponibles al menos k de ( k + m ) fragmentos, se pueden recuperar todos los datos. Esto significa que un almacenamiento codificado en ( k , m ) RS puede tolerar hasta ( m - k ) fallas.
Ejemplo: En el código RS (10, 4), que se utiliza en Facebook para su HDFS , [3] 10 MB de datos de usuario se dividen en diez bloques de 1 MB. Luego, se crean cuatro bloques de paridad de 1 MB adicionales 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 = 5X.
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 lo tanto, la atracción en los sistemas de almacenamiento actuales.
Ejemplos de
A continuación, se muestran algunos ejemplos de implementaciones de los distintos códigos:
Códigos de borrado casi óptimos
Códigos fuente casi óptimos (borrado sin velocidad)
Códigos de borrado óptimos
- Paridad : se utiliza en sistemas de almacenamiento RAID .
- Parchive
- Tahoe-LAFS incluye zfec
- Códigos Reed-Solomon
- Código sistemático resistente al borrado , un código MDS que supera a Reed-Solomon en el número máximo de paquetes redundantes, consulte RS (4,2) con 2 bits o RS (9,2) con 3 bits
- Regeneración de códigos [4] consulte también Wiki de almacenamiento .
- cualquier otro código MDS (un tipo de "Código separable de distancia máxima")
Otro
Ver también
- Reenviar códigos de corrección de errores.
- Uso compartido de secretos (difiere en que el secreto original se cifra y se oculta hasta que se alcanza el quórum de decodificación)
Referencias
- ^ Algunas versiones de esta historia se refieren al demonio err-mail.
- ^ "Tecnología de replicación de datos: ¿Qué es y cómo funciona?" . StoneFly . Consultado el 2 de julio de 2021 .
- ^ Xia, Mingyuan; Saxena, Mohit; Blaum, Mario; Pease, David A. (2015). "Historia de dos códigos de borrado en {HDFS}" : 213–226. ISBN 978-1-931971-20-1. Cite journal requiere
|journal=
( ayuda ) - ^ Dimakis, Alexandros G .; Godfrey, P. Brighten; Wu, Yunnan; Wainwright, Martin J .; Ramchandran, Kannan (septiembre de 2010). "Codificación de red para sistemas de almacenamiento distribuidos". Transacciones IEEE sobre teoría de la información . 56 (9): 4539–4551. arXiv : cs / 0702015 . CiteSeerX 10.1.1.117.6892 . doi : 10.1109 / TIT.2010.2054295 .
enlaces externos
- Jerasure es una biblioteca de software libre que implementa técnicas de código de borrado de Reed-Solomon y Cauchy con optimizaciones SIMD.
- El software FEC en comunicaciones informáticas de Luigi Rizzo describe los códigos de corrección de borrado óptimos
- Feclib es una extensión casi óptima del trabajo de Luigi Rizzo que utiliza matrices de bandas. Se pueden configurar muchos parámetros, como el tamaño del ancho de la banda y el tamaño del campo finito. También aprovecha con éxito el gran tamaño de registro de las CPU modernas. Se desconoce cómo se compara con los códigos casi óptimos mencionados anteriormente.
- Codificación para wiki de almacenamiento distribuido para regenerar códigos y reconstruir códigos de borrado.
- ECIP "Protocolo de Internet de código de borrado" Desarrollado en 1996, fue el primer uso de FEC "Corrección de errores de reenvío" en Internet. Se utilizó por primera vez comercialmente para * transmitir video en vivo de Sir Arthur C. Clarke en Sri Lanka a UIUC en Indiana .