Erasure Coding-Oriented Data Update for Cloud Storage: A Survey

Yifei Xiao, Shijie Zhou, Linpeng ZhongIEEE Access 2020 · DOI

Abstract

Erasure coding (EC) has become the standard for providing resilient redundancy in large-scale cloud storage systems due to its superior storage efficiency compared to traditional replication. However, EC introduces significant overhead during data updates—a process far more frequent than data repair. This survey systematically categorizes existing data update (DU) optimization schemes, proposing new resource-based and tier-based classifications. By organizing these fragmented techniques into a cohesive framework, we highlight how cross-layer optimizations can address the computation, network, and I/O bottlenecks inherent in cloud-scale data updates.

Introduction: The Redundancy Dilemma

In modern cloud storage, data durability is non-negotiable. While traditional triple-replication ensures safety, it incurs a 200% storage overhead. Erasure coding offers a more efficient alternative, breaking data into $k$ fragments and generating $m$ parity blocks. This allows the system to tolerate up to $m$ failures with significantly less overhead.

However, this efficiency comes at a cost: the "update penalty." Unlike replication, where updating a file simply involves overwriting copies, EC requires recalculating parity blocks whenever a single data fragment changes. This "Data Update" (DU) process consumes CPU cycles for matrix multiplication, generates heavy network traffic to synchronize nodes, and increases disk I/O. Given that updates are ubiquitous in active cloud workloads, optimizing this process is critical for system performance.

A Systematic Taxonomy of Update Optimizations

To navigate the diverse landscape of DU research, we propose a resource-based classification that groups techniques by the specific bottleneck they target.

Taxonomy of state-of-the-art erasure coding update techniques categorized by application scope and resource optimization.

Resource-Based Classification

  1. Computation Optimization: These methods focus on the mathematical operations required to generate parity. Techniques like Bitmatrix Normalization (BN) reduce the complexity of finite field multiplications by transforming them into simpler XOR operations.
  2. Network Optimization: In geo-distributed or multi-rack environments, moving data is the primary cost. "Delta-based" updates send only the changes (deltas) rather than full blocks, while Tree-structured updates (T-Update) replace inefficient star-topologies with parallel transmission paths.
  3. I/O Optimization: Disk access is often the slowest link. Log-based updates and hybrid schemes aim to minimize random writes and consolidate update operations to improve physical disk throughput.

Mathematical Foundations and Key Insights

The core of erasure coding lies in the Generator Matrix. This matrix defines how data fragments are combined to produce parity.

Structure of a typical Generator Matrix in erasure coding, showing the systematic (identity) and parity portions.

As shown in the figure above, the generator matrix typically consists of an identity matrix (for systematic data) and a parity-generation portion (represented by $\alpha$ coefficients). Optimizing the density of "1s" in the binary representation of this matrix—a technique known as Bitmatrix Normalization—can reduce the number of XOR operations required for an update by 25-30%.

Beyond math, the survey introduces a Five-Tier Hybrid Framework:

  • Tier 1 (Coding): Matrix and coefficient optimizations.
  • Tier 2 (Scheduling): Task placement and timing.
  • Tier 3 (Network): Topology and traffic management.
  • Tier 4 (I/O): Disk layout and write strategies.
  • Tier 5 (Hardware): Leveraging SIMD instructions, FPGAs, or programmable switches (e.g., XORInc).

Performance Gains and Real-World Impact

Synthesizing results from various benchmarks (such as MSR Cambridge and Harvard NFS traces), several state-of-the-art methods demonstrate significant promise:

  • T-Update: By utilizing tree-structured paths instead of traditional star structures, update performance can improve by over 30%.
  • CAU (Cross-rack Aware Update): This technique reduces expensive cross-rack network traffic by over 40% by grouping updates logically.
  • Hardware Acceleration: Modern programmable switches can offload update math entirely from the storage nodes, with systems like XORInc claiming speedups of over 300% in specialized environments.

Future Directions

Despite these advancements, several challenges remain. Finding the mathematically optimal schedule for multi-block updates is an NP-complete problem, necessitating better heuristics. Furthermore, as cloud environments become more dynamic, update schemes must evolve from static configurations to adaptive, real-time systems that respond to fluctuating network bandwidth and hardware availability. The next frontier in cloud storage efficiency lies in joint optimization across these five tiers, moving away from isolated fixes toward holistic, hardware-aware update protocols.

Summary updated

BibTeX
@article{xiao2020erasure,
  author = {Yifei Xiao and Shijie Zhou and Linpeng Zhong},
  title = {{Erasure Coding-Oriented Data Update for Cloud Storage: A Survey}},
  journal = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.3033024},
}
Figure