Repairing Multiple Data Losses by Parallel Max-min Trees Based on Regenerating Codes in Distributed Storage Systems

Due to high storage efficiency, erasure codes are recently used to provide high data reliability in distributed storage systems. When multiple data loses in system, regeneration time for them demands to be as short as possible so as to keep data availbility and reliability. Common way is to repair them one by one, which prolongs the regeneration time. Tree-structured regeneration may reduce regeneration time when regenerating one single node failure by relaying the network traffic, and is also extended to regenerate multiple data losses. In this paper, based on regenerating codes which achieve minimal network traffic during the regeneration, we consider reducing regeneration time by using multiple max-min trees to parallel regenerate multiple data losses. And we proposed an algorithm: bandwidth-sharing max-min algorithm (BSM2RC) to construct multiple parallel max-min trees. It realizes efficient bandwidth utilization by maximizing the minimal bottleneck edge weight of multiple regeneration trees, thus improve regeneration efficiency. Our simulation experiment shows that multiple parallel max-min trees reduce total regeneration time for multiple data losses significantly, and thus enhance system reliability, compared with existing regeneration scheme.