US5860090A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Append-only storage in a disk array using striping and parity caching
Assignee: Informix Software Inc
•
Filing: 1995-10-20
•
Granted: 1999-01-12
•
Expires: 2015-10-20
Abstract
Abstract A computer writes information to a series of blocks that form a stripe on a disk array. The computer first checks if the stripe contains data written in a current pass. If the stripe has stored data, but is not completely full, the computer calculates a parity for the stripe (assuming the information is appended to the data). If appending the information to the data would not complete the stripe, the computer caches the parity outside the disk array. The computer appends the information to the data and updates a parity block on the stripe each time information is appended to the stripe. In various implementations, the computer places a stamp on the pages forming the blocks in the stripe to which information is written. Alternatively, the computer zeroes the bits in the remaining blocks to form a complete stripe.
Inventors
- 👤 Thomas K. Clark
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 11:15
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/1009
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
106 words
A method for writing information to a stripe on an array of independent disks, the stripe comprising a series of blocks spanning the disks, the method comprising: determining whether data has been written to the stripe in a current pass; if data has been written to the stripe, determining a parity value for the stripe assuming the information is appended to the data; caching the parity value outside the disk array, only if appending the information to the data would not complete the stripe; appending the information to the date; and updating a parity block on the stripe each time information is appended to the stripe.
Claim 2
Independent Claim
106 words
A method for writing information to a stripe on an array of independent disks, the stripe comprising a series of blocks spanning the disks, the method comprising: determining whether data has been written to the stripe in a current pass; if data has been written to the stripe, determining a parity value for the stripe assuming the information is appended to the data; caching the parity value outside the disk array, only if appending the information to the data would not complete the stripe; appending the information to the date; and updating a parity block on the stripe each time information is appended to the stripe.
Claim 3
Dependent Claim
63 words
The method of claim 1 further comprising: if no data has been written to the stripe on a current pass, and the information does not comprise a full stripe, zeroing the remaining blocks of the information to form a full stripe; determining a parity value for the information; and writing the information with the zeroed blocks and the parity value to the stripe.
Claim 4
Dependent Claim
59 words
The method of claim 1 wherein the step of updating the parity block comprises: retrieving the parity value stored in the cache during a previous operation to the stripe; determining a new parity value based on the cached parity value and the information; and replacing the value of the parity block on the stripe with the new parity value.
Claim 5
Dependent Claim
29 words
The method of claim 3 wherein calculating the new parity value comprises taking the exclusive OR of the blocks of information with the parity value retrieved from the cache.
Claim 6
Dependent Claim
41 words
The method of claim 1, further comprising: zeroing the remainder of a last page of the information, if a last page of the information is not complete, where a page comprises a smallest input/output unit actually employed by the disk array.
Claim 7
Dependent Claim
47 words
The method of claim 1, further comprising: recording the amount of information stored in a last page of information in a page header, if a last page of the information is not complete, where a page comprises a smallest input/output unit actually employed by the disk array.
Claim 8
Dependent Claim
28 words
The method of claim 6, wherein updating the parity block comprises calculating a parity value of the information, excluding the information in an unused portion of the page.
Claim 9
Dependent Claim
41 words
The method of claim 1, further comprising: placing a stamp in each page of the information, with each successive page having a stamp greater than the previous page, a page comprising a smallest input/output unit actually employed by the disk array.
Claim 10
Dependent Claim
77 words
The method of claim 8, further comprising: recovering a lost block on one disk after the disk experiences a failure, wherein recovering includes: reading a stripe of information from the disks; examining the stamps in each page to find unused pages; determining a parity value of the stripe based only on used pages; comparing the parity value of the stripe to a parity value stored in the stripe; and regenerating the lost block based on the comparison.
Claim 11
Dependent Claim
41 words
The method of claim 9 wherein the step of examining the stamps comprises finding a page whose stamp does not exceed the stamp of a previous page by one, and determining that all the pages succeeding the previous page are unused.
Claim 12
Independent Claim
176 words
A method for writing information to a stripe on an array of independent disks, the stripe comprising a series of blocks spanning the disks, the method comprising: determining whether data has been written to the stripe in a current pass; if the stripe has not been written to in the current pass, calculating a parity value for the stripe; caching the parity value, only if the information does not span a full stripe; adding zeroes to the information to form a full stripe; writing the information, including the zeroes, and the parity value to the stripe, one block of the information being stored on each disk; if the stripe has been written to in the current pass, retrieving the parity value cached in a previous write operation; calculating a new parity value based on the information and the cached parity value; caching the new parity value only if appending the information would not complete the stripe; updating a parity block on the stripe based on the new parity value; and appending the information to the stripe.
Claim 13
Independent Claim
176 words
A method for writing information to a stripe on an array of independent disks, the stripe comprising a series of blocks spanning the disks, the method comprising: determining whether data has been written to the stripe in a current pass; if the stripe has not been written to in the current pass, calculating a parity value for the stripe; caching the parity value, only if the information does not span a full stripe; adding zeroes to the information to form a full stripe; writing the information, including the zeroes, and the parity value to the stripe, one block of the information being stored on each disk; if the stripe has been written to in the current pass, retrieving the parity value cached in a previous write operation; calculating a new parity value based on the information and the cached parity value; caching the new parity value only if appending the information would not complete the stripe; updating a parity block on the stripe based on the new parity value; and appending the information to the stripe.
Claim 14
Independent Claim
190 words
A method for writing information to a stripe on an array of independent disks, the stripe comprising a series of blocks spanning the disks, the method comprising: dividing the information into pages, each page being a smallest input/output unit for a disk in the array, and placing a monotonically increasing stamp in each page; determining whether the stripe has been written to in a current pass; if the stripe has not been written to in the current pass, calculating a parity value for the information; caching the parity value if the information does not span the stripe; writing the information and the parity value to the stripe, one block of the information being stored on each disk; if the stripe has been written to in the current pass, retrieving the parity value cached in a previous write operation; calculating a new parity value based on the information and the cached parity value; caching the new parity value only if appending the information to the stripe would not complete the stripe; updating a parity block on the stripe based on the new parity value; and appending the information to the stripe.
Claim 15
Independent Claim
190 words
A method for writing information to a stripe on an array of independent disks, the stripe comprising a series of blocks spanning the disks, the method comprising: dividing the information into pages, each page being a smallest input/output unit for a disk in the array, and placing a monotonically increasing stamp in each page; determining whether the stripe has been written to in a current pass; if the stripe has not been written to in the current pass, calculating a parity value for the information; caching the parity value if the information does not span the stripe; writing the information and the parity value to the stripe, one block of the information being stored on each disk; if the stripe has been written to in the current pass, retrieving the parity value cached in a previous write operation; calculating a new parity value based on the information and the cached parity value; caching the new parity value only if appending the information to the stripe would not complete the stripe; updating a parity block on the stripe based on the new parity value; and appending the information to the stripe.
References Cited (Backward Citations)
US5522065A
Cited
US5333305A
Cited
US5341381A
Cited
US5408644A
Cited
US5517632A
Cited
US5388108A
Cited
US5572660A
Cited
US5537354A
Cited
US5530948A
Cited
US5522032A
Cited
US5594862A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-11 | 2002-07-13 | 2003-01-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-11 | 2006-07-13 | 2007-01-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-11 | 2010-07-13 | 2011-01-12 | $7700.00 | Window Closed / Lapsed |