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

• US 8,015,472 B1
• Filed: 08/21/2008
• Issued: 09/06/2011
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul, Corbett, Peter F.
• Primary Examiner(s): KERVEROS, DEMETRIOS C
• Application Number:
  US12/195,968
• Time in Patent Office: 1,111 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:

detecting that three storage devices in the storage array have concurrently failed, wherein the storage array is made up of a predetermined number n of storage devices, including a plurality of first devices configured to store data and row parity, one diagonal parity device configured to store diagonal parity and one anti-diagonal parity device configured to store anti-diagonal parity, wherein the predetermined number of storage devices n is p+2 and wherein p is a prime number;

computing both diagonal parity and anti-diagonal parity that were not previously stored for the three failed storage devices;

computing an algebraic operation on missing blocks on each of a set of failed storage devices along a row, a diagonal and an anti-diagonal; and

computing a set of 4-tuple sums on a middle storage device of the three failed storage devices to enable recovery of the three concurrently failed storage devices.

2. The method of claim 1, wherein computing the diagonal parity that was not previously stored for the three failed storage devices comprises computing a parity of blocks on the diagonal parity device.

3. The method of claim 1, wherein computing the anti-diagonal parity that was not previously stored for the three failed storage devices comprises computing a parity of blocks on the anti-diagonal parity device.

4. The method of claim 1, wherein computing the set of 4-tuple sums on the middle storage device of the three failed storage devices, further 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 the results of (b), (c), (d) and (e) to form the 4-tuple sum.

5. The method of claim 1, 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 devices are disks.

8. The method of claim 1, wherein the algebraic operation comprises an exclusive or (XOR) sum.

9. A non-transitory computer readable medium containing executable program instructions executed by a processor, comprising:

program instructions that detect that three storage devices in a storage array have concurrently failed, wherein the storage array is made up of a predetermined number n of storage devices, including a plurality of first devices configured to store data and row parity, one diagonal parity device configured to store diagonal parity and one anti-diagonal parity device configured to store anti-diagonal parity, wherein the predetermined number of storage devices n is p+2 and wherein p is a prime number;

program instructions that compute a diagonal parity and anti-diagonal parity that was not previously stored for the three failed storage devices;

program instructions that compute an algebraic operation on missing blocks on each of a set of failed storage devices along a row, a diagonal and an anti-diagonal; and

program instructions that compute a set of 4-tuple sums on a middle storage device of the three failed storage devices to enable recovery of the three concurrently failed storage devices.

10. The non-transitory computer readable medium of claim 9, wherein the program instruction that computes the diagonal parity that was not previously stored for the three failed storage devices comprises program instructions that compute a parity of blocks on the diagonal parity device.

11. The non-transitory computer readable medium of claim 9, wherein the program instruction that computes the anti-diagonal parity that was not previously stored for the three failed storage devices comprises program instructions that compute a parity of blocks on the anti-diagonal parity device.

12. The non-transitory computer readable medium of claim 9, wherein the program instructions that computes the set of 4-tuple sums on the middle storage device of the three failed storage devices further comprises program instructions that:

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

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

13. The non-transitory computer readable medium of claim 9, further comprising:

program instructions that reduce the 4-tuple sums to a set of pairwise sums on the middle storage device of the three failed storage devices; and

program instructions that recover the middle storage device of the three failed storage devices.

14. The non-transitory computer readable medium of claim 13, further comprising program instructions that perform a row-diagonal parity recovery technique to recover the other failed storage devices.

15. The non-transitory computer readable medium of claim 9, wherein the algebraic operation comprises an exclusive or (XOR) sum.

16. A storage system to enable recovery from three concurrent failures of storage devices in a storage array, comprising:

a processor configured to execute a storage operating system on the storage system, the storage operating system when executed configured to

detect that three storage devices in the storage array have concurrently failed wherein the storage array is made up of a predetermined number n of storage devices, including a plurality of first devices configured to store data and row parity, one diagonal parity device configured to store diagonal parity and one anti-diagonal parity device configured to store anti-diagonal parity, wherein the predetermined number of storage devices n is p+2 and wherein p is a prime number,

compute a diagonal parity and anti-diagonal parity that was not previously stored for the three failed storage devices,

compute an algebraic operation on missing blocks on each of a set of failed storage devices along a row, a diagonal and an anti-diagonal, and

compute a set of 4-tuple sums on a middle storage device of the three failed storage devices to enable recovery of the three concurrently failed storage devices.

17. The storage system of claim 16, wherein the storage operating system is further configured to compute a parity of blocks on the diagonal parity device when computing the diagonal parity that was not previously stored for the three failed storage devices.

18. The storage system of claim 16, wherein the storage operating system is further configured to compute a parity of blocks on the anti-diagonal parity device when computing the anti-diagonal parity that was not previously stored for the three failed storage devices.

19. The storage system of claim 16, wherein the storage operating system when computing a set of 4-tuple sums on the middle storage device of the three failed storage devices is further 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 the results of (b), (c), (d) and (e) to form the 4-tuple sum.

20. The storage system of claim 16, 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 to recover the middle storage device of the three failed storage devices.

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

22. The storage system of claim 16, wherein the storage devices are disks.

23. The storage system of claim 16, wherein the algebraic operation comprises an exclusive or (XOR) sum.