Optimal block repairs in geo-distributed storage systems

A data repairing method, comprising taking a unit of input data with failed blocks as input;

• checking and reporting data loss if the said set of failed blocks forms a grid that spans (m2+1) adjacent rows and (m1+1) adjacent columns, which indicates the set of failed blocks cannot be repaired;
• finding all columns with no more than m2 failed blocks and repairing failed blocks in these columns in parallel;
• finding the rows with no more than m1 failed blocks, selecting the row with the maximum number of failed blocks, and repairing all failed blocks in the said selected row;
• repeating the third and fourth steps until all blocks in the said set of failed blocks for a unit of input data are repaired.

A data repairing method, comprising taking a row of blocks that has f failed blocks as input, where f is a positive integer;

• selecting a region as the main region and a rack as the main rack;
• selecting the smallest number of helper regions, such that the total number of surviving blocks in this row in all said helper regions and the said main region is at least k1;
• transferring k1 surviving blocks to the said main rack either when f>1 or when f=1 and the number of surviving blocks in each of the said helper regions equals one;
• selecting a rack that stores at least one surviving block in each of the said helper regions as the relay, collecting other surviving blocks in racks within the same region at each of the said relays, computing a partially decoded block at each of the said relays using an erasure code and the said collected surviving blocks at each of the said relays, and transferring all said partially decoded blocks to the said main rack, when f=1 and the number of surviving blocks in each of the said helper regions is greater than one;
• decoding all of the said f failed blocks in the said row of blocks in the said main rack;
• redistributing the said decoded f blocks from the said main rack to other racks and regions.