PaperlayerView exact revision on arXiv

Source-linked AI summary

Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes

Anne-Marie Kermarrec, Gilles Straub, Nicolas Le Scouarnec

arXiv:1102.0204v3cs.ITcs.DC

TL;DR

Distributed storage systems need to restore lost redundancy efficiently, but conventional erasure-correcting repairs can impose substantial communication overhead. The paper introduces coordinated and adaptive regenerating codes for multiple and changing repairs, and finds that lazy repairs reduce disk-related costs but not network repair bandwidth.

  • Problem

    Distributed storage systems need efficient repair of lost redundancy, while conventional erasure-correcting repairs can require downloading and decoding the whole file.

  • Method

    The paper develops coordinated regenerating codes for simultaneous failures and adaptive regenerating codes that change repair parameters as the system state changes.

  • Results

    The proposed codes achieve optimal repairs, while lazy repairs cannot reduce network-related repair costs but can reduce disk-related repair costs.

  • Takeaways & Limitations

    Simultaneous coordination and adaptation extend regenerating codes to dynamic multi-failure repairs, while delayed repairs are useful for reducing disk-related costs.

Abstract

from arXiv · show

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).

I. INTRODUCTION

The paper extends regenerating codes to coordinated and adaptive repairs for multiple failures, addressing repair efficiency in distributed storage systems. It also shows that delayed repairs save disk-related costs but not network repair bandwidth.

  • I. INTRODUCTION: Coordinated regenerating codes support simultaneous repair of multiple failed devices by having each repaired device contact live devices and coordinate with the others.The paper derives closed-form optimal information-transfer quantities for repairing t > 1 devices from d live devices.
  • I. INTRODUCTION: Adaptive regenerating codes adjust the repair strategy as t and d change over time, achieving optimal repairs in a dynamic environment.The adaptive scheme is designed for changing system conditions and repair parameters.
  • I. INTRODUCTION: Lazy repairs do not reduce network-related repair costs for regenerating-like codes, although they can reduce disk-related costs such as disk I/O.This contrasts with traditional erasure correcting codes, where delaying repairs can reduce network repair costs.
  • I. INTRODUCTION: The work targets the gap between regenerating codes without coordinated simultaneous repair and erasure-correction approaches that repair by decoding the whole file.Erasure correcting codes can require downloading and decoding the entire file to regenerate one lost block.

III. COORDINATED REGENERATING CODES

Coordinated regenerating codes repair t failed devices jointly: each contacts d live devices, exchanges information with the other repairing devices, and stores regenerated data without centralized decoding. Their correctness and optimality are characterized through information-flow graphs, min-cut constraints, and network coding.

  • A. Repair algorithm: Each of the t failed devices independently collects data from d live devices, coordinates with the other t−1 repairs, and stores regenerated sub-blocks.The repair algorithm consists of collect, coordinate, and store stages; temporary collected and coordinated data can then be erased.
  • B. Information flow graphs: The information-flow graph models storage, network transfer, and repair coordination through capacities α, β, and β′, adding edges between devices repaired simultaneously.Repairing devices first receive β from live devices, exchange β′ with one another, and store α.
  • C. Achievable codes: The framework assumes t divides k and guarantees recovery from any k devices under the characterized repair process.The paper notes that no result is known here when t does not divide k.
  • C. Achievable codes: Theorem 1 states that a coordinated code is correct exactly when suitable β and β′ satisfy the derived constraints, while minimizing γ under those constraints gives an optimal code.The constraints ensure that every relevant recovery scenario provides at least the file size to a data collector.
  • C. Achievable codes: Correctness is established by comparing source-to-collector min-cuts with the file size and applying network coding to construct recoverable data when the cuts are sufficient.A min-cut below M prevents recovery, whereas sufficient min-cuts support a linear network code under the stated finite-field assumption.

D. Optimal tradeoffs

The optimal tradeoff problem minimizes storage cost α and repair cost γ subject to the coordinated-code constraints, with β and β′ optimized as design parameters.

  • D. Optimal tradeoffs: Optimal tradeoffs minimize storage cost α and repair cost γ under constraints (1) and (2), optimizing β and β′.The analysis assumes t divides k.
  • D. Optimal tradeoffs: Minimum Bandwidth Coordinated Regenerating Codes minimize repair bandwidth γ while also minimizing storage cost α.Figure 7 compares MBCR with Dimakis et al.’s MBR and erasure-correcting codes with delayed repairs.

1) MBCR codes:

MBCR codes target the minimum repair cost while maintaining minimum storage, and the paper proves their correctness through cut-based sufficiency arguments. In the supplied comparison, MBCR codes outperform the other shown approaches.

  • 1) MBCR codes:: MBCR optimality is analyzed by examining repair successions with u = [1, 1, . . . ] and u = [t, t, . . . ] while minimizing γ before α.The proof assumes α ≥ γ.
  • 1) MBCR codes:: The MBCR correctness proof shows that the selected α, β, and β′ values satisfy the sufficient condition for every relevant cut.The argument concludes that the resulting MBCR codes are correct.
  • 1) MBCR codes:: MBCR codes permanently outperform both erasure correcting codes and regenerating codes in total repair cost tγ for M = 32, d = 48, and k = 32.The comparison is shown in Figure 7.

2) MSCR codes:

MSCR codes minimize storage while also minimizing repair cost, and the paper derives their characterization from the general theorem. The resulting coordinated tradeoffs can improve on independent-repair regenerating codes.

  • 2) MSCR codes:: The MSCR correctness proof verifies the general sufficient condition using the code’s selected α, β, and β′ values.The proof concludes that MSCR codes are correct.
  • 2) MSCR codes:: MSCR codes provide the lowest possible storage cost α while minimizing repair cost γ.The paper compares them with Dimakis et al.’s MSR and delayed-repair erasure-correcting codes.
  • 2) MSCR codes:: Coordinated regenerating codes with t > 1 can achieve tradeoffs beyond those of independent repairs with t = 1.Intermediate points are obtained by numerically minimizing γ for different storage costs α under the general constraints.

3) General CR codes:

General coordinated regenerating-code results compare repair-cost tradeoffs across coordination levels, including MSCR and MBCR against established baselines.

  • MSCR codes permanently outperform erasure correcting codes and regenerating codes in total repair cost for M = 32, d = 48, and k = 32.
  • The storage–repair-cost tradeoff compares regenerating codes at t = 1 with MSCR and MBCR codes for each coordination level t.Costs are normalized by M/k.

IV. ADAPTIVE REGENERATING CODES

Adaptive regenerating codes relax fixed repair assumptions by selecting transfer parameters from the current repair setting. The paper proves these codes are correct and optimal for dynamic repair environments.

  • The paper defines adaptive codes for systems where the numbers of repaired and contacted devices can change over time.
  • Adaptive regenerating codes map each repair setting (t, d) to transfer amounts that minimize repair cost at runtime.The system state is defined by the number of devices repaired simultaneously and the number of live devices contacted.
  • Theorem 5 states that adaptive regenerating codes are both correct and optimal.
  • Correctness follows from satisfying the sufficient information-flow constraints for every recovery scenario.The proof uses the stated lemmas and transfer values defined in equation (4).
  • Optimality is proved by contradiction: any correct code with lower transfer amounts would contradict the optimality of the corresponding MSCR code.
  • Adaptive regenerating codes are particularly intended for dynamic systems in which failures may occur randomly and simultaneously.

B. Adaptive codes at the Minimum Bandwidth point

At the Minimum Bandwidth point, adaptive repair cannot improve on a static worst-case scheme. The analysis derives lower bounds showing that adaptation can cost as much as classical erasure-correcting codes.

  • The adaptive Minimum Bandwidth analysis concludes that its cost is as high as that of classical erasure correcting codes.
  • Because future repair settings are unknown, the analysis considers minimum admissible values d = k and t = 1 when deriving adaptive lower bounds.
  • For the second repair scenario, the per-node transfer bound is β1,k ≥ M/(2k − 1).
  • The resulting lower bound for adaptive repair at the Minimum Bandwidth point is γt0,d0 ≥ M/(2k + 1).
  • An adaptive Minimum Bandwidth scheme is more expensive than a static MBCR code configured for the worst case, t = 1 and d = k.

C. Performance

At the Minimum Storage point, adaptive regenerating codes are compared with independently repaired MFR codes. Under d + t = n, adaptive repair cost remains constant while MFR cost increases with the number of failures.

  • The comparison evaluates Adaptive Regenerating Codes at the MSR point against MFR codes whose t repairs are performed independently.
  • Under d + t = n, adaptive regenerating codes maintain constant average repair cost, whereas MFR cost increases with t.
  • Adaptive regenerating-code performance does not degrade as failures increase, unlike MFR codes constructed from independently repaired Dimakis et al. codes.
  • Figure 10 reports average repair cost γ for n = 64 and k = 32, with ARC permanently outperforming ECC and MFR codes.

D. Adaptive Coding Schemes

Adaptive regenerating codes support changing repair parameters, while coordinated repairs preserve optimality and enable delayed repairs. Their implementation uses substantially smaller codes than MFR when n=d+t is constant.

  • D. Adaptive Coding Schemes: MFR requires z=lcm{1...n−k}, yielding code lengths that grow exponentially with n−k.The implementation must support all β values associated with d∈{k...n−1}.
  • D. Adaptive Coding Schemes: When n=d+t is constant, the proposed implementation uses z=n−k sub-blocks, so code length grows linearly with n−k.This is much smaller than the MFR implementation, whose code length grows exponentially with n−k.
  • D. Adaptive Coding Schemes: Adaptive regenerating codes allow d and t to change across repairs while maintaining optimal repairs in a dynamic environment.The scheme adapts the repair strategy as system conditions change.
  • D. Adaptive Coding Schemes: Delaying repairs does not provide additional network-bandwidth savings for MSR or MBR codes when t is freely chosen.Thus, deliberately forcing larger simultaneous-repair groups is not beneficial for network repair cost.

B. I/O and disk reads

Lazy coordinated repairs reduce disk accesses and disk bandwidth while preserving network repair cost, addressing the pressure repairs place on non-failed devices. The broader exact-repair landscape remains incomplete, especially for vector codes and disk-read bounds.

  • B. I/O and disk reads: Coordinating t repairs requires d disk accesses instead of td accesses for t independent repairs.Each accessed disk is woken and performs one I/O operation.
  • B. I/O and disk reads: Lazy repair significantly reduces disk I/O and disk bandwidth for MSCR or MBCR, unlike MSR or MBR.The figure compares average I/O and average data read for n=64 and k=32.
  • B. I/O and disk reads: With constant n=d+t, coordinated repairs access n−t live devices instead of t(n−1) accesses for t successive repairs.MSCR with d=n−t has the same network repair cost as MSR with d=n−1.
  • B. I/O and disk reads: Lazy repairs reduce contacted disks and total disk data read by approximately a factor t, while network repair cost remains constant or rises only slightly.This makes lazy repairs useful when limiting the impact on non-failed disks is important.
  • B. I/O and disk reads: The amount of data read in regenerating codes lacks tight bounds, unlike the amount of data transferred.Reducing disk reads may require higher computational complexity or lower storage efficiency, motivating tighter bounds for coordinated and regular codes.
  • B. I/O and disk reads: Exact repair reconstructs the lost block identically, whereas functional repair reconstructs equivalent information in a different form.The exact-repair landscape includes scalar and vector codes, but exact repair for all vector-MS​​R devices is not fully solved.

B. Variations on Regenerating Codes

The paper extends regenerating-code design toward adaptive, coordinated, and locally repairable variants. These combinations broaden the repair trade-offs while exposing open questions about exact repair and disk efficiency.

  • B. Variations on Regenerating Codes: Locally repairable codes contact fewer than k devices and read most or all data from each, reducing network and disk-related repair costs.They are not optimal on the storage–repair trade-off because they cannot outperform a regenerating code with d=n−1.
  • B. Variations on Regenerating Codes: Coordinated regenerating codes support simultaneous repairs, while adaptive regenerating codes adjust the repair strategy to the system’s current state.The paper reports that coordinated codes outperform ordinary regenerating codes when multiple failures are repaired simultaneously.
  • B. Variations on Regenerating Codes: The paper studies combining coordinated regenerating codes with lazy repairs: network repair costs do not decrease, but disk-related costs can decrease.The conclusion identifies disk I/O and disk bandwidth as the relevant savings.
  • B. Variations on Regenerating Codes: The paper focuses on functional repair with optimal repair bandwidth, leaving exact coordinated or adaptive codes as a perspective.It also proposes studying exact codes optimized for disk I/O and bandwidth under lazy repairs.
  • B. Variations on Regenerating Codes: A locally repairable regenerating code would contact r selected devices among any d available devices, combining local repair with regenerating-code flexibility.This framework includes regenerating, locally repairable, and erasure-correcting codes as special cases.
Loading 1102.0204v3…