US5720025A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Frequently-redundant array of independent disks
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1996-01-18
•
Granted: 1998-02-17
•
Expires: 2016-01-18
Abstract
Abstract There is provided a method and apparatus for effectuating data updates on a fault-tolerant storage device having a plurality of disk-drive units forming a disk array, with parity-block updates temporarily suspended to provide increased performance. Parity-block updates are typically deferred until the array is idle. Thus, data is written onto the array with no parity error correction information being present for a short amount of time. Data updates are effectuated by identifying the blocks in the array where data is to be written. New data is then written directly to the identified blocks without reading the old data present therein. A "needs parity rebuild bit" (NPRB) is written to non-volatile memory, identifying the stripes not having parity information on the array. The number of NPRBs present is monitored to allow continuous calculation of a mean-time-to-data-loss (MTTDL). If the MTTDL is acceptable, parity updates are deferred until the array is idle. To that end, the I/O patterns to and from the array are monitored to determine idleness. If the I/O patterns indicate that the disk array is idle, new data is read and parity information is generated which is then written to the array.
Inventors
- 👤 Andrew John Wilkes
- 👤 Stefan Savage
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 00:59
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/1009; G06F2211/1059
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
208 words
A method for storing data in a fault-tolerant storage device having a plurality of disk units forming a disk array with a plurality of stripes for storing data and parity information, comprising the steps of: identifying at least one target area on said array to write new data, with said at least one target area including old data and being associated with one of said plurality of stripes, defining an updated stripe; in the absence of a reading step, writing new data to said at least one target area, said new data not having corresponding parity information defining unprotected data; monitoring a quantity of said unprotected data present on said array to detect presence of a preselected condition related to susceptibility of said at least one target area to loss of said unprotected data; and in response to said step of monitoring said quantity of said unprotected data and prior to completion of writing all of said new data at said at least one target area, dynamically adjusting said quantity of unprotected data present on said array by generating and writing parity information corresponding to a first portion of said new data to said disk array, while leaving a second portion of said new data as unprotected data.
Claim 2
Independent Claim
208 words
A method for storing data in a fault-tolerant storage device having a plurality of disk units forming a disk array with a plurality of stripes for storing data and parity information, comprising the steps of: identifying at least one target area on said array to write new data, with said at least one target area including old data and being associated with one of said plurality of stripes, defining an updated stripe; in the absence of a reading step, writing new data to said at least one target area, said new data not having corresponding parity information defining unprotected data; monitoring a quantity of said unprotected data present on said array to detect presence of a preselected condition related to susceptibility of said at least one target area to loss of said unprotected data; and in response to said step of monitoring said quantity of said unprotected data and prior to completion of writing all of said new data at said at least one target area, dynamically adjusting said quantity of unprotected data present on said array by generating and writing parity information corresponding to a first portion of said new data to said disk array, while leaving a second portion of said new data as unprotected data.
Claim 3
Dependent Claim
27 words
The method as recited in claim 1 wherein said adjusting step adjusts said quantity of unprotected data to ensure said quantity does not exceed a predetermined threshold.
Claim 4
Dependent Claim
16 words
The method as recited in claim 1 wherein said monitoring step includes continuously determining a mean-time-to-data-loss.
Claim 5
Dependent Claim
35 words
The method as recited in claim 1 wherein said monitoring step includes monitoring said quantity over a predetermined amount of time, to determine an average amount of unprotected data during said period, determining a mean-data-loss-rate.
Claim 6
Dependent Claim
30 words
The method as recited in claim 1 wherein said adjusting step includes generating said parity information associated with said new data and writing said parity information to said updated stripe.
Claim 7
Dependent Claim
46 words
The method as recited in claim 5 further including the steps of (a) monitoring the rate of I/O requests to the array and (b) generating a parity block associated with said new data upon detection that said rate of I/O requests is within a predetermined range.
Claim 8
Dependent Claim
55 words
The method as recited in claim 6 wherein said identifying step and said writing new data step occur a plurality of times, thereby updating a plurality of stripes with new data before said generating said parity block step occurs, with said generating step concurrently producing parity information for said plurality of stripes containing new data.
Claim 9
Dependent Claim
63 words
The method as recited in claim 5 further including the step of writing, to memory, information indicating that parity information, corresponding to said new data, is not present on said disk array with said information defining a need-parity-rebuild bit (NPRB), said monitoring step sensing said NPRB and said adjusting step producing said parity information in response to the presence of said NPRB bit.
Claim 10
Independent Claim
210 words
A method for storing data in a fault-tolerant storage device having a plurality of disk drive units forming a disk array with a plurality of stripes for storing data and parity information, comprising the steps of: monitoring the I/O patterns to and from the disk drive units of the array to determine the idleness of the disk array; identifying multiple target areas on each disk of said array to write new data, with at least one of said multiple target areas including old data, with said multiple target areas being associated with one of said plurality of stripes, defining a target stripe; in the absence of a reading step, writing new data to a plurality of said multiple target areas, wherein new data not having corresponding parity information stored on said array defines unprotected data; monitoring a quantity of unprotected data present on said array to detect when said quantity exceeds a preselected threshold; and in response to said monitoring of said quantity of unprotected data, dynamically adjusting the quantity of unprotected data by generating and writing to said target stripe parity information corresponding to said unprotected data to at least one of said multiple target areas such that said quantity is maintained at a level below said preselected threshold.
Claim 11
Independent Claim
210 words
A method for storing data in a fault-tolerant storage device having a plurality of disk drive units forming a disk array with a plurality of stripes for storing data and parity information, comprising the steps of: monitoring the I/O patterns to and from the disk drive units of the array to determine the idleness of the disk array; identifying multiple target areas on each disk of said array to write new data, with at least one of said multiple target areas including old data, with said multiple target areas being associated with one of said plurality of stripes, defining a target stripe; in the absence of a reading step, writing new data to a plurality of said multiple target areas, wherein new data not having corresponding parity information stored on said array defines unprotected data; monitoring a quantity of unprotected data present on said array to detect when said quantity exceeds a preselected threshold; and in response to said monitoring of said quantity of unprotected data, dynamically adjusting the quantity of unprotected data by generating and writing to said target stripe parity information corresponding to said unprotected data to at least one of said multiple target areas such that said quantity is maintained at a level below said preselected threshold.
Claim 12
Dependent Claim
55 words
The method as recited in claim 9 further including the step of writing to memory, information indicating that parity information, corresponding to said new data, is not present on said array with said information defining a needs parity rebuild bit (NPRB), said generating step producing parity information in response to the presence of said NPRB.
Claim 13
Dependent Claim
27 words
The method as recited in claim 9 wherein said generating and writing step generates and writes parity information to ensure said quantity is within a predetermined range.
Claim 14
Dependent Claim
36 words
The method as recited in claim 9 wherein said monitoring step includes continuously determining a mean-time-to-data-loss and said generating and writing step generates and writes parity information to ensure said mean-time-to-data-loss is within a predetermined range.
Claim 15
Dependent Claim
55 words
The method as recited in claim 9 wherein said monitoring step includes monitoring said quantity over a predetermined amount of time, to determine an average amount of unprotected data during said period, determining a mean-data-loss-rate, and said generating and writing step includes generating and writing parity information to ensure mean-data-loss-rate is within a predetermined range.
Claim 16
Dependent Claim
57 words
The method as recited in claim 9 wherein said identifying and writing steps occur a plurality of times, writing a plurality of data stripes to said array before said generating step occurs, with said generating and writing step concurrently producing parity information for said plurality of data stripes and concurrently writing said parity information to said array.
Claim 17
Independent Claim
256 words
An apparatus for generating parity information for a plurality of disk drives, comprising: a plurality of individual disk drives defining an array of disks having a plurality of stripes, each of said plurality of stripes having multiple target areas in which data may be written, with at least one of said multiple target areas including old data, defining an old data target area; a controller means, in data communication with said array, for coordinating the operation of said array; means, in data communication with both said controller means and said array, for writing new data onto a first plurality of said multiple target areas, including said old data target area, defining new data target areas; means, in data communication with said controller means, for generating parity information from said new data present in said new data target areas, whereby new data not having corresponding parity information written on said array defines unprotected data; means, in data communication with both said controller means and said array, for monitoring a quantity of unprotected data present on said array to detect presence of a preselected condition relating to susceptibility of said new data target areas to loss of said new data; means, in data communication with both controller means and said array and responsive to said monitoring means, for dynamically adjusting said quantity of unprotected data on said array by generating and writing parity information corresponding to a first portion of said new data to said array, while leaving a second portion of said new data as unprotected data.
Claim 18
Independent Claim
256 words
An apparatus for generating parity information for a plurality of disk drives, comprising: a plurality of individual disk drives defining an array of disks having a plurality of stripes, each of said plurality of stripes having multiple target areas in which data may be written, with at least one of said multiple target areas including old data, defining an old data target area; a controller means, in data communication with said array, for coordinating the operation of said array; means, in data communication with both said controller means and said array, for writing new data onto a first plurality of said multiple target areas, including said old data target area, defining new data target areas; means, in data communication with said controller means, for generating parity information from said new data present in said new data target areas, whereby new data not having corresponding parity information written on said array defines unprotected data; means, in data communication with both said controller means and said array, for monitoring a quantity of unprotected data present on said array to detect presence of a preselected condition relating to susceptibility of said new data target areas to loss of said new data; means, in data communication with both controller means and said array and responsive to said monitoring means, for dynamically adjusting said quantity of unprotected data on said array by generating and writing parity information corresponding to a first portion of said new data to said array, while leaving a second portion of said new data as unprotected data.
Claim 19
Dependent Claim
26 words
The apparatus as recited in claim 15 wherein said adjusting means adjusts said quantity of unprotected data to ensure said quantity is within a predetermined range.
Claim 20
Dependent Claim
34 words
The apparatus as recited in claim 15 wherein said monitoring means continuously determines a mean-time-to-data-loss and said adjusting means adjusts said quantity of unprotected data to ensure said mean-time-to-data-loss is within a predetermined range.
Claim 21
Dependent Claim
50 words
The apparatus as recited in claim 15 wherein said monitoring means monitors said quantity over a predetermined amount of time, to determine an average amount of unprotected data during said period, and determines a mean-data-loss-rate, and said adjusting means adjusts said quantity to ensure mean-data-loss-rate is within said predetermined range.
References Cited (Backward Citations)
US5274799A
Cited
US5333305A
Cited
US5408644A
Cited
US5315602A
Cited
US5517632A
Cited
US5388108A
Cited
US5418925A
Cited
US5463765A
Cited
US5515500A
Cited
US5522032A
Cited
US5559764A
Cited
US5572661A
Cited
US5497457A
Cited
US5537534A
Cited
US5657468A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-16 | 2001-08-18 | 2002-02-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-16 | 2005-08-18 | 2006-02-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-16 | 2009-08-18 | 2010-02-17 | $7700.00 | Window Closed / Lapsed |