Technique for correcting multiple storage device failures in a storage array

• US 7,509,525 B2
• Filed: 06/02/2006
• Issued: 03/24/2009
• Est. Priority Date: 03/08/2002
• Status: Expired due to Fees

• 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): Beausoliel; Robert
• Assistant Examiner(s): GUYTON, PHILIP A
• Application Number:
  US11/446,495
• Publication Number:
  US 20060224917A1
• Time in Patent Office: 1,026 Days
• Field of Search: 714/6, 714/804, 714/770, 714/800, 714/802, 714/755
• US Class Current: 714/6.2
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A method for storing data for correction of multiple data storage failures in a storage array is presented. The storage array is organized as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array. A plurality of diagonal parity sets is computed, one diagonal parity set for each sub-array. A global diagonal parity is computed by logically combining together a plurality of the diagonal parity sets. The global diagonal parity is stored in a plurality of global diagonal parity storage blocks.

Claims

1. A method for storing data for correction of multiple data storage failures in a storage array, comprising:

organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;

computing a plurality of diagonal parity sets, one diagonal parity set for each sub-array;

computing a global diagonal parity by logically combining together a plurality of the diagonal parity sets; and

storing the global diagonal parity in a plurality of global diagonal parity storage blocks.

2. The method of claim 1, further comprising:

storing the diagonal parity storage blocks in a global parity storage device.

3. The method of claim 1, further comprising:

storing the local parity storage blocks in a local parity storage device.

4. The method of claim 1, wherein each sub-array is organized as a distributed parity device array.

5. The method of claim 1, further comprising:

using exclusive OR operations to logically combine the plurality of diagonal parity sets.

6. The method of claim 1, further comprising:

reconstructing the diagonal parity blocks of any sub-array having a storage error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global diagonal parity storage blocks.

7. The method of claim 1, further comprising:

reconstructing multiple errors in either data and parity storage blocks in response to the local parity storage blocks and the global diagonal parity storage blocks.

8. An apparatus to store data for correction of multiple data storage failures in a storage array, comprising:

means for organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub- array;

means for computing a plurality of diagonal parity sets, one diagonal parity set for each sub-array;

means for computing a global diagonal parity by logically combining together a plurality of the diagonal parity sets; and

means for storing the global diagonal parity in a plurality of global diagonal parity storage blocks.

9. The apparatus of claim 8, further comprising:

means for storing the diagonal parity storage blocks in a global parity storage device.

10. The apparatus of claim 8, further comprising:

means for storing the local parity storage blocks in a local parity storage device.

11. The apparatus of claim 8, wherein each sub-array is organized as a distributed parity device array.

12. The apparatus of claim 8, further comprising:

means for using exclusive OR operations to logically combine the plurality of diagonal parity sets.

13. The apparatus of claim 8, further comprising:

means for reconstructing the diagonal parity blocks of any sub-array having a storage error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global diagonal parity storage blocks.

14. The apparatus of claim 9, further comprising:

means for reconstructing multiple errors in either data and parity storage blocks in response to the local parity storage blocks and the global diagonal parity storage blocks.

15. An apparatus to store data for correction of multiple data storage failures in a storage array, comprising:

a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks to store parity information for a corresponding sub-array;

a processor to compute a plurality of diagonal parity sets, one diagonal parity set for each sub-array;

the processor to compute a global diagonal parity by logically combining together a plurality of the diagonal parity sets; and

a disk away to store the global diagonal parity in a plurality of global diagonal parity storage blocks.

16. The apparatus of claim 15, further comprising:

a global parity storage device to store the diagonal parity storage blocks.

17. The apparatus of claim 15, further comprising:

a local parity storage device to store the local parity storage blocks.

18. The apparatus of claim 15, wherein each sub-array is organized as a distributed parity device array.

19. The apparatus of claim 15, further comprising:

a processor to use exclusive OR operations to logically combine the plurality of diagonal parity sets.

20. The apparatus of claim 15, further comprising:

a processor to reconstruct the diagonal parity blocks of any sub-array having a storage error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global diagonal parity storage blocks.

21. The apparatus of claim 15, further comprising:

a processor to reconstruct multiple errors in either data and parity storage blocks in response to the local parity storage blocks and the global diagonal parity storage blocks.

22. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method for storing data for correction of multiple data storage failures in a storage array, the method having the steps of,

organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;

computing a plurality of diagonal parity sets, one diagonal parity set for each sub-array;

computing a global diagonal parity by logically combining together a plurality of the diagonal parity sets; and

storing the global diagonal parity in a plurality of global diagonal parity storage blocks.