US20090319869A1 - Failure tolerant data storage - Google Patents

Abstract

A method for storing data across a plurality of N storage devices S₁. . . 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_MAXinvolves establishing a first capacity band equal in capacity to C_MINin each of the storage devices; encoding a collection of source data with an erasure encoder to produce F_Jerasure codewords; allocating the F_Jerasure codewords uniformly among the N storage devices S₁. . . S_N; establishing a second capacity band equal in capacity to C_K−C_Jin each of the storage devices having capacity ≧C_J; encoding a collection of source data with an erasure encoder to produce F_Kerasure codewords; and allocating the F_Kerasure codewords uniformly among the storage devices S₁. . . S_Nhaving capacity ≧C_J. This abstract is not to be considered limiting, since other embodiments may deviate from the features described in this abstract.

Description

CROSS REFERENCE TO RELATED DOCUMENTS
• This application is a divisional of allowed U.S. application Ser. No. 11/297,271 filed Dec. 8, 2005 and is related to U.S. application Ser. No. 12/077,690 filed Mar. 20, 2008 (also a divisional of Ser. No. 11/297,271), both of which are hereby incorporated herein by reference.
COPYRIGHT NOTICE
• A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND
• RAID (Redundant Array of Inexpensive Disks or Redundant Array of Independent Disks) systems are in common use for securely and redundantly storing large amounts of data. The term RAID represents a family of techniques for managing collections of disks in such a way that desirable cost, availability, and performance properties are provided to host computing environments. RAID arrays come in various operating levels which are designated as RAID level 0 (RAID-0), RAID level 6 (RAID-6), etc. Additionally, there are multiple combinations of the various RAID levels that form hybrid RAID levels. Each RAID level represents a different form of data management and data storage within the RAID disk drive array. In conventional RAID systems and the like, the capacity of each disk in a given system generally has identical, or virtually identical storage capacity C_Jsuch that C=C₁=C₂= . . . =C_Nfor each of N storage systems. This makes distribution of storage among the various storage devices simple. While storage devices with capacity greater than C may be used in such a system, capacity over and above C is not used, resulting in an equivalent capacity that is limited to C. These disks are also normally very tightly coupled to a controller, and typically are contained within a single enclosure.
• In home entertainment and other home network applications, as well as many business applications, storage devices tend to be added incrementally as storage needs grow. For example, a network including a television set top box, one or more home computers and a Personal Video recorder is generally established based on existing needs at the time of acquisition of each component, and often without regard for the data security provided in more advanced and secure storage systems such as RAID systems. In addition these systems are loosely coupled, over a network. In such systems, it is generally the case that C₁≠C₂≠ . . . ≠C_Nand it is not self evident from the operation of conventional RAID systems how one might distribute storage in order to assure secure storage in the face of an evolving network in a manner that assures no data loss if one component should fail. In fact, it is not evident how to proceed if any one of C_J≠C_Kin such a system. As a consequence, RAID technology and similar technologies are not widely used in such environments. Thus, conventional backup techniques (which are often not rigorously deployed and enforced) are generally used to protect data, if anything is done at all. This often results in large amounts of data going unprotected against accidental erasure or destruction or hardware or software failure.
BRIEF DESCRIPTION OF THE DRAWINGS
• Certain illustrative embodiments illustrating organization and method of operation, together with objects and advantages may be best understood by reference detailed description that follows taken in conjunction with the accompanying drawings in which:
• FIG. 1 is a block diagram of anexemplary storage system60 using an exemplary erasure encoding system (fountain coding) consistent with certain embodiments of the present invention.
• FIG. 2 is a simplified block diagram ofstorage system60 consistent with certain embodiments of the present invention.
• FIG. 3 is a simplified block diagram ofstorage system60 illustrating loss of storage device S_P, consistent with certain embodiments of the present invention.
• FIG. 4 is a simplified block diagram ofstorage system60 illustrating addition of a new storage device S_N+1, consistent with certain embodiments of the present invention.
• FIG. 5 is a flow chart of anexemplary process80 for allocation of storage using erasure coding, consistent with certain embodiments of the present invention.
• FIG. 6 is a more detailed flow chart of anexemplary allocation process100 using erasure coding, consistent with certain embodiments of the present invention.
• FIG. 7 is a flow chart of anexemplary process150 for allocation, storage and retrieval of erasure encoded data, consistent with certain embodiments of the present invention.
• FIG. 8 is a flow chart of anexemplary process156 for distribution or redistribution of erasure encoded data, consistent with certain embodiments of the present invention.
• FIG. 9 is a flow chart of anexemplary process250 for management of loss of a storage device or system, consistent with certain embodiments of the present invention.
• FIG. 10 is a flow chart of anotherexemplary process300 for management of loss of a storage device or system, consistent with certain embodiments of the present invention.
• FIG. 11 is a flow chart of anexemplary process320 for management of addition of a storage device or system, consistent with certain embodiments of the present invention.
• FIG. 12 is a flow chart of anotherexemplary process360 for management of addition of a storage device or system, consistent with certain embodiments of the present invention.
• FIG. 13 is a block diagram of an example storage system illustrating an allocation process, consistent with certain embodiments of the present invention.
• FIG. 14 is a graphical representation of a banded storage allocation arrangement, consistent with certain embodiments of the present invention.
• FIG. 15 is a flow chart describing anotherallocation process550 consistent with certain embodiments of the present invention.
DETAILED DESCRIPTION
• While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail specific embodiments, with the understanding that the present disclosure of such embodiments is to be considered as an example of the principles and not intended to limit the invention to the specific embodiments shown and described. In the description below, like reference numerals are used to describe the same, similar or corresponding parts in the several views of the drawings.
• The terms “a” or “an”, as used herein, are defined as one or more than one. The term “plurality”, as used herein, is defined as two or more than two. The term “another”, as used herein, is defined as at least a second or more. The terms “including” and/or “having”, as used herein, are defined as comprising (i.e., open language). The term “coupled”, as used herein, is defined as connected, although not necessarily directly, and not necessarily mechanically. The term “program” or “computer program” or similar terms, as used herein, is defined as a sequence of instructions designed for execution on a computer system. A “program”, or “computer program”, may include a subroutine, a function, a procedure, an object method, an object implementation, in an executable application, an applet, a servlet, a source code, an object code, a shared library/dynamic load library and/or other sequence of instructions designed for execution on a computer system.
• Reference throughout this document to “one embodiment”, “certain embodiments”, “an embodiment” or similar terms means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of such phrases or in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments without limitation.
• The term “or” as used herein is to be interpreted as an “inclusive or” meaning any one or any combination. Therefore, “A, B or C” means “any of the following: A; B; A and B; A and C; B and C; A, B and C”. An exception to this definition will occur only when a combination of elements, functions, steps or acts are in some way inherently mutually exclusive.
• The terms “storage device”, “storage element” and “storage system” are used somewhat interchangeably herein. For example, a storage system, per se, may be treated as a storage element or storage device, but may be made up of multiple storage devices or storage elements (i.e., multiple disc drives may be used to create a single logical virtual drive). The particular meaning in a given statement should be interpreted to broadly incorporate each term where technically viable.
• The term “fountain code” and related terms are used in a manner consistent with the technical literature to describe a class of sparse graph erasure codes such as Digital Fountain, Inc.'s Raptor codes (Digital Fountain, Inc., Fremont, Calif.) and LT codes (as described by Michael Luby in “LT Codes”) in which D blocks of data are represented by any F “fountain codewords” (containing metacontent), where the number of bits of data represented by F is slightly more than the number of bits in D such that if any R of the blocks are recovered the original data can be recovered. Any number of fountain codewords can be generated using fountain coding to compensate for the projected loss of a channel or system. Details of the actual encoding and decoding process for fountain encoding is well documented in the literature and need not be repeated here.
• The name “fountain code” comes from the metaphor of a fountain spraying droplets of water, wherein it makes no difference which droplets fill the glass, it only matters that enough droplets are collected to fill it. A fountain code defines a group of mathematical of equations to encode the data and decode the data. The encoded fountain codewords contain the original data, but there can be as many fountain codewords as needed to overcome lost fountain codewords and still be able to recover the original blocks of data. These fountain codewords (or simply codewords or codes) are constructed such that the decoder can recover the original data from any combination of the fountain codewords, so long as a minimum number of fountain codewords are recovered. Fountain encoders have the ability to generate a huge number (generally >>R) of fountain codewords from any original set of source data. The original data can be recovered from an amount of data that is only slightly larger than the original data, and the encoding and decoding can be carried out rapidly.
• Another metaphor often used to explain fountain codes is that of a system of linear equations. For example, with N simultaneous independent equations and N−J unknowns, any N−J of the equations can be used to solve for the N−J unknowns. Using fountain codes, a formula for the data can be stored across multiple storage devices in a manner such that as long as a minimum number of fountain codewords are recovered, the formula can be constructed to reconstruct the data. Fountain encoding is used as an example in the description that follows, but the present invention should not be considered limited to fountain coding since other types of erasure encoding can be utilized in a manner consistent with certain embodiments.
• For purposes of this document, the following symbols are used to simplify the expression of mathematical or other ideas in connection with exemplary fountain encoding, but should be interpreted to encompass equivalent parameters in other erasure encoding:
• J, K, P=a positive integer used as a counter or designator of a particular numbered element.
• N=a maximum integer count or element number of counter or numbered element J, K, P.
• M=a maximum integer count for a number of capacity bands.
• S_K=storage element or system number K.
• C_J=capacity of a system disc drive or other storage element number J. C_Jis the capacity of S_J.
• S_MAX=storage element with maximum storage capacity.
• C=total storage capacity of a system of disc drives or other storage elements. In a system of N elements C₁, through C_N, C=C₁+C₂+ . . . +C_N.
• F_J=number of fountain codewords allocated for a given storage element C_J.
• C_MAX=storage capacity of the largest capacity storage device in a system of storage devices.
• F=a total number of fountain codewords within a system. In a system of N storage elements S₁through S_N, where F_Jis the number or fountain codewords for storage element S_J, F=F₁+F₂+ . . . +F_N.
• V=an estimate of the ratio of storage per fountain codeword (approximation of C/F, C₁/F₁, C₂/F₂, etc.). Thus, for example, V≈C/F.
• F_MAX=number of fountain codewords allocated to a storage element having the maximum number of codewords assigned thereto.
• R=a parameter of the set of fountain codewords selected. R> number of storage devices and usually much greater than the number of storage devices.
• L=a rounding factor added to a calculated minimum number of fountain codewords to assure that a minimum number of fountain codewords R will be reached.
• B_K=a K^thcapacity band—a K^thband of storage capacity allocated among a plurality of storage device.
• Int(x)=a rounding down function. In this case, Int(x)=the integer which is the next lower integer than x. The integer part of a whole number. Thus, for example, Int(3.14)=3. For purposes of this document, this function can be interpreted as a rounding up function without departing from embodiments consistent with the present invention.
• Fountain codes are an example of erasure codes. Fountain codes have been discussed in the technical literature primarily for use in the encoding data which is transmitted between two points. One of the most extensive uses of fountain codes to date has been in connection with satellite radio transmissions. While it has generally been suggested that fountain encoding could be utilized for more secure data storage by sending fountain codewords to multiple storage devices, to date no known strategy has been proposed for actually accomplishing this. In particular, no strategy is known for efficiently using fountain encoding to encode data for storage in multiple storage devices of varying size.
• A storage system utilizing the fountain codes is shown generally inFIG. 1 assystem60 in which a source data block20 is processed by afountain code encoder22 to produce any desired number offountain codewords26. It is an attribute of fountain code encoding that almost any desired number of fountain codewords can be generated for any given block of source data. Depending upon the parameters selected for carrying out the fountain code encoding, the original source block of data can generally be recovered if any R fountain codewords are properly recovered or received for decoding.
• Continuing with the example ofFIG. 1,codewords30 are stored in storage device S₁which is shown asstorage device32. Similarly,codewords34 can be stored in storage device S₂which is depicted asstorage device36. Similarly,codewords38 could be stored in storage device40 (storage device S_P), andfountain codewords42 can be stored instorage device44. In this depiction, two fountain codewords are illustrated as being stored in each ofstorage devices32 and36. Three fountain codewords are depicted as being stored instorage device40, while five fountain codewords are depicted as being stored instorage device44. In accordance with certain embodiments consistent with the present invention, it is desirable that the storage capacity of each storage device be capable of being well (near fully if possible) utilized. It is further desirable that if any of the storage devices in the storage system should become defective or for some other reason lose the data stored therein, enough fountain codewords will be available in the remaining storage devices to permit full reconstruction of thesource data20. However, these desirable characteristics should not be considered to be limiting constraints on certain embodiments consistent with the present invention.
• When data is to be retrieved from the array ofstorage devices32,36 through40, through44, only a minimal number (greater than or equal to R) of fountain codewords need to be received at50 in order to assure that the source data can be reconstructed. Once R or more fountain codewords are received at50, thefountain code decoder52 can fully reconstruct theoriginal source data20 shown asoutput data54.
• In accordance with certain embodiments consistent with the present invention, a mechanism for distributing or allocating thefountain codewords26 among the various storage devices which might make up a complete storage system such as60 is provided under the constraints that loss of the largest storage device in the system will not result in loss of any data stored in thestorage system60. In addition, storage should be approximately allocated according to the size of the disc drives or other storage devices making up the overall storage system, so that the drives or other storage devices have the potential of full or near full utilization, in certain embodiments.
• For convenience, the system shown inFIG. 1 is referenced herein assystem60 and is shown in simplified form inFIGS. 2-4. InFIG. 2, the individual fountain codewords have been omitted, and the illustration has been generally simplified for convenience. In this illustration, a total of N storage devices is present insystem60. Now considerFIG. 3 which also depictssystem60. InFIG. 3, storage device S_P(device40) is shown as being damaged, removed, corrupted, or erased. In accordance with embodiments consistent with the present invention, even ifstorage device40 is the largest storage device in the system, it is desirable that there be no data loss. Hence, any allocation of fountain codewords among the various storage devices in thesystem60 should be made to assure that adequate fountain codewords (≧R) remain available, even withoutstorage device40, to reconstruct all stored data.
• Now also considerFIG. 4, which depictssystem60 with the addition of a newly addedstorage device68. In an evolving system where new devices with varying storage capacity may be added, it is also desirable that a newly added storage device be integrated within the existing network in a manner such that it enhances thesystem60's resistance to storage device failure, accidental erasure or other loss of data phenomenon. It is further desirable that newly added storage devices be available to assist in reconstruction of data should one of the previously existing storage devices be destroyed, damaged, or accidentally erased. Further, it is desirable that the new storage device be protected by existing storage devices against loss of data.
• An overall process for allocating and distributing fountain codewords among the N storage devices (or rearrangements after loss or addition of a storage device) is depicted asprocess80 ofFIG. 5. The allocation process starts at82 after which the process identifies a storage device S_MAXhaving a largest capacity at86. Parameters are established at90 in order to carry out fountain encoding to produce F fountain codewords in a manner that assures that an adequate number of fountain codewords (≧R) will be available (even if S_MAXis lost) to carry out full reconstruction of all data as previously described. At94, the fountain codewords are distributed among the N storage devices in approximate proportion to the storage capacity of each of the storage devices. The distribution is further subject to the constraint that enough fountain codewords are stored in each of the storage devices to assure that if any one storage device, S_Pis lost, all of the data in the system can be restored using the fountain codewords stored in the remaining storage devices, by virtue of being able to retrieve at least R fountain codewords from the remaining storage devices. The process then returns at98. The value of R is a function of the particular fountain encoding algorithm devised for a particular system in consideration of various aspects including the block size of source data that is to be encoded.
• The most difficult storage device loss to compensate for is the one with the largest capacity, S_MAX. Thus, a method for storing data across a plurality of N storage devices S₁. . . S_N, wherein at least one of the storage devices has a storage capacity that not equal to a storage capacity of others of the storage devices involves identifying a storage device S_MAXhaving a largest capacity of the plurality of storage devices S₁. . . S_N; encoding the data with an erasure encoder to produce F erasure codewords, where
• $F=\sum _{K=1}^NF_K$
• with K being a counting integer; and distributing the erasure codewords among the N storage devices S₁. . . S_N, where F_K, the number of codewords assigned to S_K, is in approximate proportion to the storage capacity C_Kof storage device S_K, for each of the N storage devices S₁. . . S_Nsubject to the constraint that if any one storage device, S_Pis lost, enough erasure codewords are stored in each of the N−1 remaining storage devices to assure that all of the data in the system can be restored using the erasure codewords stored in the remaining storage devices S₁. . . S_Nexcluding S_P. The most difficult case is when S_P=S_MAX. In accordance with certain embodiments consistent with the present invention, the erasure codewords are fountain codewords. In certain embodiments, the proportion of the number codewords F_Pto the capacity C_Pof each of the storage devices is a multiple of (C−C_MAX)/R.
• Thus, an arrangement for storing data consistent with certain embodiments has a plurality of N storage devices S₁. . . S_N, wherein at least one of the storage devices has a storage capacity that not equal to a storage capacity of others of the storage devices. A storage device S_MAXhas a largest capacity of the plurality of storage devices S₁. . . S_N. A fountain encoder encodes the data into F fountain codewords, wherein
• $F=\sum _{K=1}^NF_K$
• with K being a counting integer. The fountain encoder distributes the fountain codewords among the N storage devices S₁. . . S_Nin approximate proportion to the storage capacity C_Kof each of the N storage devices S₁. . . S_Nsubject to the constraint that enough fountain codewords are stored in each of the N storage devices, to assure that all of the data in all of the N storage devices can be recovered if any one of the N storage devices is lost, using the fountain codewords stored in the remaining storage devices S₁. . . S_Nexcluding the lost device, even if it is S_MAX.
• Further, an arrangement for storing data consistent with certain embodiments includes a plurality of N storage devices S₁. . . S_N, wherein at least one of the storage devices has a storage capacity that not equal to a storage capacity of others of the storage devices. A storage device S_MAXhas a largest capacity of the plurality of storage devices S₁. . . S_N. A fountain or other erasure encoder encodes the data into F fountain codewords (or erasure codewords), wherein
• $F=\sum _{K=1}^NF_K$
• with K being a counting integer. The fountain encoder (or other erasure encoder) distributes the codewords among the N storage devices S₁. . . S_Nin approximate proportion to the storage capacity C_Kof each of the N storage devices S₁. . . S_Nsubject to the constraint that enough codewords are stored in each of the N storage devices excepting S_MAX, to assure that all of the data in S_MAXcan be restored using the codewords stored in the remaining storage devices S₁. . . S_Nexcluding S_MAX.
• A more detailed algorithm for this process is depicted inFIG. 6 asprocess100. This process starts at82 after which the capacity C_MAXof the largest storage device S_MAXis determined at104. The total storage of all of the storage devices C₁through C_Nis determined at108. Knowing R, the number of codewords needed to reconstruct the original data, and the capacities C and C₁through C_N, we need to determine the number of codewords F_Pto assign to each storage devices S_P. The total number of fountain codewords to be generated to fill all the disc drives or other storage devices is given by F at112 as the sum of the individual fountain codewords allocated to eachindividual storage device1 through N. The design target is established such that the ratio of capacity to fountain codewords (C_P/F_P) is approximately equal for each of the individual storage devices (each S_P) as well as the total capacity C at116. At120, the ratio V is determined using the parameter R established for the fountain encoding selected for use. V is approximated as:
• 
  V≈C/F≈(C−C_MAX)/(F−F_MAX)=(C−C_MAX)/R.
• This establishes the relationship between R, the C's, S_MAXand C_MAX, as well as V so that an initial estimate of the overall value of ratio V can be determined.
• The individual estimates for the number of fountain codewords allocated to each of the storage devices can then be determined by taking the integer value of the capacity of the particular storage device and dividing it by Vas illustrated at128 and given by:
• 
  F₁=Int(C₁/V); andF₂=Int(C₂/V); . . . ;F_N=Int(C_N/V).
• This provides an estimate or approximation of the number of fountain codewords that should be allocated to each of the individual storage devices S₁through S_N. Since these are estimates, it should be verified that:
• 
  F₁+F₂+ . . . +F_N−F_MAX≧R
• 
  and that
• 
  F_MAX≧F_Pfor P=1 through N
• That is, if F_MAX, the maximum number of codewords assigned to any given storage device, codewords are removed all data can still be reconstructed. Thus, at130, the initial estimates are checked to assure that the sum of all fountain codes minus the number of fountain codes allocated to S_MAX(F_MAX) is greater than or equal to R so that it is assured that if F_MAXfountain codes are removed by virtue of loss of S_MAXall of the data can still be reconstructed. If this is verified at134, the fountain codewords can be allocated across the storage systems at138, and the process returns at142.
• However, if it is not verified at134, an integer rounding factor L can be added at146 to provide additional codewords to each or some of the storage devices to assure that for any particular storage device S_Jthat F_Jcan be determined by:
• 
  F_J=Int(C_J/V+L), and retry untilF−F_MAX≧R.
• The process then returns to130 to verify that enough fountain codewords have been generated. The process iterates until the conditions of130 are met, at which point, the fountain codewords are allocated according to the values of F_Jand the process returns. By use of the above process, it can be guaranteed that even under the constraint that the largest capacity storage device S_MAXis lost, no data will be compromised.
• In certain applications, iteration of the number of codes and testing may not be required if it can be predetermined how much adjustment to the estimate is needed to assure that adequate numbers of fountain codewords are available. In such case, the estimate can simply be refined by addition of L as a part of the initial estimating process.
• Thus, a method of allocating storage for storing data across a plurality of N storage devices S₁. . . S_N, wherein at least one of the storage devices has a storage capacity that is not equal to a storage capacity of others of the storage devices involves determining a maximum capacity C_MAXof a storage device S_MAXhaving a largest capacity of the plurality of storage devices S₁. . . S_N; determining a total storage capacity C of all of the plurality of storage devices S₁. . . S_Nas
• $C=\sum _{K=1}^NC_K,$
• where K is a counting integer; defining a maximum total number of fountain codewords
• $F=\sum _{K=1}^NF_K$
• that could be stored in the plurality of storage devices S₁. . . S_N; defining F_MAXas a maximum number of fountain codewords that would be lost if the data in S_MAXis lost; estimating a target ratio of capacity to fountain codewords V as V≈C/F≈(C−C_MAX)/(F−F_MAX)≈(C−C_MAX)/R, where R is a number of fountain codewords required to recover C_MAXif the data in S_MAXis lost; using the estimate of the value of V to estimate the values of F₁. . . F_Nas F_K=Int(C_K/V); adjusting the estimated values of F₁. . . F_Nby addition of a rounding factor to assure that
• $\left(\sum _{K=1}^NF_K\right)-F_{\mathrm{MAX}}\ge R;$
• and allocating fountain codewords storing data to the storage devices S₁. . . S_Nin proportion to the estimated values of F₁. . . F_N.
• It should be noted, however, that the present allocation method is contingent upon there being an adequate amount of storage available after loss of a storage device in the remaining storage devices to provide at least R fountain codewords for any stored data so that the stored data can be reconstructed. This implies that the summation of storage available on all devices excluding S_MAXshould total to at least the capacity of S_MAXwhich is C_MAX. If this condition is not met, the recovery of loss of the largest storage device cannot be assured; however, this may be acceptable in certain applications and the process modified accordingly if it is acceptable in a particular application for certain data to be expendable.
• Process100 (or process80) is carried out at initialization of a storage system having multiple storage devices. The process can also be carried out whenever a redistribution needs to be carried out as a result of loss of a storage device or acquisition of a new storage device withinstorage system60. Referring toFIG. 7, anoverall process150 for allocating fountain codewords, storage and retrieval of files is depicted starting at152. At156, the initial fountain codeword distribution process is carried out so that the encoder and storage device controllers can know how to allocate and distribute fountain codewords whenever source data is to be stored. If a file is to be stored at160, the file is broken into source data blocks at164. The fountain code encoder generates fountain codewords at168 for each of the data blocks produced at164. Those fountain codewords are then distributed to the storage devices in accordance with the distribution determined at156. If no error occurs in the storage process and no change is detected in the configuration of the storage system at176, the system determines if a file is to be fetched at180. If so, the file is associated with a collection of stored fountain codewords and those stored fountain codewords are requested from the storage devices.
• At188, fountain codewords are received from the available storage devices until it is determined at192 that R codewords have been received. At this point, it is possible to halt the process of fetching additional codewords at196 if desired, and the fountain decoder can decode the received fountain codewords and return the recovered source file at198. A determination can then be made at199 as to whether or not the process was successful and/or a storage device error or change has taken place. If not, control returns to160 to determine if a file is to be stored.
• As a convenience in depicting the process, if a file is not to be stored at160, control passes first to179 where a check is made to determine if a storage device error or change has taken place. If so, control passes to156 where a redistribution process is carried out. If not, control passes to180 where a determination is made as to whether or not a file is to be fetched. If no file is to be fetched at180, control passes back to160 to determine if a file is to be stored. Those skilled in the art will recognize that in a physical system, the process depicted may not literally be followed, but rather the system may await an instruction to either store or fetch a file. In the event a change in the storage system is detected at either176 or199, control passes back to156 where a redistribution process is carried out to determine how fountain codewords are distributed within the system under a new configuration.
• There are many ways to view the fountain codeword distribution and redistribution processes within the constraints defined above, as depicted inprocess80 and inprocess100. This process can be further illustrated inFIG. 8 asprocess156 starting at204. At208, the number of storage devices and the capacity of each withinsystem60 is ascertained. A source block size for each fountain encoding is then established at212 (This might be fixed at system design time rather than here. If this is determined here, it may also determine various other fountain code parameters, such as R.). The distribution can be calculated in order to determine the number of fountain codewords for each storage device to be generated for each source block so that it can be assured that all data can be recovered in the event of any storage device failure at216. The fountain codewords are then generated and distributed or redistributed at220, and the process returns at224.
• When a storage device is lost fromsystem60, several possible courses of action can be implemented. One such course of action is depicted inFIG. 9 asprocess250 starting at252 where it is determined that a storage system has been lost. Such determination can be made by any suitable mechanism including, but not limited to, verifying a response from each storage device at prescribed intervals or when codewords are stored or fetched. At256, a determination is made as to whether or not all data in all storage systems can be reconstructed, recoded, and repartitioned among the remaining storage systems in view of the loss of a particular storage device or system. If not enough storage exists at260, an error can be reported or other error trapping action can be carried out at264, and the process returns at268. (In other embodiments, the process can proceed subject to there being no guarantee that all data is recoverable.) If, however, enough storage exists at260, and a new value of R and a new fountain coding scheme can be selected at272. A new value of C_MAXcan then be determined at280, and a new value of V can be determined at284. This provides enough information to calculate a new allocation as with the initial allocation at288. The process can then return for storage of the fountain codes. Another option when a storage system is lost is to discard files according to some pre-arranged algorithm until the data does fit in the remaining space.
• FIG. 10 depicts another process for dealing with loss of a storage device or system. This process is referenced atprocess300 and starts out identically to theprior process250 ofFIG. 9. However, if enough storage is available at260, a new allocation can be calculated at306 and new fountain codewords to replace those lost can be generated and distributed among the available storage systems according to the new allocation. This process differs fromprocess250 in that a whole new allocation is not carried out. Instead, only the missing fountain codewords are generated and redistributed according to a new allocation scheme.
• Several processes can also be utilized to deal with a circumstance wherein a new storage device is added to the system. One such process is depicted asprocess320 ofFIG. 11. When it is determined at324 that a new storage device is added (Such determination can be made by any suitable mechanism including, but not limited to, verifying a response from each storage device at prescribed intervals or when codewords are stored or fetched, or via other monitoring provided by a programmed processor), a new capacity C can be calculated as the previous capacity plus the new capacity at328. A new fountain coding arrangement with a new R value can be selected at332. A new value of C_MAXcan be determined at336, and the value of V can be determined at340 as the new C minus the new C_MAX, then divided by the new R. At344, the fountain codewords can be reallocated as with the initial allocation using the new values of the relevant variables as modified by the change in capacity. Each stored file can then be reconstructed according to the new distribution at348, and the process returns at352.
• FIG. 12 depicts analternative process360 for dealing with the addition of a new storage system. When it is determined that a new storage system has been added at364, the new capacity can be calculated at328 and new values of C, C_MAXand V can be calculated at336 and340 as before. At380, however, according to theprocess360, fountain codewords are moved from other storage systems to the new storage system within the allocation constraints. Thus, rather than a complete reallocation,process360 moves existing codewords to the new storage system in order to more rapidly affect the allocation. At384, new fountain codewords are generated where needed to assure recovery if a storage system fails. Since the addition of a new storage system or device may affect the availability of an adequate number R of codewords, the new fountain codewords generated at384 are generated according to a specified fountain coding scheme and distributed in order to assure recovery of any lost data. The process then returns at390.
• Thus, according to certain of the above example embodiments, when it is determined that an additional storage device S_N+1is available for storage of the codewords, the codewords are reallocated across the plurality of storage devices S₁. . . S_N+1. In certain embodiments, the reallocating comprises moving codewords from certain of the storage devices S₁. . . S_Nto storage device S_N+1. In certain embodiments, the reallocation is carried out subject to the constraint that
• $\left(\sum _{K=1}^{N+1}F_K\right)-F_{\mathrm{MAX}}\ge R,$
• where F_MAXis the number of codewords to be stored on the largest of storage devices S₁. . . S_N+1.
• In certain embodiments, the reallocation involves: determining a new maximum capacity C_MAXof a storage device S_MAXhaving a largest capacity of the plurality of storage devices S₁. . . S_N+1; determining a total storage capacity C of all of the plurality of storage devices S₁. . . S_N+1as
• $C=\sum _{K=1}^{N+1}C_K;$
• defining a maximum total number of fountain codewords
• $F=\sum _{K=1}^{N+1}F_K$
• that could be stored in the plurality of storage devices S₁. . . S_N+1; defining F_MAXas a maximum number of fountain codewords that would be lost if the data in S_MAXis lost; estimating a revised target ratio of capacity to fountain codewords V as V≈C/F≈(C−C_MAX)/(F−F_MAX)≈(C−C_MAX)/R, where R is a number of fountain codewords required to recover C_MAXif the data in S_MAXis lost; using the estimate of the value of V to estimate the values of F₁. . . F_N+1as F_K=Int(C_K/V); adjusting the estimated values of F₁. . . F_N+1by addition of a rounding factor to assure that
• $\left(\sum _{K=1}^{N+1}F_K\right)-F_{\mathrm{MAX}}\ge R;$
• and allocating fountain codewords storing data to the storage devices S₁. . . S_N+1in proportion to the estimated values of F₁. . . F_N+1.
• In certain embodiments, the method further involves determining that storage device S_P, being one of storage devices S₁. . . S_Nis no longer available for storage of the codewords; and reallocating the codewords across the plurality of storage devices S₁. . . S_Nexcluding S_P.
• In certain embodiments, the reallocating involves calculating a new allocation; generating new codewords; and distributing the new codewords among the storage devices S₁. . . S_Nexcluding S_P. In certain embodiments, the reallocation is carried out subject to the constraint that
• $\left(\sum _{K=1}^NF_K\right)-F_P-F_{\mathrm{MAX}}\ge R,$
• where F_Pis the number of codewords that were allocated to storage device S_Pand F_MAXis the number of codewords to be stored on the largest of storage devices S₁. . . S_N, excluding S_P
• In certain embodiments, the reallocation involves determining a new maximum capacity C_MAXof a storage device S_MAXhaving a largest capacity of the plurality of storage devices S₁. . . S_Nexcluding S_P; determining a total storage capacity C of all of the plurality of storage devices S₁. . . S_Nexcluding S_Pas
• $C=\left(\sum _{K=1}^NC_K\right)-C_P;$
• defining a maximum total number of fountain codewords
• $F=\left(\sum _{K=1}^NF_K\right)-F_P$
• that could be stored in the plurality of storage devices S₁. . . S_Nexcluding S_P; defining F_MAXas a maximum number of fountain codewords that would be lost if the data in S_MAXis lost; estimating a revised target ratio of capacity to fountain codewords V as V≈C/F≈(C−C_MAX)/(F−F_MAX)≈(C−C_MAX)/R, where R is a number of fountain codewords required to recover C_MAXif the data in S_MAXis lost; using the estimate of the value of V to estimate the values of F₁. . . F_N+1as F_K=Int(C_K/V) for S₁. . . S_Nexcluding S_P; adjusting the estimated values of F₁. . . F_N+1by addition of a rounding factor to assure that
• $\left(\sum _{K=1}^{N+1}F_K\right)-F_{\mathrm{MAX}}\ge R$
• for each of S₁. . . S_Nexcluding S_P; and allocating fountain codewords storing data to the storage devices S₁. . . S_Nexcluding S_Pin proportion to the estimated values of F₁. . . F_N.
• In certain embodiments, the method further involves determining that storage device S_P, being one of storage devices S₁. . . S_Nis 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₁. . . S_Nexcluding S_P; and if not, establishing that an error condition exists.
• In another alternative embodiment, after a consolidation of data following loss of a drive, data can be deleted according to some user/system defined plan (such as deleting already viewed video, or old versions of files, etc.) to make the necessary room on the new protected system for the essential content from the old protected system. A protected system being a system implemented such that if one drive dies, the system can restore the data. When one drive has died, the system is no longer protected. It can still retrieve all the data, but another failure will make for complete loss. It isn't protected until it reinitializes with the new allocation.
• Many further variations will occur to those skilled in the art upon consideration of the present teachings.
• Hence, if the fountain codewords and R are unchanged, in one embodiment certain codes are simply removed from each storage device and those codewords are stored on the newly added storage device. In fact, if under a revised calculation following addition of the storage device, if F_MAX<F−R (that is if the new allocation of codewords has its F_MAXlower than the prior F_MAX, i.e. F_MAXNEW<F_MAXOLD, then no new codes need to be generated at all—and in fact, some may be able to be discarded.
• In each example above, it should be noted that the number of available fountain codewords should always be ≧R. Clearly, providing more codewords above and beyond R provides greater insurance against data loss, but does so at the expense of storage efficiency, since more codewords per storage device would be required.
• Anexample system400 is shown inFIG. 13. In this example system, three storage devices are shown. The storage devices are respectively a 40GB storage device404, a 60GB storage device408, and an 80GB storage device412. For this example, we will assume that each input source file is divided into blocks of 2 KB each at420 for encoding byfountain code encoder424.
• For the simple system depicted inFIG. 13, N=3 storage devices—S₁, S₂and S₃, illustrated as404,408 and412. Also assume a value of R of 5 for the fountain encoding. In this example:
• C₁=40 GB;
• C₂=60 GB; and
• C₃=80 GB.
Clearly, C_MAX=80 GB, and C=C₁+C₂+C₃=180 GB.
• Now, selecting a fountain coding scheme constrained by R=5, on input blocks of 2 KB each, then:
• 
  V≈(C−C_MAX)/R=(180−80)/5=20;
• 
  F₁=int(C₁/V)=40/20=2;
• 
  F₂=int(C₂/V)=60/20=3;
• 
  F₃=int(C₃/V)=80/20=4;
• 
  F=F₁+F₂+F₃=2+3+4=9; and
• 
  F_MAX=4
• Hence, in this example, for each input block of data (2 KB) nine fountain codewords are created. Since the constraint of providing adequate codewords if S_MAXis lost is met, there is no need to add a factor L to any or all of the values of F_J.
• In accord with this example, in order to store the example 10 KB source file at420, the source file is divided into 2 KB source file blocks (5 such blocks total) which are each encoded byfountain code encoder424 to produce 2fountain codewords428 forstorage device404, 10 codewords in total, 3fountain codewords432 forstorage device408, 15 codewords in total, and 4fountain codewords440 forstorage device412, 20 codewords in total. In order to recover the stored source file, any 5 fountain codewords for each of the 2 KB source file blocks can be retrieved from any of the storage devices at450, for a total of 25 codewords, and the source file can be recovered using a fountain decoder at454. The details of selection of a particular variant of fountain encoding and selection of a particular value of R is well documented in the literature and need not be repeated here. Moreover, the present invention may well be implemented using other erasure codes without departing from the invention.
• It is noted with this example that even if thelargest storage device412 should fail or be accidentally erased, enough fountain codewords (R=5) are available from the combination ofstorage device404 and408 in order to recreate the 10KB source file420.
• Now consider a second identical example except that:
• C₁=30 GB;
• C₂=50 GB; and
• C₃=80 GB.
Clearly, C_MAX=80 GB, and C=C₁+C₂+C₃=160 GB.
• Again, selecting a fountain coding scheme constrained by R=5, on input blocks of 2 KB each, then:
• 
  V≈(C−C_MAX)/R=(160−80)/5=16;
• 
  estimateF₁≈int(C₁/V)=int(30/16)=int(1.88)=1
• 
  estimateF₂≈int(C₂/V)=int(50/16)=int(3.13)=3;
• 
  estimateF₃≈int(C₃/V)=int(80/18)=int(4.44)=4;
• 
  F=F₁+F₂+F₃=1+3+4=8;
• 
  F_MAX=4.
• Now test the estimates. Is the criteria F₁+F₂+ . . . +F_N−F_MAX≧R met?
• 
  1+3+4−F_MAX=1+3+4−4=4
• 4<R, thus the criteria is not met.
• In this example, since the constraint of providing adequate codewords if S_MAXis lost is not yet met, a factor L can be added to any or all of the values of F_Jas follows:
• 
  F₁=int(1.88+L);
• 
  F₂=int(3.13+L); and
• 
  F₃=int(4.44+L).
• Let L=0.5; then refine the estimate as:
• 
  F₁=int(1.88+L)=2;
• 
  F₂=int(3.13+L)=3; and
• 
  F₃=int(4.44+L)=4.
• Now repeat the test. Is the criteria F₁+F₂+ . . . +F_N−F_MAX≧R met?
• 
  2+3+4−F_MAX=2+3+4−4=5
• 5≧R, thus the criteria is met.
• In accord with this example, in order to store the example 10 KB source file, the source file is divided into 2 KB source file blocks (5 such blocks) which are encoded by the fountain code encoder to produce 10 fountain codewords for storage in S₁, 15 fountain codewords for storage in storage device S₂, and 20 fountain codewords for storage in storage device S₃. In order to recover the stored source file, any 5 fountain codewords for each block can be retrieved from any of the storage devices, and the source file can be recovered using the fountain decoder. Again, the details of selection of a particular variant of fountain encoding and selection of a particular value of R is well documented in the literature and need not be repeated here. Moreover, the present invention may well be implemented using other erasure codes without departing from the invention.
• It is noted with this example that even if the largest storage device S₃should fail or be accidentally erased, enough fountain codewords (R=5) are available from the combination of storage device S₁and S₂in order to recreate the 10KB source file420.
• It is noted that under certain circumstances, there may be no solution to the problem of assuring that loss of the largest drive is to be recoverable. For example, consider a storage system with two 20 GB drives and one 100. Clearly, the above techniques do not account for a mechanism to store enough codewords on the two 20 GB drives to recover 100 GB. Thus, the embodiments described above work best when there are a large number of storage devices, and wherein the capacity of all drives excluding S_MAXexceeds the capacity C_MAX. It is also noted that if with varying capacities, some of the drives may not be used completely if all of the source data is to be assured protection. However, since most such systems have excess capacity, this is not likely to be of major concern. Moreover, the potentially unused capacity can be utilized for simple redundant storage of certain information to more fully utilize the full storage capacity. In another variation, the unused portion of the drives could be combined into a separate redundant system, except with fewer devices. This could be done until all capacity that spans more than one drive is consumed. This would allow some otherwise unused space to be efficiently utilized.
• In an alternative implementation, instead of allocating storage as described above, the capacity can be allocated using a banding approach as follows:
• Suppose there are N storage systems S . . . S_N, with corresponding capacities C₁. . . C_N, such that C₁≦C₂≦ . . . ≦C_N. as depicted graphically as500 inFIG. 14. In this embodiment, the system can be implemented using up to N−1 backed up bands on each of the storage devices. Thefirst band506 would have capacity C1, and all drives would participate. In this case R could ideally (but not necessarily) be chosen such that R=N−1, (or some multiple thereof). Forband506, allocation of erasure codewords (e.g., fountain codewords or other erasure codewords) across all storage devices is uniform.
• The second band510 has capacity C₂−C₁, and could ideally, but not necessarily, be selected such that R≧N−2. In this example, storage devices S₂and S₃have equal capacity C₂=C₃. The next band514 has capacity C₄−C₃, and so on until all bands are depleted.
• Similarly each band would have capacity C_J−C_J-1, and have R ideally equal to N−J. If there are adjacent C_J, C_J-1that are equal, then they are dealt with as a single band. The final band encompassing multiple drives may be reached (e.g., band520 as shown) at a certain point. Beyond this point, in range524, the ability to provide protection to the data using the present arrangement ends because the other systems are already full. However, depending upon the exact storage capacity of the storage devices in a particular system, this arrangement may provide greater storage utilization.
• In the present banded implementation in particular, any suitable erasure coding arrangement can be used including conventional RAID parity or simple data duplication for each band. The erasure coding can be devised in a manner that provides efficient utilization, encoding, decoding or subject to other constraints of the storage system.
• The present banded embodiment is further illustrated asprocess550 in the flow chart ofFIG. 15 starting at552. At556, a counting integer J is initialized at J=1. At560, the capacities of each of the N storage devices S₁. . . S_Nis determined. At564, the capacities of the capacity bands B₁<B_J<B_Mis then determined for the M different sizes of storage devices, potentially excluding a largest capacity if a single storage device remains with the largest capacity (e.g., device S_NofFIG. 14). At568, for the J^thband B_J, a capacity band is established in each storage device with enough capacity (capacity ≧C_J). Once capacity bands are established, codewords such as fountain codewords F_Jare allocated at572 for all storage devices with enough storage capacity (capacity ≧C_J). If J is not equal to M (the last band) at576, J is incremented at580 and the process returns to568. Once J is equal to M at576, the process returns at584 with storage in all bands B₁. . . B_Mallocated.
• Thus, a method consistent with certain embodiments for storing data across a plurality of N storage devices S₁. . . S_N, wherein at least certain of the storage devices have a storage capacity C_MIN=C_J≦C_K≦C_MAXinvolves establishing a first capacity band equal in capacity to C_MINin each of the storage devices; encoding a collection of source data with an erasure encoder to produce F_Jerasure codewords; allocating the F_Jerasure codewords among the N storage devices S₁. . . S_N; establishing a second capacity band equal in capacity to C_Kin each of the storage devices having capacity ≧C_K; encoding a collection of source data with an erasure encoder to produce F_Kerasure codewords; allocating the F_Kerasure codewords among the storage devices among S₁. . . S_Nhaving capacity ≧C_K.
• In this embodiment, reallocation after loss or addition of storage devices can be handled the same as in a new configuration. Essentially a new system is designed based on the new configuration, and data is gradually moved from the old structure to the new. If using traditional RAID (XOR) parity, it may be trickier to maintain the old structure while copying to the new, but nevertheless, reconstruction of the system can be carried out in the same way. In other embodiments, other reconstruction methods may be implemented.
• Those skilled in the art will recognize, upon consideration of the above teachings, that certain of the above exemplary embodiments are based upon use of a programmed processor. However, the invention is not limited to such exemplary embodiments, since other embodiments could be implemented using hardware component equivalents such as special purpose hardware and/or dedicated processors. Similarly, general purpose computers, microprocessor based computers, micro-controllers, optical computers, analog computers, dedicated processors, application specific circuits and/or dedicated hard wired logic may be used to construct alternative equivalent embodiments.
• Certain embodiments described herein, are or may be implemented using a programmed processor acting in the capacity of a fountain encoder and decoder executing programming instructions that are broadly described above in flow chart form that can be stored on any suitable electronic or computer readable storage medium and/or can be transmitted over any suitable electronic communication medium. However, those skilled in the art will appreciate, upon consideration of the present teaching, that the processes described above can be implemented in any number of variations and in many suitable programming languages without departing from embodiments of the present invention. For example, the order of certain operations carried out can often be varied, additional operations can be added or operations can be deleted without departing from certain embodiments of the invention. Error trapping can be added and/or enhanced and variations can be made in user interface and information presentation without departing from certain embodiments of the present invention. Such variations are contemplated and considered equivalent. The programming instructions that in certain instances are broadly described above in flow chart form can be stored on any suitable electronic or computer readable storage medium (such as, for example, disc storage, Read Only Memory (ROM) devices, Random Access Memory (RAM) devices, network memory devices, optical storage elements, magnetic storage elements, magneto-optical storage elements, flash memory, core memory and/or other equivalent volatile and non-volatile storage technologies) and/or can be transmitted over any suitable electronic communication medium.
• While certain illustrative embodiments have been described, it is evident that many alternatives, modifications, permutations and variations will become apparent to those skilled in the art in light of the foregoing description. The use of reference letters in the claims that follow should not be construed to assign an absolute order to the steps or acts associated therewith.

Claims (20)

1. A method for storing data across a plurality of N storage devices S₁. . . 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_MAXwith the method comprising:

establishing a first capacity band equal in capacity to C_MINin each of the storage devices;

encoding a collection of source data with an erasure encoder to produce F_Jerasure codewords;

allocating the F_Jerasure codewords uniformly among the N storage devices S₁. . . S_N;

establishing a second capacity band equal in capacity to C_K−C_Jin each of the storage devices having capacity ≧C_J;

encoding a collection of source data with an erasure encoder to produce F_Kerasure codewords; and

allocating the F_Kerasure codewords uniformly among the storage devices S₁. . . S_Nhaving capacity ≧C_J.

2. The method according toclaim 1, wherein the erasure codewords are encoded using a RAID parity encoder.

3. The method according toclaim 1, wherein the erasure codewords are encoded using a fountain encoder.

4. The method according toclaim 1, wherein the erasure codewords are encoded using a simple data duplication encoder.

5. The method according toclaim 1, wherein the storage devices S₁. . . S_Ncomprise 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 toclaim 1, further comprising:

determining that a storage device S_N+1is available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁. . . S_N+1.

7. The method according toclaim 1, further comprising:

determining that storage device S_P, being any one of storage devices S₁. . . S_Nis no longer available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁. . . S_Nexcluding S_P.

8. The method according toclaim 1, further comprising:

determining that storage device S_P, being any one of storage devices S₁. . . S_Nis 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₁. . . S_Nexcluding 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₁. . . 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_MAXwith the method comprising:

establishing a first capacity band equal in capacity to C_MINin each of the storage devices;

encoding a collection of source data with an erasure encoder to produce F_Jerasure 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_Jerasure codewords uniformly among the N storage devices S₁. . . S_N;

establishing a second capacity band equal in capacity to C_K−C_Jin each of the storage devices having capacity ≧C_J;

encoding a collection of source data with an erasure encoder to produce F_Kerasure codewords;

allocating the F_Kerasure codewords uniformly among the storage devices S₁. . . S_Nhaving capacity ≧C_J;

determining that a storage device S_N+1is available for storage of the codewords; and

reallocating the codewords across the plurality of storage devices S₁. . . S_N+1.

10. The method according toclaim 9, wherein the storage devices S₁. . . S_Ncomprise 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 toclaim 9, further comprising:

determining that storage device S_P, being any one of storage devices S₁. . . S_Nis no longer available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁. . . S_Nexcluding S_P.

12. The method according toclaim 9, further comprising:

determining that storage device S_P, being any one of storage devices S₁. . . S_Nis 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₁. . . S_Nexcluding 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₁. . . 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_MAXcomprising:

establishing a first capacity band equal in capacity to C_MINin each of the storage devices;

encoding a collection of source data with an erasure encoder to produce F_Jerasure codewords;

allocating the F_Jerasure codewords uniformly among the N storage devices S₁. . . S_N;

establishing a second capacity band equal in capacity to C_K−C_Jin each of the storage devices having capacity ≧C_J;

encoding a collection of source data with an erasure encoder to produce F_Kerasure codewords; and

allocating the F_Kerasure codewords uniformly among the storage devices S₁. . . S_Nhaving capacity ≧C_J.

14. The computer readable storage medium according toclaim 13, wherein the erasure codewords are encoded using a RAID parity encoder.

15. The computer readable storage medium according toclaim 13, wherein the erasure codewords are encoded using a fountain encoder.

16. The computer readable storage medium according toclaim 13, wherein the erasure codewords are encoded using a simple data duplication encoder.

17. The computer readable storage medium according toclaim 13, wherein the storage devices S₁. . . S_Ncomprise 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 toclaim 13, further comprising:

determining that a storage device S_N+1is available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁. . . S_N+1.

19. The method according toclaim 13, further comprising:

determining that storage device S_P, being any one of storage devices S₁. . . S_Nis no longer available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁. . . S_Nexcluding S_P.

20. The computer readable storage medium according toclaim 13, further comprising:

determining that storage device S_P, being any one of storage devices S₁. . . S_Nis 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₁. . . S_Nexcluding S_P; and

if not, establishing that an error condition exists.

Images