Failure tolerant data storage

Abstract

A method for storing data across a plurality of N storage devices S 1 . . . S N , wherein at least certain of the storage devices have a storage capacity C MIN =C J ≦C K . . . ≦C MAX , and C MIN <C MAX involves establishing a first capacity band equal in capacity to C MIN in each of the storage devices; encoding a collection of source data with an erasure encoder to produce F J erasure codewords; allocating the F J erasure codewords uniformly among the N storage devices S 1 . . . S N ; establishing a second capacity band equal in capacity to C K −C J in each of the storage devices having capacity ≧C J ; encoding a collection of source data with an erasure encoder to produce F K erasure codewords; and allocating the F K erasure codewords uniformly among the storage devices S 1 . . . S N having capacity ≧C J . This abstract is not to be considered limiting, since other embodiments may deviate from the features described in this abstract.

1 . A method for storing data across a plurality of N storage devices S 1  . . . S N , wherein at least certain of the storage devices have a storage capacity C MIN =C J ≦C K  . . . ≦C MAX , and C MIN <C MAX  with the method comprising:
 establishing a first capacity band equal in capacity to C MIN  in each of the storage devices;   encoding a collection of source data with an erasure encoder to produce F J  erasure codewords;   allocating the F J  erasure codewords uniformly among the N storage devices S 1  . . . S N ;   establishing a second capacity band equal in capacity to C K −C J  in each of the storage devices having capacity ≧C J ;   encoding a collection of source data with an erasure encoder to produce F K  erasure codewords; and   allocating the F K  erasure codewords uniformly among the storage devices S 1  . . . S N  having capacity ≧C J .   
     
     
         2 . The method according to  claim 1 , wherein the erasure codewords are encoded using a RAID parity encoder. 
     
     
         3 . The method according to  claim 1 , wherein the erasure codewords are encoded using a fountain encoder. 
     
     
         4 . The method according to  claim 1 , wherein the erasure codewords are encoded using a simple data duplication encoder. 
     
     
         5 . The method according to  claim 1 , wherein the storage devices S 1  . . . S N  comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory. 
     
     
         6 . The method according to  claim 1 , further comprising:
 determining that a storage device S N+1  is available for storage of the codewords;   reallocating the codewords across the plurality of storage devices S 1  . . . S N+1 .   
     
     
         7 . The method according to  claim 1 , further comprising:
 determining that storage device S P , being any one of storage devices S 1  . . . S N  is no longer available for storage of the codewords;   reallocating the codewords across the plurality of storage devices S 1  . . . S N  excluding S P .   
     
     
         8 . The method according to  claim 1 , further comprising:
 determining that storage device S P , being any one of storage devices S 1  . . . S N  is no longer available for storage of the codewords;   determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S 1  . . . S N  excluding S P ; and   if not, establishing that an error condition exists.   
     
     
         9 . A method for storing data across a plurality of N storage devices S 1  . . . S N , wherein at least certain of the storage devices have a storage capacity C MIN =C J ≦C K  . . . ≦C MAX , and C MIN <C MAX  with the method comprising:
 establishing a first capacity band equal in capacity to C MIN  in each of the storage devices;   encoding a collection of source data with an erasure encoder to produce F J  erasure codewords, wherein the erasure codewords are encoded using an encoder selected from the group consisting of a RAID parity encoder, a fountain encoder, and simple data duplication encoder;   allocating the F J  erasure codewords uniformly among the N storage devices S 1  . . . S N ;   establishing a second capacity band equal in capacity to C K −C J  in each of the storage devices having capacity ≧C J ;   encoding a collection of source data with an erasure encoder to produce F K  erasure codewords;   allocating the F K  erasure codewords uniformly among the storage devices S 1  . . . S N  having capacity ≧C J ;   determining that a storage device S N+1  is available for storage of the codewords; and   reallocating the codewords across the plurality of storage devices S 1  . . . S N+1 .   
     
     
         10 . The method according to  claim 9 , wherein the storage devices S 1  . . . S N  comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory. 
     
     
         11 . The method according to  claim 9 , further comprising:
 determining that storage device S P , being any one of storage devices S 1  . . . S N  is no longer available for storage of the codewords;   reallocating the codewords across the plurality of storage devices S 1  . . . S N  excluding S P .   
     
     
         12 . The method according to  claim 9 , further comprising:
 determining that storage device S P , being any one of storage devices S 1  . . . S N  is no longer available for storage of the codewords;   determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S 1  . . . S N  excluding S P ; and   if not, establishing that an error condition exists.   
     
     
         13 . A computer readable storage medium storing instructions that, when executed on one or more programmed processors, carry out a method for storing data across a plurality of N storage devices S 1  . . . S N , wherein at least certain of the storage devices have a storage capacity C MIN =C J ≦C K  . . . ≦C MAX , and C MIN <C MAX  comprising:
 establishing a first capacity band equal in capacity to C MIN  in each of the storage devices;   encoding a collection of source data with an erasure encoder to produce F J  erasure codewords;   allocating the F J  erasure codewords uniformly among the N storage devices S 1  . . . S N ;   establishing a second capacity band equal in capacity to C K −C J  in each of the storage devices having capacity ≧C J ;   encoding a collection of source data with an erasure encoder to produce F K  erasure codewords; and   allocating the F K  erasure codewords uniformly among the storage devices S 1  . . . S N  having capacity ≧C J .   
     
     
         14 . The computer readable storage medium according to  claim 13 , wherein the erasure codewords are encoded using a RAID parity encoder. 
     
     
         15 . The computer readable storage medium according to  claim 13 , wherein the erasure codewords are encoded using a fountain encoder. 
     
     
         16 . The computer readable storage medium according to  claim 13 , wherein the erasure codewords are encoded using a simple data duplication encoder. 
     
     
         17 . The computer readable storage medium according to  claim 13 , wherein the storage devices S 1  . . . S N  comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory. 
     
     
         18 . The computer readable storage medium according to  claim 13 , further comprising:
 determining that a storage device S N+1  is available for storage of the codewords;   reallocating the codewords across the plurality of storage devices S 1  . . . S N+1 .   
     
     
         19 . The method according to  claim 13 , further comprising:
 determining that storage device S P , being any one of storage devices S 1  . . . S N  is no longer available for storage of the codewords;   reallocating the codewords across the plurality of storage devices S 1  . . . S N  excluding S P .   
     
     
         20 . The computer readable storage medium according to  claim 13 , further comprising:
 determining that storage device S P , being any one of storage devices S 1  . . . S N  is no longer available for storage of the codewords;   determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S 1  . . . S N  excluding S P ; and   if not, establishing that an error condition exists.