Storage Assignment Technique for Scalable and Fault Tolerant Storage System

• US 20070245082A1
• Filed: 04/04/2007
• Published: 10/18/2007
• Est. Priority Date: 04/04/2006
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Permabit Technology Corporation (International Business Machines Corporation)
• Inventors: Margolus, Norman, Coburn, Jonathan
• Granted Patent: US 8,364,891 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2211/1023 Different size disks, i.e. non uniform size of disks in RAID systems with parity
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

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.

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; 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.

2. The method of claim 1 further comprising:

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;

locating a table entry within the storage assignment table using the block address;

identifying the one of the storage elements using the table entry; and

storing a one of the set of R redundant data components on the one of the storage elements.

3. The method of claim 1 wherein the fraction of all table entries that identify the one of the storage elements is equal to its fraction of the total available capacity, to within a preassigned tolerance T.

4. The method of claim 2 wherein the block address is determined using a process designed to produce a random distribution for at least portions of block addresses.

5. The method of claim 2 wherein the encoding step makes use of an ensure resilient code.

6. The method of claim 3 wherein a new storage element is added to the storage system, increasing the total available capacity, and the storage assignment table is updated in a manner that ensures that the fraction of all table entries that identify each of the storage elements is not more than (1+T) times its fraction of the total available capacity.

7. The method of claim 6 wherein the total available capacity increases by more than the available capacity of the new storage element.

8. The method of claim 3 wherein the one of the storage elements fails and is removed from the storage system, reducing the total available capacity, and the storage assignment table is updated to reassign all table entries that identified the one of the storage elements to instead identify remaining ones of the storage elements, with the reassignment performed in a manner than ensures that no remaining one of the storage elements is assigned a greater fraction of all the table entries than (1+T) times its fraction of the total available capacity.

9. The method of claim 1 wherein the storage allocation table is organized in a manner that groups together pluralities of table entries, with the different members of each plurality identifying different storage elements.

10. The method of claim 1 wherein the one of the storage elements comprises a computer attached to at least one disk drive, and the one of the storage elements makes use of a copy of the storage assignment table that is separate from copies used by others of the storage elements.

11. The method of claim 1 wherein storage is added to or removed from the storage system and the storage assignment table is updated by changing one entry at a time, with the decision to make some changes depending on a comparison of ratios, where each of the ratios consists of a number of entries in the table divided by an available capacity.

12. The method of claim 1 wherein storage is added to or removed from the storage system and the storage assignment table is updated by changing some entries, and the fraction of all entries that change is approximately equal to the fraction of the total available capacity represented by the storage that was added or removed.

13. The method of claim 1 wherein the one of the storage elements is assigned a reduced available capacity during a period of time when it is believed to have an enhanced risk of failure.

14. The method of claim 2 wherein the one of the storage elements comprises a second-level storage system and a portion of the block address is used to locate table entries within the storage assignment table, and the portion is different than a portion of th block address that is used to locate table entries within a storage assignment table used within the second-level storage system.

15. The method of claim 2 wherein the one of the storage elements fails and is removed from the storage system, and 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 date components is reconstructed by the remaining one of the storage elements from remaining ones of the set of R redundant data components.

16. The method of claim 2 wherein the one of the storage elements fails and is removed from the storage system causing D to become less than R, and a constraint that different redundant components be placed on different storage elements is relaxed.

17. The method of claim 2 wherein each of two blocks of data has a block address determined by computing a cryptographic hash of its data, and the two block share storage space in the storage system.

18. The method of claim 1 wherein there is at least one block of data stored in the storage system that is encoded as three or more redundant components, not al of which are needed in order to reconstruct the at least one block.