Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array

• US 7,409,625 B2
• Filed: 02/23/2007
• Issued: 08/05/2008
• Est. Priority Date: 12/28/2001
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Primary Examiner(s): KERVEROS, DEMETRIOS C
• Application Number:
  US11/710,304
• Publication Number:
  US 20070180348A1
• Time in Patent Office: 529 Days
• Field of Search: 714/763, 714/764, 714/770, 714/755, 714/756, 714/800, 714/804, 714/805, 714/6, 714/801, 714/802, 714/803, 714/758, 714/114
• 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 method for enabling recovery from concurrent failure of a plurality of storage devices in a storage array is disclosed. The method stores data on a first plurality of storage devices of the storage array. The first plurality of storage devices may have a number of storage devices equal to a prime number greater then three. Row parity is stored on one or more storage devices of the storage array. A diagonal parity set is computed for the plurality of storage devices. The diagonal parity set is stored on an additional diagonal parity device, the diagonal parity device separate from the first plurality of storage devices.

Claims

1. A method for enabling recovery from concurrent failure of a plurality of storage devices in a storage array, comprising:

storing data on a first plurality of storage devices of the storage array;

storing row parity on one or more storage devices of the storage array;

computing a diagonal parity set across the plurality of storage devices; and

storing the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the first plurality of storage devices.

2. The method as in claim 1, further comprising:

configuring the first plurality of storage devices as a number of storage devices equal to a prime number greater then three.

3. The method as in claim 1, further comprising:

configuring the data on the storage devices in rows of blocks.

4. The method as in claim 1, further comprising:

storing the row parity blocks on a single storage device.

5. The method as in claim 1, further comprising:

configuring the plurality of storage devices with one or more absent storage devices, and treating the one or more absent storage devices as containing zero data.

6. The method as in claim 1, further comprising:

computing row parity blocks by an encoding of data blocks that is tolerant of single storage device failure.

7. The method as in claim 1, further comprising:

configuring each row to have a plurality of parity blocks.

8. The method as in claim 1, further comprising:

placing parity blocks in different locations in different stripes from device to device.

9. A storage array having recovery from concurrent failure of a plurality of storage devices, comprising:

a first plurality of storage devices to store data;

row parity stored on one or more storage devices of the storage array;

a diagonal parity set computed across the plurality of storage devices; and

an additional diagonal parity device to store the diagonal parity set, the diagonal parity device separate from the first plurality of storage devices.

10. The storage away as in claim 9, further comprising:

the first plurality of storage devices having a number of storage devices equal to a prime number greater then three.

11. The storage away as in claim 9, further comprising:

the data on the plurality of storage devices configured in rows of blocks.

12. The storage away as in claim 9, further comprising:

a single storage device to store the row parity blocks.

13. The storage away as in claim 9, further comprising:

one or more absent storage devices of the plurality of storage devices, wherein the one or more absent storage devices contain zero data.

14. The storage array as in claim 9, further comprising:

the row parity blocks computed by an encoding of data blocks that is tolerant of single storage device failure.

15. The storage away as in claim 9, further comprising:

each of the rows configured to have a plurality of parity blocks.

16. The storage away as in claim 9, further comprising:

the storage devices having parity blocks placed in different locations in different stripes from device to device.

17. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method of enabling recovery from concurrent failure of a plurality of storage devices in a storage array, the method having the steps of,

storing data on a first plurality of storage devices of the storage array, where the first plurality of storage devices has a number of storage devices equal to a prime number greater than three;

storing row parity on one or more storage devices of the storage array;

computing a diagonal parity set across the plurality of storage devices; and

storing the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the first plurality of storage devices.

18. A storage array having recovery from concurrent failure of a plurality of storage devices, comprising:

means for storing data on a first plurality of storage devices of the storage array;

means for storing row parity on one or more storage devices of the storage array;

means for computing a diagonal parity set across the plurality of storage devices; and

means for storing the diagonal parity set on an additional diagonal parity device, the diagonal parity device separate from the first plurality of storage devices.

19. The storage array as in claim 18, further comprising:

means for configuring the first plurality of storage devices as a number of storage devices equal to a prime number greater than three.

20. A method, comprising:

storing data on a first plurality of storage devices of a storage array, wherein each storage device of the storage array stores data or parity on a persistent storage device;

storing row parity on one or more storage devices of the storage array;

computing a diagonal parity set across the first plurality of storage devices; and

storing the diagonal parity set on an additional diagonal parity storage device, where the diagonal parity storage device is separate from the first plurality of storage devices, wherein the diagonal parity and row parity allows recovery from failure of one or two storage devices of the storage array.