STORAGE ASSIGNMENT AND ERASURE CODING TECHNIQUE FOR SCALABLE AND FAULT TOLERANT STORAGE SYSTEM

摘要

A method for organising a storage system that is scalable and fault tolerant, the method including 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 includes 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; and assigning the table entries in the storage assignment table to each identify 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, and wherein the fraction of all table entries that identify a one of the storage elements depends upon its fraction, of the total available capacity. A method for encoding a block, of data to allow it to be stored or transmitted correctly in the face of accidental or deliberate modifications, the method including constructing a numbern greater than one of original components, each of which is derived from the block and each of which is smaller than the block, and combining original components to construct a number m greater than one of new components, wherein each of the new components is smaller than the sum of the sizes of the original components combined to produce it. wherein the block can be reconstructed from any set of n different components selected from the original components and new components, and wherein a. set ofn different components selected from the original components, and new components contains more redundant information about the block than the set of n original components.