Partial-parallel-repair (PPR)
- 18 April 2016
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
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.Keywords
This publication has 27 references indexed in Scilit:
- PErasure: A parallel Cauchy Reed-Solomon coding library for GPUsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Accurate application progress analysis for large-scale parallel debuggingPublished by Association for Computing Machinery (ACM) ,2014
- Locally Repairable CodesIEEE Transactions on Information Theory, 2014
- The quantcast file systemProceedings of the VLDB Endowment, 2013
- XORing elephantsProceedings of the VLDB Endowment, 2013
- Windows Azure StoragePublished by Association for Computing Machinery (ACM) ,2011
- Optimization of Collective Communication Operations in MPICHThe International Journal of High Performance Computing Applications, 2005
- High Availability in DHTs: Erasure Coding vs. ReplicationLecture Notes in Computer Science, 2005
- Erasure Coding Vs. Replication: A Quantitative ComparisonLecture Notes in Computer Science, 2002
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960