System and method for symmetric triple parity for failing storage devices

• US 7,979,779 B1
• Filed: 09/15/2009
• Issued: 07/12/2011
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul
• Primary Examiner(s): KERVEROS, DEMETRIOS C
• Application Number:
  US12/560,075
• Time in Patent Office: 665 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

Abstract

A symmetric triple parity (TP) technique in an array comprising a number p of storage devices, such as disks, with p being a prime number is provided. The p disks are organized as one row parity disk, two symmetric parity disks and p-3 data disks. Phantom diagonal and anti-diagonal parity disks assumed to be present are further assumed to contain a predetermined value, thereby enabling parity encoding/decoding utilizing the phantom (anti-) diagonal disks. Row parity and symmetric parity values are included within the computation of the diagonal and anti-diagonal parities; accordingly, the two symmetric parity and the row parity values may be computed using the same technique as used for a triple parity erasure, i.e., in a symmetric fashion.

Claims

1. A method comprising:

providing an array with a predetermined number of storage devices p configured to store data and three parity values, wherein p is a prime number;

dividing each of the predetermined storage device into blocks;

organizing the blocks into stripes, the stripes having a same number of blocks in each of the predetermined storage device;

defining a diagonal parity along a plurality of diagonal parity sets;

defining an anti-diagonal parity along a plurality of anti-diagonal parity sets;

assigning a predetermined value to the diagonal parity and anti-diagonal parity; and

computing parity for the predetermined storage devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array.

2. The method of claim 1, wherein the predetermined number of storage devices include a plurality of devices configured to store data and symmetric parity.

3. The method of claim 1 wherein each stripe comprises p-1 rows of blocks.

4. The method of claim 1 wherein the diagonal parity sets wrap around within a group of p-1 rows allowing all blocks belonging to diagonal parity sets of a stripe to be stored in the stripe, and the anti-diagonal parity sets wrap around within a group of p-1 rows allowing all blocks belonging to the anti-diagonal parity sets of a stripe to be stored in the stripe.

5. The method of claim 1, computing parity comprising computing a total of p 4-tuple sums on one of the predetermined number of storage devices configured to store symmetric parity.

6. The method of claim 5, computing comprising generating the computed 4-tuple sums using a number of crosses.

7. The method of claim 1 wherein the predetermined number of storage devices comprise a plurality of storage devices, and at least one storage device a phantom storage device wherein the spaces where the at least one phantom storage device treated as containing zero-value data constant in the parity computation.

8. The method of claim 1, wherein locations of parity blocks are configured to shift from device to device within different stripes.

9. The method of claim 1, the stripes further configured to a power of two number of bits in size.

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

an array having a predetermined number of storage devices p configured to store data and three parity values, wherein p is a prime number;

a storage operating system including a device storage layer configured to implement a symmetric triple parity (TP) technique configured to,

detect that three storage devices have concurrently failed;

compute a diagonal parity along diagonal parity sets,

compute an anti-diagonal parity along anti-diagonal parity sets, the diagonal and anti-diagonal parity are assigned a predetermined value,

compute parity for the predetermined storage devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array; 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 triple parity technique.

11. The method of claim 10, wherein the predetermined number of storage devices include a plurality of devices configured to store data and symmetric parity.

12. The method of claim 10 wherein each stripe comprises p-1 rows of blocks.

13. The method of claim 10 wherein the diagonal parity sets wrap around within a group of p-1 rows allowing all blocks belonging to diagonal parity sets of a stripe to be stored in the stripe, and the anti-diagonal parity sets wrap around within a group of p-1 rows allowing all blocks belonging to the anti-diagonal parity sets of a stripe to be stored in the stripe.

14. The method of claim 10, computing parity comprising computing a total of p 4-tuple sums on one of the predetermined number of storage devices configured to store symmetric parity.

15. The system of claim 10, wherein the device storage layer is a RAID system and the storage devices are disks.

16. The system of claim 10, the RAID system further configured to divide each disk into blocks and organizes the blocks into stripes.

17. The system of claim 16, the RAID system further configured to implement in logic circuitry.

18. The system of claim 10 wherein the devices are one of a group consisting of:

video tape, magnetic tape, optical, DVD, bubble memory, magnetic disk, electronic random access memory and micro-electro mechanical storage devices.

19. The system of claim 10, wherein the predetermined number of storage devices further comprising a plurality of storage devices, at least one storage device a phantom storage device wherein the spaces where there is at least one phantom device contain a zero-value data constant in the parity computation.

20. A computer readable medium containing executable program instructions executed by a processor, comprising:

program instructions that divide each of a predetermined storage devices p, configured to store data and three parity values, into blocks, wherein p is a prime number;

program instructions that organize the blocks into stripes, the stripes having a same number of blocks in each of the predetermined storage device;

program instructions that define a diagonal parity along a plurality of diagonal parity sets;

program instructions that define an anti-diagonal parity along a plurality of anti-diagonal parity sets;

program instructions that assign a predetermined value to the diagonal parity and anti-diagonal parity; and

program instructions that compute parity for the predetermined storage is devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array.