Partial-parallel-repair (PPR)

TLDR

Erasure‑coded storage, especially Reed‑Solomon codes, offers lower overhead and higher reliability than replication, but its reconstruction time suffers from network bottlenecks, and existing solutions either add storage or restrict coding parameters. The authors propose Partial Parallel Repair (PPR), a distributed reconstruction technique that splits reconstruction into small partial operations scheduled across nodes already involved in data reconstruction. PPR employs a distributed protocol that progressively merges partial results from participating nodes and is applied atop existing codes such as Local Reconstruction Code and Rotated Reed‑Solomon to further reduce reconstruction time. Theoretically, PPR reduces network transfer time to ⌈log₂(k+1)⌉ steps versus k for Reed‑Solomon, and experiments confirm significant reductions in repair and degraded‑read times without extra storage overhead.

Abstract

With the explosion of data in applications all around us, erasure coded storage has emerged as an attractive alternative to replication because even with significantly lower storage overhead, they provide better reliability against data loss. Reed-Solomon code is the most widely used erasure code because it provides maximum reliability for a given storage overhead and is flexible in the choice of coding parameters that determine the achievable reliability. However, reconstruction time for unavailable data becomes prohibitively long mainly because of network bottlenecks. Some proposed solutions either use additional storage or limit the coding parameters that can be used. In this paper, we propose a novel distributed reconstruction technique, called Partial Parallel Repair (PPR), which divides the reconstruction operation to small partial operations and schedules them on multiple nodes already involved in the data reconstruction. Then a distributed protocol progressively combines these partial results to reconstruct the unavailable data blocks and this technique reduces the network pressure. Theoretically, our technique can complete the network transfer in ⌈(log2(k + 1))⌉ time, compared to k time needed for a (k, m) Reed-Solomon code. Our experiments show that PPR reduces repair time and degraded read time significantly. Moreover, our technique is compatible with existing erasure codes and does not require any additional storage overhead. We demonstrate this by overlaying PPR on top of two prior schemes, Local Reconstruction Code and Rotated Reed-Solomon code, to gain additional savings in reconstruction time.