Erasure coding: cómo HDFS baja el costo de replicar de 200% a 50%

⏱️ Lectura: 13 min

Guardar tres copias completas de cada archivo funciona, pero cuesta el triple de disco. Erasure coding logra la misma tolerancia a fallos con una fracción del espacio: parte los datos en fragmentos, calcula piezas de paridad con matemática de campos finitos y reconstruye lo que falta sin necesitar una copia idéntica guardada en otro lado.

📑 En este artículo

1. TL;DR
2. Qué es erasure coding y por qué importa
3. Cómo funciona erasure coding por dentro
   1. La matemática en un párrafo
   2. Codificación y decodificación
4. Ejemplos prácticos con código
   1. Hola mundo con reedsolo
   2. Sharding de un archivo real con fallos simulados
5. Cómo empezar
6. Casos de uso reales
7. Errores comunes y buenas prácticas
8. Comparativa con alternativas
9. Profundizando
   1. Por qué GF(256) y no aritmética normal
   2. Códigos sistemáticos vs no sistemáticos
10. Preguntas frecuentes
    1. ¿Erasure coding reemplaza completamente a la replicación?
    2. ¿Cuántos fragmentos puedo perder con un esquema RS 6-3?
    3. ¿Erasure coding funciona igual para archivos chicos que para archivos grandes?
    4. ¿Qué diferencia hay entre erasure coding y un simple checksum tipo CRC?
    5. ¿RAID 6 y HDFS erasure coding usan el mismo algoritmo?
11. Referencias

Sistemas como HDFS, el almacenamiento de objetos tipo S3 y los arreglos RAID 6 usan esta técnica todos los días para sobrevivir a discos que fallan sin duplicar cada byte. Entender cómo funciona por dentro, y programarla vos mismo, es más simple de lo que parece.

TL;DR

• Vas a entender por qué erasure coding reemplaza la replicación 3x con la mitad o menos de espacio en disco.
• Vas a programar un codificador y decodificador Reed-Solomon en Python con la librería reedsolo.
• Vas a simular la pérdida de fragmentos completos y reconstruir un archivo sin ninguna copia idéntica.
• Vas a leer una notación k+m como RS 6-3 y calcular cuántos fallos tolera y qué overhead paga.
• Vas a distinguir cuándo conviene RAID 6, cuándo HDFS con erasure coding y cuándo replicación simple.
• Vas a comprender por qué QR, CDs y erasure coding comparten la matemática de Reed-Solomon de 1960.

Qué es erasure coding y por qué importa

La forma más simple de tolerar fallos es guardar copias: si un disco muere, leés otra copia. Es lo que hace HDFS por defecto con su factor de replicación 3, donde cada bloque vive en tres máquinas distintas. Funciona, pero el costo de almacenamiento es 200% extra: por cada terabyte de datos útiles, guardás dos terabytes adicionales solo de respaldo.

Erasure coding ataca el mismo problema desde otro ángulo. En vez de copiar el dato entero, lo divide en k fragmentos de datos y calcula m fragmentos de paridad adicionales, usando álgebra sobre campos finitos: los mismos campos de Galois que protegen un CD rayado o un código QR sucio. El resultado son k+m fragmentos totales, de los cuales alcanza con tener cualquier k para reconstruir el archivo original completo.

Esa palabra “cualquier” es la clave: no importa cuáles m fragmentos falten, ni si fallan discos, nodos o hasta racks enteros. Mientras sobrevivan k de los k+m fragmentos, la reconstrucción es matemáticamente posible. Esto es lo que separa a erasure coding de un simple RAID con un disco espejo: la protección no depende de qué fragmento específico se pierda.

Cómo funciona erasure coding por dentro

La matemática en un párrafo

Reed-Solomon, publicado por Irving Reed y Gustave Solomon en 1960 (ver Wikipedia), trata cada fragmento de datos como un punto de un polinomio sobre un campo finito, típicamente GF(256) porque encaja perfecto en un byte. Con k puntos alcanza para definir un polinomio de grado k-1; los m fragmentos de paridad son ese mismo polinomio evaluado en m puntos adicionales. Perder fragmentos es como borrar puntos del gráfico: si todavía quedan k puntos, el polinomio, y por lo tanto el dato original, se reconstruye por interpolación.

Codificación y decodificación

La codificación multiplica los k fragmentos de datos por una matriz de generación (Vandermonde o Cauchy, ambas garantizan que cualquier subconjunto de filas sea invertible) para producir los m fragmentos de paridad. La decodificación hace lo inverso: con los fragmentos que sobrevivieron, arma una submatriz cuadrada, la invierte en el campo finito y multiplica para recuperar los fragmentos perdidos.

💡 Tip: antes de elegir k y m en producción, calculá primero cuántos fallos simultáneos tolera tu infraestructura real (discos por rack, racks por zona) y recién ahí fijá m, no al revés.

flowchart LR
 A["Archivo original"] --> B["Codificador Reed-Solomon"]
 B --> C["Fragmento D1"]
 B --> D["Fragmento D2"]
 B --> E["Fragmento D3"]
 B --> F["Paridad P1"]
 B --> G["Paridad P2"]
 subgraph Almacenamiento
 C
 D
 E
 F
 G
 end

Ejemplos prácticos con código

Hola mundo con reedsolo

La librería reedsolo implementa Reed-Solomon en Python puro. Instalala con pip install reedsolo y probá lo mínimo: codificar una cadena, corromper unos bytes y decodificarla.

from reedsolo import RSCodec

# 10 bytes de paridad agregados al mensaje
rsc = RSCodec(10)

mensaje = b"hola desde programacion"
codificado = rsc.encode(mensaje)

# Simulamos 3 bytes danados, dentro del limite tolerado (10 // 2 = 5)
danado = bytearray(codificado)
danado[0] ^= 0xFF
danado[5] ^= 0xFF
danado[9] ^= 0xFF

recuperado, _, _ = rsc.decode(danado)
print(recuperado)  # b'hola desde programacion'

RSCodec(10) agrega 10 bytes de paridad, lo que permite corregir hasta 5 bytes corruptos en posición desconocida: cada error hay que primero localizarlo y después corregirlo, por eso la capacidad de corrección es la mitad de la paridad. El resultado impreso es el mensaje original intacto.

Sharding de un archivo real con fallos simulados

El caso de uso real no corrige bytes sueltos: reparte un archivo en fragmentos completos entre discos o nodos, y tolera perder fragmentos enteros. Con la misma librería, separando en shards manualmente:

from reedsolo import RSCodec
import os

K, M = 6, 3  # 6 fragmentos de datos, 3 de paridad (RS 6-3, igual que HDFS)
rsc = RSCodec(M)

datos = os.urandom(1024 * 1024)  # archivo de 1 MB de ejemplo
tam_fragmento = len(datos) // K
fragmentos = [datos[i*tam_fragmento:(i+1)*tam_fragmento] for i in range(K)]

# Codificamos byte a byte a lo largo de los K fragmentos
# y guardamos solo los ultimos M bytes de paridad de cada posicion
paridad = [rsc.encode(bytes([f[i] for f in fragmentos]))[-M:]
           for i in range(tam_fragmento)]

print(f"Fragmentos de datos: {K}, fragmentos de paridad: {M}")
print(f"Overhead de almacenamiento: {M/K:.0%}")

Con RS 6-3 el overhead es 3/6 = 50%, muy por debajo del 200% de guardar tres copias completas. Esa cuenta, m/k, es la que hay que memorizar antes de elegir un esquema.

Cómo empezar

Para experimentar con erasure coding en tu propia máquina sin instalar Hadoop ni tocar un clúster, tres pasos alcanzan:

1. Instalá la librería: pip install reedsolo
2. Elegí tu esquema k+m según cuántos fallos simultáneos querés tolerar. Regla práctica: m es igual a la cantidad de fallos simultáneos a tolerar.
3. Corré el script de sharding de arriba, después borrá manualmente uno o dos fragmentos guardados en disco y confirmá que el decodificador reconstruye el original igual.

Si preferís probarlo directamente en un sistema de archivos distribuido real, HDFS trae erasure coding activado por política desde Hadoop 3.0. Para confirmar qué política corre sobre un directorio:

hdfs ec -getPolicy -path /datos/produccion
hdfs ec -listPolicies

El primer comando muestra si esa carpeta usa replicación clásica o una política RS-6-3-1024k (Reed-Solomon 6+3 con celdas de 1 MB). El segundo lista todas las políticas disponibles en el clúster, documentadas en la guía oficial de HDFS Erasure Coding.

Casos de uso reales

Erasure coding no es una curiosidad académica: sostiene infraestructura que se usa todos los días.

• HDFS: desde Hadoop 3.0 ofrece políticas Reed-Solomon como alternativa a la replicación 3x, documentado en la guía oficial. La política por defecto RS-6-3 paga 50% de overhead contra el 200% de tres copias.
• RAID 6: tolera dos discos rotos a la vez calculando dos bloques de paridad independientes (P y Q) por cada fila de datos, a diferencia de RAID 5, que solo tolera uno.
• Object storage tipo S3: los proveedores de almacenamiento de objetos usan variantes de erasure coding entre zonas de disponibilidad para sostener durabilidad sin triplicar el costo de infraestructura.
• QR codes y códigos de barras: usan Reed-Solomon para seguir siendo legibles aunque una esquina del código esté rota, sucia o tapada.
• CDs y DVDs: el estándar CIRC (Cross-Interleaved Reed-Solomon Coding) corrige rayones físicos del disco con la misma matemática.
• Backblaze Vaults: la empresa de backup explica en su blog técnico cómo usa Reed-Solomon para repartir cada archivo entre decenas de servidores y tolerar perder varios discos sin perder datos.

Errores comunes y buenas prácticas

Erasure coding no es gratis ni universal. Estos son los gotchas más frecuentes:

• CPU en la reconstrucción: reconstruir un fragmento perdido exige invertir una matriz e interpolar sobre GF(256), un costo de cómputo que la replicación simple no tiene, porque ahí alcanza con leer la copia. En clústeres con fallos frecuentes de disco, ese costo se nota.
• Archivos chicos, overhead relativo alto: un archivo de pocos KB dividido en 6 fragmentos deja fragmentos casi vacíos; el overhead de metadata supera el ahorro de espacio. Por eso HDFS aplica erasure coding sobre todo a datos fríos o poco accedidos, y sigue usando replicación 3x para datos calientes.
• Latencia de lectura ante fallos: leer un archivo con fragmentos faltantes obliga a reconstruirlo antes de servirlo, lo que agrega latencia comparado con leer directo de una réplica sana.
• No todos los m son iguales: un esquema RS 10-4 tolera 4 fallos, pero si esos 4 discos están en el mismo rack y el rack completo se cae, no importa cuánta paridad tengas. La distribución física de los fragmentos importa tanto como la matemática.

⚠️ Ojo: erasure coding protege contra pérdida de fragmentos, no contra corrupción silenciosa no detectada. Sin checksums por fragmento, un byte corrupto que no fue marcado como “perdido” puede colarse en la reconstrucción.

Comparativa con alternativas

Esquema	Overhead de espacio	Fallos tolerados	Cuándo usarlo
Replicación 3x	200%	2 copias	Datos calientes, prioridad en velocidad de lectura sobre costo
RAID 5	1 disco de paridad	1 disco	Arreglos pequeños donde perder 2 discos a la vez es poco probable
RAID 6	2 discos de paridad	2 discos	Arreglos grandes donde el tiempo de reconstrucción es largo
Erasure coding RS 6-3	50%	3 fragmentos	Datos fríos o poco accedidos en almacenamiento distribuido a gran escala

Profundizando

Por qué GF(256) y no aritmética normal

Si se usara aritmética entera común, sumar o multiplicar fragmentos podría desbordar el rango de un byte (0 a 255) y perder información. Los campos de Galois GF(2⁸) resuelven esto: toda suma, resta, multiplicación y división entre bytes da como resultado otro byte válido, sin overflow. Es la misma construcción algebraica que usa AES para su S-box.

Códigos sistemáticos vs no sistemáticos

Un código es “sistemático” cuando los primeros k fragmentos codificados son literalmente los datos originales sin modificar, y solo los últimos m son paridad calculada. Es la forma que usan HDFS y RAID: si no falta nada, se leen los fragmentos de datos directo, sin decodificar nada. Los códigos no sistemáticos mezclan datos y paridad en todos los fragmentos, útiles en canales de comunicación pero raros en almacenamiento porque obligan a decodificar siempre, incluso cuando no hace falta.

💭 Clave: la misma matemática de campos finitos que reconstruye un archivo en HDFS es la que hace que un CD rayado siga sonando bien.

Un dato histórico que rara vez se menciona: las sondas espaciales de la NASA transmiten datos codificados con Reed-Solomon desde los años setenta para tolerar el ruido de la señal en el espacio profundo, la misma familia de códigos que hoy protege discos rígidos en un data center.

sequenceDiagram
 participant Cliente
 participant Coordinador
 participant NodoSano1
 participant NodoSano2
 participant NodoCaido
 Cliente->>Coordinador: pide leer archivo
 Coordinador->>NodoCaido: solicita fragmento D4
 NodoCaido--xCoordinador: sin respuesta, disco roto
 Coordinador->>NodoSano1: solicita fragmento D5
 Coordinador->>NodoSano2: solicita paridad P1
 Coordinador->>Coordinador: reconstruye D4 por interpolacion
 Coordinador-->>Cliente: devuelve archivo completo

flowchart TD
 A["1 TB de datos utiles"] --> B["Replicacion 3x"]
 A --> C["Erasure coding RS 6-3"]
 B --> D["3 TB en disco"]
 C --> E["1.5 TB en disco"]

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: instalá pip install reedsolo, corré el script de sharding de este artículo y borrá a mano uno de los fragmentos guardados en disco para confirmar que la reconstrucción funciona antes de llevarlo a un sistema real.

Preguntas frecuentes

¿Erasure coding reemplaza completamente a la replicación?

No siempre. Sistemas como HDFS combinan ambas: replicación 3x para datos calientes de acceso frecuente, y erasure coding para datos fríos donde el ahorro de espacio pesa más que la velocidad de lectura.

¿Cuántos fragmentos puedo perder con un esquema RS 6-3?

Hasta 3 de los 9 fragmentos totales (6 de datos más 3 de paridad), sin importar cuáles. Perder un cuarto fragmento hace que el archivo ya no sea recuperable con ese esquema.

¿Erasure coding funciona igual para archivos chicos que para archivos grandes?

No conviene igual. Con archivos de pocos kilobytes, el overhead de metadata y la fragmentación superan el ahorro de espacio; por eso en la práctica se aplica sobre todo a datos de cierto tamaño mínimo.

¿Qué diferencia hay entre erasure coding y un simple checksum tipo CRC?

Un CRC solo detecta que hubo un error, no lo corrige ni reconstruye datos perdidos. Reed-Solomon puede detectar y corregir errores, o directamente reconstruir fragmentos enteros que faltan, siempre que sobrevivan suficientes fragmentos.

¿RAID 6 y HDFS erasure coding usan el mismo algoritmo?

Ambos se basan en Reed-Solomon sobre campos de Galois, pero con distintos parámetros: RAID 6 típicamente usa 2 discos de paridad fijos, mientras HDFS permite elegir el esquema k+m según la política configurada.

Referencias

• Reed-Solomon error correction (Wikipedia): historia, matemática y aplicaciones del código publicado en 1960.
• HDFS Erasure Coding (Apache Hadoop): guía oficial de políticas RS-6-3 y comandos de administración.
• reedsolo (GitHub): implementación en Python puro usada en los ejemplos de código de este artículo.
• Reed-Solomon (Backblaze Blog): explicación técnica de cómo un proveedor de backup aplica erasure coding en producción.
• RAID (Wikipedia): niveles de RAID, incluyendo la paridad doble de RAID 6.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.

Imagen destacada: Foto de Marc PEZIN en Unsplash