What is Erasure Coding?

Erasure coding (EC) is a data protection technique used in distributed storage systems to improve fault tolerance while minimizing storage overhead. It divides data into fragments, adds redundant pieces, and stores them across multiple locations. If some fragments are lost due to failures, the original data can still be reconstructed.

---

Core Idea

• Efficient Data Redundancy: Unlike simple replication (e.g., making three copies of data), erasure coding provides reliability with less storage overhead.
• Mathematical Encoding: Data is split into k original chunks and m parity chunks, forming an (k + m) scheme.
• Fault Recovery: If up to m chunks are lost, they can be reconstructed using the remaining k data and parity chunks.

---

How It Works (Markdown Explanation)

1. Data Splitting: A file is divided into k data blocks.
2. Parity Generation: m additional parity blocks are computed using mathematical functions (e.g., Reed-Solomon codes).
3. Storage: The k + m blocks are distributed across different storage nodes.
4. Failure Recovery: If some blocks are lost, the missing data is reconstructed using the remaining available blocks.

---

Example (Reed-Solomon Code with (4+2) Scheme)

• Original data: [D1, D2, D3, D4]
• Parity data: [P1, P2]
• Storage nodes contain: [D1, D2, D3, D4, P1, P2]
• If D3 and P1 are lost, the original file can still be reconstructed from [D1, D2, D4, P2].

---

Advantages

• More Storage Efficient: Requires less space than full replication (e.g., 3-way replication uses 300% storage, while EC with (4+2) uses only 150%).
• Fault-Tolerant: Can recover from multiple node failures.

---

Disadvantages

• Computational Overhead: Encoding and decoding require CPU resources.
• Latency: Read performance is slower than simple replication due to decoding operations.

---

Similar Technologies

Technology	Purpose
RAID (Redundant Array of Independent Disks)	Uses mirroring and parity for redundancy.
Replication (3-way, 2-way)	Simple data duplication for fault tolerance.
Network Coding	Optimized data transmission with redundancy.

---

Applications

Erasure coding is widely used in cloud storage (e.g., Amazon S3, Microsoft Azure, Google Cloud), distributed file systems (e.g., HDFS, Ceph), and data archival to reduce storage costs while ensuring high reliability.