Lost writes detection in a redundancy group based on RAID with multiple parity

• US 7,552,357 B2
• Filed: 04/29/2005
• Issued: 06/23/2009
• Est. Priority Date: 04/29/2005
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Sankar, Sunitha S., Grcanac, Tomislav
• Primary Examiner(s): Beausolel; Robert
• Assistant Examiner(s): Ehne; Charles
• Application Number:
  US11/117,852
• Publication Number:
  US 20060248378A1
• Time in Patent Office: 1,516 Days
• Field of Search: None
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A storage server stores data in a redundancy group of mass storage devices according to a data redundancy scheme. The redundancy scheme enables reconstruction of all data stored in the redundancy group if N or fewer mass storage devices in the redundancy group contain erroneous data, where N is at least 2. In response to determining that the redundancy group contains erroneous data, N−1 mass storage devices in the redundancy group can be specifically identified as containing the erroneous data.

Claims

1. A method comprising:

storing data in a redundancy group of mass storage devices according to a data redundancy scheme, wherein the data redundancy scheme enables reconstruction of all data stored in X or fewer mass storage devices in the redundancy group which contain erroneous data, where X is at least 2; and

in response to determining that the redundancy group contains erroneous data, specifically identifying X−

1 mass storage devices in the redundancy group which contain the erroneous data by

reconstructing data on a selected subset of the redundancy group, the selected subset including at least two but fewer than all of the mass storage devices in the redundancy group,

comparing the reconstructed data to the stored data in the mass storage devices of the selected subset,

if the reconstructed data does not match the stored data for only one of the mass storage devices in the subset, then determining that said one mass storage device contains the erroneous data, and

if the reconstructed data does not match the stored data for all of the mass storage devices in the subset, then repeating said reconstructing and said comparing with a different selected subset of the redundancy group.

2. A method as recited in claim 1, wherein the redundancy group includes a plurality of data mass storage devices to store data, a first parity mass storage device to store parity information of a first type according to the data redundancy scheme, and a second parity mass storage device to store parity information of a second type according to the data redundancy scheme.

3. A method of specifically identifying at least one mass storage device in a redundancy group of mass storage devices as containing erroneous data, the method comprising:

reconstructing data on a selected subset of the redundancy group, the selected subset including at least two, but fewer than all, of the mass storage devices in the redundancy group;

comparing the reconstructed data to corresponding stored data in the mass storage devices of the selected subset; and

if the reconstructed data does not match the corresponding stored data for only one of the mass storage devices of the subset, then identifying each mass storage device of said at least one but fewer than all of the mass storage devices of the subset as containing the erroneous data; and

if the reconstructed data does not match the stored data for all of the mass storage devices in the subset, then repeating said reconstructing and said comparing with a different selected subset of the redundancy group.

4. A method as recited in claim 3, wherein said reconstructing data comprises using parity information to reconstruct the data on each mass storage device of the subset.

5. A method as recited in claim 3, wherein the redundancy group includes a plurality of data storage devices to store data, a row parity storage device to store row parity information, and a diagonal parity storage device to store diagonal parity information;

and wherein the redundancy scheme includes;

computing the diagonal parity information along diagonal parity sets, each of the diagonal parity sets including at least two of the data storage devices and the row parity storage device; and

storing, on the diagonal parity storage device, the diagonal parity information for all but one of the diagonal parity sets.

6. A method comprising:

storing data in a parity group that includes a plurality of disks by using a redundancy scheme that includes row parity and diagonal parity, the parity group including a plurality of data disks to store data, a row parity disk to store row parity information, and a diagonal parity disk to store diagonal parity information, each of the plurality of disks including a plurality of data blocks, wherein the row parity information corresponds to parity rows that include data from each of the plurality of data disks;

using an error detection process to detect, based on the redundancy scheme, that at least one disk in the parity group contains erroneous data;

in response to detecting that at least one disk in the parity group contains erroneous data, executing an error location process that includes

selecting a subset of the parity group, the subset containing at least two but less than all of the plurality of disks, and

performing a subprocess that includes

reconstructing data on each disk of the subset,

determining whether the reconstructed data for each disk in the subset match the stored data on each disk of the subset,

if the reconstructed data does not match the stored data for only one of the disks in the subset, then determining that said one disk contains the erroneous data, and

if the reconstructed data does not match the stored data for all the disks in the subset, then repeating said subprocess with a different selected subset of the parity group.

7. A method as recited in claim 6, wherein said determining that said one disk contains the erroneous data comprises specifically identifying the erroneous data block on said one disk.

8. A method as recited in claim 6, wherein said redundancy scheme comprises:

computing the diagonal parity information along diagonal parity sets, each of the diagonal parity sets including at least two of the data disks and the row parity disk; and

storing, on the diagonal parity disk, the diagonal parity information for all but one of the diagonal parity sets.

9. A method as recited in claim 6, wherein said redundancy scheme comprises:

computing the diagonal parity information along diagonal parity sets, each of the diagonal parity sets including at least two of the data disks and the row parity disk; and

storing, on the diagonal parity disk, the diagonal parity information for all but one of the diagonal parity sets;

and wherein the error location process further comprises;

if the reconstructed data mismatches the stored data for all disks of the subset, then repeating said subprocess with a different selected subset of the parity group.

10. A processing system comprising:

a client interface through which to receive a data access request from a client;

a storage interface through which to access a redundancy group of mass storage devices in response to the data access request;

a file system to issue a write, the write for causing data to be written to the redundancy group; and

a storage layer to apply a data redundancy scheme to data stored in the redundancy group, and to specifically identify a mass storage device in the redundancy group which contains the erroneous data, by;

reconstructing data on a selected subset of the redundancy group, the selected subset including at least two but fewer than all of the mass storage devices in the redundancy group,

comparing the reconstructed data to the stored data in the mass storage devices of the selected subset,

if the reconstructed data does not match the stored data for only one of the mass storage device in the subset, then determining that said one mass storage device contains the erroneous data, and

if the reconstructed data mismatches the stored data for all of the mass storage devices in the subset, then repeating said reconstructing and said comparing with a different selected subset of the redundancy group.

11. A processing system as recited in claim 10, wherein the storage layer is a RAID layer to apply a RAID scheme to the redundancy group.

12. A processing system as recited in claim 11, wherein the redundancy group includes a plurality of data storage devices to store data, a row parity storage device to store row parity information, and a diagonal parity storage device to store diagonal parity information;

and wherein the RAID scheme includes;

computing the diagonal parity information along diagonal parity sets, each of the diagonal parity sets including at least two of the data storage devices and the row parity storage device; and

storing, on the diagonal parity storage device, the diagonal parity information for all but one of the diagonal parity sets.

13. A storage server comprising:

a processor unit;

a client interface, coupled to the processor unit, through which to communicate with a client;

a storage interface, coupled to the processor unit, through which to access a parity group of storage devices in response to a data access request from the client, the parity group including a plurality of data disks to store data, a row parity disk to store row parity information, and a diagonal parity disk to store diagonal parity information, wherein the row parity information corresponds to parity rows that include data from each of the plurality of data disks; and

a memory storing software which, when executed by the processor unit, causes the storage server to execute a process that includes;

storing data in the parity group by applying a redundancy scheme that generates the row parity information and the diagonal parity information;

using an error detection process to detect, based on the redundancy scheme, that at least one disk in the parity group contains erroneous data; and

executing an error location process in response to detecting that at least one disk in the parity group contains erroneous data, the error location process including

reconstructing data on a selected subset of the parity group, the subset including at least two but fewer than all of the disks in the parity group,

comparing the reconstructed data to the stored data in the disks of the subset,

if the reconstructed data does not match the stored data for only one of the disks in the subset, then determining that said one disk contains the erroneous data, and

if the reconstructed data does not match the stored data for all of the disks in the subset, then repeating said reconstructing and said comparing with a different selected subset of the parity group.

14. A storage server as recited in claim 13, wherein said redundancy scheme comprises:

computing the diagonal parity information along diagonal parity sets, each of the diagonal parity sets including at least two of the data disks and the row parity disk; and

storing, on the diagonal parity disk, the diagonal parity information for all but one of the diagonal parity sets.