Patent ID: 8364891

Claim:
A method for organizing a storage system that is scalable and fault tolerant, the method comprising: grouping together a number D of storage elements to form the storage system, where D is more than one; constructing a storage assignment table that comprises table entries; computing, for each of the storage elements, an available capacity that depends on constraints on the placement of redundant data within the storage system; summing the available capacities to form a total available capacity for the storage system; assigning the table entries in the storage assignment table to each identify one of the storage elements; determining a block address that uniquely identifies a block of data independently of where it is stored within the storage system; encoding the block of data as a set of R redundant data components, not all of which are needed in order to reconstruct the block; selecting a table entry within the storage assignment table using the block address; identifying a one of the storage elements using the selected table entry; and storing a one of the set of R redundant data components on the one of the storage elements; wherein the available capacity of each of the storage elements is its effective storage capacity when used as part of the storage system; wherein not all of the D storage elements that form the storage system have the same available capacity; wherein the fraction of the table entries that identify the one of the storage elements is equal to its fraction of the total available capacity, to within a preassigned small tolerance T; and wherein if the one of the storage elements fails and a plurality of redundant data components stored on it become inaccessible, the storage assignment table is updated to reassign the inaccessible redundant data components to a remaining plurality of the storage elements that have not failed, and the inaccessible redundant data components are recreated and stored on the remaining storage elements.