Method for providing parity in a raid sub-system using non-volatile memory

• US 5,948,110 A
• Filed: 06/05/1995
• Issued: 09/07/1999
• Est. Priority Date: 06/04/1993
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Hitz, David, Rakitzis, Byron, Lau, James, Malcolm, Michael
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US08/471,218
• Time in Patent Office: 1,555 Days
• Field of Search: 395/182.04, 395/182.03, 395/182.05, 395/182.06, 395/182.09, 395/182.1, 371/2.2, 371/10.2, 371/10.3, 371/21.1, 371/40.11, 371/40.12, 371/40.13, 711/114, 711/118
• US Class Current: 714/6.22
• 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/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: G06F 2211/1061 Parity-single bit-RAID4, i.e. RAID 4 implementations
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

A method is disclosed for providing error correction for an array of disks using non-volatile random access memory (NV-RAM). Non-volatile RAM is used to increase the speed of RAID recovery from a disk error(s). This is accomplished by keeping a list of all disk blocks for which the parity is possibly inconsistent. Such a list of disk blocks is much smaller than the total number of parity blocks in the RAID subsystem. The total number of parity blocks in the RAID subsystem is typically in the range of hundreds of thousands of parity blocks. Knowledge of the number of parity blocks that are possibly inconsistent makes it possible to fix only those few blocks, identified in the list, in a significantly smaller amount of time than is possible in the prior art. The technique for safely writing to a RAID array with a broken disk is complicated. In this technique, data that can become corrupted is copied into NV-RAM before the potentially corrupting operation is performed.

Claims

1. A method for maintaining a consistent file system, wherein said file system is stored in stripes of blocks in a RAID array, that allows for recovery of the file system to a consistent state after a disk failure and a system failure occur prior to successful completion of writing new data to one or more blocks of a stripe of said RAID array, said disk failure rendering a block of said stripe in said RAID array unreadable, comprising the steps of:

prior to writing new data to one or more blocks of a stripe in said RAID array, reading said one or more blocks of said stripe to obtain prior data stored in said one or more blocks of said stripe, said prior data stored in said stripe storage means comprising a prior parity value read from a parity block of said stripe and prior data read from one or more data blocks of said stripe;

storing said prior data stored in said one or more blocks of said stripe in stripe storage means;

initiating the writing of said new data to said one or more blocks of said stripe; and

if said writing of said new data to said one or more blocks of said stripe in said RAID array is successfully completed, clearing said prior data from said one or more blocks of said stripe from said stripe storage means;

otherwise, performing the steps of;

after a failure has occurred, checking said stripe storage means to determine whether said stripe storage means contains any prior data for any stripe;

when said stripe storage means contains prior data for any stripe, performing the steps of;

determining whether said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array for which prior data has been stored in said stripe storage means;

if said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array for which prior data has been stored in said stripe storage means, performing the steps of;

reading data from each remaining readable data block of said stripe in said RAID array other than said data block rendered unreadable by said disk failure;

recomputing a parity value for said stripe based on said prior data stored in said stripe storage means for said data block rendered unreadable by said disk failure and on said data read from said each remaining readable data block of said stripe; and

writing said recomputed parity value for said stripe to said parity block of said stripe in said RAID array.

2. A method for maintaining a consistent file system, wherein said file system is stored in stripe of blocks in a RAID array, that allows for recovery of the file system to a consistent state after disk failure and system failure occur prior to completion of writing new data to one or more blocks of a stripe of said RAID array, said disk failure rendering a block of said stripe in said RAID array unreadable, comprising the steps of:

prior to writing new data to one or more blocks of a stripe in said RAID array, reading said one or more blocks of said stripe to obtain prior data stored in said one or more blocks of said stripe, said prior data stored in said stripe storage means comprising a prior parity value read from a parity block of said stripe and prior data read from one or more data blocks of said stripe;

storing said prior data stored in said one or more blocks of said stripe in stripe storage means;

initiating the writing of said new data to said one or more blocks of said stripe; and

if said writing of said new data to said one or more blocks of said stripe in said RAID array is successfully completed, clearing said prior data from said one or more blocks of said stripe from said stripe storage means;

otherwise, performing the steps of;

after a failure has occurred, checking said stripe storage means to determine whether said stripe storage means contains any prior data for any stripe;

when said stripe storage means contains prior data for any stripe, performing the steps of;

determining whether said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array other than said one or more data blocks for which prior data has been stored in said stripe storage means;

if said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array other than said one or more data blocks for which prior data has been stored in said stripe storage means, performing the steps of;

reading data from each remaining readable data block of said stripe in said RAID array other than said one or more data blocks of said stripe for which prior data has been stored in said stripe storage means;

computing data for said data block rendered unreadable by said disk failure based on said data read from said each remaining data block of said stripe in said RAID array other than said one or more data blocks of said RAID array for which prior data has been stored in said stripe storage means and on said prior data or said one or more data blocks of said stripe and said prior parity value for said parity block of said stripe stored in said stripe storage means;

reading data from said data blocks of said stripe in said RAID array for which prior data has been stored in said stripe storage means;

recomputing a new parity value based on said computed data for said data block rendered unreadable by said disk failure, said data read from said data blocks of said stripe in said RAID array for which prior data has been stored in said stripe storage means; and

said data read from said each remaining readable data block of said stripe in said RAID array other than said one or more data blocks for which prior data has been stored in said stripe storage means; and

writing said new parity value for said stripe to said parity block of said stripe in said RAID array.

3. A method for maintaining a consistent file system, wherein said file system is stored in stripes of blocks in a RAID array, that allows for recovery of the file system to a consistent state after disk failure and system failure occur prior to completion of writing new data to one or more blocks of a stripe of said RAID array, said disk failure rendering a block of said stripe in said RAID array unreadable, comprising the steps of:

prior to writing new data to one or more blocks of a stripe in said RAID array, reading said one or more blocks of said stripe to obtain prior data stored in said one or more blocks of said stripe, said prior data stored in said stripe storage means comprising a prior parity value read from a parity block of said stripe and prior data read from one or more data blocks of said stripe;

storing said prior data stored in said one or more blocks of said stripe in stripe storage means;

initiating the writing of said new data to said one or more blocks of said stripe; and

if said writing of said new data to said one or more blocks of said stripe in said RAID array is successfully completed, clearing said prior data from said one or more blocks of said stripe from said stripe storage means;

otherwise, performing the steps of;

after a failure has occurred, checking said stripe storage means to determine whether said stripe storage means contains any prior data for any stripe;

when said stripe storage means contains prior data for any stripe, performing the steps of;

determining whether said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array other than said one or more data blocks for which prior data has been stored in said stripe storage means;

if said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array other than said one or more data blocks for which prior data has been stored in said stripe storage means, writing said prior data for said one or more data blocks of said stripe and said prior parity value stored in said stripe storage means to said stripe in said RAID array.

4. A method for maintaining a consistent file system, wherein said file system is stored in stripes of blocks of a RAID array, that allows for recovery of the file system to a consistent state after a disk failure and a system failure occur prior to successful completion of writing new data to one or more blocks of a stripe of said RAID array, said disk failure rendering a block of said stripe in said RAID array unreadable, comprising the steps of:

prior to writing new data to one or more blocks of a stripe in said RAID array, reading any other blocks of said stripe in said RAID array other than said one or more blocks to which new data is to be written to obtain prior data stored in said other blocks of said stripe;

storing said prior data stored in said other blocks of said stripe in stripe storage means;

initiating the writing of said new data to said one or more blocks of said stripe in said RAID array; and

if said writing of said new data to said one or more blocks of said stripe is successfully completed, clearing said prior data from said other blocks of said stripe from said stripe storage means;

otherwise performing the steps of;

after a failure has occurred, checking said stripe storage means to determine whether said stripe storage means contains any prior data for any stripe;

when said stripe storage means contains prior data for any stripe, performing the steps of;

determining whether said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array for which prior data has been stored in said stripe storage means;

if said block of said stripe in said RAID array rendered unreadable by said disk failure is one of said data blocks of said stripe in said RAID array for which prior data has been stored in said stripe storage means, performing the steps of;

reading data from each remaining readable data block of said stripe in said RAID array other than said data block rendered unreadable by said disk failure;

recomputing a new parity value for said stripe based upon said data read from said each remaining readable data block of said stripe in said RAID array and said prior data stored in said stripe storage means for said data block rendered unreadable by said disk failure; and

writing said new parity value for said stripe to a parity block of said stripe in said RAID array.

5. A method for operating a file system that provides protection against corruption of the file system upon writing new data to the file system after a disk failure has rendered unreadable a data block in a stripe of RAID array wherein file system is stored, and that allows recovery of the file system to a consistent state when a system failure occurs prior to all of said new data being successfully written and comprising the steps of:

prior to writing new data to one or more blocks of said stripe, reading all readable blocks of said stripe in said RAID array;

computing data for said unreadable block based upon said readable blocks;

storing said computed data in stripe storage means;

initiating the writing of said new data to said one or more blocks of said stripe in said RAID array; and

if said writing of said new data to said one or more blocks of said stripe is successfully completed, clearing said computed data from said stripe storage means;

otherwise, performing the steps of;

after said system failure has occurred, checking said stripe storage means to determine whether said stripe storage means contains any computed data for any unreadable data block of any stripe;

when said stripe storage means containing computed data for an unreadable data block of a stripe, performing the steps of;

reading data from each readable data block of said stripe failure in said RAID array other than said data block rendered unreadable by said disk;

recomputing a parity value for said stripe based on said computed data for said unreadable data blocks of said strip stored in said stripe storage means and said data read from said remaining readable data blocks in said stripe in said RAID array; and

writing said recomputed parity value for said stripe to a parity block of said stripe in said RAID array.