Method of exact repair of pairs of failed storage nodes in a distributed data storage system and corresponding device

Patent metadata

Field	Value
Publication number	US-9104603-B2
Application number	US-201213622199-A
Country	US
Kind code	B2
Filing date	Sep 18, 2012
Priority date	Sep 19, 2011
Publication date	Aug 11, 2015
Grant date	Aug 11, 2015

Abstract

The invention proposes a method and corresponding device for exact repair of pairs of failed storage nodes interconnected in a distributed data storage system, which method and device are particularly efficient with respect to reliability while keeping the use of resources of the distributed storage network low.

First claim

The invention claimed is:

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.

2. The method according to claim 1 , wherein said first and said second set of non-failed storage nodes are determined such that said first and said second set of non-failed storage nodes comprise the same storage nodes.

3. The method according to claim 1 , wherein said first and said second set of non-failed storage nodes are determined such that said first and said second set of non-failed nodes comprise at least one distinct storage node.

4. The method according to claim 1 , wherein said first and said second set of non-failed storage nodes are determined such that said first and said second set of non-failed nodes comprise totally distinct storage nodes.

5. The method according to claim 2 , wherein a storage node is implemented by one or more distinct storage devices.

6. The method according to claim 2 , wherein a storage node is implemented by one or more same storage device.

7. A device for exact repair of sets of two failed storage nodes interconnected in a distributed storage system, wherein a data item of two blocks is encoded 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, said device comprising:
a memory; and
a processing unit coupled to the memory and configured to:
identify data lost by a failure of a pair of failed storage nodes, where lost data is identified 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, to choose a first new storage node and a second new storage node to replace said pair of failed storage nodes, and to determine a first set and a second set of at least three non-failed storage nodes for participating in said exact repair;
apply a first linear interference alignment operation to each of the storage nodes in said first set over sub-blocks stored by said each of the storage nodes, said first linear interference alignment operation being a scalar product between each of the sub-blocks stored by each of the storage nodes and a repair vector, thus obtaining a first result sub-block, said 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 apply a second linear interference alignment operation to each of the storage nodes in said second set over sub-blocks stored by each of 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 nodes in the second set is identical in all of said second result sub-block;
transmit all first result sub-blocks to said first new storage node, and transmit all second result sub-blocks to said second new storage node;
apply said first linear interference alignment operation to said first new storage node over all received sub-blocks, resulting in a third result sub-block that aligns interfering information about said first lost block, and apply said second linear interference alignment operation to said second new storage node over all received sub-blocks, resulting in a fourth result sub-block that aligns interfering information about said second lost block;
transmit the third result sub-block to said second new storage node, and transmit said fourth result sub-block to said first new storage node;
recover said first lost sub-blocks through calculation from all sub-blocks received by said first new storage node, and recover said second lost sub-blocks through calculation from all sub-blocks received by said second new storage node.

8. The device according to claim 7 , wherein said first and said second set of non-failed storage nodes are determined such that said first and said second set of non-failed storage nodes comprise the same storage nodes.

9. The device according to claim 7 , wherein said first and said second set of non-failed storage nodes are determined such that said first and said second set of non-failed nodes comprise at least one distinct storage node.

10. The device according to claim 7 , wherein said first and said second set of non-failed storage nodes are determined such that said first and said second set of non-failed nodes comprise totally distinct storage nodes.

11. The device according to claim 8 , wherein a storage node is implemented by one or more distinct storage devices.

12. The device according to claim 8 , wherein a storage node is implemented by one or more same

Assignees

• Thomson Licensing

Inventors

• Le Scouarnec Nicolas

Classifications

• G06F11/1092 Primary

  Rebuilding, e.g. when physically replacing a failing disk · CPC title