×

Storage assignment technique for scalable and fault tolerant storage system

  • US 8,364,891 B2
  • Filed: 04/04/2007
  • Issued: 01/29/2013
  • Est. Priority Date: 04/04/2006
  • Status: Active Grant
First Claim
Patent Images

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 all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×