Random linear coding approach to distributed data storage

Patent metadata

Field	Value
Publication number	US-9680928-B2
Application number	US-201514788968-A
Country	US
Kind code	B2
Filing date	Jul 1, 2015
Priority date	Dec 30, 2004
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

First claim

What is claimed is:

1. A method comprising:
at a downloader computer, retrieving a file that has been stored as network coded parts comprising code vectors that are distributed among a plurality of storage peers of a distributed storage system by:
collecting ones of the code vectors associated with the file from ones of the storage peers;
generating a matrix of the collected ones of the code vectors, the matrix having a dimension; and
recovering the file using the collected ones of the code vectors when the dimension of the matrix is equal to a number of code vectors that are distributed among a plurality of storage peers.

2. The method of claim 1 wherein recovering the file using the collected ones of the code vectors comprises using a number of the collected ones of the code vectors that is less than the number of code vectors that are distributed among a plurality of storage peers.

3. The method of claim 2 wherein the file is broken into m pieces and wherein the m pieces of the file are viewed as elements f 1 , f 2 , . . . f k of a particular peer in which are vectors of size s in a field F of size q.

4. The method of claim 3 wherein an element of a peer f i can be represented as

f
i

=

∑

j
=
1

m

⁢

⁢

β
i

⁢

c
i

,

Pr
⁡

(

β
i

=
β

)

=

1
q

⁢

∀

β
∈

F
q

for r peers, wherein chunks of said file are denoted as c i , i=1, 2, . . . m, and each peer stores k random combinations of c i 's, and an associated code vector (β 1 , β 2 , . . . , β m ) is stored for each of said k pieces.

5. The method of claim 4 wherein there are a total of kr m-dimensional code vectors available for said downloader, wherein r is the number of peers to which the downloader can connect to after spending some time in the network and wherein each of said code vectors represents a random mixture of file pieces, wherein a collection of said code vectors can be viewed as a kr×m matrix over F q and wherein the file can be recovered once a rank of said matrix is m.

6. A non-transitory computer readable medium having computer readable code thereon, the medium comprising instructions for:
retrieving, at a downloader computer, a file that has been stored as network coded parts comprising code vectors that are distributed among a plurality of storage peers of a distributed storage system by:
collecting ones of the code vectors associated with the file from ones of the storage peers;
generating a matrix of the collected ones of the code vectors, the matrix having a dimension; and
recovering the file using the collected ones of the code vectors when the dimension of the matrix is equal to a number of code vectors that are distributed among a plurality of storage peers.

7. The computer readable medium of claim 6 wherein recovering the file using the collected ones of the code vectors comprises using a number of the collected ones of the code vectors that is less than the number of code vectors that are distributed among a plurality of storage peers.

8. The computer readable medium of claim 7 wherein the file is broken into m pieces and wherein the m pieces of the file are viewed as elements f 1 , f 2 , . . . f k of a particular peer in which are vectors of size s in a field F of size q.

9. The computer readable medium of claim 8 wherein an element of a peer f i can be represented as

f
i

=

∑

j
=
1

m

⁢

⁢

β
i

⁢

c
i

,

Pr
⁡

(

β
i

=
β

)

=

1
q

⁢

∀

β
∈

F
q

for r peers, wherein chunks of said file are denoted as c i , i=1, 2, . . . m, and each peer stores k random combinations of c i 's, and an associated code vector (β 1 , β 2 , . . . , β m ) is stored for each of said k pieces.

10. The computer readable medium of claim 9 wherein there are a total of kr m-dimensional code vectors available for said downloader, wherein r is the number of peers to which the downloader can connect to after spending some time in the network and wherein each of said code vectors represents a random mixture of file pieces, wherein a collection of said code vectors can be viewed as a kr×m matrix over F q and wherein the file can be recovered once the rank of said matrix is m.

11. A downloader comprising:
a memory;
a processor;
a communications interface;
an interconnection mechanism coupling the memory, the processor and the communications interface; and
wherein the memory is encoded with an application that retrieves a file that has been stored as network coded parts comprising code vectors that are distributed among a plurality of storage peers of a distributed storage system by:
collecting

Assignees

• Massachusetts Inst Technology
• Nat Science Found

Inventors

• Medard Muriel
• Deb Supratim
• Koetter Ralf

Classifications

• H04L67/104

  Peer-to-peer [P2P] networks · CPC title

• H04L67/1095 Primary

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title

• G06F17/30209

  Physics · mapped topic

• G06F16/1837 Primary

  Management specially adapted to peer-to-peer storage networks (topology management mechanisms of peer-to-peer networks H04L67/1042) · CPC title