Random linear coding approach to distributed data storage

• US 9,680,928 B2
• Filed: 07/01/2015
• Issued: 06/13/2017
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: National Science Foundation (Government of the United States of America)
• Inventors: Medard, Muriel, Deb, Supratim, Koetter, Ralf
• Primary Examiner(s): Baturay, Alicia
• Application Number:
  US14/788,968
• Publication Number:
  US 20150304419A1
• Time in Patent Office: 713 Days
• Field of Search: 709217
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

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.

Claims

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₁, f₂, . . . 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

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₁, f₂, . . . 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

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 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.

12. The downloader of claim 11 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.

13. The downloader of claim 12 wherein the file is broken into m pieces and wherein the m pieces of the file are viewed as elements f₁, f₂, . . . f_k of a particular peer in which are vectors of size s in a field F of size q.

14. The downloader of claim 13 wherein an element of a peer f_i can be represented as

15. The downloader of claim 14 wherein there are a total of kr m-dimensional code vectors available for said downloader, 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.