Patent US6480969B1 successfully refreshed from Google Patents.
US6480969B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Providing parity in a RAID sub-system using non-volatile memory
Assignee: NetApp Inc
•
Filing: 1999-06-30
•
Granted: 2002-11-12
•
Expires: 2019-06-30
Abstract
Abstract The present invention is a method 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.
Inventors
- 👤 David Hitz
- 👤 Michael Malcolm
- 👤 James Lau
- 👤 Byron Rakitzis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 04:55
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/1059; G06F2211/1061
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
156 words
A method for providing parity correction for a RAID array in a computer system after a system failure, including steps of: maintaining information about stripes having possibly inconsistent parity during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having a stripe number and an existing parity, reading a second one or more blocks of said stripe required to compute a new parity of said stripe; computing said new parity for said stripe; adding said stripe number to a list of dirty stripes; writing said portion of said data to said stripe; writing said new parity to said stripe; removing said stripe number from said list of dirty stripes.
Claim 2
Independent Claim
156 words
A method for providing parity correction for a RAID array in a computer system after a system failure, including steps of: maintaining information about stripes having possibly inconsistent parity during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having a stripe number and an existing parity, reading a second one or more blocks of said stripe required to compute a new parity of said stripe; computing said new parity for said stripe; adding said stripe number to a list of dirty stripes; writing said portion of said data to said stripe; writing said new parity to said stripe; removing said stripe number from said list of dirty stripes.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein said second one or more blocks includes said existing parity block.
Claim 4
Dependent Claim
17 words
The method of claim 1 wherein said second one or more blocks excludes said existing parity block.
Claim 5
Independent Claim
199 words
A method for providing parity correction for a RAID array in a computer system after a system failure, including steps of: maintaining information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said information includes a bitmap and including the further step of, when said bitmap is sufficiently full and after all pending writes are successfully completed, clearing said bitmap; wherein each bit in said bitmap is associated with a group of one or more stripes; and wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having an associated group and an existing parity, reading a second one or more blocks of said stripe used to compute a new parity of said stripe; computing said new parity for said stripe; selecting a bit in said bitmap responsive to said group; setting said bit; writing said portion of said data to said stripe; writing said new parity to said stripe.
Claim 6
Independent Claim
199 words
A method for providing parity correction for a RAID array in a computer system after a system failure, including steps of: maintaining information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said information includes a bitmap and including the further step of, when said bitmap is sufficiently full and after all pending writes are successfully completed, clearing said bitmap; wherein each bit in said bitmap is associated with a group of one or more stripes; and wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having an associated group and an existing parity, reading a second one or more blocks of said stripe used to compute a new parity of said stripe; computing said new parity for said stripe; selecting a bit in said bitmap responsive to said group; setting said bit; writing said portion of said data to said stripe; writing said new parity to said stripe.
Claim 7
Independent Claim
224 words
An apparatus for providing parity correction for a RAID array in a computer system after a system failure, said apparatus including: a maintenance mechanism configured to maintain information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; an identification mechanism configured to identify stripes in response to said information, said identification apparatus activated in response to check on reboot after a system failure; a correction mechanism configured to correct said possibly inconsistent parity for each of said stripes identified by said identification mechanism; wherein said maintenance mechanism further includes: a read mechanism configured to read a second one or more blocks of said stripe required to compute a new parity of said stripe, said mechanism activated when new data is to be written to a first one or more blocks of a stripe having a stripe number and an existing parity; a compute mechanism configured to compute said new parity for said stripe responsive to said reading; an add mechanism configured to add said stripe number to a list of dirty stripes responsive to said compute mechanism; a write mechanism configured to write said data to said stripe; a second write mechanism configured to write said new parity to said stripe; a remove mechanism configured to remove said stripe number from said list of dirty stripes.
Claim 8
Independent Claim
224 words
An apparatus for providing parity correction for a RAID array in a computer system after a system failure, said apparatus including: a maintenance mechanism configured to maintain information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; an identification mechanism configured to identify stripes in response to said information, said identification apparatus activated in response to check on reboot after a system failure; a correction mechanism configured to correct said possibly inconsistent parity for each of said stripes identified by said identification mechanism; wherein said maintenance mechanism further includes: a read mechanism configured to read a second one or more blocks of said stripe required to compute a new parity of said stripe, said mechanism activated when new data is to be written to a first one or more blocks of a stripe having a stripe number and an existing parity; a compute mechanism configured to compute said new parity for said stripe responsive to said reading; an add mechanism configured to add said stripe number to a list of dirty stripes responsive to said compute mechanism; a write mechanism configured to write said data to said stripe; a second write mechanism configured to write said new parity to said stripe; a remove mechanism configured to remove said stripe number from said list of dirty stripes.
Claim 9
Dependent Claim
17 words
The apparatus of claim 5 wherein said second one or more blocks includes said existing parity block.
Claim 10
Dependent Claim
17 words
The apparatus of claim 5 wherein said second one or more blocks excludes said existing parity block.
Claim 11
Independent Claim
242 words
An apparatus for providing parity correction for a RAID array in a computer system after a system failure, said apparatus including: a maintenance mechanism configured to maintain information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; an identification mechanism configured to identify stripes in response to said information, said identification apparatus activated in response to check on reboot after a system failure; a correction mechanism configured to correct said possibly inconsistent parity for each of said stripes identified by said identification mechanism; wherein said information includes a bitmap and further including a clear mechanism configured to clear said bitmap when said bitmap is sufficiently full and after all pending writes are successfully completed; and wherein said maintenance mechanism includes: a read mechanism configured to read a first one or more blocks of said stripe used to compute a new parity of a stripe, a second one or more blocks of said stripe to be updated with new data, said stripe having an associated group and an associated parity block; a compute mechanism configured to compute said new parity for said stripe, responsive to said read mechanism; a selector configured to select a bit in said bitmap responsive to said group; a set mechanism configured to set said bit; a first write mechanism configured to write new data to said stripe; a second write mechanism configured to write said new parity to said stripe.
Claim 12
Independent Claim
242 words
An apparatus for providing parity correction for a RAID array in a computer system after a system failure, said apparatus including: a maintenance mechanism configured to maintain information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; an identification mechanism configured to identify stripes in response to said information, said identification apparatus activated in response to check on reboot after a system failure; a correction mechanism configured to correct said possibly inconsistent parity for each of said stripes identified by said identification mechanism; wherein said information includes a bitmap and further including a clear mechanism configured to clear said bitmap when said bitmap is sufficiently full and after all pending writes are successfully completed; and wherein said maintenance mechanism includes: a read mechanism configured to read a first one or more blocks of said stripe used to compute a new parity of a stripe, a second one or more blocks of said stripe to be updated with new data, said stripe having an associated group and an associated parity block; a compute mechanism configured to compute said new parity for said stripe, responsive to said read mechanism; a selector configured to select a bit in said bitmap responsive to said group; a set mechanism configured to set said bit; a first write mechanism configured to write new data to said stripe; a second write mechanism configured to write said new parity to said stripe.
Claim 13
Dependent Claim
168 words
A memory storing information including instructions, the instructions executable by a processor to provide parity correction for a RAID array in a computer system after a system failure, the instructions including steps of: maintaining information about stripes having possibly inconsistent parity during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having a stripe number and an existing parity, reading a second one or more blocks of said stripe required to compute a new parity of said stripe; computing said new parity for said stripe; adding said stripe number to a list of dirty stripes; writing said portion of said data to said stripe; writing said new parity to said stripe; removing said stripe number from said list of dirty stripes.
Claim 14
Dependent Claim
168 words
A memory storing information including instructions, the instructions executable by a processor to provide parity correction for a RAID array in a computer system after a system failure, the instructions including steps of: maintaining information about stripes having possibly inconsistent parity during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having a stripe number and an existing parity, reading a second one or more blocks of said stripe required to compute a new parity of said stripe; computing said new parity for said stripe; adding said stripe number to a list of dirty stripes; writing said portion of said data to said stripe; writing said new parity to said stripe; removing said stripe number from said list of dirty stripes.
Claim 15
Dependent Claim
17 words
The memory of claim 9 wherein said second one or more blocks includes said existing parity block.
Claim 16
Dependent Claim
17 words
The memory of claim 9 wherein said second one or more blocks excludes said existing parity block.
Claim 17
Dependent Claim
211 words
A memory storing information including instructions, the instructions executable by a processor to provide parity correction for a RAID array in a computer system after a system failure, the instructions including steps of: maintaining information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said information includes a bitmap and including the further step of, when said bitmap is sufficiently full and after all pending writes are successfully completed, clean said bitmap; wherein each bit in said bitmap is associated with a group of one or more stripes; and wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having an associated group and an existing parity, reading a second one or more blocks of said stripe used to compute a new parity of said stripe; computing said new parity for said stripe; selecting a bit in said bitmap responsive to said group; setting said bit; writing said portion of said data to said stripe; writing said new parity to said stripe.
Claim 18
Dependent Claim
211 words
A memory storing information including instructions, the instructions executable by a processor to provide parity correction for a RAID array in a computer system after a system failure, the instructions including steps of: maintaining information about stripes having possibly inconsistent parity caused by updating data during routine operation of the computer system; after said system failure, identifying stripes in response to said information; and for each said stripe so identified, correcting said possibly inconsistent parity; wherein said information includes a bitmap and including the further step of, when said bitmap is sufficiently full and after all pending writes are successfully completed, clean said bitmap; wherein each bit in said bitmap is associated with a group of one or more stripes; and wherein said step of maintaining includes steps of: when updating data, a portion of said data destined for a first one or more blocks of a stripe having an associated group and an existing parity, reading a second one or more blocks of said stripe used to compute a new parity of said stripe; computing said new parity for said stripe; selecting a bit in said bitmap responsive to said group; setting said bit; writing said portion of said data to said stripe; writing said new parity to said stripe.
References Cited (Backward Citations)
DE6942565U
Cited
US5008786A
Cited
US4825354A
Cited
JPH01273395A
Cited
US4984272A
Cited
US5202983A
Cited
US5222217A
Cited
US5113442A
Cited
US5144659A
Cited
US5283830A
Cited
WO1994029807A1
Cited
EP0702815A1
Cited
US6289356B1
Cited
US5819292A
Cited
DE69425658D1
Cited
US5572711A
Cited
US5617568A
Cited
US5689701A
Cited
US5963962A
Cited
US5675782A
Cited
US5761669A
Cited
US5668958A
Cited
US5737523A
Cited
US5825877A
Cited
US5915087A
Cited
US5931935A
Cited
US5876278A
Cited
US6101585A
Cited
US5890959A
Cited
WO2000007104A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-11-11 | 2006-05-13 | 2006-11-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-11-11 | 2010-05-13 | 2010-11-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-11-11 | 2014-05-13 | 2014-11-12 | $7700.00 | Window Closed / Lapsed |