System and method for symmetric triple parity

• US 20080016435A1
• Filed: 12/29/2006
• Published: 01/17/2008
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul
• Granted Patent: US 7,613,984 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

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 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 symmetric parity, wherein the pre-determined number of storage devices is p 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 p-1 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 p-1 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe;

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 p-1 rows so that all blocks belonging to the anti-diagonal parity sets of a stripe are stored in the stripe;

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

computing parity for the plurality of devices configured to store three parity values using values written to the plurality of devices configured to store data and the predetermined value assigned to the diagonal parity and anti-diagonal parity sets.

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 step of computing parity comprises 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 wherein the step of computing further comprises generating the computed 4-tuple sums using a number of crosses.

5. 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.

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

7. The method of claim 1 wherein the stripes are 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, wherein the predetermined number of storage devices is p and wherein p is a prime number;

a storage operating system including a device storage layer configured to implement a symmetric triple parity (TP) technique that (i) computes the diagonal parity along diagonal parity sets that span the first devices, (ii) computes the anti-diagonal parity along anti-diagonal parity sets that span the first devices, wherein the diagonal and anti-diagonal parity are assigned a predetermined value, (iii) computes a total of p 4-tuple sums along an intermediate storage device of the failed storage devices; and

(iv) generates the computed 4-tuple sums using a number of crosses; 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 wherein row parity blocks in a stripe are all stored on a single device.

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

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

12. The system of claim 11 wherein each stripe comprises p-1 rows of blocks, wherein each row contains one block from each disk.

13. The system of claim 10 wherein the RAID system is implemented in logic circuitry.

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

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

16. A computer readable medium containing executable program instructions for enabling recovery from three or fewer concurrent failures of 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 symmetric parity, wherein the pre-determined number of storage devices is p 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 p-1 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 p-1 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe;

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 p-1 rows so that all blocks belonging to the anti-diagonal parity sets of a stripe are stored in the stripe;

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

computing parity for the plurality of devices configured to store row parity and symmetric parity using values written to the plurality of devices configured to store data and the predetermined value assigned to the diagonal parity and anti-diagonal parity.

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

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, wherein 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.

18. The method of claim 17 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 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 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 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.

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

21. The method of claim 17 wherein the storage devices are disks.

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

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