Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes

Anne-Marie Kermarrec, Nicolas Le Scouarnec, Gilles Straub

Distributed storage systems, such as those powering Google and Amazon, rely on data fragmentation and distribution across numerous disks to ensure reliability. When a disk fails, the system must perform a "self-repair" to restore the lost data fragment. This paper, originally presented at NetCod 2011, establishes a theoretical and practical framework for handling multiple simultaneous node failures using Coordinated and Adaptive Regenerating Codes.

The Challenge of Simultaneous Failures and Lazy Repairs

In large-scale data centers, disk failures are frequent. Traditional Erasure Correcting Codes (like Reed-Solomon) are storage-efficient but costly to repair, often requiring the download of an entire file to fix a single lost fragment. Regenerating Codes (RC) improved this by minimizing repair bandwidth for single failures. However, two practical challenges remained:

  1. Simultaneous Failures: Standard RC treats multiple failures as independent events, missing opportunities for collective efficiency.
  2. Lazy Repairs: System administrators often defer repairs until a certain number of failures ($t$) occur to minimize operational overhead.
Figure 1: Delayed (lazy) repairs wait for multiple failures before triggering a restoration process.

Coordinated and Adaptive Regenerating Codes

The authors extend Regenerating Code theory through two primary innovations:

Coordinated Regenerating Codes (CRC)

CRC introduces a three-step repair process for $t$ failed nodes:

  1. Collect: Each of the $t$ new nodes downloads small data chunks from $d$ surviving nodes.
  2. Coordinate: The $t$ new nodes exchange information among themselves to "fill in the gaps."
  3. Store: Each node processes the combined data to store its final fragment.
Figure 5: Coordinated regenerating codes allow new nodes to communicate with each other, reducing total repair bandwidth.

Adaptive Regenerating Codes

Unlike static models, adaptive codes allow the number of live nodes ($d$) and failed nodes ($t$) to vary at each repair event while maintaining mathematical optimality. Using Information Flow Graphs and Network Coding theory, the authors derived fundamental limits for storage and bandwidth in these coordinated scenarios.

Key Insights: The Lazy Repair Paradox

A significant finding is the "Lazy Repair Paradox." For traditional codes, waiting for more failures reduces network traffic. For Regenerating Codes, network bandwidth costs remain flat or may even increase. However, lazy repair remains crucial because it drastically reduces Disk I/O. By repairing $t$ nodes simultaneously, surviving disks are accessed only once instead of $t$ times, addressing the primary bottleneck in modern data centers.

Performance and Practicality

The proposed MSCR (Minimum Storage Coordinated Regenerating) and MBCR (Minimum Bandwidth Coordinated Regenerating) codes consistently outperform traditional erasure codes and standard RC during multiple failures. Furthermore, the implementation is computationally efficient; the code length grows linearly with system size ($n-k$), making it far more practical than previous exponential-growth approaches.

Future Directions

While this work focuses on "functional repair" (mathematically equivalent fragments), industry often prefers "exact repair" (bit-for-bit copies). Future research aims to bridge this gap and integrate coordinated repairs with Locally Repairable Codes (LRC), the current standard in systems like Windows Azure.

Summary updated

Abstract

Erasure correcting codes are widely used to ensure data persistence in distributed storage systems. This paper addresses the simultaneous repair of multiple failure in such codes. We go beyond existing work (i.e., regenerating codes by Dimakis et al.) and propose coordinated regenerating codes allowing devices to coordinate during simultaneous repairs thus further reducing the costs. We define optimal coordinated regenerating codes outperforming existing codes for simultaneous repairs with respect to both storage and repair costs. We prove that deliberately delaying repairs does not bring additional gains (i.e., regenerating codes are optimal as long as each failure can be repaired before a second one occurs). Finally, we propose adaptive regenerating codes that self-adapt to the system state and prove they are optimal.
BibTeX
@misc{kermarrec2011repairing,
  author = {Anne-Marie Kermarrec and Nicolas Le Scouarnec and Gilles Straub},
  title = {{Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes}},
  year = {2011},
  eprint = {1102.0204},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1102.0204},
}
Figure