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

• US 20070089045A1
• Filed: 12/15/2005
• Published: 04/19/2007
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul, Corbett, Peter
• Granted Patent: US 7,640,484 B2
• Time in Patent Office: Days
• US Class Current: 714/801
• 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 or fewer concurrent failures of storage devices in a storage array, the method comprising the steps of:

providing the array with a predetermined number 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;

dividing each device into blocks;

organizing the blocks into stripes that contain a same number of blocks in each device, wherein each stripe comprises n−

3 rows of blocks;

defining the diagonal parity along diagonal parity sets that span the first devices, wherein the diagonal parity sets wrap around within a group of n−

3 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe;

computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device.

defining the anti-diagonal parity along anti-diagonal parity sets that span the first devices, wherein the anti-diagonal parity set wraps around within a group of n−

3 rows so that all blocks belonging to the anti-diagonal parity sets of a stripe are stored in the stripe; and

computing and storing the anti-diagonal parity for all the diagonal parity sets except one on the anti-diagonal parity device.

2. The method of claim 1 wherein row parity blocks in a stripe are all stored on a single device.

3. The method of claim 1 wherein the first devices include a plurality of data devices, and wherein the data devices are not all present and absent data devices are treated as containing zero-valued data.

4. The method of claim 1 wherein locations of parity blocks shift from device to device within different stripes.

5. The method of claim 1 wherein the stripes are a power of two number of bits in size.

6. A system configured to enable recovery from three or fewer concurrent failures of two storage devices, the system comprising:

an array having a predetermined number 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;

a storage operating system including a device storage layer configured to implement a triple parity (TP) technique that (i) computes the diagonal parity along diagonal parity sets that span the first devices, (ii) stores the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device, (iii) computes the anti-diagonal parity along anti-diagonal parity sets that span the first devices, and (iv) stores the anti-diagonal parity for all of the anti-diagonal parity sets except one on the anti-diagonal parity device; and

a processing element configured to execute the storage operating system to thereby invoke storage access operations to and from the array in accordance with the TP parity technique.

7. The system of claim 6 wherein row parity blocks in a stripe are all stored on a single device.

8. The system of claim 6 wherein the device storage layer is a RAID system and wherein the storage devices are disks.

9. The system of claim 6 wherein the RAID system further divides each disk into blocks and organizes the blocks into stripes.

10. The system of claim 9 wherein each stripe comprises n−

3 rows of blocks, with n=p+2, wherein each row contains one block from each disk.

11. The system of claim 8 wherein the RAID system is implemented in logic circuitry.

12. The system of claim 6 wherein the devices are one of video tape, magnetic tape, optical, DVD, bubble memory, magnetic disk, electronic random access memory and micro-electro mechanical storage devices.

13. The system of claim 6 wherein the first devices include a plurality of data devices, and wherein the data devices are not all present and absent data devices are treated as containing zero-valued data.

14. An apparatus for enabling recovery from three or fewer concurrent failures of two storage devices in a storage array, the apparatus comprising:

means for providing the array with a predetermined number 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;

means for dividing each device into blocks;

means for organizing the blocks into stripes that contain a same number of blocks in each device, wherein each stripe comprises n−

3 rows of blocks;

means for defining the diagonal parity along diagonal parity sets that span the first devices, wherein the diagonal parity sets wrap around within a group of n−

3 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe;

means for computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device;

means for defining the anti-diagonal parity along anti-diagonal parity sets that span the first devices, wherein the anti-diagonal parity set wraps around within a group of n−

3 rows so that all blocks belonging to the anti-diagonal parity sets of a stripe are stored in the stripe; and

means for computing and storing the anti-diagonal parity for all the anti-diagonal parity sets except one on the anti-diagonal parity device.

15. The apparatus of claim 14 wherein row parity blocks in a stripe are all stored on a single device.

16. The apparatus of claim 14 further comprising:

means for dividing each device into blocks; and

means for organizing the blocks into stripes.

17. The apparatus of claim 16 wherein the means for storing comprises means for storing diagonal parity blocks on the diagonal parity disk for each of the diagonal parity sets of a stripe except one.

18. The apparatus of claim 16 wherein the means for storing comprises means for storing anti-diagonal parity blocks on the anti-diagonal parity disk for each of the anti-diagonal parity sets of a stripe except one.

19. The apparatus of claim 14 wherein the first devices include a plurality of data devices, and wherein the data devices are not all present and absent data devices are treated as containing zero-valued data.

20. The apparatus of claim 16 wherein the stripes are a power of two number of bits in size.

21. The apparatus of claim 16 wherein a number of blocks in each stripe multiplied by a first block size, is equal to a second block size used by a file system to access the storage array.

22. A computer readable medium containing executable program instructions for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the executable program instructions comprising program instructions for:

providing the array with a predetermined number 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;

dividing each device into blocks;

organizing the blocks into stripes that contain a same number of blocks in each device, wherein each stripe comprises n−

3 rows of blocks;

defining the diagonal parity along diagonal parity sets that span the first devices, wherein the diagonal parity sets wrap around within a group of n−

3 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe;

computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device;

defining the anti-diagonal parity along anti-diagonal parity sets that span the first devices, wherein the anti-diagonal parity set wraps around within a group of n−

3 rows so that all blocks belonging to the anti-diagonal parity sets of a stripe are stored in the stripe; and

computing and storing the anti-diagonal parity for all the diagonal parity sets except one on the anti-diagonal parity device.

23. The computer readable medium of claim 22 wherein row parity blocks in a stripe are all stored on a single device.

24. A method for enabling recovery from three or fewer concurrent failures of three storage devices in a storage array, the method comprising the steps of:

providing the array with a predetermined number 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;

computing the diagonal parity along diagonal parity sets that span the first devices;

storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device;

computing the anti-diagonal parity along anti-diagonal parity sets that span the first devices; and

storing the anti-diagonal parity for all of the anti-diagonal parity sets except one on the anti-diagonal parity device.

25. The method of claim 24 further comprising the steps of:

dividing each device into blocks; and

organizing the blocks into stripes.

26. The method of claim 24 wherein the first devices include a plurality of data devices, and wherein the data devices are not all present and absent data devices are treated as containing zero-valued data.

27. The method of claim 24 wherein the predetermined number of storage devices is n, and wherein n=p+2 and p is a prime number.

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

computing a dropped diagonal parity and anti-diagonal parity;

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 failed storage device.

29. The method of claim 28 wherein the step of computing the dropped diagonal parity comprises the step of computing a parity of blocks on a diagonal parity storage device.

30. The method of claim 28 wherein the step of computing the dropped anti-diagonal parity comprises the step of computing a parity of blocks on an anti-diagonal parity storage device.

31. The method of claim 28 wherein the step of computing a set of 4-tuple sums on a middle storage device further comprises the steps of:

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;

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

32. The method of claim 28 further comprising the steps of:

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

recovering the middle storage device.

33. The method of claim 32 further comprising the step of performing a row-diagonal parity recovery technique to recover the other failed storage devices.

34. The method of claim 28 wherein the storage devices are disks.

35. The method of claim 28 wherein the algebraic operation comprises an exclusive or (XOR) sum.