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

• US 8,181,090 B1
• Filed: 08/31/2011
• Issued: 05/15/2012
• 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/223,211
• Time in Patent Office: 258 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 the 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 comprises the storage operating system computing a diagonal parity block and an anti-diagonal parity block that were not previously stored for the three failed storage devices.

2. The method of claim 1, wherein computing the diagonal parity and the anti-diagonal parity that were not previously stored comprises computing the diagonal parity block on a diagonal parity storage device of the storage array and computing the anti-diagonal parity block on an anti-diagonal parity storage device of the storage array.

3. The method of claim 1, wherein executing the triple parity recovery technique further comprises computing a set of 4-tuple sums on a middle storage device of the three failed storage devices.

4. The method of claim 3, wherein computing the set of 4-tuple sums on the middle storage device comprises:

ordering the failed storage devices;

for each row of the storage devices;

(a) selecting a row of the storage array;

(b) retrieving row parity sum of blocks on missing storage devices corresponding to the selected row;

(c) retrieving diagonal parity for a block on the selected row for a first failed storage device;

(d) retrieving anti-diagonal parity for a block on the selected row for a second failed storage device;

(e) retrieving row parity sum of blocks on missing storage devices corresponding to a row where the anti-diagonal and diagonal end; and

performing an exclusive or (XOR) operation on results of (b), (c), (d) and (e) to form the 4-tuple sum.

5. The method of claim 3, further comprising:

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.

6. The method of claim 5, further comprising performing a row-diagonal parity recovery technique to recover the other failed storage devices.

7. The method of claim 1, wherein the storage array comprises a disk.

8. The method of claim 1, further comprising performing an algebraic operation on one or more of the blocks not previously stored missing blocks on the storage array.

9. 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 comprises the storage operating system computing a diagonal parity block and an anti-diagonal parity block that were not previously stored for the three failed storage devices.

10. The system of claim 9, wherein the storage operating system is configured to compute the diagonal parity block on a diagonal parity storage device of the storage array and compute the anti-diagonal parity block on an anti-diagonal parity storage device of the storage array to compute the diagonal parity and the anti-diagonal parity that were not previously stored.

11. The system of claim 9, wherein the storage operating system is configured to computing a set of 4-tuple sums on a middle storage device of the three failed storage devices to execute the triple parity recovery technique.

12. The system of claim 11, wherein to compute the set of 4-tuple sums on the middle storage device, storage operating system is configured to:

order the failed storage devices;

for each row of the storage devices;

(a) select a row of the storage array;

(b) retrieve row parity sum of blocks on missing storage devices corresponding to the selected row;

(c) retrieve diagonal parity for a block on the selected row for a first failed storage device;

(d) retrieve anti-diagonal parity for a block on the selected row for a second failed storage device;

(e) retrieve row parity sum of blocks on missing storage devices corresponding to a row where the anti-diagonal and diagonal end; and

performing an exclusive or (XOR) operation on results of (b), (c), (d) and (e) to is form the 4-tuple sum.

13. The system of claim 11, wherein the storage operating system is further configured to:

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.

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

15. The system of claim 9, wherein the storage array comprises a disk.

16. The system of claim 9, wherein the storage operating system is further configured to perform an algebraic operation on one or more of the blocks not previously stored missing blocks on the storage array.

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

program instructions that execute, by a processor, a storage operating system of a computer;

program instructions that determine, by 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 comprises program instructions that compute a diagonal parity block and an anti-diagonal parity block that were not previously stored for the three failed storage devices.

18. The computer-readable storage medium of claim 17, further comprising program instructions that compute the diagonal parity block on a diagonal parity storage device of the storage array.

19. The computer-readable storage medium of claim 17, further comprising program instructions that compute the anti-diagonal parity block on an anti-diagonal parity storage device of the storage array.

20. The computer-readable storage medium of claim 17, further comprising program instructions that compute a set of 4-tuple sums on a middle storage device of the three failed storage devices to execute the triple parity recovery technique.