Hispanopedia Wiki
Articulo de referencia

Código de borrado

En teoría de la codificación , un código de borrado es un código de corrección de errores hacia adelante (FEC) que, bajo el supuesto de borrado de bits (en lugar de errores de b...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de la codificación , un código de borrado es un código de corrección de errores hacia adelante (FEC) que, bajo el supuesto de borrado de bits (en lugar de errores de bits), transforma un mensaje de k símbolos en un mensaje más largo (palabra clave) con n símbolos, de manera que el mensaje original pueda recuperarse a partir de un subconjunto de los n símbolos. La fracción r  = k / n se denomina tasa de codificación . 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 presupone que se conocen cuáles de los n símbolos se han perdido. 

Historia

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 modernos de almacenamiento de datos pueden diseñarse para tolerar la falla completa de algunos discos sin pérdida de datos , utilizando uno de 3 enfoques: [ 2 ] [ 3 ] [ 4 ]

  • Replicación
  • RAID (matriz redundante de discos económicos )
  • Codificación de borrado

Si bien técnicamente RAID puede considerarse un tipo de código de borrado, [ 5 ] RAID generalmente se aplica a una matriz conectada a una sola computadora host (que es un único punto de falla ), mientras que la "codificación de borrado" generalmente implica múltiples hosts, [ 3 ] a veces llamada 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 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 ]

Códigos de borrado óptimos

Los códigos de borrado óptimos tienen la propiedad de que cualquier conjunto de k símbolos de la palabra código, de un total de n, 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 a distancia máxima (códigos MDS).

Verificación de paridad

La comprobación de paridad es el caso especial donde n  = k + 1. A partir de un conjunto de k valores   {vi}1≤i≤k{\displaystyle \{v_{i}\}_{1\leq i\leq k}}Se calcula una suma de verificación y se agrega a los k valores de origen:

vk+1=−∑i=1kvi.{\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}

El conjunto de k  +  1 valores{vi}1≤i≤k+1{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}ahora es consistente con respecto a la suma de verificación. Si uno de estos valores,vmi{\displaystyle v_{e}}Si se borra, se puede recuperar fácilmente sumando las variables restantes:

vmi=−∑i=1,i≠mik+1vi.{\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}

RAID 5 es una aplicación ampliamente utilizada del código de borrado de comprobación de paridad mediante XOR. [ 1 ]

Sobremuestreo polinomial

Ejemplo: Correo de error ( k  =  2)

En el caso simple donde 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 usando err-mail. Err-mail funciona igual que el correo electrónico, excepto

  1. Aproximadamente la mitad del correo se pierde.
  2. Los mensajes de más de 5 caracteres son ilegales.
  3. Es muy caro (similar al correo aéreo).

En lugar de pedirle a Bob que confirme la recepción de los mensajes que le envía, Alice idea el siguiente plan.

  1. Ella divide su número de teléfono en dos partes, a = 555, b = 629, y envía dos mensajes: "A=555" y "B=629" a Bob.
  2. Ella construye una función lineal,F(i)=a+(b−a)(i−1){\displaystyle f(i)=a+(ba)(i-1)}, en este casoF(i)=555+74(i−1){\displaystyle f(i)=555+74(i-1)}, de tal manera queF(1)=555{\displaystyle f(1)=555}yF(2)=629{\displaystyle f(2)=629}.

  1. Ella calcula los valores f (3), f (4) y f (5), y luego transmite tres mensajes redundantes: "C=703", "D=777" y "E=851".

Bob sabe que la forma de f ( k ) esF(i)=a+(b−a)(i−1){\displaystyle f(i)=a+(ba)(i-1)}, 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 cualquier par de correos electrónicos de error, 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, ya que contiene seis caracteres, y 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 confirmara la recepción de cada parte, de todos modos tendría que enviar al menos cuatro mensajes (dos de Alice y dos confirmaciones de Bob). Por lo tanto, el código de borrado en este ejemplo, que requiere cinco mensajes, resulta 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 distinto a la función f ( i ) dada.

Caso general

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 de orden al menos n , pero generalmente una potencia de 2. El emisor numera los símbolos de datos del 0 al 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 . A continuación, envía p ( k ), ..., p ( n − 1). El receptor también puede usar 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 varios polinomios.    

El emisor puede construir símbolos de 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 realizar 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 ). Primero sabemos que r ( i ) = 0 si el símbolo i < k se ha recibido correctamente. Segundo, 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'.                    

Implementación en el mundo real

Este proceso se implementa mediante códigos de Reed-Solomon, con palabras clave 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).

Códigos de borrado casi óptimos

Los códigos de borrado casi óptimos requieren (1  +  ε) k símbolos para recuperar el mensaje (donde ε>0). Reducir ε puede hacerse a costa de un mayor tiempo de CPU. Estos códigos sacrifican la capacidad de corrección a cambio de una mayor complejidad computacional: los algoritmos prácticos pueden codificar y decodificar con una complejidad temporal lineal.

Los códigos Fountain (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 k símbolos en una forma codificada prácticamente infinita; es decir, pueden generar una cantidad arbitraria de símbolos de redundancia que se pueden usar para la corrección de errores. Los receptores pueden comenzar a decodificar después de haber recibido algo más de k símbolos codificados.

La regeneración de códigos aborda el problema de reconstruir (también llamado reparar) fragmentos codificados perdidos a partir de fragmentos codificados existentes. Este problema se presenta en sistemas de almacenamiento distribuido donde la comunicación para mantener la redundancia codificada es problemática. [ 12 ]

Aplicaciones de la codificación de borrado en sistemas de almacenamiento

La codificación de borrado es ahora una práctica estándar para el almacenamiento de datos confiable. [ 13 ] [ 14 ] [ 15 ] En particular, varias implementaciones de la codificación de borrado Reed-Solomon son utilizadas por Apache Hadoop , el RAID-6 integrado en Linux, Microsoft Azure, el almacenamiento en frío de Facebook y Backblaze Vaults. [ 15 ] [ 12 ]

La forma clásica de recuperarse de fallos en los sistemas de almacenamiento era mediante la replicación. Sin embargo, la replicación conlleva 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, emplean almacenamiento con codificación de borrado. La forma más común de codificación de borrado en sistemas de almacenamiento es el código Reed-Solomon (RS) , una fórmula matemática avanzada que permite la regeneración de datos faltantes a partir de fragmentos de datos conocidos, denominados bloques de paridad. En un código RS ( k , r ), un conjunto dado de k bloques de datos, llamados "fragmentos", se codifica en ( k + r ) fragmentos. El conjunto total de fragmentos conforma una franja . La codificación se realiza de tal manera que, siempre que al menos k de los ( k + r ) fragmentos estén disponibles, se puede recuperar la totalidad de los datos. Esto significa que un almacenamiento con codificación RS ( k , r ) puede tolerar hasta r fallos. (Esto difiere de la notación RS( n , k ) estándar, donde n = k + r ).           

RS(10,4)

Ejemplo: En  el código RS(10, 4), que se utiliza en Facebook para su HDFS (ahora parte de Apache Hadoop), 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 fallos concurrentes. La sobrecarga de almacenamiento aquí es 14/10 = 1,4 × . [ 16 ]

En el caso de un sistema totalmente replicado, los 10 MB de datos de usuario deberán replicarse 4 veces para tolerar hasta 4 fallos concurrentes. La sobrecarga de almacenamiento en ese caso será de 50/10  =  5,0×.

Esto da una idea de la menor sobrecarga de almacenamiento del almacenamiento con codificación de borrado en comparación con la replicación completa y, por lo tanto, de su atractivo en los sistemas de almacenamiento actuales.

El esquema Hitchhiker se puede combinar con la codificación RS para reducir la cantidad de cálculos y transferencia de datos necesarios para la reconstrucción de bloques de datos. También se implementa como un códec HDFS, aunque será necesario definir manualmente una política para su uso. [ 12 ]

Datos calientes

Inicialmente, los códigos de borrado se utilizaron para reducir el costo de almacenar datos "fríos" (de acceso poco frecuente) de manera eficiente; pero también pueden utilizarse para mejorar el rendimiento al servir datos "calientes" (de acceso más frecuente) en comparación con esquemas de redundancia más simples (replicación). [ 12 ]

El ejemplo clásico de cómo la codificación de borrado mejora el rendimiento es RAID 5 , que proporciona la misma protección contra fallos de una sola unidad, pero requiere menos discos duros que RAID 1. Los discos duros adicionales se pueden usar para almacenar más datos y aprovechar el multiplicador de velocidad de lectura/escritura mejorado de RAID 5. Esto también se aplica a RAID 6 (doble redundancia: un código de paridad y uno de borrado), siempre que la potencia de procesamiento sea suficiente. [ 1 ] RAID generalizado puede funcionar con cualquier número de unidades de redundancia. Hay dos notaciones para RAID generalizado: RAID7. x se refiere a un sistema con x unidades de redundancia, lo que permite la recuperación cuando fallan hasta x unidades. [ 17 ] Alternativamente, RAID N+M se refiere a N unidades de datos normales con M unidades de redundancia, lo que permite recuperar todos los datos cuando fallan M unidades. [ 1 ]

Un ejemplo más avanzado es EC-Cache , una caché en clúster, es decir, una caché distribuida entre varios nodos. Estos sistemas pueden sufrir desequilibrio de carga cuando un nodo aloja más elementos populares, y un método común para abordar este problema es la replicación selectiva , es decir, crear más réplicas para los objetos más populares. Sin embargo, este método está limitado por la cantidad de memoria disponible. Al dividir individualmente cada objeto en k particiones y r unidades de redundancia, se puede lograr un equilibrio de carga perfecto con un mínimo desperdicio de memoria. [ 12 ]

Ejemplos

Aquí tenéis algunos ejemplos de implementaciones de los distintos códigos:

Códigos de borrado casi óptimos

Códigos de fuente casi óptimos (borrado sin tasa)

Códigos de borrado óptimos

  • Paridad XOR, que añade un símbolo borrable. Se utiliza en RAID4 y RAID5.
  • Códigos Reed-Solomon. Su funcionamiento es óptimo en modo de borrado, permitiendo k borrados para k símbolos añadidos. En modo de corrección de errores, también es óptimo, permitiendo errores floor( k /2).
    • Los formatos de archivo Parchive 1.0, 2.0 y (abierto) 3.0 utilizan RS. La versión 3.0 también admite otros códigos lineales.
    • RAID6 utiliza una variedad de códigos de borrado óptimos, pero RS es una opción común.
    • Tahoe-LAFS incluye zfec , una implementación de Classic RS.
  • Código sistemático resistente al borrado , un código MDS que permite paquetes más redundantes que Reed-Solomon con el mismo tamaño de símbolo, véase RS(4,2) con 2 bits o RS(9,2) con 3 bits.
  • Códigos regenerativos [ 18 ] [ 19 ]
  • Cualquier otro código de distancia máxima separable

Véase también

Referencias

  1. 1 2 3 4 5 "RAID vs. Codificación de borrado. ¿Cuál es la diferencia? | Blog | Xinnor" . El RAID por software más rápido y fiable | Xinnor . 3 de septiembre de 2023. Consultado el 18 de septiembre de 2024 .
  2. ↑ "Ceph.io — Codificación de borrado en Ceph" . ceph.io. 7 de abril de 2014. Consultado el 18 de septiembre de 2024 .
  3. 1 2 Lee, Brandon (26-12-2023). "RAID vs Codificación de borrado vs Replicación" . BDRSuite . Recuperado el 18-09-2024 .
  4. 1 2 O'Reilly, Jim. "RAID vs. Codificación de borrado" . www.networkcomputing.com . Consultado el 18 de septiembre de 2024 .
  5. ↑ Dimitri Pertin, Alexandre van Kempen, Benoît Parrein, Nicolas Normand. «Comparación de códigos de borrado RAID-6» . Tercer Taller Sino-Francés sobre Tecnologías de la Información y la Comunicación, SIFWICT 2015, junio de 2015, Nantes, Francia. ffhal-01162047f
  6. ↑ "Comprensión de la tolerancia a fallos de IBM Spectrum Scale Erasure Code Edition" . www.ibm.com . Consultado el 18 de septiembre de 2024 .
  7. ↑ "Codificación de borrado de almacenamiento de objetos frente a RAID de almacenamiento en bloques" . Blog de MinIO . 27 de julio de 2021. Consultado el 18 de septiembre de 2024 .
  8. ↑ "Codificación de borrado vs. RAID como método de protección de datos | Computer Weekly" . ComputerWeekly.com . Consultado el 18 de septiembre de 2024 .
  9. ↑ Kruth, Peter (04/10/2023). "Erasure Code: RAID As It Should Be – Huawei BLOG" . Archivado del original el 04/10/2023 . Recuperado el 18/09/2024 .
  10. ↑ "Codificación de borrado 101" . Blog de MinIO . 25 de abril de 2022. Consultado el 18 de septiembre de 2024 .
  11. ↑ Bhaskaran, Dinesh Kumar (6 de julio de 2018). "Por qué la codificación de borrado es el futuro de la resiliencia de datos" . Archivado del original el 7 de agosto de 2020.
  12. 1 2 3 4 5 6 Rashmi Vinayak. "Codificación de borrado para sistemas de macrodatos: teoría y práctica" . 2016. pág. 2: sección "Resumen". pág. 9: sección "Códigos sistemáticos". pág. 12: sección "Códigos regenerativos".
  13. ↑ "Codificación por borrado: práctica y principios" . 2016.
  14. ↑ Matt Sarrel. "Codificación de borrado 101" . 2022.
  15. 1 2 Brian Beach. "Backblaze publica el código fuente del sistema de codificación de borrado Reed-Solomon" . 2015.
  16. ↑ Xia, Mingyuan; Saxena, Mohit; Blaum, Mario; Pease, David A. (2015). Una historia de dos códigos de borrado en HDFS . FAST '15. págs. 213–226 . ISBN  978-1-931971-20-1.
  17. ↑ Leventhal, Adam (diciembre de 2009). "RAID de triple paridad y más allá: a medida que las capacidades de los discos duros siguen superando su rendimiento, ha llegado el momento de un nuevo nivel de RAID". ACM Queue . 7 (11): 30– 39. doi : 10.1145/1661785.1670144 .
  18. ↑ Dimakis, Alexandros G.; Godfrey, P. Brighten; Wu, Yunnan; Wainwright, Martin J.; Ramchandran, Kannan (septiembre de 2010). "Codificación de red para sistemas de almacenamiento distribuido". IEEE Transactions on Information Theory . 56 (9): 4539– 4551. arXiv : cs/0702015 . Bibcode : 2010ITIT...56.4539D . CiteSeerX 10.1.1.117.6892 . doi : 10.1109/TIT.2010.2054295 . S2CID 260559901 .  
  19. ↑ "Inicio [ Wiki de codificación de borrado para almacenamiento distribuido ] " . 31/07/2017. Archivado del original el 31/07/2017 . Recuperado el 20/08/2023 .
  • Jerasure es una biblioteca de software libre que implementa técnicas de códigos de borrado Reed-Solomon y Cauchy con optimizaciones SIMD.
  • El software FEC en comunicaciones informáticas , por Luigi Rizzo, describe códigos de corrección de borrado óptimos.
  • Feclib es una extensión casi óptima del trabajo de Luigi Rizzo que utiliza matrices de banda. Se pueden configurar muchos parámetros, como el ancho de la banda y el tamaño del campo finito. Además, aprovecha con éxito el gran tamaño de los registros de las CPU modernas. Se desconoce cómo se compara con los códigos casi óptimos mencionados anteriormente.
  • Wiki de codificación para almacenamiento distribuido para regenerar códigos y reconstruir códigos de borrado.
  • ECIP "Erasure Code Internet Protocol" Desarrollado en 1996, fue el primer uso de FEC "Forward Error correction" en Internet. Se utilizó comercialmente por primera vez para * transmitir en vivo video de Sir Arthur C. Clarke en Sri Lanka a UIUC en Indiana .
Obtenido de " https://en.wikipedia.org/w/index.php?title=Erasure_code&oldid=1350963299 "
Lecturas relacionadas
6 articulos
Teoría de la codificaciónTeoría de la codificaciónLa teoría de la codificación es el estudio de las propiedades de los códigos y su respectiva idoneidad para aplicaciones específicas. Los códigos s...Código de corrección de erroresCódigo de corrección de erroresEn informática , telecomunicaciones , teoría de la información y teoría de codificación , la corrección de errores hacia adelante ( FEC ) o codific...Tasa de códigoTasa de códigoEn la teoría de la información y las telecomunicaciones , la tasa de código (o tasa de información [1] ) de un código de corrección de errores haci...Gustave SalomónGustave SalomónGustave Solomon (27 de octubre de 1930 - 31 de enero de 1996) fue un matemático e ingeniero eléctrico estadounidense que fue uno de los fundadores ...Código de verificación de paridad de baja densidadCódigo de verificación de paridad de baja densidadLos códigos de verificación de paridad de baja densidad ( LDPC ) , también conocidos como códigos de Gallager , son una clase de códigos de correcc...Código turboCódigo turboEn teoría de la información , los códigos turbo son una clase de códigos de corrección de errores hacia adelante (FEC) de alto rendimiento desarrol...