Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes

Anne-Marie Kermarrec, Gilles Straub, Nicolas Le Scouarnec

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 failures in such codes. We go beyond existing work (i.e., regenerating codes by Dimakis et al.) by describing (i) coordinated regenerating codes (also known as cooperative regenerating codes) which support the simultaneous repair of multiple devices, and (ii) adaptive regenerating codes which allow adapting the parameters at each repair. Similarly to regenerating codes by Dimakis et al., these codes achieve the optimal tradeoff between storage and the repair bandwidth. Based on these extended regenerating codes, we study the impact of lazy repairs applied to regenerating codes and conclude that lazy repairs cannot reduce the costs in term of network bandwidth but allow reducing the disk-related costs (disk bandwidth and disk I/O).
BibTeX
@misc{kermarrec2011repairing,
  author = {Anne-Marie Kermarrec and Gilles Straub and Nicolas Le Scouarnec},
  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