US5315602A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimized stripe detection for redundant arrays of disk drives
Assignee: Hewlett Packard Development Co LP
•
Filing: 1992-08-12
•
Granted: 1994-05-24
•
Expires: 2012-08-12
Abstract
Abstract A system for reducing the number of I/O requests required to write data to an redundant array of inexpensive disks (RAID) of a computer system including a host central processor unit and a memory buffer cache. The system includes determinations for writing new data stored in the cache to the disk drives, as stripes, using the least number of I/O requests possible. The system uses the best of two alternative techniques in which the parity for the stripe can be generated. A first procedure determines the number of I/O requests that would be required to generate the parity data from the entire stripe including the new data to be written to the disk drives. A second procedure determines the number of I/O requests that would be required to generate the parity data from the new data to be written to the disk drives and the old parity data of the stripe. The system then aggregates in memory the blocks necessary to generate the parity data as either an entire stripe or as individual blocks using the technique which requires the least number of I/O requests as determined by the first and second procedures.
Inventors
- 👤 Eric S. Noya
- 👤 Randy M. Arnott
- 👤 Mitchell N. Rosich
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 13:37
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/1008; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0804; G06F12/0866; G06F3/00; G06F3/06; G06F3/0601; G06F2212/00; G06F2212/31; G06F2212/311; G06F3/0668; G06F3/0671; G06F3/0673
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
248 words
An apparatus for generating parity data for a plurality of disk drives, each of the plurality of disk drives divided into a plurality of blocks, the plurality of blocks further organized into a plurality of stripes, each of the plurality of stripes including one block from each of the plurality of disk drives, one of the blocks of each stripe storing parity data generated from the data stored in the other blocks of the stripe, the apparatus comprising; memory means for storing data, said memory means partitioned into blocks compatible with the block structure of the plurality of disk drives; means for identifying an updated memory block storing data to be written to one of the plurality of disk drives; means for identifying a predetermined stripe, said predetermined stripe including a disk block to be overwritten by said updated memory block; first means for determining the number of I/O requests required to aggregate in said memory means all of the data, except the parity data, of said predetermined stripe; second means for determining the number of I/O requests required to aggregate in said memory means said block to be overwritten and the parity block of said predetermined stripe; and means for choosing said first means OR said second means to perform said I/O requests by choosing the means which requires the fewest number of I/O requests to aggregate in said memory means the blocks of said identified stripe necessary to generate the parity data of said predetermined stripe.
Claim 2
Independent Claim
248 words
An apparatus for generating parity data for a plurality of disk drives, each of the plurality of disk drives divided into a plurality of blocks, the plurality of blocks further organized into a plurality of stripes, each of the plurality of stripes including one block from each of the plurality of disk drives, one of the blocks of each stripe storing parity data generated from the data stored in the other blocks of the stripe, the apparatus comprising; memory means for storing data, said memory means partitioned into blocks compatible with the block structure of the plurality of disk drives; means for identifying an updated memory block storing data to be written to one of the plurality of disk drives; means for identifying a predetermined stripe, said predetermined stripe including a disk block to be overwritten by said updated memory block; first means for determining the number of I/O requests required to aggregate in said memory means all of the data, except the parity data, of said predetermined stripe; second means for determining the number of I/O requests required to aggregate in said memory means said block to be overwritten and the parity block of said predetermined stripe; and means for choosing said first means OR said second means to perform said I/O requests by choosing the means which requires the fewest number of I/O requests to aggregate in said memory means the blocks of said identified stripe necessary to generate the parity data of said predetermined stripe.
Claim 3
Dependent Claim
41 words
The apparatus as in claim 1 wherein said memory means includes a non-volatile memory for storing data to be written to the plurality of the disk drives, and a volatile memory for storing data read from the plurality of disk drives.
Claim 4
Dependent Claim
36 words
The apparatus as in claim 1 wherein said first and second means include means for determining if the data of the disk blocks of said predetermined stripe are stored in said memory means as memory blocks.
Claim 5
Dependent Claim
60 words
The apparatus as in claim 1 including means for generating the parity data of said predetermined stripe from all of the data, except the parity data, of said predetermined stripe, and means for generating the parity data of said predetermined stripe from said updated memory block, said disk block to be overwritten, and said parity block of said predetermined stripe.
Claim 6
Dependent Claim
23 words
The apparatus as in claim 4 wherein said means for generating the parity data includes a means for performing an exclusive OR function.
Claim 7
Independent Claim
238 words
A method for generating parity data for a plurality of disk drives, each of the plurality of disk drives divided into a plurality of blocks, the plurality of blocks further organized into a plurality of stripes, each of the plurality of stripes including one block from each of the plurality of disk drives, one of the blocks of each stripe storing parity data generated from the data stored in the other blocks of the stripe, the method comprising the steps of; storing data in a memory means, said memory means partitioned into blocks compatible with the block structure of the plurality of disk drives; identifying an updated memory block storing data to be written to one of the plurality of disk drives; identifying a predetermined stripe, said predetermined stripe including a disk block to be overwritten by said updated memory block; determining by a first means, the number of I/O requests required to aggregate in said memory means all of the data, except the parity data, of said predetermined stripe; determining by a second means, the number of I/O requests required to aggregate in said memory means said block to be overwritten and the parity block of said predetermined stripe; and aggregating in said memory means the blocks of said identified stripe necessary to generate the parity data of said predetermined stripe with the fewest number of I/O requests as determined by said second OR said first means.
Claim 8
Independent Claim
238 words
A method for generating parity data for a plurality of disk drives, each of the plurality of disk drives divided into a plurality of blocks, the plurality of blocks further organized into a plurality of stripes, each of the plurality of stripes including one block from each of the plurality of disk drives, one of the blocks of each stripe storing parity data generated from the data stored in the other blocks of the stripe, the method comprising the steps of; storing data in a memory means, said memory means partitioned into blocks compatible with the block structure of the plurality of disk drives; identifying an updated memory block storing data to be written to one of the plurality of disk drives; identifying a predetermined stripe, said predetermined stripe including a disk block to be overwritten by said updated memory block; determining by a first means, the number of I/O requests required to aggregate in said memory means all of the data, except the parity data, of said predetermined stripe; determining by a second means, the number of I/O requests required to aggregate in said memory means said block to be overwritten and the parity block of said predetermined stripe; and aggregating in said memory means the blocks of said identified stripe necessary to generate the parity data of said predetermined stripe with the fewest number of I/O requests as determined by said second OR said first means.
Claim 9
Dependent Claim
44 words
The method as in claim 6 wherein said memory means includes the step of storing data to be written to the plurality of the disk drives in a non-volatile memory, and storing data read from the plurality of disk drives in a volatile memory.
Claim 10
Dependent Claim
32 words
The method as in claim 6 further including the step of determining if the data of the disk blocks of said predetermined stripe are stored in said memory means as memory blocks.
Claim 11
Dependent Claim
73 words
The method as in claim 6 including the step of generating the parity data of said predetermined stripe from all of the data, except the parity data, of said predetermined stripe, OR generating the parity data of said predetermined stripe from said updated memory block, said disk block to be overwritten, and said parity block of said predetermined stripe, generating the parity data according to the step which requires the fewest I/O requests.
Claim 12
Dependent Claim
22 words
The method as in claim 6 further includes the step of generating the parity data by means of an exclusive OR function.
References Cited (Backward Citations)
US4437155A
Cited
US4489378A
Cited
US4636946A
Cited
US5109500A
Cited
US4972364A
Cited
US4972316A
Cited
US4882642A
Cited
US5109485A
Cited
US5263145A
Cited
US5274799A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-05-23 | 1997-11-22 | 1998-05-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-23 | 2001-11-22 | 2002-05-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-23 | 2005-11-22 | 2006-05-24 | $7700.00 | Window Closed / Lapsed |