Practical Multiple Node Failure Recovery in Distributed Storage Systems

Abstract

As multiple node failures are becoming so frequent in distributed storage systems, many erasure coding techniques are emerging to handle such failures. In this paper we use the fractional repetition code to apply as a redundancy scheme for multiple failure recovery with optimized system cost. The fractional repetition (FR) code is a class of regenerating codes that consists of a concatenation of an outer maximum distance separable (MDS) code and an inner fractional repetition code that splits the data into several blocks and stores multiple replicas of each on different nodes in the system. We model the problem as an integer linear programming problem that uses modified versions of the fractional repetition code by allowing different block sizes, and minimizes the recovery cost of all dependent and independent multiple node failure scenarios. First, we generate an optimized block distribution scheme that minimizes the total system repair cost together with a full recovery plan with a node repair order for the system. Moreover, we account for the common scenario of having newcomer blocks. We allocate newcomers to nodes with minimal computations and without changing the original optimized plan. The problem is solved using genetic algorithms that search within the feasible solution space. Fast convergence validates the efficacy of our algorithms for different system parameters. Simulation results are shown to be close to optimal for the case of newly arriving blocks.