Patent ID: 9104603
Filing Date: 2015-08-11
Classification: G06F

Abstract:
1. A method for exact repair of sets of two failed storage nodes interconnected in a distributed storage system, the method comprising: encoding a data item of two blocks into n blocks, each of the n blocks being stored on a storage node belonging to a set of n storage nodes, each of the n blocks comprising a number of sub-blocks greater than two, and n is an integer; identifying data lost by a failure of a pair of failed storage nodes as a first lost block and a second lost block, said first lost block comprising first lost sub-blocks and said second lost block comprising second lost sub-blocks, choosing a first new storage node and a second new storage node to replace said pair of failed storage nodes, and determining a first set and a second set of at least three non-failed storage nodes for participating in said exact repair; applying a first linear interference alignment operation to each of the storage nodes in said first set over sub-blocks stored by the storage nodes, said first linear interference alignment operation being a scalar product between each of the sub-blocks stored by said each of the storage nodes and a repair vector, thus obtaining a first result sub-block, the repair vector being chosen so that information about each of the sub-blocks stored by the storage nodes in the first set is identical in all of said first result sub-block, and applying a second linear interference alignment operation to each of the storage nodes in said second set over sub-blocks stored by the storage nodes, said second linear interference alignment operation being a scalar product between each of the sub-blocks stored by said each of the storage nodes and a repair vector, thus obtaining a second result sub-block, said repair vector being chosen so that information about each of the sub-blocks stored by the storage nodes in the second set is identical in all of said second result sub-block; transferring all first result sub-blocks to said first new storage node, and transferring all second result sub-blocks to said second new storage node; applying said first linear interference alignment operation to said first new storage node over the transferred sub-blocks, resulting in a third result sub-block that aligns interfering information about said first lost block, and applying said second linear interference alignment operation to said second new storage node over the transferred sub-blocks, resulting in a fourth result sub-block that aligns interfering information about said second lost block; transferring the third result sub-block to said second new storage node, and transferring said fourth result sub-block to said first new storage node; and recovering by calculating said first lost sub-blocks from all sub-blocks received by said first new storage node, and calculating said second lost sub-blocks from all sub-blocks received by said second new storage node.