Parallel Data Regeneration Based on Multiple Trees with Network Coding in Distributed Storage System

摘要

Distributed storage systems can provide large-scale data storage and high data reliability by redundant schemes, such as replica and erasure codes. Redundant data may get lost due to frequent node failures in the system. The lost data is needed to be regenerated as soon as possible so as to maintain data availability and reliability. The direct way for reducing regeneration time is to reduce network traffic in regeneration. Compared with that way, tree-structured regeneration achieves shorter regeneration time by constructing better tree-structured topology to increase transmission bandwidth. However, some bandwidth of many other edges beyond the tree is not utilized to speed up transmission in tree-structured regeneration. In this paper, we consider to use multiple edge-disjoint trees to parallel regenerate the lost data, and analyze the total regeneration time. We deduce the formula about optimal regeneration time, and propose an approximate construction algorithm with polynomial time complexity for the optimal multiple regeneration trees. Our experiments shows, the regeneration time reduces 62 % compared with common tree-structured scheme, and the file availability reaches almost 99 %.