US5537534A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Disk array having redundant storage and methods for incrementally generating redundancy as data is written to the disk array
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-02-10
•
Granted: 1996-07-16
•
Expires: 2015-02-10
Abstract
Abstract A data storage system has a disk array having multiple storage disks and a disk array controller coupled to the disk array to coordinate data transfer to and from the storage disks. The disk array is configured into multiple stripes where each stripe extends across multiple ones of the storage disks. Additionally, each stripe consists of multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array. A memory manager is provided to manage memory allocation for storing user data redundantly according to parity redundancy techniques. The memory manager maintains a partial stripe pointer to reference individual stripes in the disk array and a segment fill pointer to references individual segments in the referenced stripe. These pointers are used to select a non-filled stripe and individual segments in that stripe. The memory manager writes user data to a selected segment and incrementally determines a parity value for the stripe after each segment is written. The parity value is based upon the user data contained in those segments of the stripe that have been written. The empty segments in the stripe are not managed during the write process and thus are not included in the incremental parity generation.
Inventors
- 👤 Douglas L. Voigt
- 👤 Marvin D. Nelson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 13:59
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; A; A61; A61P; A61P9/00; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/1009; G06F2211/1059
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
197 words
A method for writing user data to a disk array according to redundant parity storage techniques, the disk array having multiple storage disks and being configured into multiple stripes where each stripe extends across multiple ones of the storage disks, each stripe comprising multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array, the method comprising the following steps: (a) differentiating between segments which hold user data or parity information and segments which are empty; (b) identifying a non-filled stripe in the disk array, the non-filled stripe having multiple empty segments; (c) locating one of the empty segments in the identified non-filled stripe; (d) writing user data to the one empty segment in the stripe without writing user data to other empty segments in the non-filled stripe; (e) determining, after the user data is written to the one empty segment per step (d), a parity value for the user data contained in those segments in the non-filled stripe that have been written to; and (f) repeating steps (c)-(e) to fill one or more of the other empty segments in the non-filled stripe.
Claim 2
Independent Claim
197 words
A method for writing user data to a disk array according to redundant parity storage techniques, the disk array having multiple storage disks and being configured into multiple stripes where each stripe extends across multiple ones of the storage disks, each stripe comprising multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array, the method comprising the following steps: (a) differentiating between segments which hold user data or parity information and segments which are empty; (b) identifying a non-filled stripe in the disk array, the non-filled stripe having multiple empty segments; (c) locating one of the empty segments in the identified non-filled stripe; (d) writing user data to the one empty segment in the stripe without writing user data to other empty segments in the non-filled stripe; (e) determining, after the user data is written to the one empty segment per step (d), a parity value for the user data contained in those segments in the non-filled stripe that have been written to; and (f) repeating steps (c)-(e) to fill one or more of the other empty segments in the non-filled stripe.
Claim 3
Dependent Claim
21 words
A method according to claim 1 wherein the identifying step comprises using a partial stripe pointer to reference the non-filled stripe.
Claim 4
Dependent Claim
27 words
A method according to claim 1 wherein the locating step comprises using a segment fill pointer to reference a segment to be written to in the stripe.
Claim 5
Dependent Claim
69 words
A method according to claim 1 wherein: the identifying step comprises using a partial stripe pointer to reference the non-filled stripe; the locating step comprises using a segment fill pointer to reference a segment to be written to in the stripe; the method further comprising: providing a non-volatile memory separate from the disk array; and storing the partial stripe pointer and the segment fill pointer in the non-volatile memory.
Claim 6
Dependent Claim
25 words
A method according to claim 1 wherein the locating step comprises sequentially referencing the empty segments contiguously according to their order within the non-filled stripe.
Claim 7
Dependent Claim
39 words
A method according to claim 1 wherein the step of determining parity comprises computing a parity value based on a logical function of the user data contained in the segments in the non-filled stripe that have been written to.
Claim 8
Dependent Claim
37 words
A method according to claim 1 further comprising the following additional steps: providing a non-volatile memory separate from the disk array; and temporarily caching the parity value after each said determining step (e) in the non-volatile memory.
Claim 9
Dependent Claim
59 words
A method according to claim 1 further comprising the following additional steps: temporarily caching the parity value after each said determining step (e); and the step of determining parity comprises computing a new parity value based on a logical function of the previously cached parity value and user data most recently written into an empty segment in the stripe.
Claim 10
Dependent Claim
25 words
A method according to claim 1 further comprising the step of writing the parity value to the disk array after each said determining step (e).
Claim 11
Dependent Claim
73 words
A method according to claim 1 further comprising the following additional steps: writing the parity value to the disk array after each said determining step (e); and the step of determining parity comprises reading the previously written parity value from the disk array and computing a new parity value based on a logical function of the previously written parity value and user data most recently written into an empty segment in the stripe.
Claim 12
Dependent Claim
62 words
A method according to claim 1 wherein the identifying step comprises identifying an entirely empty stripe, the method further comprising: in the event that an empty stripe cannot be identified, identifying a partially filled stripe having both empty and filled segments and emptying the partially filled stripe by moving user data from the filled segments to other locations on the disk array.
Claim 13
Independent Claim
237 words
A method for writing user data to a disk array according to redundant parity storage techniques, the disk array having multiple storage disks and being configured into multiple stripes where each stripe extends across multiple ones of the storage disks, each stripe comprising multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array, the method comprising the following steps: (a) providing a non-volatile memory separate from the disk array; (b) providing a partial stripe pointer in the non-volatile memory that references individual stripes in the disk array; (c) providing a segment fill pointer in the non-volatile memory that references individual segments in the referenced stripe; (d) selecting an empty stripe by setting the partial stripe pointer to that empty stripe; (e) selecting a first segment in the selected stripe by setting the segment fill pointer to that first segment; (f) writing user data to the first segment while leaving empty other segments in the stripe; (g) computing a parity value for only the first segment in the stripe; (h) caching the parity value in the non-volatile memory; (i) selecting a next segment in the stripe using the segment fill pointer; (j) writing user data to the next segment in the stripe; and (k) computing another parity value based on the cached parity value and the user data written to the next segment.
Claim 14
Independent Claim
237 words
A method for writing user data to a disk array according to redundant parity storage techniques, the disk array having multiple storage disks and being configured into multiple stripes where each stripe extends across multiple ones of the storage disks, each stripe comprising multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array, the method comprising the following steps: (a) providing a non-volatile memory separate from the disk array; (b) providing a partial stripe pointer in the non-volatile memory that references individual stripes in the disk array; (c) providing a segment fill pointer in the non-volatile memory that references individual segments in the referenced stripe; (d) selecting an empty stripe by setting the partial stripe pointer to that empty stripe; (e) selecting a first segment in the selected stripe by setting the segment fill pointer to that first segment; (f) writing user data to the first segment while leaving empty other segments in the stripe; (g) computing a parity value for only the first segment in the stripe; (h) caching the parity value in the non-volatile memory; (i) selecting a next segment in the stripe using the segment fill pointer; (j) writing user data to the next segment in the stripe; and (k) computing another parity value based on the cached parity value and the user data written to the next segment.
Claim 15
Dependent Claim
29 words
A method according to claim 12 further comprising the step of repeating steps (i)-(k) until all segments in the stripe that are used to store user data are filled.
Claim 16
Dependent Claim
31 words
A method according to claim 13 further comprising the step of writing a last computed parity value from the non-volatile memory to a segment in the stripe on the disk array.
Claim 17
Dependent Claim
214 words
A data storage system comprising: a disk array having multiple storage disks, the disk array being configured into multiple stripes where each stripe extends across multiple ones of the storage disks, each stripe comprising multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array; a disk array controller coupled to the disk array to coordinate data transfer to and from the storage disks; a memory manager operatively coupled to the disk array controller to manage memory allocation for storing user data redundantly according to parity redundancy techniques, the memory manager placing user data in data segments and parity information in parity segments whereby at least one parity segment and one or more data segments are included in each stripe, the memory manager having means for determining which data segments are incorporated into the parity information of the stripe; the memory manager selecting a non-filled stripe and an empty segment in that stripe; and the memory manager writing user data to the selected segment and incrementally determining a parity value for the stripe after each segment is written to, the parity value being based upon the user data contained in those segments of the stripe that have been written to.
Claim 18
Dependent Claim
214 words
A data storage system comprising: a disk array having multiple storage disks, the disk array being configured into multiple stripes where each stripe extends across multiple ones of the storage disks, each stripe comprising multiple segments of storage space where each segment is a portion of the stripe that resides on a single storage disk in the disk array; a disk array controller coupled to the disk array to coordinate data transfer to and from the storage disks; a memory manager operatively coupled to the disk array controller to manage memory allocation for storing user data redundantly according to parity redundancy techniques, the memory manager placing user data in data segments and parity information in parity segments whereby at least one parity segment and one or more data segments are included in each stripe, the memory manager having means for determining which data segments are incorporated into the parity information of the stripe; the memory manager selecting a non-filled stripe and an empty segment in that stripe; and the memory manager writing user data to the selected segment and incrementally determining a parity value for the stripe after each segment is written to, the parity value being based upon the user data contained in those segments of the stripe that have been written to.
Claim 19
Dependent Claim
59 words
A data storage system according to claim 15 wherein the determining means of the memory manager comprises: a partial stripe pointer to reference individual stripes in the disk array; a segment fill pointer to reference individual segments in the referenced stripe; and the memory manager using the pointers to select a non-filled stripe and a segment in that stripe.
Claim 20
Dependent Claim
32 words
A data storage system according to claim 16 further comprising a non-volatile memory to store the partial stripe pointer and the segment fill pointer, the non-volatile memory also caching the parity value.
Claim 21
Dependent Claim
97 words
A data storage system according to claim 15 wherein: the disk array is configured to group the multiple stripes into a plurality of RAID areas where each RAID area contains more than one stripe; the determining means of the memory manager comprises multiple pairs of partial stripe pointers and segment fill pointers in which one pair corresponds to each RAID area, each pair having a partial stripe pointer to reference an individual stripe in the corresponding RAID area and a segment fill pointer to reference an individual segment within the stripe referenced by the partial stripe pointer.
Claim 22
Dependent Claim
59 words
A data storage system according to claim 15 further comprising: a non-volatile memory resident to cache the parity value each time the parity value is determined; and the memory manager computing a new parity value based on a logical function of the previously cached parity value and user data most recently written into an empty segment in the stripe.
Claim 23
Dependent Claim
43 words
A data storage system according to claim 15 wherein the memory manager writes the parity value to a segment in the stripe of the disk array after all segments in the stripe that have been used to store user data have been filled.
Claim 24
Dependent Claim
77 words
A data storage system according to claim 15 wherein: the memory manager writes the parity value to a segment in the stripe of the disk array each time the parity value is determined; and the memory manager reads the previously written parity value from the disk array and computes a new parity value based on a logical function of the previously written parity value and user data most recently written into an empty segment in the stripe.
References Cited (Backward Citations)
US4092732A
Cited
US4914656A
Cited
US4989205A
Cited
US5072378A
Cited
US5195100A
Cited
US5124987A
Cited
US5155845A
Cited
US5375128A
Cited
US5155835A
Cited
US5278838A
Cited
US5237658A
Cited
US5297258A
Cited
US5287462A
Cited
US5333305A
Cited
US5289418A
Cited
US5410667A
Cited
US5408644A
Cited
US5392244A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |