A method for organizing a storage system that is scalable and fault tolerant, the method comprising: associating with a block of data to be stored in the storage system a block address that uniquely identifies the block of data, independently of where it is stored or moved within the storage system; computing, for each of D>1 storage elements that constitute the storage system, an available capacity that depends on constraints on the placement of redundant data within the storage system, with the sum of the available capacities defining a total available capacity; constructing a storage assignment table that comprises a plurality of table entries, each table entry associated with a respective range of block addresses and each table entry identifying a respective one of the storage elements assigned to the respective range; encoding the block of data as a set of R>2 redundant data components (B 1, B 2, B 3), so that the block of data can be reconstructed from a proper subset of the set of R redundant data components (B 1, B 2, B 3); and storing a one of the set of R redundant data components (B 1, B 2, B 3) in a one of the storage elements, using the block address to locate an entry in the storage assignment table that identifies the one of the storage elements; wherein not all of the D storage elements that form the storage system have the same available capacity; wherein the block address is determined using a process designed to produce a random distribution of values; and wherein the fraction of the table entries that identify each of the storage elements is equal to its fraction of the total available capacity, to within a pre-assigned tolerance, T wherein if the one of the storage elements fails or is removed from the storage system, the table entry that identified the one of the storage elements is reassigned to identify a remaining one of the storage elements, and the one of the set of R redundant data components (B 1, B 2, B 3) is reconstructed by the remaining one of the storage elements from remaining ones of the set of R redundant data components (B 1, B 2, B 3). associating with a block of data to be stored in the storage system a block address that uniquely identifies the block of data, independently of where it is stored or moved within the storage system; computing, for each of D>1 storage elements that constitute the storage system, an available capacity that depends on constraints on the placement of redundant data within the storage system, with the sum of the available capacities defining a total available capacity; constructing a storage assignment table that comprises a plurality of table entries, each table entry associated with a respective range of block addresses and each table entry identifying a respective one of the storage elements assigned to the respective range; encoding the block of data as a set of R>2 redundant data components (B 1, B 2, B 3), so that the block of data can be reconstructed from a proper subset of the set of R redundant data components (B 1, B 2, B 3); and storing a one of the set of R redundant data components (B 1, B 2, B 3) in a one of the storage elements, using the block address to locate an entry in the storage assignment table that identifies the one of the storage elements; wherein not all of the D storage elements that form the storage system have the same available capacity; wherein the block address is determined using a process designed to produce a random distribution of values; and wherein the fraction of the table entries that identify each of the storage elements is equal to its fraction of the total available capacity, to within a pre-assigned tolerance, T wherein if the one of the storage elements fails or is removed from the storage system, the table entry that identified the one of the storage elements is reassigned to identify a remaining one of the storage elements, and the one of the set of R redundant data components (B 1, B 2, B 3) is reconstructed by the remaining one of the storage elements from remaining ones of the set of R redundant data components (B 1, B 2, B 3).