Storage assignment technique for scalable and fault tolerant storage system
First Claim
1. 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.
4 Assignments
0 Petitions
Accused Products
Abstract
A method for organizing 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.
-
Citations
22 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
Specification