Concentrated parity technique for handling double failures and enabling storage of more than one parity block per stripe on a storage device of a storage array

• US 7,627,715 B1
• Filed: 01/31/2005
• Issued: 12/01/2009
• Est. Priority Date: 11/13/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Corbett, Peter F.
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US11/047,079
• Time in Patent Office: 1,765 Days
• Field of Search: 711/114, 714/6
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

A method for constructing an extended array of storage devices that enables storage of more than one parity block per stripe on a single device of the array is disclosed. Each device is divided into blocks. The blocks are organized into stripes across the devices, wherein each stripe contains a first number of parity blocks from each of a second number of parity storage devices of the array. Data blocks are stored on a third number of data storage devices, to thereby construct the array to enable storage of more than one parity block per stripe on a single device, wherein the extended array is recoverable from any one or two storage device failures.

Claims

1. A method for constructing an array of storage devices comprising:

dividing each of the devices into blocks;

storing data blocks on a first set of the devices;

storing more than one parity block on each of a second set of the devices;

forming a plurality of parity sets wherein each parity set includes a plurality of data blocks selected from less than all of the first set of devices and a parity block that is computed parity for the plurality of data blocks, and each data block belonging to two parity sets; and

organizing the array so that;

i) no data block belongs to two parity sets having parity blocks on the same device of the second set of the devices; and

ii) the array is recoverable from any one or two device failures.

2. The method of claim 1 wherein the devices are disks.

3. The method of claim 1, further comprising:

assigning the data blocks to parity sets, each parity set contains at least one data block and a parity block.

4. The method of claim 3, further comprising:

defining the parity sets, including the data and parity blocks within stripes in the first and second sets of devices.

5. The method of claim 4 wherein the first set of devices is a set of data devices and the second set of devices is a set of parity devices, and wherein each data device contains one or more blocks of a stripe and each parity device contains the same or fewer blocks from the stripe.

6. The method of claim 5, further comprising:

numbering each parity set from 0 to n−

1, where n is the number of data devices.

7. The method of claim 6, further comprising:

precluding assignment of certain parity deltas to the data blocks.

8. The method of claim 7 wherein the storing comprises storing the parity blocks separated by the precluded parity deltas on the single device of the second set.

9. The method of claim 8, further comprising:

configuring the array with a predetermined number of devices.

10. The method of claim 9 wherein the predetermined number of devices is an even number n and wherein one of the precluded parity deltas is n/2.

11. The method of claim 1 wherein storing comprises creating an unbalanced stripe array of data and parity blocks across the devices.

12. The method of claim 11 further comprising the step of combining a plurality of unbalanced stripe arrays to thereby produce a single balanced super-stripe array across the devices.

13. An array of storage devices, comprising:

a plurality of storage devices, each device of the plurality of storage devices divided into blocks that stripe the data into a plurality of data blocks, the data blocks stored on data devices and parity blocks stored on parity devices;

a storage operating system including a device storage layer configured to implement a concentrated parity technique that forms a plurality of parity sets wherein each parity set includes a plurality of data blocks selected from less than all of the data devices and a parity block that is computed parity for the plurality of data blocks, where each data block belongs to two parity set, the array organized so that;

i) no data block belongs to two parity sets having parity blocks on a same parity devices; and

ii) the array is recoverable from any one or two devices; and

a processing element configured to execute the operating system to thereby invoke storage access operations to and from the array in accordance with the concentrated parity technique.

14. The system of claim 13 wherein each parity set contains at least one data block and a parity block, while precluding assignment of certain parity deltas to the data blocks.

15. The system of claim 14 wherein the device storage layer further stores the parity blocks separated by the precluded parity deltas on a single device of the second set.

16. The system of claim 15 wherein the storage devices are media adapted to store information contained within the data and parity blocks.

17. A computer readable medium containing executable program instructions for constructing an array of storage devices, comprising:

program instructions that divide each device into blocks;

program instructions that store data blocks on a first set of the devices;

program instructions that store more than one parity block on each of a second set of devices;

program instructions that form a plurality of parity sets wherein each parity set includes a plurality of data blocks selected from less than all of the first set of devices and a parity block that is computed parity for the plurality of data blocks, and each data block belonging to two parity sets; and

program instructions that organize the array so that;

i) no data block belongs to two parity sets having parity blocks on the same device of the second set of devices; and

ii) the array is recoverable from any one or two device failures.

18. A method for storing parity for a plurality of storage devices, comprising:

dividing each device of the plurality of devices into blocks;

storing data into a plurality of data blocks, wherein the data blocks are stored on a first set of data devices;

storing parity blocks on a second set of parity devices;

organizing the plurality of data blocks and parity blocks into a plurality of parity sets, wherein each parity set includes a particular group of data blocks selected from less than all of the first set of data devices and a particular parity block that is computed parity for the group of data blocks, and each data block belongs to two parity sets; and

organizing the first set of data devices and the second set of parity devices in an array so that;

i) no data block belongs to two parity sets having parity blocks on the same parity device; and

ii) any one or two device failures is recoverable.

19. A method comprising:

dividing each device of a plurality of devices into blocks;

storing a plurality of data blocks on a first set of data devices;

storing more than one parity block on each of a second set of parity devices;

forming a plurality of parity sets, wherein each parity set includes a plurality of data blocks selected from less than all of the first set of devices and a parity block that is computed parity for the plurality of data blocks, and each data block belonging to two parity sets; and

organizing the first set of data devices and the second set of parity devices to construct an unbalanced stripe array so that;

i) no data block belongs to two parity sets having parity blocks on the same parity device; and

ii) any one or two device failures is recoverable.