Triple parity technique for enabling efficient recovery from triple failures in a storage array

• US 8,516,342 B2
• Filed: 05/15/2012
• Issued: 08/20/2013
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Corbett, Peter F., Goel, Atul
• Primary Examiner(s): Kerveros, James C
• Application Number:
  US13/472,133
• Publication Number:
  US 20120324284A1
• Time in Patent Office: 462 Days
• Field of Search: 714/770
• 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
• CPC Class Codes: G06F 2211/1061 Parity-single bit-RAID4, i.e. RAID 4 implementations

Abstract

A triple parity (TP) technique reduces overhead of computing diagonal and anti-diagonal parity for a storage array adapted to enable efficient recovery from the concurrent failure of three 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. Similarly, the anti-diagonal parity is computed along anti-diagonal parity sets that collectively span all data disks and a row parity disk of the array. The parity for all of the anti-diagonal parity sets except one is stored on the anti-diagonal parity disk. The TP technique provides a uniform stripe depth and an optimal amount of parity information.

Claims

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

executing, by a processor, a storage operating system of a computer;

determining, by the storage operating system, that three storage devices of the storage array have concurrently failed; and

in response to determining that the three storage devices have concurrently failed, executing, by the storage operating system, a triple parity recovery technique, wherein the triple parity recovery technique includes the storage operating system computing a diagonal parity block on a diagonal parity storage device of the storage array and an anti-diagonal parity block on an anti-diagonal parity storage device of the storage array that were not previously stored for the three failed storage devices.

2. The method of claim 1, further comprising:

computing a set of 4-tuple sums on a middle storage device of the three failed storage devices;

reducing the 4-tuple sums to a set of pairwise sums on the middle storage device of the three failed storage devices; and

recovering the middle storage device of the three failed storage devices.

3. The method of claim 2 further comprising performing a row-diagonal parity recovery technique to recover other failed storage devices of the three failed storage devices.

4. The method of claim 1 further comprising providing p+2 storage devices in the storage array, wherein p comprises a prime number.

5. The method of claim 4 further comprising computing p diagonal parities, wherein each diagonal parity is computed by performing an operation on p−

1 blocks.

6. The method of claim 5 wherein the operation comprises an XOR operation.

7. The method of claim 5 wherein the p−

1 blocks are selected from a group consisting of data blocks and row parity blocks.

8. The method of claim 4 further comprising computing p anti-diagonal parities, where each anti-diagonal parity is computed by performing an operation on p−

1 blocks.

9. The method of claim 8 wherein the operation comprises an XOR operation.

10. The method of claim 8 wherein the p−

1 blocks are selected from a group consisting of data blocks and row parity blocks.

11. The method of claim 1 further comprising:

computing a row parity value to be stored on a row parity storage device of the array of storage devices;

computing a diagonal parity block using both data blocks and at least one row parity block; and

computing an anti-diagonal parity block using both the data blocks and the at least one row parity block.

12. The method of claim 1 wherein the diagonal parity storage device stores all but one diagonal parity block.

13. The method of claim 1 wherein the anti-diagonal parity storage device stores all but one anti-diagonal parity block.

14. A system configured to enable recovery from three concurrent failures of storage devices in a storage array operatively connected to a computer, comprising:

a processor configured to execute a storage operating system of the computer;

the storage operating system, when executed, configured to determine that three storage devices of the storage array have concurrently failed; and

the storage operating system, in response to determining that the three storage devices have concurrently failed, further configured to execute a triple parity recovery technique, wherein the triple parity recovery technique includes the storage operating system configured to compute a diagonal parity block on a diagonal parity storage device of the storage array and an anti-diagonal parity block on an anti-diagonal parity storage device of the storage array that were not previously stored for the three failed storage devices.

15. The system of claim 14, further comprising:

the storage operating system further configured to compute a set of 4-tuple sums on a middle storage device of the three failed storage devices, reduce the 4-tuple sums to a set of pairwise sums on the middle storage device of the three failed storage devices and recover the middle storage device of the three failed storage devices.

16. The system of claim 15 further wherein the storage operating system is further configured to perform a row-diagonal parity recovery technique to recover other failed storage devices of the three failed storage devices.

17. A computer-readable storage medium stored with executable program instructions for execution by a processor, comprising:

program instructions that execute a storage operating system of a computer;

program instructions that determine, for the storage operating system, that three storage devices of a storage array of the computer have concurrently failed; and

program instructions that, in response to determining that the three storage devices have concurrently failed, execute a triple parity recovery technique, wherein the triple parity recovery technique includes program instructions that compute a diagonal parity block on a diagonal parity storage device of the storage array and an anti-diagonal parity block on an anti-diagonal parity storage device of the storage array that were not previously stored for the three failed storage devices.