System and method for symmetric triple parity for failing storage devices

• US 7,613,984 B2
• Filed: 12/29/2006
• Issued: 11/03/2009
• 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:
  US11/648,709
• Publication Number:
  US 20080016435A1
• Time in Patent Office: 1,040 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, including a plurality of first devices configured to store data and symmetric parity, the predetermined number of storage devices are p and 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, each stripe comprising p-1 rows of blocks;

defining a diagonal parity along diagonal parity sets that span the first devices, 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;

defining an anti-diagonal parity along anti-diagonal parity sets that span the first devices, 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;

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

computing parity for a plurality of devices configured to store three parity values using values written to a plurality of devices configured to store data and the predetermined value assigned to the diagonal parity 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, row parity blocks in a stripe configured to be all stored on a single device.

3. The method of claim 1, computing parity further comprising computing a total of p 4-tuple sums on one of the first devices configured to store symmetric parity.

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

5. The method of claim 1 wherein the first devices further 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.

6. The method of claim 1, locations of parity blocks further configured to shift from device to device within different stripes.

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

8. 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, including a plurality of first devices configured to store data, and symmetric parity, the predetermined number of storage devices is p and 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;

computes a diagonal parity along diagonal parity sets that span the first devices,

computes an anti-diagonal parity along anti-diagonal parity sets that span the first devices, the diagonal and anti-diagonal parity are assigned a predetermined value,

computes a total of p 4-tuple sums along an intermediate storage device of the failed storage devices; and

generates the computed 4-tuple sums using a number of crosses, the computed sums 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 TP parity technique.

9. The system of claim 8, row parity blocks in a stripe are configured to be all stored on a single device.

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

11. The system of claim 10, the RAID system further configured to:

implement in logic circuitry.

12. The system of claim 8, the RAID system further configured to:

divide each disk into blocks and organizes the blocks into stripes.

13. The system of claim 11, each stripe further comprising p-1 rows of blocks, each row having one block from each disk.

14. The system of claim 8, 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.

15. The system of claim 8, wherein the first devices further comprising a plurality of storage devices, at least one storage device a phantom storage device wherein the spaces where the at least one phantom device containing a zero-value data constant in the parity computation.

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

program instructions that provide an array with a predetermined number of storage devices including a plurality of first devices configured to store data, and symmetric parity, the predetermined number of storage devices is p and p is a prime number;

program instructions that divide each device into blocks;

program instructions that organize the blocks into stripes that contain a same number of blocks in each device, each stripe having p-1 rows of blocks;

program instructions that define a diagonal parity along diagonal parity sets that span the first devices, the diagonal parity sets wrapping 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;

program instructions that define an anti-diagonal parity along anti-diagonal parity sets that span the first devices, the anti-diagonal parity set wrapping 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;

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

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

17. A method comprising:

detecting that three storage devices have concurrently failed

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 a diagonal parity value and an anti-diagonal parity value are set to a predetermined value; and

computing a set of 4-tuple sums on a middle failed storage device, the computed parity-sum enabling recovery from three concurrent failures of storage devices in a storage array.

18. The method of claim 17, computing a set of 4-tuple sums on a middle storage device further comprising:

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 sums of blocks on missing storage devices corresponding to the diagonal on the selected row for the third storage device;

(d) retrieving anti-diagonal parity parity sums of blocks on missing storage devices corresponding to the anti-diagonal on the selected row for the first 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.

19. The method of claim 17, further comprising:

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

recovering the middle storage device.

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

21. The method of claim 17, the storage devices further configured to be disks.

22. The method of claim 17 the algebraic operation further comprising an exclusive or (XOR) sum.

23. The method of claim 17, further comprising solving a set of linear equations represented by the 4-tuple sums of blocks on the middle disk to recover the middle disk.

24. A method for recovering from three concurrent disk failures in a computer data storage system, comprising:

computing row parity for a set of data disks;

computing a first diagonal parity for the set of data disks and disks on which the row parity was stored;

computing a second diagonal parity for the set of data disks and disks on which the row parity was stored;

detecting a failure on each of three different disks of the set of disks, referred to hereinafter as the three failed disks;

choosing an intermediate disk of the three failed disks;

performing sums using the row parity and the first diagonal parity and the second diagonal parity to generate an equation having one unknown, the computed sums enabling recovery from three concurrent failures of storage devices in a storage array; and

solving the equation to reconstruct a data block on a disk of the three failed disks.

25. The method of claim 24, computing parity further comprising computing a total of p 4-tuple sums on the set of data disks.

26. The method of claim 25, computing further comprising generating the computed 4-tuple sums using a number of crosses.

27. The method of claim 24, the first devices further comprising a plurality of storage devices, and at least one storage device is not present and the spaces where the at least one not present storage device treated as containing zero-valued data constants in the parity computation.

28. The method of claim 24, locations of parity blocks further configured to shift from device to device within different stripes.

29. A computer readable medium containing executable program instructions for recovering from three concurrent disk failures in a computer data storage system, the executable program instructions comprising program instructions for:

computing row parity for a set of data disks;

computing a first diagonal parity for the set of data disks and disks on which the row parity was stored;

computing a second diagonal parity for the set of data disks and disks on which the row parity was stored;

detecting a failure on each of three different disks of the set of disks, referred to hereinafter as the three failed disks;

choosing an intermediate disk of the three failed disks;

performing sums using the row parity and the first diagonal parity and the second diagonal parity to generate an equation having one unknown, the computed sums enabling recovery from three concurrent failures of storage devices in a storage array; and

solving the equation to reconstruct a data block on a disk of the three failed disks.

30. A system configured to enable recovery from three concurrent disk failures in a computer data storage system, the system comprising:

an array having a predetermined number of storage devices, including a plurality of first devices configured to store data, and symmetric parity, the predetermined number of storage devices is p and p is a prime number;

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

compute row parity for a set of data disks;

compute a first diagonal parity for the set of data disks and disks on which the row parity was stored;

compute a second diagonal parity for the set of data disks and disks on which the row parity was stored;

detect a failure on each of three different disks of the set of disks, referred to hereinafter as the three failed disks;

choose an intermediate disk of the three failed disks;

perform sums using the row parity and the first diagonal parity and the second diagonal parity to generate an equation having one unknown, the computed sums enabling recovery from three concurrent failures of storage devices in a storage array; and

solve the equation to reconstruct a data block on a disk of the three failed disks.