Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array

• US 7,203,892 B2
• Filed: 12/16/2005
• Issued: 04/10/2007
• Est. Priority Date: 12/28/2001
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Primary Examiner(s): KERVEROS, DEMETRIOS C
• Application Number:
  US11/303,788
• Publication Number:
  US 20060107135A1
• Time in Patent Office: 480 Days
• Field of Search: 714/718, 714/763, 714/770, 714/6, 714/7, 711/114
• US Class Current: 714/770
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A “row-diagonal” (R-D) parity technique reduces overhead of computing diagonal parity for a storage array adapted to enable efficient recovery from the concurrent failure of two storage devices in the array. The diagonal parity is computed along diagonal parity sets that collectively span all data disks and a row parity disk of the array. The parity for all of the diagonal parity sets except one is stored on the diagonal parity disk. The R-D parity technique provides a uniform stripe depth and an optimal amount of parity information.

Claims

1. A method for enabling recovery from concurrent failure of two storage devices in a storage array, comprising:

storing data and row parity on a plurality of storage devices, the data configured as rows of blocks on the plurality of storage devices, where a number of the plurality of storage devices is equal to a prime number greater then three;

computing a diagonal parity set for the plurality of storage devices; and

storing the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the plurality of storage devices, where the plurality of storage devices combine with the separate diagonal parity device to form the storage array.

2. The method as in claim 1, further comprising:

predetermining a total number of storage devices in the storage array as n, where n is p+1, and where p is the prime number, and the one is for the additional diagonal parity device.

3. The method as in claim 1, wherein the row parity blocks are stored on a single storage device of the plurality of storage devices.

4. The method as in claim 1, further comprising:

configuring the plurality of storage devices so that not all first storage devices are present, and treating absent data storage devices as containing zero valued data.

5. The method as in claim 1, further comprising:

computing row parity blocks by an encoding of data blocks that is tolerant of single device failures.

6. The method as in claim 1, further comprising:

configuring each row to have one row parity block and one diagonal parity block.

7. The method as in claim 1, further comprising:

placing parity blocks in different locations in different stripes from device to device.

8. The method as in claim 1, further comprising:

implementing a row-diagonal (R-D) parity technique that computes the diagonal parity along diagonal parity sets that span the plurality of storage devices, and that stores the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device.

9. The method as in claim 1, further comprising:

invoking storage access operations to and from the array in accordance with a R-D parity technique.

10. The method as in claim 1, further comprising:

configuring the array as a RAID system of computer storage units.

11. The method as in claim 1, further comprising:

configuring the array as a RAID system of computer storage disks;

organizing each computer storage disk into blocks; and

organizing the blocks into stripes, the stripes extending across a plurality of the computer storage disks.

12. An apparatus for enabling recovery from concurrent failure of two storage devices in a storage array, comprising:

means for storing data and row parity on a plurality of storage devices, the data configured as rows of blocks on the plurality of storage devices, where a number of the plurality of storage devices is equal to a prime number greater then three;

means for computing a diagonal parity set for the plurality of storage devices; and

means for storing the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the plurality of storage devices, where the plurality of storage devices combine with the separate diagonal parity device to form the storage array.

13. The apparatus as in claim 12, further comprising:

means for predetermining a total number of storage devices in the storage array as n, where n is p+1, and where p is the prime number, and the one is for the additional diagonal parity device.

14. The apparatus as in claim 12,

wherein the row parity blocks are stored on a single storage device of the plurality of storage devices.

15. The apparatus as in claim 12, further comprising:

means for configuring the plurality of storage devices so that not all storage devices are present, and treating absent data storage devices as containing zero valued data.

16. The apparatus as in claim 12, further comprising:

means for computing row parity blocks by an encoding of data blocks that is tolerant of single device failures.

17. The apparatus as in claim 12, further comprising:

means for configuring each row to have one row parity block and one diagonal parity block.

18. The apparatus as in claim 12, further comprising:

means for placing parity blocks in different locations in different stripes from device to device.

19. The apparatus as in claim 12, further comprising:

means for implementing a row-diagonal (R-D) parity technique that computes the diagonal parity along diagonal parity sets that span the plurality of storage devices, and that stores the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device.

20. The apparatus as in claim 12, further comprising:

means for invoking storage access operations to and from the array in accordance with a R-D parity technique.

21. The apparatus as in claim 12, further comprising:

means for configuring the array as a RAID system of computer storage units.

22. The apparatus as in claim 12, further comprising:

means for configuring the array as a RAID system of computer storage disks;

means for organizing each computer storage disk into blocks; and

means for organizing the blocks into stripes, the stripes extending across a plurality of the computer storage disks.

23. A system for enabling recovery from concurrent failure of two storage devices in a storage array, comprising:

a plurality of storage devices to store data and row parity, the data configured as rows of blocks on the plurality of storage devices, where a number of the plurality of storage devices is equal to a prime number greater then three; and

a storage operating system is configured to compute a diagonal parity set for the plurality of storage devices, and to store the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the plurality of storage devices, where the plurality of storage devices combine with the separate diagonal parity device to form the storage array.

24. The system as in claim 23, further comprising:

the plurality of storage devices configured with a predetermined number of storage devices in the storage array as n, where n is p+1, and where p is the prime number, and the one is for the additional diagonal parity device.

25. The system as in claim 23, wherein a single storage device of the plurality of storage devices, where the single storage device is configured to store row parity blocks.

26. The system as in claim 23, further comprising:

the plurality of storage devices configured so that not all storage devices are present, and treating absent data storage devices as containing zero valued data.

27. The system as in claim 23, further comprising:

the storage operating system to compute row parity blocks by an encoding of data blocks that is tolerant of single device failures.

28. The system as in claim 23, further comprising:

the storage operating system to configure each row to have one row parity block and one diagonal parity block.

29. The system as in claim 23, further comprising:

the storage operating system to place parity blocks in different locations in different stripes from device to device.

30. The system as in claim 23, further comprising:

the storage operating system to implement a row-diagonal (R-D) parity technique that computes the diagonal parity along diagonal parity sets that span the plurality of storage devices, and that stores the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device.

31. The system as in claim 23, further comprising:

the storage operating system to invoke storage access operations to and from the array in accordance with a R-D parity technique.

32. The system as in claim 23, further comprising:

the storage operating system to configure the array as a RAID system of computer storage units.

33. The system as in claim 23, further comprising:

the storage operating system to configure the array as a RAID system of computer storage disks, organizes each computer storage disk into blocks, and organizes the blocks into stripes, the stripes extending across a plurality of the computer storage disks.

34. A computer readable media, comprising:

said computer readable media having instructions written thereon for execution on a processor for the practice of enabling recovery from concurrent failure of two storage devices in a storage array comprising,

storing data and row parity on a plurality of storage devices, the data configured as rows of blocks on the plurality of storage devices, where a number of the plurality storage devices is equal to a prime number greater then three;

computing a diagonal parity set for the plurality of storage devices; and

storing the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the plurality of storage devices, where the plurality of storage devices combine with the separate diagonal parity device to form the storage array.

35. A method for enabling recovery from concurrent failure of two storage devices in a storage array, comprising:

configuring a plurality of storage devices with data and row parity stored in a stripe across the plurality of storage devices with one block stored on each storage device of the plurality of storage devices of each row of the stripe;

configuring an additional storage device with diagonal parity, a diagonal parity storage device;

determining that two storage devices of the plurality of storage devices have failed resulting in missing blocks;

reconstructing a first missing block using diagonal parity, where the first missing block is within a diagonal with only one missing block; and

reconstructing other missing block in same row as the first missing block.

36. The method of claim 35, further comprising:

reconstructing a next missing block using diagonal parity, where the next missing block is within a next diagonal with only one missing block;

reconstructing other missing block in same row as the next missing block; and

repeating above steps for any remaining missing blocks.

37. The method of claim 35, wherein a total number of storage devices used in the storage array includes both the plurality of storage devices and the diagonal parity storage device, where the total number of devices (n) is equal to one plus a prime number (p) greater then three.

38. The method of claim 37, wherein each stripe has n−

2 rows of blocks.

39. The method of claim 35, further comprising:

placing row parity blocks in different devices in different stripes across the plurality of storage devices.

40. The method of claim 35, further comprising:

implementing a row-diagonal (R-D) parity technique that computes the diagonal parity along diagonal parity sets that span the first storage devices, and that stores the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device.

41. The method of claim 35, further comprising:

storing row parity blocks for the stripe on a single disk of the plurality of storage devices.