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

• US 8,010,874 B2
• Filed: 11/06/2009
• Issued: 08/30/2011
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul, Corbett, Peter F.
• Primary Examiner(s): Abraham; Esaw T
• Application Number:
  US12/613,743
• Publication Number:
  US 20100050015A1
• Time in Patent Office: 662 Days
• Field of Search: 714/756, 714/763, 714/764, 714/770, 714/775, 714/776, 714/800
• 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
• CPC Class Codes: G06F 2211/1061 Parity-single bit-RAID4, i.e. RAID 4 implementations

Abstract

A method for recovering from three failed data storage devices is disclosed. A plurality of data storage devices hold data, and a row parity storage device holds row parity for them. The data storage devices and the row parity storage device form a set of storage devices. A diagonal parity storage device and an anti-diagonal parity storage device hold parity computed diagonally over the set of storage devices. In the event of a failure of three data storage devices of the set of storage devices, a first failed storage device is chosen for first restoration. A missing block of the first failed storage device is computed by using the remaining set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device. The remaining two failed storage devices are restored by a diagonal parity restoration technique.

Claims

1. A method for recovering from three failed data storage devices, comprising:

establishing a plurality of storage devices to hold data, referred to as the data storage devices;

establishing a storage device to hold row parity for the data devices, referred to as the row parity storage device, and referring to the data storage devices and the row parity storage device together as a set of storage devices;

establishing a diagonal parity storage device to hold diagonal parity computed over the set of storage devices;

establishing an anti-diagonal parity storage device to hold anti-diagonal parity computed over the set of storage devices;

in the event of a failure of three data storage devices of the set of storage devices, choosing a first failed storage device to restore;

computing a missing block of the first failed storage device using remaining storage devices of the set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device; and

using diagonal parity restoration techniques to restore the remaining two failed storage devices.

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

solving for a value of the missing block using equations generated from the remaining storage devices of the set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device.

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

treating one row of each storage device of the set of storage devices as holding a data block of zero value to assist in recovering the missing block of the first failed storage device.

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

using a magnetic disk as the storage device.

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

using an electronic random memory as the storage device.

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

using an optical memory as the storage device.

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

using a DVD as the storage device.

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

using a magnetic tape as the storage device.

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

using a micro-electro mechanical memory as the storage device.

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

using a bubble memory as the storage device.

11. A computer data storage system apparatus, comprising:

a plurality of storage devices to hold data, referred to as the data storage devices;

a storage device to hold row parity for the data storage devices, referred to as the row parity storage device, and referring to the data storage devices and the row parity storage device together as a set of storage devices;

a diagonal parity storage device to hold diagonal parity computed over the set of storage devices;

an anti-diagonal parity storage device to hold anti-diagonal parity computed over the set of storage devices;

in the event of a failure of three data storage devices of the set of storage devices, a processor to choose a first failed storage device to restore;

a process executing on the processor to compute a missing block of the first failed storage device by solving for a value of the block using equations generated from the remaining storage devices of the set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device; and

the processor to use diagonal parity restoration techniques to restore the remaining two failed storage devices, to recover from three failed data storage devices.

12. The apparatus as in claim 11, further comprising:

the processor executing a process to solve for the value of the missing block using equations generated from the remaining storage devices of the set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device.

13. The apparatus as in claim 11, further comprising:

the processor to treat one row of each storage device of the set of storage devices as holding a data block of zero value to assist in recovering the missing block of the first failed storage device.

14. The apparatus as in claim 11, further comprising:

a magnetic disk used as the storage device.

15. The apparatus as in claim 11, further comprising:

an electronic random memory used as the storage device.

16. The apparatus as in claim 11, further comprising:

an optical memory used as the storage device.

17. The apparatus as in claim 11, further comprising:

a DVD used as the storage device.

18. The apparatus as in claim 11, further comprising:

a magnetic tape used as the storage device.

19. The apparatus as in claim 11, further comprising:

a micro-electro mechanical memory used as the storage device.

20. The apparatus as in claim 11, further comprising:

a bubble memory used as the storage device.

21. A non-transitory computer readable storage media, comprising:

said computer readable storage media containing program instructions for execution on a processor for a method of recovering from three failed data storage devices, the program instructions for,

establishing a plurality of storage devices to hold data, referred to as the data storage devices;

establishing a storage device to hold row parity for the data devices, referred to as the row parity storage device, and referring to the data storage devices and the row parity storage device together as a set of storage devices;

establishing a diagonal parity storage device to hold diagonal parity computed over the set of storage devices;

establishing an anti-diagonal parity storage device to hold anti-diagonal parity computed over the set of storage devices;

in the event of a failure of three data storage devices of the set of storage devices, choosing a first failed storage device to restore;

computing a missing block of the first failed storage device by solving for a value of the block using equations generated from the remaining storage devices of the set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device; and

using diagonal parity restoration techniques to restore the remaining two failed storage devices.

22. A method for recovering from three failed data storage devices in a computer data storage system having a plurality of storage devices to hold data, referred to as the data storage devices, and having a storage device to hold row parity for the data storage devices, referred to as the row parity storage device, and referring to the data storage devices and the row parity storage device together as a set of storage devices, comprising:

establishing a diagonal parity storage device to hold diagonal parity computed over the set of storage devices;

establishing an anti-diagonal parity storage device to hold anti-diagonal parity computed over the set of storage devices;

configuring the data storage system to respond to a failure of three storage devices of the set of storage devices by choosing a first failed storage device to restore;

configuring the data storage system to compute a missing block of the first failed storage device by using the remaining storage devices of the set of storage devices, and the diagonal parity storage device, and the anti-diagonal parity storage device; and

configuring the data storage system to use diagonal parity restoration techniques to restore the remaining two failed storage devices.