摘要
To reduce the time required to complete the regeneration process of erasure codes, we propose a Tree-structured Parallel Regeneration (TPR) scheme for multiple data losses in distributed storage systems. Under the scheme, two algorithms are proposed for the construction of multiple regeneration trees, namely the edge-disjoint algorithm and edge-sharing algorithm. The edge-disjoint algorithm constructs multiple independent trees, and is simple and appropriate for environments where newcomers and their providers are distributed over a large area and have few intersections. The edge-sharing algorithm constructs multiple trees that compete to utilize the bandwidth, and make a better utilization of the bandwidth, although it needs to measure the available band-width and deal with the bandwidth changes; it is therefore difficult to implement in practical systems. The parallel regeneration for multiple data losses of TPR primarily includes two optimizations: firstly, transferring the data through the bandwidth optimized-paths in a pipe-line manner; secondly, executing data regeneration over multiple trees in parallel. To evaluate the proposal, we implement an event-based simulator and make a detailed comparison with some popular regeneration methods. The quantitative comparison results show that the use of TPR employing either the edge-disjoint algorithm or edge-sharing algorithm reduces the regeneration time significantly.
To reduce the time required to complete the regeneration process of erasure codes, we propose a Tree-structured Parallel Regeneration （TPR） scheme for multiple data losses in distributed storage systems. Under the scheme, two algorithms are proposed for the construction of multiple regeneration trees, namely the edge-disjoint algorithm and edge- sharing algorithm. The edge-disjoint algorithm constructs multiple independent trees, and is simple and appropriate for environments where newcomers and their providers are distributed over a large area and have few intersections. The edge-sharing algorithm constructs multiple trees that compete to utilize the bandwidth, and make a better utilization of the bandwidth, alth- ough it needs to measure the available band- width and deal with the bandwidth changes; it is therefore difficult to implement in practical systems. The parallel regeneration for multiple data losses of TPR primarily includes two op- timizations： firstly, transferring the data thr ough the bandwidth optimized-paths in a pipe line manner; secondly, executing data regen eration over multiple trees in parallel. To eva- luate the proposal, we implement an event based simulator and make a detailed compari son with some popular regeneration methods. The quantitative comparison results show that the use of TPR employing either the edge-dis joint algorithm or edge-sharing algorithm re duces the regeneration time significantly.
基金
supported by the National Grand Fundamental Research of China (973 Program) under Grant No. 2011CB302601
the National High Technology Research and Development of China (863 Program) under GrantNo. 2013AA01A213
the National Natural Science Foundation of China under Grant No. 60873215
the Natural Science Foundation for Distinguished Young Scholars of Hunan Province under Grant No. S2010J5050
Specialized Research Fund for the Doctoral Program of Higher Education under Grant No. 20124307110015
